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