一 填空題 （13分）
 
1 數(shù)據(jù)結(jié)構(gòu)從邏輯上分（線(xiàn)性）結(jié)構(gòu)和（非線(xiàn)性）結(jié)構(gòu)。
2 若廣義表中的每個(gè)元素都是（原子），則廣義表變成為線(xiàn)性表。
3 連通圖的極小連通子圖稱(chēng)為改圖的（生成樹(shù)）。
4 哈希（hash）法存儲(chǔ)的基本思想是根據(jù)（關(guān)鍵字）來(lái)決定（存儲(chǔ)地址）。
5 迪杰斯特拉算法是按（路徑長(zhǎng)度遞增）次序產(chǎn)生最短路徑。
6 兩個(gè)字符串相等的充要條件是：兩個(gè)串的（長(zhǎng)度）相等，且（對(duì)應(yīng)位置）的字符相等。
7 哈夫曼樹(shù)是葉子節(jié)點(diǎn)（帶權(quán)路徑長(zhǎng)度）最短的二叉樹(shù)。
8 稀疏矩陣一般的壓縮方法有兩種（三元組表）和（十字鏈表）。
9 N個(gè)結(jié)點(diǎn)的線(xiàn)索樹(shù)有（n+1）根線(xiàn)索。
 
二 選擇題 （12分）
 
1 一個(gè)棧的入棧序列是a,b,c,d,e,則棧的不可能的輸入序列是dceab 
2 深度為h的4階B-樹(shù)（根在第一層，葉子在第h層），葉子結(jié)點(diǎn)的數(shù)目最少為 2^h-1
3 廣義表(a,b,(c,(d,e))) 的尾是 （b,(c,(d,e))）。
4 具有5層結(jié)點(diǎn)的平衡二叉樹(shù)至少有12個(gè)結(jié)點(diǎn)。
5 設(shè)二叉樹(shù)是由森林變換得來(lái)的，若森林中有n個(gè)非終端結(jié)點(diǎn)，則二叉樹(shù)中無(wú)右孩子的結(jié)點(diǎn)有n＋1個(gè)。
6 下列不屬于內(nèi)部排序的算法是B
A 歸并排序         B 拓?fù)渑判?nbsp;      C 樹(shù)型排序        D 折半插入排序
 
三 回答問(wèn)題（20分）
 
1 對(duì)n個(gè)結(jié)點(diǎn)的二叉樹(shù)進(jìn)行中序遍歷，算法中所設(shè)的棧，棧中元素最少時(shí)可能是多少個(gè)？最多時(shí)可能是多少個(gè)？
答：2個(gè)   ，n+1個(gè)
 
2 對(duì)n個(gè)記錄進(jìn)行簡(jiǎn)單的插入排序，最少共需要比較多少次？最多共需要比較多少次？
答 最少n－1次   最多1＋2＋3…………＋（n－1）次
 
3 對(duì)13個(gè)有序記錄進(jìn)行折半查找，查找成功和不成功的平均查找長(zhǎng)度各為多少？
4 采用上三角壓縮存儲(chǔ)10階對(duì)稱(chēng)矩陣A，若以行序?yàn)橹鞔鎯?chǔ)，且起始地址為d則A3，8的存儲(chǔ)地址為多少？它與以列序?yàn)橹餍虼鎯?chǔ)時(shí)的哪一個(gè)元素的起始位置一致？
答：d＋24       A4,7
 
5 設(shè)循環(huán)隊(duì)列最大空間為m（0，…，m－1），頭，尾指針為front，rear。加入判別隊(duì)列空的條件是（front＋1）MODm＝rear，那么判別隊(duì)列滿(mǎn)的條件是什么？front，rear的初值應(yīng)是多少？
答 front＝rear    初值front＝0 rear＝1
 
四 應(yīng)用題（25分）
1 對(duì)一組記錄的關(guān)鍵字（49，38，66，80，75，19，22）進(jìn)行快速排序，請(qǐng)寫(xiě)出各趟排序后的狀態(tài)，并說(shuō)明總共比較了多少次？
 
2 設(shè)哈希表的地址空間為0－6，哈希函數(shù)H(K)=K MOD 7。請(qǐng)對(duì)關(guān)鍵字序列（32，13，49，18，22，38，21）按鏈地址法解決沖突的辦法構(gòu)造哈希表。并求出查找成功的平均查找長(zhǎng)度。
 
3 已知二叉樹(shù)的左，右子樹(shù)各含3個(gè)結(jié)點(diǎn)。試分別構(gòu)造滿(mǎn)足如下要求的二叉樹(shù)：（1）左子樹(shù)的先序序列與中序序列相同，右子樹(shù)的先序序列與中序序列相同。（2）左子樹(shù)的中序序列與后序序列相同，右子樹(shù)的先序序列與中序序列相同。
 
4 對(duì)關(guān)鍵字（67，49，80，14，22，31，95，38，43，56，73）構(gòu)造平衡二叉樹(shù)。
 
5 請(qǐng)寫(xiě)出表達(dá)式a+b*(c-d)-e/f的二叉樹(shù)表示，并使其成為后序線(xiàn)索樹(shù)。
 
五 算法題（30分）
 
1 設(shè)計(jì)一算法，在單鏈表中刪除數(shù)據(jù)元素的值相同的多余結(jié)點(diǎn)。
 
2 設(shè)計(jì)一算法，在中序線(xiàn)索樹(shù)上求指針P所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)。
 
3 將二叉樹(shù)的結(jié)點(diǎn)按層編號(hào)（從根還是往下，同層自左至右）。請(qǐng)?jiān)O(shè)計(jì)一算法，將該二叉樹(shù)的結(jié)點(diǎn)按編號(hào)從小到大順序輸出。設(shè)二叉樹(shù)用二叉鏈表表示。