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

1、.數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)試題一一 、簡答問題：1 四類數(shù)據(jù)結(jié)構(gòu)2 線性結(jié)構(gòu)與非線性結(jié)構(gòu)有何差別？3 簡述算法的定義與特性。4 設(shè)有 1000 個(gè)無序元素，僅要求找出前 10 個(gè)最小元素，在下列排序方法中（歸并排序、基數(shù)排序、快速排序、堆排序、插入排序）哪一種方法最好，為什么？二、判斷正誤：（每小題 1 分，共 5 分）正確在（）內(nèi)打，否則打。1 （）二叉排序樹或是一棵空樹，或是具有下列性質(zhì)的二叉樹：若它的左子樹非空，則根結(jié)點(diǎn)的值大于其左孩子的值，若它的右子樹非空，則根結(jié)點(diǎn)的值大于其右孩子的值。2 （）索引順序表的特點(diǎn)是塊內(nèi)可無序，塊間要有序。3 （）子串是主串中任意個(gè)連續(xù)字符組成的序列。4 （）線性結(jié)構(gòu)

2、只能用順序結(jié)構(gòu)存放，非線性結(jié)構(gòu)只能用鏈表存放。5 （）快速排序的樞軸元素可以任意選定。三、單項(xiàng)選擇題： ( 每小題 1 分，共 4 分)1棧 S 最多能容納 4 個(gè)元素?，F(xiàn)有 6 個(gè)元素按 A 、B、C 、D、E、F 的順序進(jìn)棧 , 問下列哪一個(gè)序列是可能的出棧序列 ?A)E 、D、 C、 B、A、FB)B、C、E、F、A、DC)C 、 B、 E、D、A、FD)A 、 D、 F、E、B、C2將一棵有 100 個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點(diǎn)進(jìn)行編號，根結(jié)點(diǎn)編號為 1，則編號為 49 的結(jié)點(diǎn)的左孩子的編號為：A 、 98B、 99C、50D 、483. 對下列關(guān)鍵字序列

3、用快速排序法進(jìn)行排序時(shí)，速度最快的情形是：A） 21、 25、 5、 17、 9、 23、 30B） 25、 23、 30、 17、 21、 5、9B） 21、 9、17、 30、 25、 23、 5D ） 5、 9、 17、 21、 23、 25、 304. 設(shè)森林 F 中有三棵樹，第一、第二和第三棵樹的結(jié)點(diǎn)個(gè)數(shù)分別為M1 、 M2 和 M3 。與森林 F 對應(yīng)的二叉樹根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)個(gè)數(shù)是：A） M1B） M1+M2C） M3D） M2+M3四、填空題： ( 每小題 2 分, 共 20 分)1設(shè)一哈希表表長M 為 100 ，用除留余數(shù)法構(gòu)造哈希函數(shù)，即 H（ K ）=K MOD P

4、（ P<=M ）,為使函數(shù)具有較好性能，P 應(yīng)選2 N 個(gè)結(jié)點(diǎn)的二叉樹采用二叉鏈表存放，共有空鏈域個(gè)數(shù)為3 單鏈表與多重鏈表的區(qū)別是4 在各種查找方法中，平均查找長度與結(jié)點(diǎn)個(gè)數(shù)無關(guān)的是5深度為6（根層次為1）的二叉樹至多有個(gè)結(jié)點(diǎn)。6已知二維數(shù)組A2010 采用行序?yàn)橹鞣绞酱鎯?每個(gè)元素占2 個(gè)存儲單元 ,并且 A105的存儲地址是1000,則 A189 的存儲地址是7在一個(gè)單鏈表中p 所指結(jié)點(diǎn)之后插入s 所指結(jié)點(diǎn)時(shí) ,應(yīng)執(zhí)行s->next=和 p->next=的操作 .8廣義表 (a,b),c,d) 的表頭是,表尾是9循環(huán)單鏈表LA 中，指針P 所指結(jié)點(diǎn)為表尾結(jié)點(diǎn)的條件是10

5、在一個(gè)待排序的序列中，只有很少量元素不在自己最終的正確位置上，但離他們的正確位置都不遠(yuǎn)，則使用排序方法最好。五、構(gòu)造題：（每小題 5 分，共 25 分）1 已知一棵二叉樹，其中序序列DBCAFGE ，后序序列DCBGFEA ，構(gòu)造該二叉樹。2 設(shè)哈希表長度為11，哈希函數(shù)H （ K ）=（ K 的第一字母在字母表中的序號）MOD11 ，若輸入順序?yàn)椋― ，BA ，TN ，M ， CI ，I ， K， X，TA ），處理沖突方法為線性探測再散;.列或鏈地址法，要求構(gòu)造哈希表，并求出等概率情況下查找成功平均查找長度。3 有一組關(guān)鍵字 50，52，85，22，96，17，36，55，請用快速排序，寫

6、出第一趟排序結(jié)果。4 已知葉子結(jié)點(diǎn)值2，3， 5， 6， 9， 11，構(gòu)造哈夫曼樹，計(jì)算其帶權(quán)路徑長度。5 畫出 8 個(gè)結(jié)點(diǎn)的折半判定樹。六、算法設(shè)計(jì)題：（每小題 15 分，共 30 分）（僅要求給出子程序）1編寫算法，判斷帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L 是否對稱。（ 15 分）對稱是指：設(shè)各元素值a1,a2,.,an, 則有 ai=an-i+1，即指： a1= an， a2= an-1。結(jié)點(diǎn)結(jié)構(gòu)為：priordatanext2 二叉排序樹T 用二叉鏈表表示，其中各元素均不相同。（ 1）寫出遞歸算法，按遞減順序打印各元素的值。（10 分）（ 2）寫出完成上述要求的非遞歸算法。（ 5 分）;.數(shù)據(jù)結(jié)構(gòu)

7、試卷參考答案一 、簡答問題：（每小題4 分，共 16 分）1集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、網(wǎng)狀結(jié)構(gòu)2線性結(jié)構(gòu)的前驅(qū)與后繼之間為一對一關(guān)系，非線性結(jié)構(gòu)的前驅(qū)與后繼之間通常為一對多或多對多關(guān)系。3解決特定問題的有限指令序列。有限性、確定性、可行性、有0 個(gè)或多個(gè)輸入數(shù)據(jù)、有1 個(gè)或多個(gè)輸出結(jié)果。4堆排序。因?yàn)橐惶硕雅判蚺哦ㄒ粋€(gè)元素，只需進(jìn)行前10 趟堆排序就可以了。其它排序方法均需進(jìn)行完全排序。二、判斷正誤： （每小題1 分，共 5 分）正確在（）內(nèi)打，否則打。1.（）2.（）3.（）4.（）5.（）三、單項(xiàng)選擇題：(每小題 1 分，共 4 分)1 C)2 A)3. A)4.D)四、填空題：(每小

8、題 2 分 ,共 20 分 )1972.n+13. 鏈域數(shù)目不同4. 哈希查找法5. 26 16. 11687. p->next、s8.(a,b)、(c,d)9. P->next=LA10. 直接插入五、構(gòu)造題：（每小題5 分，共 25 分）12012345678910KTABAMDCIXTNIASL=20/9012345678910;.ASL=15/9336 ，17，22，50，96，85，52，554WPL=11×2+6×2+9×2 +5×3 +2×4+3×4 =87 注：哈夫曼樹的左右子樹可以互換。5;. 注：如果求

9、中點(diǎn)時(shí)采用向上取整，則二叉樹的形態(tài)為左子樹偏長。六、算法設(shè)計(jì)題：（每小題15 分，共 30 分）（僅要求給出子程序）1解答 ：int judge(DLinkList L)p=L->next;q=L->prior;while(p!=q) if(p->data!=q->data) return 0; if(p->next=q) return 1;p=p->next;q=q->prior;return 1; 注：可以不用返回值，而用打印信息。2解答 ：（ 1）void print_1(BiTree T)if(T!=NULL) print_1(T->RC

10、hild); printf( “%c”->data);,T print_1(T->LChild);（ 2）voidPrint_2（BiTree T） InitStack (&S); p=T;while(p!=NULL | ! IsEmpty(S) while (p!=NULL);. Push(&S,p);p=p->RChild;if ( ! IsEmpty(S) ) Pop(&S,&p);printf (“ %cp”,->data );p = p -> LChild;.數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)試題二一、簡答題： （每小題3 分，共 15 分）1

11、. 什么情況下二叉排序樹的查找性能較好？什么情況下二叉排序樹的查找性能最差？2. 比較順序表與單鏈表的優(yōu)缺點(diǎn)。3. 請寫出棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)的類型定義。4. 在起泡排序過程中，有的關(guān)鍵字在某趟排序中可能朝著與最終排序相反的方向移動，試舉例說明之。5. 簡述參數(shù)傳遞的主要方式及其特點(diǎn)。二、判斷正誤： （每小題1 分，共 5 分）正確在（）內(nèi)打，否則打。()（ 1）在拓樸序列中，如果結(jié)點(diǎn)Vi 排在結(jié)點(diǎn)Vj 的前面，則一定存在從Vi 到 Vj 的路徑。()（ 2）在采用線性探測法處理沖突的散列表中，所有同義詞在表中一定相鄰。()（ 3）在一個(gè)小根堆中，具有最大值的元素一定是葉結(jié)點(diǎn)。()（ 4）索引順序

12、表的特點(diǎn)是塊間可無序，但塊內(nèi)一定要有序。()（ 5）哈夫曼樹中沒有度為1 的結(jié)點(diǎn)，所以必為滿二叉樹。三、單項(xiàng)選擇題：(每小題 1 分，共 5 分)1對于只在表的首、尾進(jìn)行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為:A) 順序表B) 用頭指針表示的單循環(huán)鏈表C) 用尾指針表示的單循環(huán)鏈表D) 單鏈表2假設(shè)以第一個(gè)元素為分界元素，對字符序列（Q, H, C, Y, P, A, M, S, R, D, F, X）進(jìn)行快速排序，則第一次劃分的結(jié)果是：A)(A, C, D, F, H, M, P, Q, R, S, X, Y)B)(A, F, H, C, D, P, M, Q, R, S, Y, X)C)(F

13、, H, C, D, P, A, M, Q, R, S, Y, X)D)(P, A, M, F, H, C, D, Q, S, Y, R, X)3下面是三個(gè)關(guān)于有向圖運(yùn)算的敘述：（ 1）求有向圖結(jié)點(diǎn)的拓?fù)湫蛄?，其結(jié)果必定是唯一的（ 2）求兩個(gè)指向結(jié)點(diǎn)間的最短路徑，其結(jié)果必定是唯一的（ 3）求 AOE 網(wǎng)的關(guān)鍵路徑，其結(jié)果必定是唯一的其中哪個(gè)（些）是正確的？A) 只有（ 1）B) （ 1）和（ 2）C)都正確D) 都不正確4若進(jìn)棧序列為a, b, c，則通過入出棧操作可能得到的a, b, c 的不同排列個(gè)數(shù)為 :A) 4B) 5C) 6D) 75. 以下關(guān)于廣義表的敘述中 ,正確的是：A) 廣義

14、表是由 0 個(gè)或多個(gè)單元素或子表構(gòu)成的有限序列B) 廣義表至少有一個(gè)元素是子表C) 廣義表不能遞歸定義D) 廣義表不能為空表四、填空題： (每小題 2 分 ,共 20 分 )1 一棵含有 101 個(gè)結(jié)點(diǎn)的完全二叉樹存儲在數(shù)組A1.101 中 ,對 1k101, 若 Ak 是非葉結(jié)點(diǎn) , 則 k 的最小值是 :， k 的最大值是 :。2. 設(shè) s=YOU ARE JUDGING IT RIGHT OR WRONG，順序執(zhí)行下列操作：SubString(sub1,s,1,8);SubString(sub2,s,20,5); StrCat(sub1,sub2); 則最后 sub1 的值為：。3. 若

15、一個(gè)算法中的語句頻度之和為T(n) = 3720n+4nlogn ，則算法的時(shí)間復(fù)雜度為_ 。4廣義表 (a),b),c),d) 的表頭是，表尾是。5 已知有向圖的鄰接矩陣，要計(jì)算i 號結(jié)點(diǎn)的入度，計(jì)算方法是：將累加。6要在一個(gè)單鏈表中p 所指結(jié)點(diǎn)之后插入一個(gè)子鏈表，子鏈表第一個(gè)結(jié)點(diǎn)的地址為s，子鏈表最后一個(gè)結(jié)點(diǎn)的地址為t, 則應(yīng)執(zhí)行操作：;.和。7. 用 帶 頭 結(jié) 點(diǎn) 的 循 環(huán) 鏈 表 表 示 的 隊(duì) 列 , 若 只 設(shè) 尾 指 針 rear, 則 隊(duì) 空 的 條 件是。8已知二維數(shù)組 A1020 采用行序?yàn)橹鞣绞酱鎯?，每個(gè)元素占2 個(gè)存儲單元 ,并且 A00的存儲地址是 1024, 則

16、 A618 的地址是9在表示二叉樹的二叉鏈表中,共有個(gè)空鏈域。10 n 個(gè) 頂 點(diǎn) 的 連 通 無 向 圖 至 少 有條邊，至多有條邊。五、構(gòu)造題： （每小題 6 分，共 30 分）1已知二叉樹的中序序列為DBGEAFC ，后序序列為DGEBFCA ，給出對應(yīng)的二叉樹。2已知一個(gè)圖的頂點(diǎn)為 A 、B、 C、 D，其鄰接矩陣的上三角元素全為0（包括主對角線元素），其他元素均為 1。請畫出該圖，并給出其鄰接表。3給定權(quán)值 8， 12， 4， 5， 26， 16， 9，構(gòu)造一棵帶權(quán)路徑長度最短的二叉樹，并計(jì)算其帶權(quán)路徑長度。4圖 2 表示一個(gè)地區(qū)的通訊網(wǎng)，邊表示城市間的通訊線路，邊上的權(quán)值表示架設(shè)線

17、路花費(fèi)的代價(jià)，請找出能連通每個(gè)城市、且總代價(jià)最省的n-1條線路。圖 25對關(guān)鍵字序列 (72， 87， 61， 23， 94， 16， 05， 58) 進(jìn)行堆排序，使之按關(guān)鍵字遞減次序排列。請寫出排序過程中得到的初始堆和一趟排序后的序列狀態(tài)。六、算法設(shè)計(jì)題： （共 25 分）1 設(shè)有一個(gè)由正整數(shù)組成的單鏈表L（含頭結(jié)點(diǎn)） ，編寫完成下列功能的算法：找出最小值結(jié)點(diǎn) P， 若最小值是奇數(shù)，則刪除結(jié)點(diǎn)P。 15 分 2 已知樹用孩子兄弟鏈表存儲，root 指向根結(jié)點(diǎn)。編寫算法，逐層遍歷這棵樹。10 分 ;.數(shù)據(jù)結(jié)構(gòu)試卷參考答案一、簡答題： （每小題3 分，共 15 分）1. 前驅(qū)與后繼之間通常為一對

18、多或多對多的關(guān)系。2. 順序表優(yōu)點(diǎn)：隨機(jī)查找，存儲密度大順序表缺點(diǎn)：插入、刪除不便，靜態(tài)分配，表長固定單鏈表優(yōu)點(diǎn)：插入、刪除方便，動態(tài)分配，表長靈活單鏈表缺點(diǎn)：查找不便，存儲密度小3. 關(guān)鍵字相同的兩個(gè)記錄，排序前后其先后順序不變。4. typedef struct node ElemType data; struct node * next; *LinkStack;5. 當(dāng)二叉排序樹接近平衡二叉樹或完全二叉樹時(shí)查找性能較好， 當(dāng)二叉排序樹為單邊單枝二叉樹時(shí)查找性能最差。二、判斷正誤： （每小題1 分，共5 分）正確在（）內(nèi)打，否則打。( )（1） ()（2） ()（3） ()（4） ()（

19、5）三、單項(xiàng)選擇題： (每小題 1 分，共 5分 )1 C)2 C)3 D)4 B)5. A)四、填空題： (每小題 2分,共 20 分)112. YOU ARE RIGHT3. O(nlogn)4(a),b),c) ，(d)5i 列元素6 t->next=p->next，p->next=s7.rear->next=rear8 13009 n+110n-1五、構(gòu)造題：（每小題6 分，共 30 分）12;.3或：WPL=8×3+4×4+5×4+16×2+9×3+12×3+26×2 =207注：哈夫曼樹的

20、左右子樹可以互換。4解 1：;.解 2：注：邊上的權(quán)值可以省略。5初始堆：05，23，16，58，94，72，61，87一趟排序后的序列狀態(tài)：87，23，16，58，94，72，61，05篩成堆后為：16，23，61，58，94，72，87，05;.注：如果采用大根堆，應(yīng)適當(dāng)減分。六、算法設(shè)計(jì)題： （共 25 分）315 分void min(LinkList L)if(L->next=NULL) return;q=L;r=L->next;m=r->data;while(r->next!=NULL) if(r->next->data<m) m= r-&g

21、t;next->data;q=r; r=r->next;p=q->next;if(m%2=1) q->next=p->next;free(p); 410 分void layer(CSTree root)InitQueue(&Q); EnterQueue(&Q, root);while(!Empty(Q) DelQueue(&Q, &p);visit(p);p=p->FirstChild;while(p!=NULL) EnterQueue(&Q, p);p=p->NextSibling; ;.數(shù)據(jù)結(jié)構(gòu)輔導(dǎo)試題三一、

22、簡答題（ 15 分，每小題 3 分）1. 簡要說明算法與程序的區(qū)別。2. 在哈希表中，發(fā)生沖突的可能性與哪些因素有關(guān)？為什么？3. 說明在圖的遍歷中，設(shè)置訪問標(biāo)志數(shù)組的作用。4. 說明以下三個(gè)概念的關(guān)系：頭指針，頭結(jié)點(diǎn)，首元素結(jié)點(diǎn)。5. 在一般的順序隊(duì)列中，什么是假溢出？怎樣解決假溢出問題？二、判斷題（ 10 分，每小題 1 分）正確在括號內(nèi)打，錯(cuò)誤打×()（ 1）廣義表 ( a ), b), c ) 的表頭是 ( a ), b)，表尾是 ( c )。()（ 2）在哈夫曼樹中，權(quán)值最小的結(jié)點(diǎn)離根結(jié)點(diǎn)最近。()（ 3）基數(shù)排序是高位優(yōu)先排序法。()（ 4）在平衡二叉樹中，任意結(jié)點(diǎn)左右子

23、樹的高度差（絕對值）不超過1。()（ 5）在單鏈表中，給定任一結(jié)點(diǎn)的地址p，則可用下述語句將新結(jié)點(diǎn)s插入結(jié)點(diǎn) p 的后面 ：p->next = s; s->next = p->next;()（ 6）抽象數(shù)據(jù)類型（ ADT ）包括定義和實(shí)現(xiàn)兩方面，其中定義是獨(dú)立于實(shí)現(xiàn)的，定義僅給出一個(gè) ADT 的邏輯特性，不必考慮如何在計(jì)算機(jī)中實(shí)現(xiàn)。( )（ 7）數(shù)組元素的下標(biāo)值越大，存取時(shí)間越長。( )（ 8）用鄰接矩陣法存儲一個(gè)圖時(shí)，在不考慮壓縮存儲的情況下，所占用的存儲空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。()（ 9）拓?fù)渑判蚴前?AOE 網(wǎng)中每個(gè)結(jié)點(diǎn)事件的最早發(fā)生時(shí)間對結(jié)點(diǎn)進(jìn)

24、行排序。()（ 10）長度為 1 的串等價(jià)于一個(gè)字符型常量。三、單項(xiàng)選擇題（ 10 分 , 每小題 1 分）1排序時(shí)掃描待排序記錄序列，順次比較相鄰的兩個(gè)元素的大小，逆序時(shí)就交換位置。這是哪種排序方法的基本思想？A、堆排序B、直接插入排序C、快速排序D、冒泡排序2 已知一個(gè)有向圖的鄰接矩陣表示，要刪除所有從第i 個(gè)結(jié)點(diǎn)發(fā)出的邊， 應(yīng)該：A）將鄰接矩陣的第i 行刪除B）將鄰接矩陣的第i 行元素全部置為0C）將鄰接矩陣的第i 列刪除D）將鄰接矩陣的第i 列元素全部置為03有一個(gè)含頭結(jié)點(diǎn)的雙向循環(huán)鏈表，頭指針為head,則其為空的條件是：A.head->priro=NULLB.head->

25、;next=NULLC.head->next=headD.head->next-> priro=NULL4. 在順序表( 3, 6, 8, 10, 12, 15, 16, 18, 21, 25, 30 ) 中，用折半法查找關(guān)鍵碼值11，所需的關(guān)鍵碼比較次數(shù)為：A) 2B) 3C) 4D) 55. 以下哪一個(gè)不是隊(duì)列的基本運(yùn)算？A）從隊(duì)尾插入一個(gè)新元素B）從隊(duì)列中刪除第i 個(gè)元素C）判斷一個(gè)隊(duì)列是否為空D）讀取隊(duì)頭元素的值6. 在長度為 n 的順序表的第 i 個(gè)位置上插入一個(gè)元素（ 1 i ）n+1，元素的移動次數(shù)為：A)n i + 1B)n iC)iD)i 1;.7對于只在表

26、的首、尾兩端進(jìn)行插入操作的線性表，宜采用的存儲結(jié)構(gòu)為:A) 順序表B) 用頭指針表示的循環(huán)單鏈表C) 用尾指針表示的循環(huán)單鏈表D) 單鏈表8對包含 n 個(gè)元素的哈希表進(jìn)行查找，平均查找長度為：A) O(log2n)B) O(n)C) O(nlog2 n)D) 不直接依賴于 n9將一棵有 100 個(gè)結(jié)點(diǎn)的完全二叉樹從根這一層開始，每一層從左到右依次對結(jié)點(diǎn)進(jìn)行編號，根結(jié)點(diǎn)編號為1，則編號最大的非葉結(jié)點(diǎn)的編號為：A、 48B、49C、50D、5110某二叉樹結(jié)點(diǎn)的中序序列為A、B、C、 D、E 、F、G，后序序列為 B、 D、C、 A、F、G、E，則其左子樹中結(jié)點(diǎn)數(shù)目為：A）3B）2C）4D）5四、

27、填空題（ 10 分，每空 1 分）1填空完成下面一趟快速排序算法：intQKPass ( RecordType r ,intlow， inthigh)x = r low ；while ( low < high )while ( low < high && r . key >= x.key )high - -；if ( low < high ) r = r high ；low+; while ( low < high && r . key < x. key )low+;if ( low < high ) r = r low

28、 ；high-; r low = x；returnlow ;2. 假設(shè)用循環(huán)單鏈表實(shí)現(xiàn)隊(duì)列，若隊(duì)列非空，且隊(duì)尾指針為R, 則將新結(jié)點(diǎn)S加入隊(duì)列時(shí)，需執(zhí)行下面語句：；R=S；3通常是以算法執(zhí)行所耗費(fèi)的和所占用的來判斷一個(gè)算法的優(yōu)劣。4已知一個(gè) 3 行、4 列的二維數(shù)組 A（各維下標(biāo)均從1 開始），如果按“以列為主”的順序存儲，則排在第8 個(gè)位置的元素是：5高度為 h 的完全二叉樹最少有個(gè)結(jié)點(diǎn)。五、構(gòu)造題（ 20 分）1（4 分）已知數(shù)據(jù)結(jié)構(gòu)DS 的定義如下，請給出其邏輯結(jié)構(gòu)圖示。;.DS = (D, R)D = a, b, c, d, e, f, g R=TT = <a, b>, &

29、lt;a, g>, <b, g>, <c, b>, <d, c>, <d, f>, <e, d>, <f, a>, <f, e>, <g, c>, <g, d>, <g, f> 2（ 6 分）對以下關(guān)鍵字序列建立哈希表： （SUN, MON, TUE, WED, THU, FRI, SAT）,哈希函數(shù)為 H(K) = （ K 中最后一個(gè)字母在字母表中的序號） MOD 7 。用線性探測法處理沖突， 要求構(gòu)造一個(gè)裝填因子為 0.7 的哈希表，并計(jì)算出在等概率情況下查找成功的

30、平均查找長度。3.（ 6 分）將關(guān)鍵字序列（ 3，26，12， 61，38，40， 97，75， 53， 87）調(diào)整為大根堆。4（4 分）已知權(quán)值集合為： 5，7，2，3，6，9 ，要求給出哈夫曼樹，并計(jì)算其帶權(quán)路徑長度 WPL 。六、算法分析題（ 10 分）閱讀下面程序，并回答有關(guān)問題。其中 BSTree 為用二叉鏈表表示的二叉排序樹類型。（1） 簡要說明程序功能。（5 分）（2） n 個(gè)結(jié)點(diǎn)的滿二叉樹的深度h 是多少？（ 3 分）（3） 假設(shè)二叉排序樹 *bst 是有 n 個(gè)結(jié)點(diǎn)的滿二叉樹 ,給出算法的時(shí)間復(fù)雜度。（2 分）intProc (BSTree*bst,KeyTypeK) BST

31、ree f, q, s; s=(BSTree)malloc(sizeof(BSTNode);s-> key = K;s-> lchild = NULL;s-> rchild = NULL;if ( *bst = NULL ) *bst = s;return1; f = NULL;q = *bst;while( q != NULL ) if ( K < q -> key )f = q;q = q -> lchild;elsef = q;q = q -> rchild;if ( K < f -> key )f -> lchild = s;elsef -> rchild = s;return1;七、算法設(shè)計(jì)題（ 25 分）1 已知一個(gè)帶頭結(jié)點(diǎn)的整數(shù)