1、一、判斷（每小題1分，共10分）1 數據的存儲結構是數據的邏輯結構的存儲映象，不僅要存儲數據元素的 值，還要存儲元素之間的相互關系。2用順序表來存儲線性表時，不需要另外開辟空間來保存數據元素之間的 相互關系。3 完全二叉樹的葉子結點只能出現在最后一層上。4 折半查找方法要求待查表必須是有序的順序表。5在有向圖G中， 2 ，V 1 和 1，V 2 是兩條不同的邊。6圖的最小生成樹是唯一的。7從循環單鏈表的某一結點出發，只能找到它的后繼結點，不能找到它的 前趨結點。8 在單鏈表中，頭結點是必不可少的。9 對快速排序來說，初始序列為正序和反序，都是最壞情況。10廣義表是特殊的線性表。二、選擇（每題1

2、分，共15分）1 .設棧S和隊列Q的初始狀態均為空，元素abcdefg依次進入棧S。 若每個元素出棧后立即進入隊列 Q ,且7個元素出隊的順序是bdcfeag ，則 棧S的容量至少是（）。A. 1B. 2C . 3D . 4C（用虛線表示線索），符合后序線索樹定義的是（3. 已知廣義表 A= ( a,b ) ,(c,d),則 head(A)等于()。A. (a,b)B. (a,b)C. a,bD. a4. 設字符串 s仁'ABCDEFG',s2=卩QRST',則運算 s=strcat(strsub(s1,2,strle n(s2),strsub (s1,strle n(

3、s2),2)后結果為()。A. BCQRB. BCDEFC. BCDEFGD. BCDEFEF5. 具有8個頂點的連通圖的深度優先生成樹，其邊數為()。A. 8B. 9C. 7D. 66 .算法分析的兩個主要方面是()。A.空間復雜性和時間復雜性C可讀性和文檔性B .正確性和簡明性D.數據復雜性和程序復雜性7. 下列四種排序中（）的空間復雜度最大。A.插入排序B .冒泡排序C .堆排序D .歸并排序8. 下列關于無向連通圖特性的敘述中，正確的是（）。I .所有頂點的度之和為偶數II .邊數大于頂點個數減1 III .至少有一個頂點的度為1A.只有IB.只有II C . I和IID. I 和 I

4、II9.在一棵度為4的樹T中，若有20個度為4的結點,10個度為3的結點，1個度為2的結點,10個度為1的結點，則數T的葉結點個數是()。A. 41B . 82C. 113D . 12210 .對下圖進行拓撲排序，可以得到不同的拓撲序列的個數是（ ）A . 4A . 4B . 512 .對一組數據（2 , 12 , 16 趟排序結果如下：第一趟：2 ，12 ，16 ，10 ，16 ，88 第三趟：2 ，則采用的排序方法可能是（） A.起泡排序13 .設有二維數組 A5060 基地址為200，則元素A1825B.希爾排序C歸并排序D.基數排序 按行優先順序存儲A .3700B . 4376C.

5、390014 .隊列操作的原則是（）。A .先進先出B.后進先出C.只能進行插入D .15 .已知關鍵序列5 , 8,12 ,19 , 28 , 20,15堆（最小堆），插入關鍵字3，調整后得到的小根堆是A .3,5, 12,8 ,28,20,15 , 22 ,19B .3 , 5 , 12,19 ,20,15 , 22 , 8 ,28C.3 , 8 , 12,5 ,20,15,22 , 28 ,19D.3 , 12 , 5,8 ,28,20,15 , 22 ,19三、填空（每空1分，共25分）D. 4620只能進行刪除，22是小根，其元素長度為4字節, 的存儲地址為（）。11 .已知一個長度

6、為16的順序表L，其元素按關鍵字有序排列，若采用 折半查找法查找一個不存在的元素，則比較次數最多的是（）C . 6D . 7，88 ， 5 ， 10 ）進行排序，若前三10 ，88 第二趟：2 ， 12 ，5 ，10 ， 12 ， 16 ，88I 在一個有向圖的鄰接表中，一個頂點的邊表中結點的個數等于這個頂點的（），在逆鄰接表中，一個頂點的邊表中結點的個數等于這個頂點的（）。2四類基本邏輯結構是集合、（）、（）、圖狀結構。3當一個AOV網用鄰接表表示時，可按下列方法進行拓撲排序。（1）查鄰接表中入度為（）的頂點，并進棧；（2）若棧不空，則輸出棧頂元素Vj ，并退棧；查Vj的直接后繼Vk， 對V

7、k入度處理，處理方法是（）；（3）若?？諘r，輸出頂點數小于圖的頂點數，說明有（），否則拓撲排序完 成。4 空格串是指（），其長度等于（）。5. 我們學過的構造散列函數的方法有（）、平方取中法、分段疊加法、（）、 偽隨機數法。6 設一棵完全二叉樹中有21個結點，如果按照從上到下、從左到右的順 序從1開始順序編號，則編號為8的結點的雙親結點的編號是（），編號為 8的結點的左孩子結點的編號是（）。7 順序存儲結構是通過（）表示兀素之間的關系的；鏈式存儲結構是通（）表示元素之間的關系的。8僅允許在表的一端進行插入和刪除運算的線性表被稱為（）。9在分塊查找中雖不要求整個表有序，但要求表（）有序。10根據

8、二叉樹的定義可知二叉樹共有（）種不同的形態。II 設一棵二叉樹中有n個結點，則當用二叉鏈表作為其存儲結構時，該 二叉鏈表中共有（）個指針域，（）個空指針域。12.用Dijkstra算法求某一頂點到其余各頂點間的最短路徑是按路徑長度（）的次序來得到最短路徑的。13在散列法中要解決兩個問題：構造一個（）的散列函數、給出解決（） 的方法。14.在順序隊列中做入隊運算時，應先判別隊列是否（）；在做出隊運算時， 應先判別隊列是否（）。四、簡答題（每題5分，共30分）1設完全二叉樹的順序存儲結構中存儲數據 ABCDE，如圖，要求給出該二 叉樹的鏈式存儲結構并給出該二叉樹的前序、中序和后序遍歷序列。1 23

9、45ABCDE2 設給定一個權值集合 W=（3，5 ，7 ，9，11），要求根據給定的權值集合構造一棵哈夫曼樹并計算哈夫曼樹的帶權路徑長度WPL。3設無向圖G （如下圖所示），要求給出該圖的深度優先和廣度優先遍歷 的序列并給出該圖的最小生成樹。14 設一組初始記錄關鍵字集合為 (25 , 10 , 8 , 27 , 32 , 68), 散列表的長度為8，散列函數H(k)=k mod 7 ，要求用線性探測法作為解決沖 突的方法設計哈希表。并計算該表查找成功的平均查找長度和查找不成功的平均 查找長度。5. 已知一棵樹如下圖所示，要求將該樹轉化為二叉樹。6. 已知關鍵字集合： 46 , 55 , 1

10、3 , 42 , 94 , 17 , 05 , 7 0 ，用冒泡排序從小到大排序，分別寫出第一趟、第二趟、第三趟排序結束時 的序列，該排序方法穩定嗎？五、算法設計題(每題10分，共20分)1. 設有一個由正整數組成的無序(向后)單鏈表，編寫完成下列功能的算 法：(1) 找出最小值結點，且打印該數值；(2) 若該數值是偶數，則將其直接后繼結點刪除； 單鏈表類型描述：typedef struct Node ElemType data ;struct Node* n ext;Node, *L in kList；2. 已知一個二叉樹采用二叉鏈表存放，寫一算法，統計出二叉樹中葉子結 點的個數。二叉鏈表類

11、型描述為：typedef struct Node DataType data;struct Node * Ichild;struct Node * rchild;BiTNode, *BiTree;一、判斷（每小題1分，共10分）1 V 2 V 3 X 4 V 5 V 6 X 7 X 8 X 9 V 10 V二、選擇（每題1分，共15分）I. C 2. D 3. A 4. D 5. C6. A 7. D 8. A 9. B 10. AII. B 12. A 13. B 14. A 15. A三、填空（每空1分，共25分）1 .出度 入度2 .線性結構樹狀結構3. 0 Vk入度減1，若為0進棧環（

12、回路）4. 由空格組成的串空格的個數5. 數字分析法除留余數法6. 4 167. 位置相鄰指針8. 棧9. 塊間10. 511. 2n n+112. 遞增13. 均勻沖突14. 滿空四、簡答題（每題5分，共30分）中序序列:DBEAC、后序序列:DEBCA、前序序列：ABDEC、2.哈夫曼樹：WPL= （ 7*2+3*3+5*3+9*2+11*2） =78（ 1 分）3.深度優先遍歷序列：123,4,6,5（不唯一）廣度優先遍歷序列：1,2,3,4,5,6 （不唯一） 最小生成樹：4.01234567310253227111213查找成功的平均查找長度為：(1*4+2+3 ) 16=96查找不

13、成功的平均查找長度為：(1+2+1+6+5+4+3 ) /7=22/75.轉化后的二叉樹：6. 第一趟：46 13 42 55 17 05 70 94第二趟：13 42 46 17 05 55 70 94第三趟：13 42 17 05 46 55 70 94該排序方法穩定五、算法設計題(每題10分，共20分)本題無統一答案。每道題編寫算法時完成題目功能即可1.參考答案：void fun(Lin kList head) int min;Node * p , * q;if(p!=NULL) p=head;min=p->data;while(p!=NULL)if( min >p->data) min=p->data; q=p;p=p->n ext;printf(“min=%dn” ,min);if(mi n%2=0 && q-> next!=NULL) p=q->n ext;q->n ext=p->n ext;free(p);2 參考答案：/*node為保存葉子結點數目的全局變量，調用之前初始化為0 */void Cou ntNode(Bi nTree root) /*求二叉樹中葉子結點個數 */if (root!=NULL) Count