國家開放大學(xué)電大《數(shù)據(jù)結(jié)構(gòu)(本)》期末題庫及答案

最新國家開放大學(xué)電大《數(shù)據(jù)結(jié)構(gòu)(本)》期末題庫及答案考試說明：本人針對該科精心匯總了歷年題庫及答案，形成一個完整的題庫，并且每年都在更新。該題庫對考生的復(fù)習(xí)、作業(yè)和考試起著非常重要的作用，會給您節(jié)省大量的時間。做考題時，利用本文檔中的查找工具，把考題中的關(guān)鍵字輸?shù)讲檎夜ぞ叩牟檎覂?nèi)容框內(nèi)，就可迅速查找到該題答案。本文庫還有其他網(wǎng)核及教學(xué)考一體化答案，敬請查看。《數(shù)據(jù)結(jié)構(gòu)》題庫及答案一一、單項選擇題（每小題3分，共30分）

試題答案及評分標(biāo)準(zhǔn)（供參考）一、單項選擇題（每小題3分，共30分）1．C2．B3．A4．C5．B6．C7．A8．D9．A10．D二、填空題（每小題2分，共24分）11.先出12．樹形13．行下標(biāo)列下標(biāo)數(shù)組元素14.315．存儲位置16.1017.2018．二叉排序樹19.葉20.421.2,4,3;5,6,8,7,922.a2《數(shù)據(jù)結(jié)構(gòu)》題庫及答案二一、單項選擇題（每小題3分，共30分）二、填空題（每小題2分，共24分）三、綜合題【每小題中每問5分，共30分）四、程序填空題（每空2分，共16分）試題答案及評分標(biāo)準(zhǔn)（供參考）一、單項選擇題（每小題3分，共30分）1．A2．D3．C4．B5．B6．C7．B8．C9．A10.C二、填空題（每小題2分，共24分）11．圖狀12.n-j13．二叉排序樹14.1,2,4,8,3,5,915.416.317.518.319.920.1221.3222.7《數(shù)據(jù)結(jié)構(gòu)》題庫及答案三一、單項選擇題，在括號內(nèi)填寫所選擇的標(biāo)號1．輸出一個二維數(shù)組b[m][n]中所有元素的時間復(fù)雜度為()。A．（）(n)B．（）(m十n)C．（）(n2)D．（）(m*n)2．在一個長度為n的順序存儲的有序表中搜索值為x元素時，其時間效率最高的算法的時間復(fù)雜度為()。3．當(dāng)利用大小為n的數(shù)組順序存儲一個棧時，假定用top==n表示?？?，則向這個棧插入一個元素時，首先應(yīng)執(zhí)行()語句修改top指針。A．top++；B.top--；C．top=0；D．top；4．在一棵樹中，()沒有前驅(qū)結(jié)點(diǎn)。A．樹枝結(jié)點(diǎn)B.葉子結(jié)點(diǎn)C.樹根結(jié)點(diǎn)D．空結(jié)點(diǎn)5．已知一棵樹的邊集表示為{<A，B>，<A，C)，<B，D>，<C，E>，<C，F(xiàn)>，<C，G>，<F，H>，<F，I>}，則該樹的深度為()。假定樹根結(jié)點(diǎn)的深度為0。A．2B．3C．4D．56．n個頂點(diǎn)的連通圖中至少含有()條邊。A．n一1B．nC．n(n—1)／2D.n(n一1)7．設(shè)無向圖的頂點(diǎn)個數(shù)為n．則該圖最多有()條邊。A．n一1B．n(n一1)／2C．n(n+1)／2D．n(n一1)8．在采用開散列法解決沖突時，每一個散列地址所鏈接的同義詞子表中各個表項的()的值相同。A.關(guān)鍵碼B．非關(guān)鍵碼C.散列函數(shù)D．某個域9．散列函敷應(yīng)該有這樣的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以()概率取其值域范圍內(nèi)的每個值。A．最大B.最小C.平均D．同等二、填空1．面向?qū)ο蟮奶卣鲬?yīng)包括對象、類、多態(tài)、消息通信等。2．在單鏈表中設(shè)置表頭附加結(jié)點(diǎn)的作用是在插入和刪除表中任一個元素時的操作都3．若設(shè)順序棧的最大容量為MaxSize，top==-l表示?？?，則判斷棧滿的條件是top==4．在一棵高度為5的完全二叉樹中，最多包含有個結(jié)點(diǎn)。假定樹根結(jié)點(diǎn)的高度為0。5.在一個最大堆中，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的。6．具有n個頂點(diǎn)的連通無向圖的—棵生成樹中含有條邊。7．在一棵5階B樹中，每個結(jié)點(diǎn)最多含有個關(guān)鍵碼。三、判斷()1.線性表若采用鏈?zhǔn)酱鎯Ρ硎荆趧h除時不需要移動元素。()2．若讓元素1，2，3依次進(jìn)棧，任何時候都允許元素出棧，則出棧次序1，3，2是不可能出現(xiàn)的情況。()3．一個廣義表((a)，((h)，c)，(((d))))的長度為3，深度為4。()4．二叉樹是一棵無序樹。()5．對于關(guān)鍵碼互不相同的一組記錄，若生成二叉搜索樹時插入記錄的次序不同則將得到不同形態(tài)的二叉搜索樹。()6．存儲無向圖的鄰接矩陣是對稱的，因此可以只存儲鄰接矩陣的下或上三角部分。()7．在散列存儲中采取開散列(鏈地址)法解決沖突時，其裝載因子的取值一定在(0，1)之間。四。運(yùn)算提示：在進(jìn)行每題運(yùn)算時，最好先在草稿紙上根據(jù)題意畫出對應(yīng)的圖形，這樣更直觀和簡便。1．假定一棵普通樹的廣義表表示為。(b(e)，r(f(h,i,j)，g))，分別寫出先根、后根、按層遍歷的結(jié)果。先根：后根：按層：2．假定一個線性序列為(38，52，25，74，68，16，30，54，90，72)，根據(jù)此線性序列中元素的排列次序生成的一棵二叉搜索樹，求出對該二叉搜索樹進(jìn)行查找38，74，68，30，72等元素時的查找長度(即比較次敷)。待查元素3874683072比較次數(shù)3．已知——棵二叉搜索樹的廣義表表示為：28(12(，16)，49(34(30)，72(63)))，求出從中依次刪除72，12，28結(jié)點(diǎn)后，得到的--X搜索樹的廣義表表示．假定每次刪除雙支結(jié)點(diǎn)時是用它的中序后繼結(jié)點(diǎn)的值來取代，接著刪除其中序后繼結(jié)點(diǎn)。廣義表表示：4．已知一個圖的頂點(diǎn)集V和邊集G分別為：V=(1，2，3，4，5，6)；E={<1，2>，<1，3>，<2，42>，<2，5>，<3，4．7，<4，5>，<4，6>，<5，1>，<5，3>，<6，5>}；假定該圖采用鄰接矩陣表表示，試按照遍歷算法寫出：(1)從頂點(diǎn)2出發(fā)進(jìn)行深度優(yōu)先搜索所得到的頂點(diǎn)序列，(2)從頂點(diǎn)2出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的頂點(diǎn)序列。(1)(2)5．設(shè)散列表的長度m：7，散列函數(shù)為H(K)=Kmodm，若采用線性探查法解決沖突，待依次插入的關(guān)鍵碼序列為{19，14，23，68，20，84}，分別求出查找23，68，84時的搜索長度。查找23，68，84的搜索長度：五、算法分析題1．設(shè)單鏈表結(jié)點(diǎn)的結(jié)構(gòu)為LNode＝(data，link)，閱瀆下面的函數(shù)，指出它所實(shí)現(xiàn)的功能算法功能；六、算法設(shè)計1.已知f為單鏈表的表頭指針，單鏈表中的結(jié)點(diǎn)結(jié)構(gòu)為(data，link)，并假定每個結(jié)點(diǎn)的值均為大于。的整數(shù)。根據(jù)下面函數(shù)聲明寫出遞歸算法，返回單鏈表中所有結(jié)點(diǎn)的最大值，若單鏈表為空則返回數(shù)值0。intMax(LinkNode*f)；2.設(shè)Q是一個由其隊尾指針和隊列長度標(biāo)識的循環(huán)隊列，按照下面隊列定義和函數(shù)聲明寫出從此隊列中刪除一個元素的算法。／／循環(huán)隊列定義／／若隊列非空則刪除隊頭元素并由引用參數(shù)x帶回，同時返回true,否則若隊列為空則返回false。試題答案及評分標(biāo)準(zhǔn)一、單項選擇題1.D2．C3．B4．C5.B6．A7．B8．C9．D二、填空題，1．繼承2．相同3．MaxSixe一14．635．最大值6．n—l7．4三、判斷題，1．對2．錯3．對4．錯5.對6．對7．錯四、運(yùn)算題1．先根:a,b,e,c,f,h,i,j,g后根:e,b,h,i,j,f,g,c,a按層：a,b,c,e,f,g,h,i,j2．評分標(biāo)準(zhǔn)：對1個數(shù)值給1分，全對給6分待查元素：3874683072比較次數(shù)：134353．30(16，49(34，63))4．(1)2，4，5，1，3，6(2)2，4，5，6，1，35．查找23，68，84的搜索長度：1，2，4五、算法分析1．計算單鏈表的長度或計算單鏈表中結(jié)點(diǎn)的個數(shù)。2．逆序排列以first為表頭指針的單鏈表中的所有結(jié)點(diǎn)并返回新的表頭指針。六、算法設(shè)計1.評分標(biāo)準(zhǔn)：按注釋酌情給分。2．評分標(biāo)準(zhǔn)：按注釋酌情給分。《數(shù)據(jù)結(jié)構(gòu)》題庫及答案四一、單項選擇題

1.給定有n個元素的向量，建立一個有序單鏈表的時間復(fù)雜度是（C）。

A.O(1)B.O(n)

C.O(n2)D.O(nlog2n)

2.帶表頭的雙向循環(huán)鏈表的空表滿足（B）。

A.first＝NULL;B.first->rLink==first

C.first->lLink==NULLD.first->rLink==NULL

3.棧的插入和刪除操作在(A)進(jìn)行。

A.棧頂B.棧底C.任意位置D.指定位置

4.在一個順序存儲的循環(huán)隊列中，隊頭指針指向隊頭元素的(A)位置。

A.前一個B.后一個C.當(dāng)前D.后面

5.假定一個順序存儲的循環(huán)隊列的隊頭和隊尾指針分別為front和rear，則判斷隊空的條件為(D)。

A.front+1==rearB.rear+1==front

C.front==0D.front==rear

6.設(shè)鏈?zhǔn)綏Ｖ薪Y(jié)點(diǎn)的結(jié)構(gòu)為（data,link），且top是指向棧頂?shù)闹羔?。若想摘除鏈?zhǔn)綏５臈ｍ斀Y(jié)點(diǎn)，并將被摘除結(jié)點(diǎn)的值保存到x中，則應(yīng)執(zhí)行(A)操作。

A.x=top->data;top=top->link;B.top=top->link;x=top->data;

C.x=top;top=top->link;D.x=top->data;

7.為增加內(nèi)存空間的利用率和減少溢出的可能性,由兩個棧共享一塊連續(xù)的內(nèi)存空間時,應(yīng)將兩棧的(D)分別設(shè)在這塊內(nèi)存空間的兩端。

A.長度B.深度C.棧頂D.棧底

8.在系統(tǒng)實(shí)現(xiàn)遞歸調(diào)用時需利用遞歸工作記錄保存（C），當(dāng)遞歸調(diào)用程序執(zhí)行結(jié)束時通過它將控制轉(zhuǎn)到上層調(diào)用程序。

A.調(diào)用地址B.遞歸入口C.返回地址D.遞歸出口

9.如果一個遞歸函數(shù)過程中只有一個遞歸語句，而且它是過程體的最后語句，則這種遞歸屬于（D），它很容易被改寫為非遞歸過程。

A.單向遞歸B.回溯遞歸C.間接遞歸D.尾遞歸

10.設(shè)有一個廣義表A(a)，其表尾為（C）。

A．a(chǎn)B．(())C．（）D．(a)

11.對于一組廣義表A(),B(a,b),C(c,(e,f,g)),D(B,A,C),E(B,D)，其中的E是（D）。

A.線性表B.純表C.遞歸表D.再入表

12.在一棵樹中，(C)沒有前驅(qū)結(jié)點(diǎn)。

A.樹枝結(jié)點(diǎn)B.葉子結(jié)點(diǎn)C.樹根結(jié)點(diǎn)D.空結(jié)點(diǎn)

13.在一棵具有n個結(jié)點(diǎn)的二叉樹的第i層上(假定根結(jié)點(diǎn)為第0層，i大于等于0而小于等于樹的高度)，最多具有(A)個結(jié)點(diǎn)。

A.2iB.2i+1C.2i-1D.2n

二、填空題

1.鏈表與順序表、索引表、散列表等都是數(shù)據(jù)邏輯結(jié)構(gòu)的（存儲）表示。

2.隊列是一種限定在表的一端插入，在另一端刪除的線性表，它又被稱為（先進(jìn)先出）表。

3.向一個順序棧插入一個元素時，首先使（棧頂指針）后移一個位置，然后把待插入元素寫入到這個位置上。

4.向一個循環(huán)隊列中插入元素時，需要首先移動（隊尾）指針，然后再向所指位置寫入新元素。

5.在一個鏈?zhǔn)疥犃兄?，若隊頭指針與隊尾指針的值相同，則表示該隊列至多有（1）個結(jié)點(diǎn)。

6.遞歸工作棧起到兩個作用，其一是將遞歸調(diào)用時的實(shí)際參數(shù)和返回地址傳遞給下一層遞歸；其二是保存本層的形式參數(shù)和（局部變量）。

7.非空廣義表的除第一個元素外其他元素組成的表稱為廣義表的（表尾）。

8.廣義表的深度定義為廣義表括號的（重數(shù)）。

9.一棵樹的廣義表表示為a(b(c,d(e,f),g(h)),i(j,k(x,y)))，結(jié)點(diǎn)f的層數(shù)為（3）。假定樹根結(jié)點(diǎn)的層數(shù)為0。

10.在一棵三叉樹中，度為3的結(jié)點(diǎn)數(shù)有2個，度為2的結(jié)點(diǎn)數(shù)有1個，度為1的結(jié)點(diǎn)數(shù)為2個，那么度為0的結(jié)點(diǎn)數(shù)有（6）個。

11．一棵二叉樹中，假定雙分支結(jié)點(diǎn)數(shù)為5個，單分支結(jié)點(diǎn)數(shù)為6個，則葉子結(jié)點(diǎn)數(shù)為（6）個。

12.在一棵高度為h的理想平衡二叉樹中，最多含有（2h+1-1）個結(jié)點(diǎn)。假定樹根結(jié)點(diǎn)的高度為0。

三、判斷題（對/錯）

1．在用單鏈表表示的鏈?zhǔn)疥犃蠶中，隊頭指針為Q->front，隊尾指針為Q->rear，則隊空條件為Q->front==Q->rear。錯

2遞歸調(diào)用算法與相同功能的非遞歸算法相比，主要問題在于重復(fù)計算太多，而且調(diào)用本身需要分配額外的空間和傳遞數(shù)據(jù)和控制，所以時間與空間開銷通常都比較大。對

3將f=1+1/2+1/3+…+1/n轉(zhuǎn)化為遞歸函數(shù)時，遞歸部分為f(n)=f(n-1)+1/n，遞歸結(jié)束條件為f(1)=1。對

4.一個廣義表((a),((b),c),(((d))))的長度為3，深度為4。對

5.當(dāng)從一個最小堆中刪除一個元素時，需要把堆尾元素填補(bǔ)到堆頂位置完成刪除操作。錯

6.在一棵二叉樹中，假定每個結(jié)點(diǎn)只有左子女，沒有右子女，對它分別進(jìn)行中序遍歷和后序遍歷，則具有相同的結(jié)果。對

7.在樹的存儲中，若使每個結(jié)點(diǎn)帶有指向雙親結(jié)點(diǎn)的指針，這為在算法中尋找雙親結(jié)點(diǎn)帶來方便。對

8．于一棵具有n個結(jié)點(diǎn)的任何二叉樹，進(jìn)行前序、中序或后序的任一種次序遍歷的空間復(fù)雜度為O(log2n)。錯

9．對具有n個結(jié)點(diǎn)的堆進(jìn)行插入一個元素運(yùn)算的時間復(fù)雜度為O(n)。對

四、運(yùn)算題

1.已知一棵樹的靜態(tài)雙親表示如下，其中用-1表示空指針，樹根結(jié)點(diǎn)存于0號單元，分別求出該樹的葉子結(jié)點(diǎn)數(shù)、單分支結(jié)點(diǎn)數(shù)、兩分支結(jié)點(diǎn)數(shù)和三分支結(jié)點(diǎn)數(shù)。

序號：012345678910

abcdefghijk

-10113056609

data:

parent:

葉子結(jié)點(diǎn)數(shù)：5

單分支結(jié)點(diǎn)數(shù)：3

兩分支結(jié)點(diǎn)數(shù)：2

三分支結(jié)點(diǎn)數(shù)：1

2.已知一個有序表(15,26,34,39,45,56,58,63,74,76,83,94)順序存儲于一維數(shù)組a[12]中，根據(jù)折半搜索過程填寫成功搜索下表中所給元素34,56,58,63,94時的比較次數(shù)。

3456586394

21344

元素

比較次數(shù)

3.假定一個線性序列為(38,42,55,15,23,44,30,74,48，26)，根據(jù)此線性序列中元素的排列次序生成一棵二叉搜索樹，求出該二叉搜索樹中左子樹為空的所有單支結(jié)點(diǎn)和右子樹為空的所有單支結(jié)點(diǎn)，請按照結(jié)點(diǎn)值從小到大的次序?qū)懗觥?/p>

左子樹為空的所有單支結(jié)點(diǎn)：15,23,42,44

右子樹為空的所有單支結(jié)點(diǎn)：30

4.假定一組記錄為(40,28,16,56,50,32,30,63,44,38)，按次序插入每個記錄生成一棵AVL樹，請回答插入時造成不平衡的結(jié)點(diǎn)個數(shù)。

插入時造成不平衡的結(jié)點(diǎn)個數(shù)：4

5.已知圖G=(V,E)，其中V={a,b,c,d,e}，E={，，，，，，}，請寫出各結(jié)點(diǎn)的出度和入度。

結(jié)點(diǎn)abcde

出度11212

入度22111

6.已知一個圖的頂點(diǎn)集V和邊集G分別為：

V={1,2,3,4,5,6};

E={<1,2>,<1,3>,<2,4>,<2,5>,<3,4>,<4,5>,<4,6>,<5,1>,<5,3>,6,5>};

假定該圖采用鄰接表表示，每個頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號（即數(shù)值域的值）從小到大的次序鏈接的，試寫出：

(1)從頂點(diǎn)1出發(fā)進(jìn)行深度優(yōu)先搜索所得到的頂點(diǎn)序列；

(2)從頂點(diǎn)1出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的頂點(diǎn)序列。

答（1）：1,2,4,5,3,6

（2）：1,2,3,4,5,6

五、算法分析題

1.請寫出下面算法的功能.

voidunknown(Queue&Q){

StackS;intd;

S.InitStack();

while(!Q.IsEmpty()){

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

}

while(!S.IsEmpty()){

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

}

}

利用"棧"作為輔助存儲,將隊列中的元素逆置（即相反次序放置）。

2.下面是判斷一個帶表頭結(jié)點(diǎn)的雙向循環(huán)鏈表L其前后結(jié)點(diǎn)值是否對稱相等的算法,若相等則返回1，否則返回0。請按標(biāo)號補(bǔ)充合適的內(nèi)容。

intsymmetry(DoublelList*DL){

DoublelNode*p=DL->rLink,*q=DL->lLink;

while(p!=q)

if(p->data==q->data){

p=p->rLink;

___(1)___;

if(p->lLink==q)___(2)___;

}

else___(3)___;

return1;

}

(1)q=q->lLink(2)return1(3)return0

3.設(shè)有一個求解漢諾塔（Hanoi）的遞歸算法如下：

voidHANOI(intn,intpeg1,intpeg2,intpeg3){

if(n==1)cout<<PEG1<’<<PEG3<<ENDL;

else{

HANOI(n-1,peg1,peg3,peg2);

cout<<PEG1<’<<PEG3<<ENDL;

HANOI(n-1,peg2,peg1,peg3);

}

}

當(dāng)使用HANOI(3,1,2,3)進(jìn)行調(diào)用時，執(zhí)行過程中else子句的cout語句得到的結(jié)果為：

1→2

1→3

2→3

4.已知二叉樹中的結(jié)點(diǎn)類型BinTreeNode定義為:

structBinTreeNode{ElemTypedata;BinTreeNode*left,*right;};

其中data為結(jié)點(diǎn)值域，left和right分別為指向左、右子女結(jié)點(diǎn)的指針域。下面函數(shù)的功能是：從二叉樹BT中查找值為X的結(jié)點(diǎn)，返回指向其父結(jié)點(diǎn)的指針。若該結(jié)點(diǎn)不存在或為樹根結(jié)點(diǎn)則返回空。算法中參數(shù)PT的初值為NULL。請在劃有橫線的地方填寫合適內(nèi)容。

BinTreeNode*ParentPtr(BinTreeNode*BT,BinTreeNode*PT,ElemType&X)

{

if(BT==NULL)returnNULL;

elseif(BT->data==X)returnPT;

else{

if(PT=ParentPtr(BT->left,BT,X))__(1)_____;

if_________________(2)_______________returnPT;

else___(3)____;

}

}

(1)returnPT

(2)(PT=ParentPtr(BT->right,BT,X))

(3)returnNULL或return0

六、算法設(shè)計題

1.計算多項式Pn(x)=a0xn+a1xn-1+a2xn-2+……+an-1x+an通常使用的方法是一種遞推的方法。它可以描述為如下的遞推形式：

pn(x)=x*pn-1(x)+an(n>0)

此處

Pn-1(x)=a0xn-1+a1xn-2+……+an-2x+an-1

P0=an

這也是問題的遞歸形式。多項式的遞歸求解形式為：

poly(x,0)=A[0]

poly(x,n)=x*poly(x,n-1)+A[n],n>0

試編寫一個遞歸函數(shù)，計算這樣的多項式的值。

floatpoly(floatx,floatA[],intn){

}

答：

floatpoly(floatx,floatA[],intn){

if(!n)returnA[0];

elsereturnx*poly(x,A,n-1)+A[n];

}

2.已知二叉樹中的結(jié)點(diǎn)類型BinTreeNode定義為:

structBinTreeNode{chardata;BinTreeNode*left,*right;};

其中data為結(jié)點(diǎn)值域，left和right分別為指向左、右子女結(jié)點(diǎn)的指針域。根據(jù)下面函數(shù)聲明編寫出求一棵二叉樹高度的算法，該高度由函數(shù)返回。假定樹根的層次為0，參數(shù)BT初始指向這棵二叉樹的根結(jié)點(diǎn)。

intBTreeHeight(BinTreeNode*BT);

答：

intBTreeHeight(BinTreeNode*BT)

{

if(BT==NULL)

//對于空樹，返回-1并結(jié)束遞歸

return–1;

else

{

//計算左子樹的高度

inth1=BTreeHeight(BT->left);

//計算右子樹的高度

inth2=BTreeHeight(BT->right);

//返回樹的高度

if(h1>h2)returnh1+1;

elsereturnh2+1;

}

}

說明：函數(shù)體中的兩個else可以沒有

3.已知二叉樹中的結(jié)點(diǎn)類型BinTreeNode定義為:

structBinTreeNode{chardata;BinTreeNode*left,*right;};

其中data為結(jié)點(diǎn)值域，left和right分別為指向左、右子女結(jié)點(diǎn)的指針域，根據(jù)下面函數(shù)聲明編寫出求一棵二叉樹中葉子結(jié)點(diǎn)總數(shù)的算法，該總數(shù)值由函數(shù)返回。假定參數(shù)BT初始指向這棵二叉樹的根結(jié)點(diǎn)。

intBTreeLeafCount(BinTreeNode*BT);

答：

intBTreeLeafCount(BinTreeNode*BT)

{

if(BT==NULL)return0;

elseif(BT->left==NULL&&BT->right==NULL)return1;

elsereturnBTreeLeafCount(BT->left)+BTreeLeafCount(BT->right);

}

說明：函數(shù)體中的兩個else可以沒有《數(shù)據(jù)結(jié)構(gòu)》題庫及答案二一、單項選擇題

1.在一棵具有n個結(jié)點(diǎn)的完全二叉樹中，樹枝結(jié)點(diǎn)的最大編號為(D)。假定樹根結(jié)點(diǎn)的編號為0。

A.?(n-1)/2?B.?n/2?C.én/2ùD.?n/2?-1

2.在一棵樹的左子女-右兄弟表示法中，一個結(jié)點(diǎn)的右子女是該結(jié)點(diǎn)的(A)結(jié)點(diǎn)。

A.兄弟B.父子C.祖先D.子孫

3.已知一棵樹的邊集表示為{,,,,,,,}，則該樹的深度為(B)。假定樹根結(jié)點(diǎn)的高度為0。

A.2B.3C.4D.5

4.一棵樹的廣義表表示為a(b,c(e,f(g)),d)，當(dāng)用左子女-右兄弟鏈表表示時，右指針域非空的結(jié)點(diǎn)個數(shù)為(C)。

A1B2C3D4

5.對長度為10的順序表進(jìn)行搜索，若搜索前面5個元素的概率相同，均為1/8，搜索后面5個元素的概率相同，均為3/40，則搜索任一元素的平均搜索長度為(C)。

A.5.5B.5C.39/8D.19/4

6.對于長度為n的順序存儲的有序表，若采用折半搜索，則對所有元素的搜索長度中最大的為(A)的值向上取整。

A.log2(n+1)B.log2nC.n/2D.(n+1)/2

7.對于長度為18的順序存儲的有序表，若采用折半搜索，則搜索第15個元素的搜索長度為(B)。

A.3B.4C.5D.6

8.從具有n個結(jié)點(diǎn)的二叉搜索樹中搜索一個元素時，在等概率情況下進(jìn)行成功搜索的時間復(fù)雜度大致為(C)。

A.O(n)B.O(1)C.O(log2n)D.O(n2)

9.向一棵AVL樹插入元素時，可能引起對最小不平衡子樹的調(diào)整過程，此調(diào)整分為(C)種旋轉(zhuǎn)類型。

A.2B.3C.4D.5

10.設(shè)G1=（V1，E1）和G2=（V2，E2）為兩個圖，如果V1íV2，E1íE2，則稱(A)。

A．G1是G2的子圖B．G2是G1的子圖

C．G1是G2的連通分量D．G2是G1的連通分量

11.n個頂點(diǎn)的連通圖中至少含有(A)。

A．n-1條邊B．n條邊C．n(n-1)/2條邊D．n(n-1)條邊

12.對于具有e條邊的無向圖，它的鄰接表中有(D)個邊結(jié)點(diǎn)。

A．e-1B．eC．2(e-1)D．2e

13.在n個頂點(diǎn)的有向無環(huán)圖的鄰接矩陣中至少有(C)個零元素。

A．nB．n(n-1)/2C．n(n+1)/2D．n(n-1)

二、填空題

1．在一個堆的順序存儲中，若一個元素的下標(biāo)為i(0≤i≤n-1)，則它的左子女元素的下標(biāo)為（2i+1）。

2．在一個最大堆中，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的（最大值）。

3.假定一個順序表的長度為40，并假定順序搜索每個元素的概率都相同，則在搜索成功情況下的平均搜索長度為(20.5)。

4.從一棵二叉搜索樹中搜索一個元素時，若給定值大于根結(jié)點(diǎn)的值，則需要向(右子樹)繼續(xù)搜索。

5.在一棵AVL樹中，每個結(jié)點(diǎn)的左子樹高度與右子樹高度之差的絕對值不超過（1）。

6.根據(jù)一組記錄(56,42,38,64,48)依次插入結(jié)點(diǎn)生成一棵AVL樹時，當(dāng)插入到值為38的結(jié)點(diǎn)時需要進(jìn)行（右單旋轉(zhuǎn)）調(diào)整。

7.n(n﹥0)個頂點(diǎn)的連通無向圖各頂點(diǎn)的度之和最少為（2(n-1)）。

8.設(shè)圖G=(V,E)，V={1,2,3,4},E={<1,2>,<1,3>,<2,4>,<3,4>}，從頂點(diǎn)1出發(fā)，對圖G進(jìn)行廣度優(yōu)先搜索的序列有（2）種。

9.n個頂點(diǎn)的連通無向圖的生成樹含有(n-1)條邊。

10.一般來說,深度優(yōu)先生成樹的高度比廣度優(yōu)先生成樹的高度要（高）。

11.第i(i=1,2,…,n-1)趟從參加排序的序列中取出第i個元素，把它插入到由第0個至第i-1個元素組成的有序表中適當(dāng)?shù)奈恢?，此種排序方法叫做（直接插入）排序。

三、判斷題（對/錯）

1.能夠在鏈接存儲的有序表上進(jìn)行折半搜索，其時間復(fù)雜度與在順序存儲的有序表上相同。錯

2.折半搜索所對應(yīng)的判定樹，既是一棵二叉搜索樹，又是一棵理想平衡二叉樹。對

3.對于兩棵具有相同記錄集合而具有不同形態(tài)的二叉搜索樹，按中序遍歷得到的結(jié)點(diǎn)序列是相同的。對

4.用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中的頂點(diǎn)個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。對

5.存儲有向圖的鄰接矩陣是對稱的，因此可以只存儲鄰接矩陣的下（上）三角部分。錯

6.有回路的有向圖不能完成拓?fù)渑判?。?/p>

7.對于AOE網(wǎng)絡(luò)，加速任一關(guān)鍵活動就能使整個工程提前完成。錯

8.對一個連通圖進(jìn)行一次深度優(yōu)先搜索可以遍訪圖中的所有頂點(diǎn)。對

四、運(yùn)算題

1.已知一個圖的頂點(diǎn)集V和邊集G分別為：

V={1,2,3,4,5,6};

E={<1,2>,<1,3>,<2,4>,<2,5>,<3,4>,<4,5>,<4,6>,<5,1>,<5,3>,6,5>};

假定該圖采用鄰接表表示，每個頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號（即數(shù)值域的值）從大到小的次序鏈接的，試按照遍歷算法寫出：

(1)從頂點(diǎn)1出發(fā)進(jìn)行深度優(yōu)先搜索所得到的頂點(diǎn)序列；

(2)從頂點(diǎn)1出發(fā)進(jìn)行廣度優(yōu)先搜索所得到的頂點(diǎn)序列。

答（1）：1,3,4,6,5,2

（2）：1,3,2,4,5,6

2.已知一個帶權(quán)圖的頂點(diǎn)集V和邊集G分別為：

V={0,1,2,3,4,5,6};

E={(0,1)19,(0,2)10,(0,3)14,(1,2)6,(1,5)5,(2,3)26,(2,4)15,(3,4)18,

(4,5)6,(4,6)6,(5,6)12};

試根據(jù)迪克斯特拉(Dijkstra)算法求出從頂點(diǎn)0到其余各頂點(diǎn)的最短路徑，在下面填寫對應(yīng)的路徑長度。

頂點(diǎn)：0123456

路徑長度：0161014252131

3.已知一個AOV網(wǎng)絡(luò)的頂點(diǎn)集V和邊集G分別為：

V={0,1,2,3,4,5,6,7};

E={<0,2>,<1,3>,<1,4>,<2,4>,<2,5>,<3,6>,<3,7>,<4,7>,<5,7>,<6,7>};

若存儲它采用鄰接表，并且每個頂點(diǎn)鄰接表中的邊結(jié)點(diǎn)都是按照終點(diǎn)序號(即dest域的值)從小到大的次序鏈接的，則按主教材中介紹的進(jìn)行拓?fù)渑判虻乃惴?，寫出得到的拓?fù)湫蛄校ㄌ崾荆合犬嫵鰧?yīng)的圖形，然后再運(yùn)算）。

拓?fù)湫蛄校?,3,6,0,2,5,4,7

4.已知一個AOE網(wǎng)絡(luò)的頂點(diǎn)集V和邊集G分別為：

V={0,1,2,3,4,5};

E={<0,1>5,<0,2>8,<1,2>7,<1,3>10,<1,4>6,<2,4>3,<3,4>9,<3,5>15,<4,5>12};

若存儲它采用鄰接表，則按主教材中介紹的求關(guān)鍵路徑的方法，依次寫出所有的關(guān)鍵活動（用邊表示），并求出關(guān)鍵路徑長度（提示：先畫出對應(yīng)的圖形，然后再運(yùn)算）。

所有關(guān)鍵活動：<0,1>5,<1,3>10,<3,4>9,<4,5>12

關(guān)鍵路徑長度：36

5.如果某個文件經(jīng)內(nèi)排序得到80個初始?xì)w并段，試問

(1)若使用多路歸并執(zhí)行3趟完成排序，那么應(yīng)取的歸并路數(shù)至少應(yīng)為多少？

(2)如果操作系統(tǒng)要求一個程序同時可用的輸入/輸出文件的總數(shù)不超過15個，則按多路歸并至少需要幾趟可以完成排序？

答（1）歸并路數(shù)：5（2）需要?dú)w并躺數(shù)：2

答案解釋：

(1)設(shè)歸并路數(shù)為k，初始?xì)w并段個數(shù)m=80，根據(jù)歸并趟數(shù)計算公式S=élogkmù=élogk80ù=3得：k3≥80。由此解得k≥5，即應(yīng)取的歸并路數(shù)至少為5。

(2)設(shè)多路歸并的歸并路數(shù)為k，需要k個輸入緩沖區(qū)和1個輸出緩沖區(qū)。1個緩沖區(qū)對應(yīng)1個文件，有k+1=15，因此k=14，可做14路歸并。由S=élogkmù=élog1480ù=2。即至少需2趟歸并可完成排序。

五、算法分析題

1.已知二叉樹中的結(jié)點(diǎn)類型BinTreeNode定義為:

structBinTreeNode{ElemTypedata;BinTreeNode*left,*right;};

其中data為結(jié)點(diǎn)值域，left和right分別為指向左、右子女結(jié)點(diǎn)的指針域。根據(jù)下面函數(shù)的定義指出函數(shù)的功能。算法中參數(shù)BT指向一棵二叉樹。

voidBTC(BinTreeNode*BT)

{

if(BT!=NULL){

if(BT->left!=NULL&&BT->right!=NULL)

if(BT->left->data>BT->right->data){

BinTreeNode*t=BT->left;

BT->left=BT->right;

BT->right=t;

}

BTC(BT->left);

BTC(BT->right);

}

}

算法功能：當(dāng)BT中每個結(jié)點(diǎn)的左子女的值大于右子女的值則交換左右子樹。

2.已知二叉樹中的結(jié)點(diǎn)類型BinTreeNode定義為:

structBinTreeNode{chardata;BinTreeNode*left,*right;};

其中data為結(jié)點(diǎn)值域，left和right分別為指向左、右子女結(jié)點(diǎn)的指針域。假定一棵二叉樹采用鏈接存儲，它的廣義表表示為r(b(,d(f,g)),t(e))，rt,bt,dt和et指針變量分別保存指向r,b,d和e結(jié)點(diǎn)的指針值，則：

執(zhí)行BTM(rt)調(diào)用后，得到的函數(shù)值為___(1)_____;

執(zhí)行BTM(bt)調(diào)用后，得到的函數(shù)值為___(2)_____;

執(zhí)行BTM(dt)調(diào)用后，得到的函數(shù)值為___(3)_____;

執(zhí)行BTM(et)調(diào)用后，得到的函數(shù)值為__(4)______;

charBTM(BinTreeNode*BT)

{

staticcharmax=0;

if(BT!=NULL){

chark1,k2;

k1=BTM(BT->left);

k2=BTM(BT->right);

if(k1>max)max=k1;

elseif(k2>max)max=k2;

elseif(BT->data>max)max=BT->data;

}

returnmax;

}

(1)’t’

(2)’g’

(3)’g’

(4)’e’

3.在a[10]數(shù)組中數(shù)據(jù){16,35,42,73,54,58,80}為一個最小堆，n為整型變量，其值為7，則執(zhí)行DH(a,n)調(diào)用下面算法后數(shù)組a中的數(shù)據(jù)變?yōu)開____________________________。

intDH(intHBT[],int&n)

{

if(n==0){cerr<<"null!"<

inttemp=HBT[0];

n--;

intx=HBT[n];

inti=0;

intj=2*i+1;

while(j<=n-1){

if(jHBT[j+1])j++;

if(x<=HBT[j])break;

HBT=HBT[j];

i=j;j=2*i+1;

}

HBT=x;

returntemp;

}

{35,54,42,73,80,58}

4.假定p1和p2是兩個單鏈表的表頭指針，用來表示兩個集合，單鏈表中的結(jié)點(diǎn)包括值域data和指向后繼結(jié)點(diǎn)的指針域link，試根據(jù)下面算法指出算法功能。

intSS(ListNode*p1,ListNode*p2)

{

while(p2!=NULL){

ListNode*r=p1;

While(r!=NULL){

if(p2->data==r->data)break;

r=r->link;

}

if(r==NULL)return0;

p2=p2->link;

}

return1;

}

判斷p2單鏈表所代表的集合是否為p1單鏈表所代表的集合的子集合，若是則返回1否則返回0。

5.已知二叉樹中的結(jié)點(diǎn)類型BinTreeNode定義為:

structBinTreeNode{ElemTypedata;BinTreeNode*left,*right;};

其中data為結(jié)點(diǎn)值域，left和right分別為指向左、右子女結(jié)點(diǎn)的指針域。參數(shù)bt指向一棵二叉樹，引用參數(shù)x一開始具有的值小于樹中所有結(jié)點(diǎn)的值。試根據(jù)下面的函數(shù)定義指出此算法的功能。

intJB(BinTreeNode*bt,ElemType&x)

{

if(bt==NULL)return1;

else{

if(JB(bt->left,x)==0)return0;

if(bt->data

x=bt->data;

if(JB(bt->right,x)==0)return0;

elsereturn1;

}

}

算法功能：判斷二叉樹bt是否為一棵二叉搜索樹，若是則返回1否則返回0。

六、算法設(shè)計題

1.已知二叉樹中的結(jié)點(diǎn)類型BinTreeNode定義為:

structBinTreeNode{chardata;BinTreeNode*left,*right;};

其中data為結(jié)點(diǎn)值域，left和right分別為指向左、右子女結(jié)點(diǎn)的指針域，根據(jù)下面函數(shù)聲明編寫出判斷兩棵二叉樹是否相等的算法，若相等則返回1否則返回0。算法中參數(shù)T1和T2為分別指向這兩棵二叉樹根結(jié)點(diǎn)的指針。當(dāng)兩棵樹的結(jié)構(gòu)完全相同并且對應(yīng)結(jié)點(diǎn)的值也相同時才被認(rèn)為相等。

intBTreeEqual(BinTreeNode*T1,BinTreeNode*T2);

答：

intBTreeEqual(BinTreeNode*T1,BinTreeNode*T2)

{

//若兩棵樹均為空則返回1表示相等

if(T1==NULL&&T2==NULL)return1;

//若一棵為空一棵不為空則返回0表示不等

elseif(T1==NULL||T2==NULL)return0;

//若根結(jié)點(diǎn)值相等并且左、右子樹對應(yīng)相等則兩棵樹相等

elseif(T1->data==T2->data&&BTreeEqual(T1->left,T2->left)&&

BTreeEqual(T1->right,T2->right))

return1;

//若根結(jié)點(diǎn)值不等或左、右子樹對應(yīng)不等則兩棵樹不等

else

return0;

}

2.已知二叉樹中的結(jié)點(diǎn)類型用BinTreeNode表示，被定義為:

structBinTreeNode{chardata;BinTreeNode*left,*right;};

其中data為結(jié)點(diǎn)值域，left和right分別為指向左、右子女結(jié)點(diǎn)的指針域，根據(jù)下面函數(shù)聲明編寫出復(fù)制一棵二叉樹的算法，并返回復(fù)制得到的二叉樹的根結(jié)點(diǎn)指針。算法中參數(shù)BT初始指向待復(fù)制二叉樹的根結(jié)點(diǎn)。

BinTreeNode*BTreeCopy(BinTreeNode*BT);

答：

BinTreeNode*BTreeCopy(BinTreeNode*BT)

{

if(BT==NULL)returnNULL;

else{

//得到新結(jié)點(diǎn)

BinTreeNode*pt=newBinTreeNode;

//復(fù)制根結(jié)點(diǎn)值

pt->data=BT->data;

//復(fù)制左子樹

pt->left=BTreeCopy(BT->left);

//復(fù)制右子樹

pt->right=BTreeCopy(BT->right);

//返回新樹的樹根指針

returnpt;

}

}

說明：函數(shù)體中的else可以沒有

3.假定元素類型為ElemType的一維數(shù)組R[n]中保存著按關(guān)鍵碼升序排列的n個記錄，記錄的關(guān)鍵碼域key的類型為KeyType，試按照下面的函數(shù)聲明編寫一個非遞歸算法，從一維數(shù)組R[n]中折半搜索出關(guān)鍵碼等于K的記錄，若搜索成功則返回記錄位置（即元素下標(biāo)），否則返回-1。

intBinSearch(ElemTypeR[],intn,KeyTypeK);

答：

intBinSearch(ElemTypeR[],intn,KeyTypeK)

{

intlow=0,high=n-1;

while(low<=high)

{

intmid=(low+high)/2;

if(K==R[mid].key)returnmid;

elseif(K

elselow=mid+1;

}

return-1;

}

說明：函數(shù)體中第一個else可以沒有.《數(shù)據(jù)結(jié)構(gòu)》題庫及答案三一、單項選擇題

1.一個數(shù)組元素a與(A)的表示等價。

A.*(a+i)B.a+iC.*a+iD.&a+I

2．執(zhí)行下面程序段時，執(zhí)行S語句的次數(shù)為(D)。

for(inti=1;i<=n;i++)

for(intj=1;j<=i;j++)S;

A.n2B.n2/2C.n(n+1)D.n(n+1)/2

3.當(dāng)一個作為實(shí)際傳遞的對象占用的存儲空間較大并可能被修改時，應(yīng)最好說明為(B)，以節(jié)省參數(shù)值的傳輸時間和存儲參數(shù)的空間。

A.基本類型B.引用型C.指針型D.常值引用型

4.輸出一個二維數(shù)組b[m][n]中所有元素值的時間復(fù)雜度為(D)。

A.O(n)B.O(m+n)C.O(n2)D.O(m*n)

5.某算法僅含程序段1和程序段2，程序段1的執(zhí)行次數(shù)3n2，程序段2的執(zhí)行次數(shù)為0.01n3，則該算法的時間復(fù)雜度為（C）。

A.O(n)B.O(n2)C.O(n3)D.O(1)

6.多維數(shù)組實(shí)際上是由嵌套的（A）實(shí)現(xiàn)的。

A.一維數(shù)組B.多項式C.三元組表D.簡單變量

7.在一個長度為n的順序表中刪除第i個元素（0≤i≤n-1）時，需要從前向后依次前移（C）個元素。

A.n-iB.n-i+1C.n-i-1D.i

8.在一個長度為n的順序表的任一位置插入一個新元素的漸進(jìn)時間復(fù)雜度為（A）。

A.O(n)B.O(n/2)C.O(1)D.O(n2)

9.設(shè)有一個n′n的對稱矩陣A，將其上三角部分按行存放在一個一維數(shù)組B中，A[0][0]存放于B[0]中，那么第i行的對角元素A存放于B中（C）處。

A.(i+3)*i/2B.(i+1)*i/2C.(2n-i+1)*i/2D.(2n-i-1)*i/2

10.不帶頭結(jié)點(diǎn)的單鏈表first為空的判定條件是（A）。

A.first==NULL;B.first->link==NULL;

C.first->link==first;D.first!=NULL;

11.設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data,link）。已知指針p所指結(jié)點(diǎn)不是尾結(jié)點(diǎn)，若在*p之后插入結(jié)點(diǎn)*s，則應(yīng)執(zhí)行的操作是（D）。

A.s->link=p;p->link=s;B.p->link=s;s->link=p;

C.s->link=p->link;p=s;D.s->link=p->link;p->link=s;

12.設(shè)單循環(huán)鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data,link），且rear是指向非空的帶表頭結(jié)點(diǎn)的單循環(huán)鏈表的尾結(jié)點(diǎn)的指針。若想刪除鏈表第一個結(jié)點(diǎn)，則應(yīng)執(zhí)行的操作是（D）。

A.s=rear;rear=rear->link;deletes;

B.rear=rear->link;deleterear;

C.rear=rear->link->link;deleterear;

D.s=rear->link->link;rear->link->link=s->link;deletes;

二、填空題

1.數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)、(存儲結(jié)構(gòu))和數(shù)據(jù)的運(yùn)算三個方面。

2.基本數(shù)據(jù)類型是計算機(jī)已經(jīng)實(shí)現(xiàn)了的(數(shù)據(jù)結(jié)構(gòu))。

3.面向?qū)ο蟮奶卣鲬?yīng)包括對象、類、(繼承)、消息通信。

4.模板類是一種數(shù)據(jù)抽象，它把(數(shù)據(jù)類型)當(dāng)作參數(shù)，可以實(shí)現(xiàn)類的復(fù)用。

5.在程序運(yùn)行過程中不能擴(kuò)充的數(shù)組是(靜態(tài))分配的數(shù)組。這種數(shù)組在聲明它時必須指定它的大小。

6.若設(shè)一個n′n的矩陣A的開始存儲地址LOC(0,0)及元素所占存儲單元數(shù)d已知，按行存儲時其任意一個矩陣元素a[j]的存儲地址為(LOC(0,0)+(i*n+j)*d)。

7.將一個n階對稱矩陣A的上三角部分按行壓縮存放于一個一維數(shù)組B中，A[0][0]存放于B[0]中，則A[I][J]在I≤J時將存放于數(shù)組B的(2n-I-1)*I/2+J)位置。

8.若設(shè)串S=“documentHash.doc\0”，則該字符串S的長度為(16)。

9.在鏈表中進(jìn)行插入和（刪除）操作的效率比在順序存儲結(jié)構(gòu)中進(jìn)行相同操作的效率高。

10.單鏈表中邏輯上相鄰的結(jié)點(diǎn)而在物理位置上（不一定）相鄰。

11.若設(shè)L是指向帶表頭的單鏈表,語句L->link=L->link->link的作用是（刪除）單鏈表中的第一個結(jié)點(diǎn)。

三、判斷題（對/錯）

1.算法和程序原則上沒有區(qū)別，在討論數(shù)據(jù)結(jié)構(gòu)時二者是通用的。錯

2.只有用面向?qū)ο蟮挠嬎銠C(jī)語言才能描述數(shù)據(jù)結(jié)構(gòu)算法。錯

3.數(shù)組是一種靜態(tài)的存儲空間分配，就是說，在程序設(shè)計時必須預(yù)先定義數(shù)組的數(shù)據(jù)類型和存儲空間大小，由編譯程序在編譯時進(jìn)行分配。錯

4.順序表和一維數(shù)組一樣，都可以按下標(biāo)隨機(jī)（或直接）訪問。對

5.用字符數(shù)組存儲長度為n的字符串，數(shù)組長度至少為n+1。對

6.在線性鏈表中刪除中間的結(jié)點(diǎn)時，只需將被刪結(jié)點(diǎn)釋放。錯

7.鏈?zhǔn)綏Ｅc順序棧相比,一個明顯的優(yōu)點(diǎn)是通常不會出現(xiàn)棧滿的情況。對

8.在使用后綴表示實(shí)現(xiàn)計算器類時用到一個棧的實(shí)例,它的作用是暫存運(yùn)算器對象。對

四、運(yùn)算題

1.對于一個n′n的矩陣A的任意矩陣元素a[j]，按行存儲時和按列存儲時的地址之差是多少。（設(shè)兩種存儲時的開始存儲地址均為LOC(0,0)，元素所占存儲單元數(shù)均為d）

按行存儲時與按列存儲時，計算A[j]地址的公式分別為

LOC(i,j)=LOC(0,0)+(i*n+j)*d

及LOC’(i,j)=LOC(0,0)+(j*n+i)*d

兩者相減，得

LOC(i,j)–LOC’(i,j)=LOC(0,0)+(i*n+j)*d–LOC(0,0)–(j*n+i)*d

=(i-j)*(n-1)*d

2.設(shè)有一個10′10的矩陣A，將其下三角部分按行存放在一個一維數(shù)組B中，A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置。

根據(jù)題意，矩陣A中當(dāng)元素下標(biāo)I與J滿足I≥J時，

任意元素A[I][J]在一維數(shù)組B中的存放位置為

I*(I+1)/2+J，

因此，A[8][5]在數(shù)組B中位置為

8*(8+1)/2+5=41。

3.設(shè)有一個二維數(shù)組A[11][6]，按行存放于一個連續(xù)的存儲空間中，A[0][0]的存儲地址是1000，每個數(shù)組元素占4個存儲字，則A[8][4]的地址在什么地方。

對于二維數(shù)組，若第一、第二維的元素個數(shù)為m和n，每個元素所占存儲字?jǐn)?shù)為d，首地址為LOC(0,0)，則對于任一數(shù)組元素A[j]，它的存儲地址為：

LOC(i,j)=LOC(0,0)+(i*n+j)*d

根據(jù)題意，LOC(8,4)=LOC(0,0)+(8*6+4)*4=1000+52*4=1208。

4.假定一棵二叉樹的廣義表表示為A(B(,D(G)),C(E,F))，分別寫出對它進(jìn)行前序、中序、按層遍歷的結(jié)果。

前序：A,B,D,G,C,E,F

中序：B,G,D,A,E,C,F

按層：A,B,C,D,E,F,G

5.已知一棵二叉樹的中序和后序序列如下，求該二叉樹的前序序列。

中根序列：c,b,d,e,a,g,i,h,j,f

后根序列：c,e,d,b,i,j,h,g,f,a

先根序列：a,b,c,d,e,f,g,h,i,j

五、算法分析題

1.指出算法的功能并求出其時間復(fù)雜度。

voidmatrimult(inta[M][N],intb[N][L],intc[M][L])

{//M、N、L均為全局整型常量

inti,j,k;

for(i=0;i<M;i++)

for(j=0;j<L;j++)c[j]=0;

for(i=0;i<M;i++)

for(j=0;j<L;j++)

for(k=0;k<N;k++)

c[j]+=a[k]*b[k][j];

}

功能為：矩陣相乘，即a[M][N]×b[N][L]→c[M][L]。

時間復(fù)雜性為：O(M×N×L)。

2.設(shè)字符串String具有下列操作：

intLength()const;//計算字符串的長度

chargetData(k);//提取字符串第k個字符的值

若字符串Tar的值為“ababcabcacbab”，Pat的值為“abcac”時，給出算法執(zhí)行后函數(shù)返回的結(jié)果。

#include“String.h”

intunknown(String&Tar,String&Pat)const{

for(inti=0;i<=Tar.Length()–Pat.Length();i++){

intj=0;

while(j<Pat.Length())

if(Tar.getData(i+j)==Pat.getData(j))j++;

elsebreak;

if(j==Pat.Length())returni;

}

return-1;

}

算法執(zhí)行的結(jié)果是：函數(shù)返回值等于5。該算法即字符串的模式匹配。

3.設(shè)單鏈表結(jié)點(diǎn)的結(jié)構(gòu)為LNode=(data,link)，閱讀下面的函數(shù)，指出它所實(shí)現(xiàn)的功能。

intAA(LNode*Ha)

{//Ha為指向帶表頭附加結(jié)點(diǎn)的單鏈表的表頭指針

intn=0;

LNode*p=Ha->link;

while(p){

n++;

p=p->link;

}

return(n);

}

算法功能：計算單鏈表的長度或計算單鏈表中結(jié)點(diǎn)的個數(shù)。

4.寫出下列程序段的輸出結(jié)果:

voidmain(){

stackS;

charx,y;

S.InitStack();

x="c";y="k";

S.Push(x);S.Push("a");S.Push(y);

S.Pop(S,x);S.Push("t");S.Push("s");

while(!S.IsEmpty()){S.Pop(y);cout<

cout<<Y<

}//main

運(yùn)行結(jié)果：stack

六、算法設(shè)計題

1.設(shè)有兩個整數(shù)類型的順序表A（有m個元素）和B（有n個元素），其元素均以升序排列。試編寫一個函數(shù)，將這兩個順序表合并成一個順序表C，要求C的元素也以升序排列（表中允許元素重復(fù)）。

函數(shù)的原型如下所示。原型中的參數(shù)表給出參加運(yùn)算的三個順序表A、B與C。從C中得到執(zhí)行結(jié)果。函數(shù)中用到順序表的4個公有函數(shù)：

Length()求表的當(dāng)前長度；

maxLength()求表的最大允許長度；

getData(intk)提取第k個元素的值；

setData(intk,intval)修改第k個元素的值為val。

template

voidmerge(SeqList&A,SeqList&B,SeqList&C);

答：

template

voidmerge(SeqList&A,SeqList&B,SeqList&C){

intm=A.Length(),n=B.Length(),mpn=m+n;

if(mpn>C.maxLength()){

cerr<<“合并后表的長度超出表C的最大允許長度”<<ENDL;

exit(1);

}

inti=0,j=0,k=0,av=A.getData(i),bv=B.getData(j);

while(i

if(av<=bv){C.setData(k++,av);av=A.getData(++i);}

if(av>=bv){C.setData(k++,bv);bv=B.getData(++j);}

}

if(i<M)

while(kelse

while(k}

2.假定在一個帶表頭結(jié)點(diǎn)的單鏈表L中所有結(jié)點(diǎn)的值按遞增順序排列，試補(bǔ)充下面函數(shù)，功能是刪除表L中所有其值大于等于min，同時小于等于max的結(jié)點(diǎn)。

voidrangeDelete(ListNode*L,ElemTypemin,ElemTypemax)

{

ListNode*q=L,*p=L->link;

}

答：

while(p!=NULL){

if(p->data>=min&&p->data<=max){

q->link=p->link;deletep;p=q->link;

}

else{q=p;p=p->link;}

}

3.請分別寫出在循環(huán)隊列上進(jìn)行插入和刪除操作的算法。

循環(huán)隊列定義如下：

structCyclicQueue{

ElemTypeelem[M];//M為已定義過的整型常量，表示隊列長度

intrear,front;//rear指向隊尾元素后一個位置，front指向隊頭元素

inttag;

//當(dāng)front=rear且tag=0時，隊列空，當(dāng)front=rear且tag=1時，隊列滿

};

boolEnCQueue(CyclicQueue&Q,ElemTypex)

{

//Q是一個循環(huán)隊列，最多可存儲M個元素，若隊列不滿，

//將x插入至隊尾并返回true；否則返回false。

}

boolDelCQueue(CyclicQueue&Q,ElemType&x)

{

//Q是一個循環(huán)隊列，若隊列不空，則刪除隊頭元素并由x帶回，

//且返回true，否則返回false

}

答：

//將x插入至隊尾

if(Q.rear==Q.front&&Q.tag==1)returnfalse;

Q.elem[Q.rear]=x;

Q.rear=(Q.rear+1)%M;

if(Q.rear==Q.front)Q.tag=1;

returntrue;

//刪除隊頭元素

if(Q.front==Q.rear&&Q.tag==0)returnfalse;

x=Q.elem[Q.front];

Q.front=(Q.front+1)%M;

if(Q.front==Q.rear)Q.tag=0;

returntrue;

《數(shù)據(jù)結(jié)構(gòu)》題庫及答案四一、單項選擇題

1.與鄰接矩陣相比，鄰接表更適合于存儲(C)。

A．無向圖B．連通圖C．稀疏圖D．稠密圖

2.設(shè)無向圖的頂點(diǎn)個數(shù)為n，則該圖最多有（B）條邊。

A.n-1B.n(n-1)/2C.n(n+1)/2D.n(n-1)

3.圖的深度優(yōu)先搜索類似于樹的（A）次序遍歷。

A.先根B.中根C.后根D.層次

4.采用Dijkstra算法求解帶權(quán)有向圖的最短路徑問題時，要求圖中每條邊所帶的權(quán)值必須是（C）數(shù)。

A.非零B.非整C.非負(fù)D.非正

5.對待排序的元素序列進(jìn)行劃分，將其分為左、右兩個子序列，再對兩個子序列施加同樣的排序操作，直到子序列為空或只剩一個元素為止。這樣的排序方法是(C)。

A.直接選擇排序B.直接插入排序C.快速排序D.起泡排序

6.假設(shè)某文件經(jīng)過內(nèi)部排序得到100個初始?xì)w并段，那么如果要求利用多路平衡歸并在3趟內(nèi)完成排序，則應(yīng)取的歸并路數(shù)至少是(C)。

A.3B.4C.5D.6

7.一個對象序列的排序碼為{46,79,56,38,40,84}，采用快速排序（以位于最左位置的對象為基準(zhǔn)）所得到的第一次劃分結(jié)果為(C)。

A.{38,46,79,56,40,84}B.{38,79,56,46,40,84}

C.{40,38,46,79,56,84}D.{38,46,56,79,40,84}

8.5階B樹中,每個結(jié)點(diǎn)最多允許有（C）個關(guān)鍵碼。

A.2B.3C.4D.5

9.在一棵高度為h的B樹中，插入一個新關(guān)鍵碼時，為搜索插入位置需讀取（B）個結(jié)點(diǎn)。

A.h-1B.hC.h+1D.h+2

10.既希望較快的搜索又便于線性表動態(tài)變化的搜索方法是（D）。

A.順序搜索B.折半搜索C.散列搜索D.索引順序搜索

11.在采用開散列法解決沖突時，每一個散列地址所鏈接的同義詞子表中各個表項的（C）值相同。

A.關(guān)鍵碼B.非關(guān)鍵碼C.散列函數(shù)D.某個域

12.采用線性探查法解決沖突時所產(chǎn)生的一系列后繼散列地址（C）。

A.必須大于原散列地址B.必須小于原散列地址

C.可以大于或小于原散列地址D.不能超過散列表長度的一半

二、填空題

1．每次使兩個相鄰的有序表合并成一個有序表，這種排序方法叫做（二路歸并）排序。

2．堆排序中，對n個記錄建立初始堆需要調(diào)用（n/2）次調(diào)整算法。

3.對n個數(shù)據(jù)對象進(jìn)行堆排序，總的時間復(fù)雜度為（O(nlog2n)）。

4.快速排序在最壞情況下的時間復(fù)雜度為（O(n2)）。

5.給定一組數(shù)據(jù)對象的關(guān)鍵碼為{46，79，56，38，40，84}，對其進(jìn)行一趟快速排序處理，得到的右子表中有（3）個對象。

6.在索引表中，每個索引項至少包含有（關(guān)鍵碼）域和地址域這兩項。

7.在索引表中，若一個索引項對應(yīng)數(shù)據(jù)對象表中的一個表項，則稱此索引為稠密索引，若對應(yīng)數(shù)據(jù)對象表中的若干表項，則稱此索引為（稀疏）索引。

8.若對長度n=10000的線性表進(jìn)行二級索引存儲，每級索引表中的索引項是下一級20個表項的索引，則一級索引表的長度為（500）。

9.在線性表的散列存儲中，裝載因子a又稱為裝載系數(shù)，若用m表示散列表的長度，n表示待散列存儲的元素的個數(shù)，則a等于（n/m）。

10.已知一棵3階B樹中含有50個關(guān)鍵碼，則該樹的最大高度為（5）。

11.在一棵m階B樹上，每個非根結(jié)點(diǎn)的關(guān)鍵碼數(shù)最多為（m-1）個。

三、判斷題（對/錯）

1.如果有向圖中各個頂點(diǎn)的度都大于2，則該圖中必有回路。錯

2.對一個有向圖進(jìn)行拓?fù)渑判?，一定可以將圖的所有頂點(diǎn)按其關(guān)鍵碼大小排列到一個拓?fù)溆行虻男蛄兄小ｅe

3.當(dāng)輸入序列已經(jīng)基本有序時，起泡排序需要比較關(guān)鍵碼的次數(shù)，比快速排序還要少。對

4.堆排序是一種不穩(wěn)定的排序算法。對

5.在用散列表存儲關(guān)鍵碼集合時，可以用雙散列法尋找下一個空位置。在設(shè)計再散列函數(shù)時，要求計算出的值與表的大小m互質(zhì)。對

6.一棵m階B樹中每個結(jié)點(diǎn)最多有m-1個關(guān)鍵碼，最少有ém/2ù-1個關(guān)鍵碼。錯

7.在散列法中采取開散列（鏈地址）法來解決沖突時,其裝載因子的取值一定在(0,1)之間。錯

9.向一棵B樹插入關(guān)鍵碼的過程中，若最終引起樹根結(jié)點(diǎn)的分裂，則新樹與原樹高度查同。對

四、運(yùn)算題

1.已知一個數(shù)據(jù)表為{36,25,25*,62,40,53}，請寫出在進(jìn)行快速排序的過程中每次劃分后數(shù)據(jù)表的變化。

(0)[362525*624053]

(1)[25*25]36[624053]

(2)25*2536[5340]62

(3)25*2536405362

2.已知有一個數(shù)據(jù)表為{30,18,20,15,38,12,44,53,46,18*,26,86}，給出進(jìn)行歸并排序的過程中每一趟排序后的數(shù)據(jù)表變化。

(0)[30182015381244534618*2686]

(1)[1830][1520][1238][4453][18*46][2686]

(2)[15182030][12384453][18*264686]

(3)[1215182030384453][18*264686]

(4)[12151818*2026303844465386]

3.設(shè)散列表的長度m=11，散列函數(shù)為H(K)=Kmodm，采用鏈地址法解決沖突，待依次插入的關(guān)鍵碼序列為{1,13,12,34,38,33,27,22}。根據(jù)構(gòu)成的開散列表回答：

(1)在等概率的情況下，搜索成功時的平均搜索長度；

(2)在等概率的情況下，搜索失敗時的平均搜索長度。

答(1)(1*4+2*3+3)/8=13/8

(2)(3+4+2+1+1+3+1+1+1+1+1)/11=19/11

4.設(shè)有150個表項要存儲到散列表中,要求利用線性探查法解決沖突,同時要求找到所需表項的平均比較次數(shù)不超過2次。試問散列表需要設(shè)計多大？

提示：設(shè)a是散列表的裝載因子，則有

散列表長度m至少為：225

答案說明：

已知要存儲的表項數(shù)為n=150，搜索成功的平均搜索長度為ASLsucc￡2，則有

，解得

又有，則m3225

5

五、算法分析題

1.已知圖的鄰接表中邊結(jié)點(diǎn)類型Edge的結(jié)構(gòu)為(dest,cost,link)，在表頭向量中指向頂點(diǎn)單鏈表的表頭指針為adj，下面算法是在用鄰接表表示的圖中計算所有頂點(diǎn)的出度，并保存在數(shù)組Degree[]中。請按標(biāo)號填補(bǔ)合適內(nèi)容。

template

voidGraph::FindDegree