《數(shù)據(jù)庫結(jié)構(gòu)提高》試題及答案

《數(shù)據(jù)結(jié)構(gòu)提高》

目錄

《數(shù)據(jù)結(jié)構(gòu)提高》試卷考查復(fù)習(xí)題....................1

一、單項選擇題（抽考10小題，每小題2分，共20分）..............1

二、判斷題（共10小題，每小題1分，共10分）....................4

三、填空題（每小題1分，共12分）...............................4

四、簡答題（共2小題，每小題5分，共10分。）....................5

五、畫圖題（抽考2小題，每小題6分，共12分。）..................6

六、計算題（共3小題，每小題12分，共36分。）...................7

七、算法設(shè)計題（抽考1題，共12分。）............................9

《數(shù)據(jù)結(jié)構(gòu)提高》試卷考查復(fù)習(xí)題

一、單項選擇題(抽考10小題，每小題2分，共20分)

i.設(shè)按照從上到下、從左到右的順序從i開始對完全二叉樹進行順序編號，則編號為i結(jié)點

的右孩子結(jié)點的編號為(C)。左孩子節(jié)點編號為2i

A2i+1B2iCi/2D2i-1

2.下面程序段的時間復(fù)雜度是(C)o

for(i=0；i<n；i++)

for(j=0；j<n；j++)

A[i][j]=0；

3/2

A0(n)BO(nlog2n)C0(n2)DO(n)

3.設(shè)帶有頭結(jié)點的單向循環(huán)鏈表的頭指針變量為head,則其判空條件是(C)o

Ahead==nullBhead->next==null

Chead->next=headDhead!=null

4.設(shè)某棵二叉樹的高度為8,則該二叉樹上葉子結(jié)點最多有(B)。2A(8-1)

A64B128C512D1024

5.設(shè)指針變量top指向當(dāng)前鏈?zhǔn)綏５臈ｍ?，則刪除棧頂元素的操作為_D_。

**********注意：是鏈?zhǔn)綏＿xD,順序棧選B**********

Atop=top+1;Btop=top-1;

Ctop->next=top;Dtop=top->next;

6.以下數(shù)據(jù)結(jié)構(gòu)中哪一個是線性結(jié)構(gòu)？_B_

A樹B棧C圖D二叉樹

7.設(shè)輸入序列是1、2、3、……、n,經(jīng)過棧的作用后輸出序列的第一個元素是n,則輸出序

列中第i個輸出元素是_C_。

第1頁

An-iBn-l-iCn+l-iD不能確定

8.一個棧的進棧序列是a,b,c,d,e,則棧的不可能的輸出序列是_D_。

AedcbaB.decbaC.abcdeD.dceab

9.線性表是具有n個_B_的有限序列。

A.字符B.數(shù)據(jù)元素C.數(shù)據(jù)項D.表元素

10.一個非空廣義表的表尾_D_。

*****非空廣義表，除表頭外,其余元素構(gòu)成的表稱為表尾，所以非空廣義表尾一定是個表*****

A.不可能是子表B.只能是原子C.可以是子表或原子D.只能是子表

11.數(shù)據(jù)的最小單位是_D_。

A.數(shù)據(jù)元素B.記錄C.數(shù)據(jù)對象D.數(shù)據(jù)項

12.對于一個具有n個結(jié)點和e條邊的無向圖，若采用鄰接表表示，所有邊鏈表中邊結(jié)點的

總數(shù)為_C_。

A.e/2B.eC.2eD.n+e

13.數(shù)組a[1..6,1..5]（無0行0歹U）以列序為主序順序存儲，的地址為1000,每

個元素占2個存儲單元，則a[3][4]的地址是_A_。

A.1026B.1040C.1042D.1046

14.某線性表常發(fā)生的操作為刪除第一個數(shù)據(jù)元素和在最后一個元素后添加新元素，采用

_D_的存儲結(jié)構(gòu)，能使其存儲效率和時間效率最高。

A.單鏈表B.僅用頭指針的循環(huán)鏈表

C.雙向循環(huán)鏈表D.僅用尾指針的循環(huán)鏈表

15.在一個單鏈表中，已知q所指向的結(jié)點是p指向的結(jié)點的直接前驅(qū)結(jié)點，若在q所指向的

結(jié)點和P指向的結(jié)點間插入s所指向的結(jié)點，則執(zhí)行_C_。

A.s->next=p->next;p->next=s;

B.p->next=s->next;s->next=p;

C.q->next=s;s->next=p;

D.p->next=s;s->next=q;

第2頁

16.若循環(huán)隊列使用C數(shù)組A[m]存放其數(shù)據(jù)元素，已知頭指針front指向隊首元素，尾指針

rear指向尾元素后的空單元，則當(dāng)前隊列中的元素個數(shù)為_A_。

A.(rear-front+m)%mB.rear-front+1

C.rear-frontD.rear-front-1

17.棧和隊列的共同點是_C_。

A.先進先出B.后進先出

C.只允許在端點處插入和刪除元素D.運算受限的線性表

18.一棵深度為5的完全二叉樹，葉結(jié)點數(shù)最大值和最小值分別為_B_。

A.10,5B.16,8C.8,4D.32,16

19.折半查找有序表(5,15,25,35,40,65,70,75,80,85,88,90),若查找元素75,需依次與表中

元素_A_進行比較。

A.65,80,70,75B.65,85,75C.65,80,75D.70,85,75

20.算法suanfa的時間復(fù)雜度為_A_。

intsuanfa(intn)

{inti=l；

while(pow(2,i)<=n)/*pow(2,i)表示2i*/

i=i+l；

returni；

)

A.0(logn)B.0()C.0(n2)D.O(n)

第3頁

二、判斷題（共10小題，每小題1分，共10分）

1.中序遍歷一棵二叉排序樹得到的結(jié)點序列一定是有序的序列。（X）

2.由樹轉(zhuǎn)化成二叉樹，該二叉樹的右子樹不一定為空。（X）

3.線性表中的所有元素都有一個前驅(qū)元素和后繼元素。（X）

4.順序存儲方式只能用于存儲線性結(jié)構(gòu)。（X）

5.棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是一種后進先出型結(jié)構(gòu)。（J）

6.隊是一種插入與刪除操作分別在表的兩端進行的線性表，是一種先進后出型結(jié)構(gòu)。（X）

7.在Huffman樹中只有度為2和度為0的節(jié)點。（V）

8.在n個節(jié)點的二叉鏈表中有n+1個空的指針域。（V）

9.最小代價生成樹的形狀不唯一，但各邊權(quán)值之和必相等。（義）

10.算法的時間復(fù)雜度與計算機硬件有關(guān)。（X）

三、填空題（每小題1分，共12分）

1.線性結(jié)構(gòu)中元素之間存在一對一關(guān)系,樹形結(jié)構(gòu)中元素之間存在一對多關(guān)系,圖

形結(jié)構(gòu)中元素之間存在多對多關(guān)系。

2.評價算法的優(yōu)劣通常主要考慮算法的時間復(fù)雜度和空間復(fù)雜度這兩方面。

3.若對一個線性表經(jīng)常進行查找操作，而很少進行插入和刪除操作時，則采用順序存儲

結(jié)構(gòu)為宜，相反，若經(jīng)常進行的是插入和刪除操作時，則采用」存儲結(jié)構(gòu)為宜。

5.對于棧只能在棧頂位置插入和刪除元素。

6.設(shè)sl='Good',s3='Luck!',!）1iJsi和s2連接的結(jié)果是GoodLuck。

7,完全二叉樹中第4層上最少有8個結(jié)點,最多有15個結(jié)點。【最少2A（n-1）和最多2徇-1】

8.順序查找、折半查找、分塊查找都屬于靜態(tài)查找。

第4頁

四、簡答題（共2小題，每小題5分，共10分。）

1.已知一棵完全二叉樹的第6層（設(shè)根為第1層）有8個葉結(jié)點，則該完全二叉樹的結(jié)點個數(shù)最

多和最少分別是多少？

答：分析圖如右側(cè)圖所示

完全二叉樹的結(jié)點個數(shù)最多有（27-1）-（2*8）=127-16=111個

完全二叉樹的結(jié)點個數(shù)最少有（25-1）+8=31+8=39個

完全二叉樹分析圖

第1^((27)1)

第2層((2^2)-1)

第3層（（2人3）-1）

第4層((2A4)-1)

第5層（（2人5）-1）I22||23||24JI30||

第6層（（2人6）-1）

I第7層《”川I匚第7層的8個父結(jié)點無葉子樹，減去2*8

第(1層((2An)-l)

2.設(shè)文件R共有1500條記錄，磁盤的讀、寫單位為250條記錄，內(nèi)存可提供750條記錄的空

間，試簡要說明對文件R的排序過程。

答：

第一步，每次將三個記錄塊即750個記錄有外存讀到內(nèi)存，進行內(nèi)部排序，整個文件被分成2個

有序子序列，然后分別把它們寫到外存上去。

第二步，兩兩歸并有序子文件，進行了一趟，最終成為了一個有序文件。

第5頁

五、畫圖題（抽考2小題，每小題6分，共12分。）

I.從頂點D出發(fā)，用Prim算法求網(wǎng)N的一棵最小生成樹并計算各邊權(quán)值之和。

答：最小生成樹如圖所示

o?Q?a?

????fe0GJ?

?05O050

最小生成樹的結(jié)果圖為：G]。一左。

/54

]D[iFi

網(wǎng)N的最小生成樹各邊權(quán)值之和為：

DC+CA+AB+CG+GE+EF=5+1+3+5+6+4=24

2.已知一棵二叉樹的中序序列和后序序列分別為BCDEAFHG和DECBHGFA,畫出這棵二叉樹。

答：二叉樹如圖所示

第6頁

3.對給定的關(guān)鍵字序列（52,48,67,92,23,7,12）請采用簡單選擇排序法將其排列成遞

增的序列，寫出排序過程示意圖。（6分）

答：排序過程示意圖

步驟線性表

初始52,48,67,92,23,7,12

17,48,|67,92,23,52,12

27,12,67,|92,23,52,48

37,12,23,92,|67,52,48

47,12,23,48,67,|52,92

57,12,23,48,52,67,|92

67,12,23,48,52,67,921

........

六、計算題（共3小題，每小題12分，共36分。）

1.設(shè)對18個記錄的表作折半查找，（1）畫出折半查找過程的判定樹；（2）假定每個元素的查找概

率相等，試計算查找成功時的平均查找長度。

ASL成功=(1*1+2*2+4*34-8*4+3*5)718=64/18=32/9

2.給定一組權(quán)值{12,4,5,6,1,2},試設(shè)計相應(yīng)的哈夫曼樹，并求其帶權(quán)路徑長度WPL。

答：哈弗曼樹如圖所示。

第7頁

帶權(quán)路徑長度為：WPL=4*(1+2)+3*(4+5+6)+1*12=69

3.試用關(guān)鍵字序列(39,25,24,50,12,14,20,19,37,6),構(gòu)造哈希(Hash)表，設(shè)哈希函數(shù)

為:H(key)=key%13,其中key為關(guān)鍵字,％為求余運算符；用開放定址法處理沖突，用線性探測

再散列法查找空位,用數(shù)組A[15]表示哈希表。(1)畫出該哈希表的存儲結(jié)構(gòu)圖；(2)假定每個元

素的查找概率相等，計算查找成功及查找失敗時的平均查找長度。

答：線性探測法如下圖所示。

等概率情況下查找成功的平均查找長度為：

ASL成功=(1+1+1+1+3+2+1+1+6+4)/10=21/10

等概率情況下查找失敗的平均查找長度為：

ASL不成行(5+4+3+2+1+1+5+4+3+2)/10=30/10

第8頁

七、算法設(shè)計題（抽考1題，共12分。）

題1.設(shè)a口的初值為（119,527,9,768,22,549）,a[0]為臨時工作單元。分析如下程序段:

?for(i=0,d=l;i<3;i++,d*=10)

?(

?for(j=0;j<10;j++)count[j]=0;

?for(j=0;j<6;j++)count[afj]/d%10]+