數(shù)據(jù)結(jié)構(gòu)試卷B卷(含答案)

千里之行，始于足下讓知識(shí)帶有溫度。第第2頁/共2頁精品文檔推薦數(shù)據(jù)結(jié)構(gòu)試卷B卷(含答案)《數(shù)據(jù)結(jié)構(gòu)》試卷B

一、填空題（每空1分，共15分）

1.向量、棧和隊(duì)列都是結(jié)構(gòu)，可以在向量的

位置插入和刪除元素；對于棧只能在插入和刪除元素；對于隊(duì)列只能在插入和刪除元素。

2.棧是一種特別的線性表，允許插入和刪除運(yùn)算的一端稱

為。不允許插入和刪除運(yùn)算的一端稱為。

3.數(shù)據(jù)結(jié)構(gòu)是一門討論非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算

機(jī)的以及它們之間的和運(yùn)算等的學(xué)科。

4.在挨次表中插入或刪除一個(gè)元素，需要平均移動(dòng)

元素，詳細(xì)移動(dòng)的元素個(gè)數(shù)與

有關(guān)。

5.在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有

個(gè)元素。

6.假設(shè)在有序線性表a[20]上舉行折半查找，則比較一次查找勝利的結(jié)點(diǎn)數(shù)為1；比較兩次查找勝利的結(jié)點(diǎn)數(shù)為；比較四次查找勝利的結(jié)點(diǎn)數(shù)為；平均查找長度為。

二、推斷正誤（推斷下列概念的正確性，并作出簡要的說明。）（每小題1分，共10分）

（）1.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)容易類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。

（）2.在表結(jié)構(gòu)中最常用的是線性表，棧和隊(duì)列不太常用。

（）3.棧是一種對全部插入、刪除操作限于在表的一端舉行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。

（）4.對于不同的使用者，一個(gè)表結(jié)構(gòu)既可以是棧，也可以是隊(duì)列，也可以是線性表。

（）5.線性表的規(guī)律挨次與存儲(chǔ)挨次總是全都的

（）6.棧和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)。

（）7.棧和隊(duì)列的存儲(chǔ)方式既可是挨次方式，也可是鏈接方式。

（）8.兩個(gè)棧分享一片延續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存

利用率，削減溢出機(jī)會(huì)，應(yīng)把兩個(gè)棧的棧底分

別設(shè)在這片內(nèi)存空間的兩端。

（）9.隊(duì)是一種插入與刪除操作分離在表的兩端舉行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。

（）10.一個(gè)棧的輸入序列是12345，則棧的輸出序列不行能是12345。

三、單項(xiàng)挑選題（每小題1分，共20分）

（）1．?dāng)?shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏

輯地址相同并且是延續(xù)的，稱之為：（A）存儲(chǔ)結(jié)構(gòu)（B）規(guī)律結(jié)構(gòu)（C）挨次存儲(chǔ)結(jié)構(gòu)（D）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

（）2.若已知一個(gè)棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為

Ａ．iＢ．n=iＣ．n-i+1

Ｄ．不確定

（）3.判定一個(gè)棧ST（最多元素為m0）為空的條件

是

Ａ．ST->top0Ｂ．ST->top=0Ｃ．ST->topm0Ｄ．ST->top=m0

（）4設(shè)矩陣A是一個(gè)對稱矩陣，為了節(jié)約存儲(chǔ)，將其

下三角部分（如下圖所示）按行序存放在一維數(shù)組B[1,

n(n-1)/2]中，對下三角部分中任一元素ai,j(i≤j),在一維數(shù)

組B中下標(biāo)k的值是：Ａ．i(i-1)/2+j-1Ｂ．i(i-1)/2+j

Ｃ．i(i+1)/2+j-1Ｄ．i(i+1)/2+j

（）5．具有n(n>0)個(gè)結(jié)點(diǎn)的徹低二叉樹的深度

為。

(Ａ)?log2(n)?(Ｂ)?log2(n)?(Ｃ)?log2(n)

?+1(Ｄ)?log2(n)+1?

（）6.有8個(gè)結(jié)點(diǎn)的無向連通圖最少有條邊。

A．5B.6C.7

D.8

7.數(shù)據(jù)結(jié)構(gòu)反映了數(shù)據(jù)元素之間的結(jié)構(gòu)關(guān)系。鏈表是一種??????

????????=nnnnaaaaaaA,2,1,2,21,21,1ΛΛ

A，它對于數(shù)據(jù)元素的插入和刪除

B。通常查找線性表數(shù)據(jù)元素的辦法有

C和

D兩種辦法，其中C是一種只適合于挨次存儲(chǔ)結(jié)構(gòu)但

E的辦法；而D是一種對挨次和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)均適用的辦法。

供挑選的答案：

A：①挨次存儲(chǔ)線性表②非挨次存儲(chǔ)非線性表③挨次存儲(chǔ)非線性表④非挨次存儲(chǔ)線性表

B：①不需要移動(dòng)結(jié)點(diǎn)，不需轉(zhuǎn)變結(jié)點(diǎn)指針②不需要移動(dòng)結(jié)點(diǎn)，只需轉(zhuǎn)變結(jié)點(diǎn)指針

③只需移動(dòng)結(jié)點(diǎn)，不需轉(zhuǎn)變結(jié)點(diǎn)指針④既需移動(dòng)結(jié)點(diǎn)，又需轉(zhuǎn)變結(jié)點(diǎn)指針

C：①挨次查找②循環(huán)查找③條件查找④二分法查找

D：①挨次查找②隨機(jī)查找③二分法查找

④分塊查找

E：①效率較低的線性查找②效率較低的非線性查找③效率較高的非線性查找④效率較高的線性查找

答案：A＝B＝C＝D＝E＝

8.散列法存儲(chǔ)的基本思想是按照A來打算B，碰撞（矛盾）指的是C，處理碰撞的兩類主要辦法是D。

供挑選的答案

A，B：①存儲(chǔ)地址②元素的符號(hào)③元素個(gè)數(shù)

④關(guān)鍵碼值

⑤非碼屬性⑥平均檢索長度⑦負(fù)載因子⑧散列表空間

C:①兩個(gè)元素具有相同序號(hào)②兩個(gè)元

素的關(guān)鍵碼值不同，而非碼屬性相同

③不同關(guān)鍵碼值對應(yīng)到相同的存儲(chǔ)地址④負(fù)載因子過大⑤數(shù)據(jù)元素過多

D：①線性探查法和雙散列函數(shù)法②建溢出區(qū)法和不建溢出區(qū)法

③除余法和折疊法④拉鏈法和開地址法

答案：A＝B＝C＝D＝

9.考慮具有如下性質(zhì)的二叉樹：除葉子結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)的值都大于其左子樹上的一切結(jié)點(diǎn)的值。并小于等于其右子樹上的一切結(jié)點(diǎn)的值。

現(xiàn)把9個(gè)數(shù)1，2，3，…，8，9填入下圖所示的二叉樹的9個(gè)結(jié)點(diǎn)中，并使之具有上述性質(zhì)。此時(shí)，n1的值是A，n2的值是B，n9的值是C?，F(xiàn)欲把10放入此樹并使該樹保持前述性質(zhì)，增強(qiáng)的一個(gè)結(jié)點(diǎn)可以放在D或E。

供挑選的答案

A～C：①1②2③3④

4⑤

5⑥6

⑦7⑧8⑨9

D～E：①n7下面②n8下面

③n9下面

④n6下面⑤n1與n2之間

⑥n2與n4之間

⑦n6與n9之間⑧n3與n6之間

答案：A＝B＝C＝

D＝E＝

四、簡答題（每小題5分，共25分）

1.說明線性表、棧與隊(duì)的異同點(diǎn)。

2.試寫出如圖所示的二叉樹分離按先序、中序、后序遍歷時(shí)得到的結(jié)點(diǎn)序列

3.假設(shè)正讀和反讀都相同的字符序列為“回文”，例如，‘a(chǎn)bba’和‘a(chǎn)bcba’是回文，‘a(chǎn)bcde’和‘a(chǎn)babab’則不是回文。假設(shè)一字符序列已存入計(jì)算機(jī)，請分析用線性表、堆棧和隊(duì)列等方式正確輸出其回文的可能性？

4.試比較挨次存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。在什么狀況下用挨次表比鏈表好？

5.給定二叉樹的兩種遍歷序列，分離是：

前序遍歷序列：D，A，C，E，B，H，F(xiàn)，G，I；

中序遍歷序列：D，C，B，E，H，A，G，I，F(xiàn)，

試畫出二叉樹B，并簡述由隨意二叉樹B的前序遍歷序列和中序遍歷序列求二叉樹B的思想辦法。

五、閱讀理解（每小題5分，共20分）

1、已知L是無表頭結(jié)點(diǎn)的單鏈表，且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn)，

也不是尾元結(jié)點(diǎn)，請寫出在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的核心語句序列。

2、閱讀下列算法，若有錯(cuò)，改正之。

1.寫出下列程序段的輸出結(jié)果（隊(duì)列中的元素類型QElemType為char）。

voidmain(){

QueueQ;InitQueue(Q);

Charx=’e’;y=’c’;

EnQueue(Q,’h’);EnQueue(Q,’r’);EnQueue(Q,’y’);

DeQueue(Q,x);EnQueue(Q,x);

DeQueue(Q,x);EnQueue(Q,’a’);

while(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);};Printf(x);

}

2.簡述以下算法的功能（棧和隊(duì)列的元素類型均為int）。voidalgo3(Queueintd;

InitStack(S);

while(!QueueEmpty(Q)){

DeQueue(Q,d);Push(S,d);

};

while(!StackEmpty(S)){

Pop(S,d);EnQueue(Q,d);

}

}

六、算法設(shè)計(jì)（每小題5分，共15分。至少要寫出思路）

1.寫出在挨次存儲(chǔ)結(jié)構(gòu)下將線性表逆轉(zhuǎn)的算法，要求使用最少的附加空間。

2.編寫程序，將若干整數(shù)從鍵盤輸入，以單鏈表形式存儲(chǔ)起來，然后計(jì)算單鏈表中結(jié)點(diǎn)的個(gè)數(shù)（其中指針P指向該鏈表的第一個(gè)結(jié)點(diǎn)）。

3.試寫一個(gè)算法，判別讀入的一個(gè)以‘@’為結(jié)束符的字符序列是否是“回文”。

答案

一、填空題（每空1分，共15分）

1.向量、棧和隊(duì)列都是線性結(jié)構(gòu)，可以在向量的任何位置插入和刪除元素；對于棧只能在棧頂插入和刪除元素；對于隊(duì)列只能在隊(duì)尾插入和隊(duì)首刪除元素。

2.棧是一種特別的線性表，允許插入和刪除運(yùn)算的一端稱為棧頂。不允許插入和刪除運(yùn)算的一端稱為棧底。

3.數(shù)據(jù)結(jié)構(gòu)是一門討論非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的操作對象以及它們之間的關(guān)系和運(yùn)算等的學(xué)科。

4.在挨次表中插入或刪除一個(gè)元素，需要平均移動(dòng)表中一

半元素，詳細(xì)移動(dòng)的元素個(gè)數(shù)與表長和該元素在表中的位置有關(guān)。

5.在具有n個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有n-1個(gè)元

素。

8.假設(shè)在有序線性表a[20]上舉行折半查找，則比較一次查

找勝利的結(jié)點(diǎn)數(shù)為1；比較兩次查找勝利的結(jié)點(diǎn)數(shù)為

2；比較四次查找勝利的結(jié)點(diǎn)數(shù)為8；平均查找長

度為3.7。解：明顯，平均查找長度＝O（log2n）top0Ｂ．ST->top=0

Ｃ．ST->topm0Ｄ．ST->top=m0

(B)4、設(shè)矩陣A是一個(gè)對稱矩陣，為了節(jié)約存儲(chǔ)，將

其下三角部分（如下圖所示）按行序存放在一維數(shù)組B[1,

n(n-1)/2]中，對下三角部分中任一元素ai,j(i≤j),在一維數(shù)

組B中下標(biāo)k的值是：

Ａ．i(i-1)/2+j-1Ｂ．i(i-1)/2+jＣ．i(i+1)/2+j-1Ｄ．i(i+1)/2+j

（C）5．具有n(n>0)個(gè)結(jié)點(diǎn)的徹低二叉樹的深度

為。

(Ａ)?log2(n)?(Ｂ)?log2(n)?(Ｃ)?log2(n)

?+1(Ｄ)?log2(n)+1?

（C）6.有8個(gè)結(jié)點(diǎn)的無向連通圖最少有條邊。

A．5B.6C.7??????

????????=nnnnaaaaaaA,2,1,2,21,21,1ΛΛ

D.8

7、答案：A＝④B＝②C＝④D＝①E＝③

8、答案：A＝④B＝①C＝③D＝④

9、答案：A＝⑦B＝④C＝⑥D(zhuǎn)＝②E＝⑥

四、簡答題（每小題4分，共20分）

1.說明線性表、棧與隊(duì)的異同點(diǎn)。

劉答：相同點(diǎn)：都是線性結(jié)構(gòu)，都是規(guī)律結(jié)構(gòu)的概念。都可以用挨次存儲(chǔ)或鏈表存儲(chǔ)；棧和隊(duì)列是兩種特別的線性表，即受限的線性表，只是對插入、刪除運(yùn)算加以限制。

不同點(diǎn)：①運(yùn)算規(guī)章不同，線性表為隨機(jī)存取，而棧是只允許在一端舉行插入、刪除運(yùn)算，因而是后進(jìn)先出表LIFO；隊(duì)列是只允許在一端舉行插入、另一端舉行刪除運(yùn)算，因而是先進(jìn)先出表FIFO。

②用途不同，堆棧用于子程調(diào)用和庇護(hù)現(xiàn)場，隊(duì)列用于多道作業(yè)處理、指令寄存及其他運(yùn)算等等。

2.試寫出如圖所示的二叉樹分離按先序、中序、后序遍歷時(shí)得到的結(jié)點(diǎn)序列。

答：DLR：ABDFJGKCEHILM

LDR:BFJDGKACHELIM

LRD：JFKGDBHLMIECA

3.假設(shè)正讀和反讀都相同的字符序列為“回文”，例如，‘a(chǎn)bba’和‘a(chǎn)bcba’是回文，‘a(chǎn)bcde’和‘a(chǎn)babab’則不是回文。假設(shè)一字符序列已存入計(jì)算機(jī)，請分析用線性表、堆棧和隊(duì)列等方式正確輸出其回文的可能性？

答：線性表是隨機(jī)存儲(chǔ)，可以實(shí)現(xiàn)，靠循環(huán)變量（j--）從表尾開頭打印輸出；

堆棧是后進(jìn)先出，也可以實(shí)現(xiàn)，靠正序入棧、逆序出棧即可；

隊(duì)列是先進(jìn)先出，不易實(shí)現(xiàn)。

哪種方式最好，要詳細(xì)狀況詳細(xì)分析。若正文在機(jī)內(nèi)已是挨次存儲(chǔ)，則直接用線性表從后往前讀取即可，或?qū)⒍褩ｍ旈_到數(shù)組末尾，然后直接用POP動(dòng)作實(shí)現(xiàn)。（但堆棧是先減后壓還是……）

若正文是單鏈表形式存儲(chǔ)，則等同于隊(duì)列，需開輔助空間，可以從鏈?zhǔn)组_頭入棧，所有壓入后再依次輸出。

4.試比較挨次存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的優(yōu)缺點(diǎn)。在什么狀況下用挨次表比鏈表好？

答：①挨次存儲(chǔ)時(shí)，相鄰數(shù)據(jù)元素的存放地址也相鄰（規(guī)律與物理統(tǒng)一）；要求內(nèi)存中可用存儲(chǔ)單元的地址必需是延續(xù)的。

優(yōu)點(diǎn)：存儲(chǔ)密度大（＝1？），存儲(chǔ)空間利用率高。缺點(diǎn)：插入或刪除元素時(shí)不便利。

②鏈?zhǔn)酱鎯?chǔ)時(shí)，相鄰數(shù)據(jù)元素可任意存放，但所占存儲(chǔ)空間分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針

優(yōu)點(diǎn)：插入或刪除元素時(shí)很便利，使用靈便。缺點(diǎn)：存儲(chǔ)密度?。╪ext=P->next;

P->next=S;

2、答：這是找結(jié)點(diǎn)后繼的程序。

共有3處錯(cuò)誤。

注：當(dāng)rtag

＝1時(shí)說明內(nèi)裝后繼指針，可直接返回，第一句無錯(cuò)。

當(dāng)rtag＝0時(shí)說明內(nèi)裝右孩子指針，但孩子未必是后繼，需要計(jì)算。中序遍歷應(yīng)該先左再根再右，所以應(yīng)該找左子樹直到葉子處。r=r->lchild;直到LTag=1；

應(yīng)改為：while(!r->Ltag)r=r->Lchild;

3.寫出下列程序段的輸出結(jié)果（隊(duì)列中的元素類型QElem

Type為char）。

voidmain(){

QueueQ;InitQueue(Q);

Charx=’e’;y=’c’;

EnQueue(Q,’h’);EnQueue(Q,’r’);EnQueue(Q,y);

DeQueue(Q,x);EnQueue(Q,x);

DeQueue(Q,x);EnQueue(Q,’a’);

while(!QueueEmpty(Q)){DeQueue(Q,y);printf(y);};Printf(x);

}

答：輸出為“char”。

4.簡述以下算法的功能（棧和隊(duì)列的元素類型均為int）。voidalgo3(Queueintd;

InitStack(S);

while(!QueueEmpty(Q)){

DeQueue(Q,d);Push(S,d);

};

while(!StackEmpty(S)){

Pop(S,d);EnQueue(Q,d);

}

}

答：該算法的功能是：利用堆棧做輔助，將隊(duì)列中的數(shù)據(jù)元素舉行逆置。

六、算法設(shè)計(jì)（每小題5分，共15分。至少要寫出