數(shù)據(jù)結(jié)構(gòu)期末考試題

千里之行，始于足下讓知識帶有溫度。第第2頁/共2頁精品文檔推薦數(shù)據(jù)結(jié)構(gòu)期末考試題

一、推斷題：（共10分，每題1分）

1.挨次表和一維數(shù)組一樣，都可以按下標隨機（或直接）拜訪。（）

2.數(shù)據(jù)的規(guī)律結(jié)構(gòu)是指各數(shù)據(jù)元素之間的規(guī)律關(guān)系，是用戶按照應(yīng)用需要建立的。（）

3.惟獨用面對對象的計算機語言才干描述數(shù)據(jù)結(jié)構(gòu)算法。（）

4.在對雙向循環(huán)鏈表做刪除一個結(jié)點操作時，應(yīng)先將被刪除結(jié)點的前驅(qū)結(jié)點和后繼結(jié)點鏈

接好再執(zhí)行刪除結(jié)點操作。（）

5.遞歸的算法容易、易懂、簡單編寫，而且執(zhí)行效率也高。（）

6.在AOE網(wǎng)絡(luò)中一定惟獨一條關(guān)鍵路徑。（）

7.二叉樹是一棵無序樹。（）

8.在任何狀況下，迅速排序需要舉行關(guān)鍵碼比較的次數(shù)都是O(nlog2n)。（）

9.圖的深度優(yōu)先搜尋是一種典型的回溯搜尋的例子，可以通過遞歸算法求解。（）

10.當從一個最小堆中刪除一個元素時，需要把堆尾元素填補到堆頂位置，然后再按條件把

它逐層向下調(diào)節(jié)，直到調(diào)節(jié)到合適位置為止。（）

二、填空題（20分，每題2分）

1.假定一棵二叉樹的結(jié)點個數(shù)為32，則它的最小深度為______。

2.在一棵二叉樹中，度為2的結(jié)點有5個，度為1的結(jié)點有6個，那么葉子結(jié)點有______

個。

3.一棵深度為5的滿二叉樹的結(jié)點總數(shù)為______個。

4.假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)))，則結(jié)點H的雙親結(jié)點為

______。

5.對于一個具有n個頂點的圖，若采納鄰接矩陣表示，則矩陣大小為______。

6.若要對某二叉排序樹舉行遍歷，保證輸出元素的值序列按增序羅列，應(yīng)對該二叉排

序樹采納____________遍歷法。

7.元素關(guān)鍵字轉(zhuǎn)換為該元素存儲位置的函數(shù)f稱為____________。

8.每次從無序表中取出一個元素，把它插入到有序表中的適當位置，此種排序辦法叫

做____________排序。

9.假定一組數(shù)據(jù)的關(guān)鍵字為{46,79,56,38,40,84}，則利用堆排序辦法建立的初始大

頂堆為__________________。

10.對20個記錄舉行歸并排序時，共需要舉行______趟歸并。

三、挑選題（共20分，每題2分）

1.樹中全部結(jié)點的度數(shù)之和等于結(jié)點總數(shù)加______。

A.0

B.1

C.-1

D.2

2.在一棵樹中，每個結(jié)點最多有______個直接前驅(qū)結(jié)點。

A.0

B.1

C.2

D.隨意多個

3.在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加______。

A.2

B.1

C.0

D.-1

4.頂點個數(shù)為n的無向圖最多有______條邊。

A.n-1

B.n(n-1)/2

C.n(n+1)/2

D.n(n-1)

5.n個頂點的連通圖至少有______條邊。

A.n-1

B.n

C.n+1

D.0

6.在一個無向圖中，全部頂點的度數(shù)之和等于全部邊數(shù)的______倍。

A.3

B.2

C.1

D.1/2

7.對于挨次存儲的有序表(5,12,20,26,37,42,46,50,64)，為查找元素26，若采

用挨次查找，需要比較______次才干查找勝利。

A.3

B.4

C.5

D.6

班

級

：

專

業(yè)

：

姓

密

封

8.設(shè)哈希表長為14，哈希函數(shù)f（k）=k％11，已知表中已有4個元素，關(guān)鍵字分離為15，

38，61，84，存儲位置分離為4，5，6，7，其它存儲位置為空，如用二次探測再散列處理矛盾，關(guān)鍵字為49的存儲位置是______。

A.8

B.3

C.5

D.9

9.在對n個元素舉行容易挑選排序的過程中，需要舉行______趟挑選和交換。

A.n/2

B.n-1

C.n

D.n+1

10.在對n個元素舉行迅速排序的過程中，第一趟排序最多需要交換______對元素。

A.n/2

B.n-1

C.n

D.n+1

四、應(yīng)用題（共30分，每題6分）

1.已知一棵度為k的樹中有n1個度為1的結(jié)點，n2個度為2的結(jié)點，…，nk個度為k

的結(jié)點，問該樹有多少個葉子結(jié)點？（6分）

2.對于下面兩個圖，求出：

（1）無向圖中每個頂點的度，有向圖中每個頂點的入度，出度和度。（2）是否是連通圖/強連通圖，假如不是，畫出連通重量/強連通重量。（6分）

3.分離畫出在線性表(a,b,c,d,e,f,g)中舉行折半查找，以查關(guān)鍵字等于e、f

和g的過程。（6分）

4.已知一組元素的關(guān)鍵字{46,74,16,53,14,26,40,38,86,65,27,34}，利用直接插入

排序法，寫出每次向前面的有序表插入一個元素后的羅列結(jié)果。（6分）

5、將下圖轉(zhuǎn)換為二叉樹，對轉(zhuǎn)換后的二叉樹舉行先序、中序、后序遍歷序列。（6分）

五、程序題（20分）

1.將下面算法填完整。（10分，每空2分）

intSearch_Bin(SSTableST,KeyTypekey){

//在有序表ST中折半查找其關(guān)鍵字等于key的數(shù)據(jù)元素，若找到，則返回該元素//在表中的位置，否則返回0

low=1;high=ST.length;

while(low<=high){

mid=____________;

if(EQ(key,ST.elem[mid].key))return____________;

elseif(LT(key,ST.elem[mid].key))high=____________;

elselow=____________;

}

return____________;

}

2.將下面算法填完整。（10分，每空2分）

voidInsertSort(SqListi<=L.length;++i)

if(LT(L.r[i].key,L.r[i-1].key)){

L.r[0]=____________;

L.r[i]=____________;

for(j=____________;LT(L.r[0].key,L.r[j].key);--j)

L.r[j+1]=____________;

L.r[j+1]=____________;

}

}

班

級：

專業(yè)：姓

信息技術(shù)學(xué)院2022-2022學(xué)年其次學(xué)期期末考試

數(shù)據(jù)結(jié)構(gòu)試卷2（適用班級：）

（答題時光：120分鐘，滿分：100分）

一、推斷題（10分，每題1分）

1.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）

2.算法和程序都應(yīng)具有下面一些特征：有輸入，有輸出，確定性，有窮性，有效性。（）

3.挨次表和一維數(shù)組一樣，都可以按下標隨機（或直接）拜訪。（）

4.鏈式棧與挨次棧相比,一個顯然的優(yōu)點是通常不會浮現(xiàn)棧滿的狀況。（）

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

6.在一棵二叉樹中，假定每個結(jié)點惟獨左子女，沒有右子女，對它分離舉行中序遍歷和后序遍歷，則具有相同的結(jié)果。（）

7.舉行折半搜尋的表必需是挨次存儲的有序表。（）

8.用鄰接矩陣存儲一個圖時，在不考慮壓縮存儲的狀況下，所占用的存儲空間大小只與圖中的頂點個數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。（）9.直接挑選排序是一種穩(wěn)定的排序辦法。（）

10.對于AOE網(wǎng)絡(luò)，加速任一關(guān)鍵活動就能使囫圇工程提前完成。（）

二、填空題（20分，每題2分）

11.假定一棵二叉樹的結(jié)點個數(shù)為32，則它的最大深度為______。

12.在一棵二叉樹中，度為2的結(jié)點有5個，度為1的結(jié)點有6個，那么葉子結(jié)點有______

個。

13.一棵深度為5的滿二叉樹的結(jié)點總數(shù)為______個。

14.假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)))，則結(jié)點H的孩子結(jié)點為

______。

15.對于一個具有n個頂點的圖，若采納鄰接矩陣表示，則矩陣大小為______。16.若要對某二叉排序樹舉行遍歷，保證輸出元素的值序列按增序羅列，應(yīng)對該二叉排

序樹采納____________遍歷法。

17.元素關(guān)鍵字轉(zhuǎn)換為該元素存儲位置的函數(shù)f稱為____________。

18.先將囫圇待排序列分割成若干子序列分離舉行直接插入排序，待囫圇序列“基本有

序”時，再對全體舉行一次直接插入排序，此種排序辦法叫做____________排序。19.假定一組數(shù)據(jù)的關(guān)鍵字為{46,79,56,38,40,84}，則利用堆排序辦法建立的初始小

頂堆為__________________。

20.假定一組數(shù)據(jù)的關(guān)鍵字為{46,79,56,38,40,84}，則以第一個記錄為樞軸，對其進

行第一趟迅速排序的結(jié)果為__________________。

三、挑選題（20分，每題2分）

11.在一棵具有n個結(jié)點的二叉樹中，全部結(jié)點的空子樹個數(shù)等于______。A.nB.n-1C.n+1D.2*n

12.在一棵二叉樹的第5層上，最多具有______個結(jié)點。A.14B.16C.31D.32

13.在一棵深度為h的徹低二叉樹中，所含結(jié)點個數(shù)不少于______。A.2hB.2h+1C.2h-1D.2h-1

14.有向圖的一個頂點的度為該頂點的______。

A.入度

B.出度

C.入度與出度之和

D.(入度＋出度)/215.一個連通圖的生成樹是包含圖中全部頂點的一個______子圖。A.微小B.連通C.微小連通D.無環(huán)

16.具有e條邊無向圖，它的鄰接表中有______個邊結(jié)點。A.e-1B.eC.2(e-1)D.2e

密

封

17.長度為m的哈希表，采納線性探測再散列處理矛盾，假定對一個元素第一次計算的存儲

地址為d，則下一次的存儲地址為______。

A.d

B.d+1

C.(d+1)/m

D.(d+1)%m

18.適于對動態(tài)查找表舉行高效率查找的組織結(jié)構(gòu)是______。

A.有序表

B.挨次表

C.二叉排序樹

D.鏈表

19.在對n個元素舉行容易挑選排序的過程中，需要舉行______趟挑選和交換。

A.n/2

B.n-1

C.n

D.n+1

20.若對n個元素舉行直接插入排序，在舉行i趟(2≤i≤n)排序時，為尋覓插入位置最多

需要舉行______次元素的比較。

A.i+1

B.i-1

C.i

D.1

三、應(yīng)用題（30分，每題6分）

1.寫出下圖所示二叉樹的先序、中序、后序序列。（6分）

先序序列：

中序序列：

后序序列：

2.對于下面兩個圖，求出：（3）無向圖中每個頂點的度，有向圖中每個頂點的入度，出度和度。（4）每個圖的鄰接矩陣。（6分）

3.已知一組關(guān)鍵字{26,38,12,45,73,64,30,56}

1)試依次插入關(guān)鍵字生成一棵二叉排序樹

2)畫出分離刪除38和73后樹的結(jié)構(gòu)（6分）

4.已知一組元素的關(guān)鍵字{46,74,16,53,14,26,40,38,86,65,27,34}，利用起泡排序法，

寫出每趟排序后的羅列結(jié)果。（6分）

5、什么是赫夫曼（Huffman）樹？有一組數(shù)值14、21、32、15、28，畫出赫夫曼樹，并計算其WPL。（6分）四、程序題（20分）

3.將下面算法填完整。（10分，每空2分）

intSearch_Bin(SSTableST,KeyTypekey){