《數(shù)據(jù)結(jié)構(gòu)（本）》期末綜合練習(xí)（綜合題）測(cè)驗(yàn)答案解析

國家開放大學(xué)最新《數(shù)據(jù)結(jié)構(gòu)(本)》期末綜合練

習(xí)(綜合題)測(cè)驗(yàn)答案解析

試題1

滿分1.00

口標(biāo)記試題

試題正文

有一個(gè)長度為11的有序表(I，2,11,15,24,28,30,56,69,70,80),

元素的下標(biāo)依次為：1，2,3,……，11,按折半查找對(duì)該表進(jìn)行查找。

(1)畫出對(duì)上述查找表進(jìn)行折半查找所對(duì)應(yīng)的判定樹。

(2)說出成功查找到元素56,需要依次經(jīng)過與哪些元素的比較？

(3)說出不成功查找元素72,需要進(jìn)行元素比較的次數(shù)？

反饋

試題2

滿分i.oo

舊標(biāo)記試題

試題正文

（1）以3,4,5,8,9,作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹。

（2）給出相應(yīng)權(quán)重值葉結(jié)點(diǎn)的哈夫曼編碼。

(2)n個(gè)葉結(jié)點(diǎn)的哈夫曼樹，總共有多少個(gè)結(jié)點(diǎn)？

反饋

試題3

滿分i.oo

口標(biāo)記試題

試題正文

(1)一組記錄的關(guān)鍵字序列為(57,90,67,50,51,56),利用堆排序(堆

頂元素是最小元素)的方法建立初始堆(要求以完全二叉樹描述)。

(2)對(duì)關(guān)鍵字序列(56,51,71,54,46,106)利用快速排序，以第一個(gè)關(guān)

鍵字為分割元素，給出經(jīng)過一次劃分后結(jié)果。

(3)一組記錄的關(guān)鍵字序列為(60,47,80,57,39,41,46,30),利用歸

并排序的方法，分別給出(1,1)歸并、(2,2)歸并、(4,4)歸并的結(jié)果

序列。

反饋

(2)46,51,54,56,71,106

(3)

(47,60)(57,80)(39,41)(30,46)

(47,57,60,80)(30,39,41,46)

(30,39,41,46,47,57,60,80)

試題4

滿分1.00

口標(biāo)記試題

試題正文

(1)設(shè)有數(shù)據(jù)集合{40,29,7,73,101,4,55,2,81,92,39},依次取集

合中各數(shù)據(jù)構(gòu)造一棵二叉排序樹。

(2)在上述二叉排序樹上進(jìn)行查找，給出成功查找到元素92的查找路徑，其

中共經(jīng)過了多少次元素間的的比較。

(3)有一個(gè)長度為10的有序表，按折半查找對(duì)該表進(jìn)行查找，給出在等概率

情況下查找成功的平均比較次數(shù)為。

反饋

試題5

滿分1.00

臼標(biāo)記試題

試題正文

(1)以2,3,4,7,8,9作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹。

(2)給出相應(yīng)權(quán)重值葉結(jié)點(diǎn)的哈夫曼編碼。

(3)一組記錄的關(guān)鍵字序列為(47,80,57,39,41,46),利用堆排序的方

法建立的初始堆(堆頂元素是最小元素，以樹的形式給出)。

反饋

試題6

滿分i.oo

臼標(biāo)記試題

試題正文

(1)一組記錄的關(guān)鍵字序列為(36,69,46,28,30,35),給出利用堆排序

(堆頂元素是最小元素)的方法建立的初始堆(要求以完全二叉樹描述)。

(2)對(duì)關(guān)鍵字序列(36,69,46,28,30,74)采用快速排序，給出以第一個(gè)

關(guān)鍵字為分割元素，經(jīng)過一次劃分后的結(jié)果。

（3）設(shè)有數(shù)據(jù)集合{30,73,101,4,8,9,2,81},依次取集合中各數(shù)據(jù)構(gòu)

造一棵二叉排序樹。

反饋

試題7

滿分1.00

口標(biāo)記試題

試題正文

（1）已知某二叉樹的后序遍歷序列是debca,中序遍歷序列是dbeac,試畫出

該二叉樹。

（2）若上述二叉樹的各個(gè)結(jié)點(diǎn)的字符分別代表不同的整數(shù)（其中沒有相等

的），并恰好使該樹成為一棵二叉排序樹，試給出a、b、c、d、e的大小關(guān)

（3）給出該樹的前序遍歷序列。

(2)d<b<e<a<c

(3)abdec

試題8

滿分i.oo

口標(biāo)記試題

試題正文

（1）一組記錄的關(guān)鍵字序列為｛45,40,65,43,35,95｝,寫出利用快速排序

的方法，以第一個(gè)記錄為基準(zhǔn)得到的一趟劃分的結(jié)果（要求給出一趟劃分中每

次掃描和交換的結(jié)果）。

（2）對(duì)序列｛45,40,65,43,35,95｝利用直接插入排序，寫出逐次插入過程

（從第一個(gè)元素一直到第六個(gè)元素）。

反饋

(1)

(2)

404565433595

404345653595

354043456595

試題9

滿分1.00

臼標(biāo)記試題

試題正文

（1）設(shè)headi和pi分別是不帶頭結(jié)點(diǎn)的單向鏈表A的頭指針和尾指針，head2

和P2分別是不帶頭結(jié)點(diǎn)的單向鏈表B的頭指針和尾指針，若要把B鏈表接到A

鏈表之后，得到一個(gè)以headi為頭指針的單向循環(huán)鏈表，寫出其中兩個(gè)關(guān)鍵的

賦值語句（不用完整程序，結(jié)點(diǎn)的鏈域?yàn)閚ext）。

（2）單向鏈表的鏈域?yàn)閚ext,設(shè)指針p指向單向鏈表中的某個(gè)結(jié)點(diǎn)，指針s

指向一個(gè)要插入鏈表的新結(jié)點(diǎn)，現(xiàn)要把s所指結(jié)點(diǎn)插入p所指結(jié)點(diǎn)之后，某學(xué)

生采用以下語句：

p->next=s;s->next=p->next;

這樣做正確嗎？若正確則回答正確，若不正確則說明應(yīng)如何改寫。

反饋

(1)pi->next=head2；p2->next=headi；

(2)不對(duì)，s->next=p->next；p->next二s；

試題10

滿分1.00

日標(biāo)記試題

試題正文

（1）設(shè)根為第1層，對(duì)給定權(quán)值1，3,4,4,5,6,構(gòu)造深度為5的哈夫曼

樹。

提示：構(gòu)造中當(dāng)出現(xiàn)被選的結(jié)點(diǎn)值有多個(gè)相等時(shí)，可嘗試不同組合，以得到要

求的樹的深度。

（2）求樹的帶權(quán)路徑長度。

（3）用鏈接法存儲(chǔ)上述哈夫曼樹，結(jié)點(diǎn)中共有多少個(gè)指針域?yàn)榭眨f明理由？

（4）給出對(duì)上述哈夫曼樹中序遍歷得到的的序列。

（5）一棵哈夫曼樹有n個(gè)非葉結(jié)點(diǎn)，構(gòu)造該樹共有多少個(gè)權(quán)重值？簡述理由？

反饋

(1)

(2)WPL=1*4+3*4+4*3+6*2+4*2+5*2=58

（3）有12個(gè)空指針域，因?yàn)楣?1個(gè)結(jié)點(diǎn)