1、PAGE PAGE 6 數據結構試題 （開卷） A卷 （電信系本科2005級 2006年11月）姓名 班級 題 號一二三總分題 分403030100得 分得 分得 分一、回答下列問題 (每題5分，共40分)1給定序列（67，45，87，19，55，32，70，60，90，23），寫出它的初始堆序列。2設一個序列奇數項和偶數項分別由小到大有序，用什么方法可以最快得到一個有序序列，分析它的時間復雜度。3二叉排序樹中的最大值在二叉排序樹的何處？4在2048個互不相同的關鍵碼中選擇最小的5個關鍵碼，用堆排序是否比用錦標賽排序更快？為什么？5 n個頂點、m條邊的全連通圖，至少去掉幾條邊才能構成一棵樹？6

2、設模式串為：liuwenliuyuliuyingliyu, 求該模式串的next函數。7一個二叉樹按層次遍歷的順序存儲結構如下，請畫出該二叉樹 (為空) 。1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ABDCEFGH8 設數組A 1.10, 1.8 的基地址為2000，每個元素占2個存儲單元，若以列序為主序存儲（按列存儲），則元素A 4，5 的存儲地址是多少？得 分二、綜合題（每題10分，共30分）得 分輸入一序列（58，18，29，22，38，81，19，14），現分別采用順序查找和二叉排序樹查找，求等概率條件下二者的平均查找長度ASL；若改用哈希查找（哈希函數為

3、：Hash(key)=key mod 11，哈希表的大小為11，采用線性探測法進行沖突處理），求等概率條件下的平均查找長度ASL，并對這三種查找方法進行比較。2已知用線性有序鏈表存儲整數集合的元素。閱讀下面算法，并回答下列問題：（1）寫出執行ABC（a, b）的返回值，其中a和b分別為指向存儲集合 2，4，5，7，9，12 和 2，4，5，7，9 的鏈表的頭指針；（2）簡述算法ABC的功能；（3）寫出算法ABC的時間復雜度。int ABC (LinkList ha,LinkList hb) / LinkList是帶有頭結點的單鏈表 / ha和hb分別為指向存儲兩個有序整數集合的鏈表的頭指針 L

4、inkList pa, pb; pa=ha-next; pb=hb-next; while(pa & pb & pa-data=pb-data) pa=pa-next; pb=pb-next; if(pa=NULL & pb=NULL) return 1; else return 0; 3. 對于下面的一串字符，根據各字符出現的頻度求各個字母的哈夫曼編碼，并且建樹要遵循二叉樹左邊結點的權值二叉樹右邊結點的權值，請寫出詳細的求解過程。ABCCCEBAAADCCCAEECCCEDE 得 分得 分三、 算法設計題（每題10分，共30分）1采用二叉鏈表作為存儲結構，試編寫一個算法求二叉樹中結點p的雙親結點和孩子結點。2若借助棧由輸入序列為1，2，n得到的輸出序列為P1 P2 Pn , 設計一個算法輸出所有可能的序列，并分析該算法的時間復雜度和空間復雜度。3在游戲軟件和圖形軟件設計中，經常遇到下面的情況：n條直線把屏幕分成m個區域，見圖。假設每條直線的方程和