哈爾濱工程大學2002年數據結構考研試題

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