一、填空題(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+24A4,7
5.設循環隊列最大空間為m(0,…,m-1),頭,尾指針為front,rear。加入判別隊列空的條件是(front+1)MODm=rear,那么判別隊列滿的條件是什么?front,rear的初值應是多少?
答front=rear初值front=0rear=1
四、應用題(25分)
1.對一組記錄的關鍵字(49,38,66,80,75,19,22)進行快速排序,請寫出各趟排序后的狀態,并說明總共比較了多少次?
2.設哈希表的地址空間為0-6,哈希函數H(K)=KMOD7。請對關鍵字序列(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.將二叉樹的結點按層編號(從根還是往下,同層自左至右)。請設計一算法,將該二叉樹的結點按編號從小到大順序輸出。設二叉樹用二叉鏈表表示。
您現在的位置: 首頁 > 考研頻道 > 考研專業課 > 哈爾濱工程大學 > 正文

- 閱讀本文的人還閱讀了: