一、填空（每空一分，共14分）

1.數(shù)據(jù)元素是數(shù)據(jù)結(jié)構(gòu)的基本單位，數(shù)據(jù)項(xiàng)是數(shù)據(jù)的不可分割的最小單位。
2.深度是k的完全二叉樹至少有2^（k－1）個(gè)結(jié)點(diǎn)，至多有2^k-1個(gè)結(jié)點(diǎn)。
3.哈希表的查找效率主要取決于造表時(shí)選取的哈希函數(shù)和處理沖突的方法。
4.對(duì)100個(gè)記錄進(jìn)行折半查找，最多比較7次，最少比較1次。
5.有n個(gè)頂點(diǎn)的無向圖，最少有0條邊，最多有n(n-1)/2條邊。
6.AOE網(wǎng)中，從源點(diǎn)到匯點(diǎn)的最長(zhǎng)路徑上的活動(dòng)叫做關(guān)鍵活動(dòng)。有環(huán)的圖不能進(jìn)行拓?fù)渑判颉?br />7.對(duì)于堆排序，常用的建堆算法是篩選法，堆的形狀是一棵完全二叉樹。

二、判斷題（每小題1分，共5分）
1.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。 錯(cuò)
2.鏈表的每個(gè)節(jié)點(diǎn)中都帢包含一個(gè)指針。 錯(cuò) 例如雙向鏈表
3.棧和隊(duì)列都是順序存儲(chǔ)結(jié)構(gòu)的線性結(jié)構(gòu)。 錯(cuò) 鏈棧
4.若數(shù)的度為2時(shí)，則該樹為二叉樹。 錯(cuò)
5.若廣義表中的每個(gè)元素都是原子，則廣義表為線性表。 對(duì)

三、問答題（每小題4分，共16分）
1.一棵3階4層（根為第一層，葉子為第四層）的B－樹，至少有多少個(gè)關(guān)鍵字，至多有多少個(gè)關(guān)鍵字？
答：7個(gè) 26個(gè)
2.利用棧秋表達(dá)式（（A-B）-C）-(D-(E-F)) 的值，運(yùn)算符棧和操作數(shù)棧各必須具有多少項(xiàng)？
答：5項(xiàng) 4項(xiàng)

3.以行序?yàn)橹餍虼鎯?chǔ)10階對(duì)稱矩陣A，采用下三角的壓縮存儲(chǔ)方式，若起始地址是d，則A85的存儲(chǔ)地址是多少？
答：32＋d

4.設(shè)哈希表中以存在無個(gè)記錄（如圖一所示）。哈希函數(shù)為H(K)=K MOD 11，用二次探測(cè)再散列處理沖突。請(qǐng)問關(guān)鍵字為94的記錄的存儲(chǔ)地址是多少？
0 1 2 3 4 5 6 7 8 9 10
圖一
45 16 39 62 76
答：存儲(chǔ)地址是 2

四 綜合題（每小題5分，共35分）
1.給定一組權(quán)值{9，6，14，17，2，15，3，16}，請(qǐng)構(gòu)造哈夫曼樹，并計(jì)算其帶權(quán)路徑長(zhǎng)度。
答：帶權(quán)路徑長(zhǎng)度186

2.已知二叉樹的先序遍歷的結(jié)果為ABCDEFGHIJ，中序遍歷的結(jié)果為CBEDAHGIJF，請(qǐng)畫出這顆二叉樹。

3.對(duì)圖二所示的無向圖，（1）請(qǐng)用鄰接表表示，且頂點(diǎn)鏈接按序號(hào)從小到大鏈接。
（2）請(qǐng)寫出從V0出發(fā)的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的結(jié)果。
圖二：
0
O

1 2

3 4 5 6

7

4 將圖三所示的樹轉(zhuǎn)換為二叉樹，并使其成為后序線索樹。


圖三: A

B C D

E F


G H I J



K L M



N


5 對(duì)關(guān)鍵字序列{44，12，53，13，37，88，24，61}構(gòu)造一棵平衡二叉樹。

6 已知一個(gè)OE網(wǎng)，如圖四所示，求其關(guān)鍵路徑，并給出時(shí)間4的最遲發(fā)生時(shí)間和事件5最早發(fā)生時(shí)間？




圖四： 1 4 4

12
5 2 6 9
11 5 10
0 9
18
14 6
3 5
3 5
7 7 8
8

7 對(duì)序列{50，77，64，98，39，12，26，48，44，35}創(chuàng)建初始堆。

五、（8分） 設(shè)指針head 指向無表頭結(jié)點(diǎn)單鏈表的首結(jié)點(diǎn)。試設(shè)一算法，刪除鏈表中值為X的結(jié)點(diǎn)，若X結(jié)點(diǎn)不存在，則輸出“不存在”信息。

六、（10分）已知一個(gè)有向圖的鄰接表，試編寫一個(gè)算法求每個(gè)結(jié)點(diǎn)的出度和入度。

七、（12分）已知一個(gè)二叉樹存儲(chǔ)于二叉鏈表中，其結(jié)點(diǎn)結(jié)構(gòu)為 lc data rc
其中l(wèi)c和rc分別為指向左子樹和右子樹根的指針域。試編寫一個(gè)非遞歸算法，求二叉樹的結(jié)點(diǎn)總數(shù)及其深度。