05級(jí)期末考試試題開(kāi)卷空題

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

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

3、：Hash(key)=key mod 11，哈希表的大小為11，采用線性探測(cè)法進(jìn)行沖突處理），求等概率條件下的平均查找長(zhǎng)度ASL，并對(duì)這三種查找方法進(jìn)行比較。2已知用線性有序鏈表存儲(chǔ)整數(shù)集合的元素。閱讀下面算法，并回答下列問(wèn)題：（1）寫(xiě)出執(zhí)行ABC（a, b）的返回值，其中a和b分別為指向存儲(chǔ)集合 2，4，5，7，9，12 和 2，4，5，7，9 的鏈表的頭指針；（2）簡(jiǎn)述算法ABC的功能；（3）寫(xiě)出算法ABC的時(shí)間復(fù)雜度。int ABC (LinkList ha,LinkList hb) / LinkList是帶有頭結(jié)點(diǎn)的單鏈表 / ha和hb分別為指向存儲(chǔ)兩個(gè)有序整數(shù)集合的鏈表的頭指針 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. 對(duì)于下面的一串字符，根據(jù)各字符出現(xiàn)的頻度求各個(gè)字母的哈夫曼編碼，并且建樹(shù)要遵循二叉樹(shù)左邊結(jié)點(diǎn)的權(quán)值二叉樹(shù)右邊結(jié)點(diǎn)的權(quán)值，請(qǐng)寫(xiě)出詳細(xì)的求解過(guò)程。ABCCCEBAAADCCCAEECCCEDE 得 分得 分三、 算法設(shè)計(jì)題（每題10分，共30分）1采用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，試編寫(xiě)一個(gè)算法求二叉樹(shù)中結(jié)點(diǎn)p的雙親結(jié)點(diǎn)和孩子結(jié)點(diǎn)。2若借助棧由輸入序列為1，2，n得到的輸出序列為P1 P2 Pn , 設(shè)計(jì)一個(gè)算法輸出所有可能的序列，并分析該算法的時(shí)間復(fù)雜度和空間復(fù)雜度。3在游戲軟件和圖形軟件設(shè)計(jì)中，經(jīng)常遇到下面的情況：n條直線把屏幕分成m個(gè)區(qū)域，見(jiàn)圖。假設(shè)每條直線的方程和