哈爾濱工業(yè)大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法歷年考題匯總

1、期末2005數(shù)據(jù)結(jié)構(gòu)與算法試卷試卷類型：期末試卷年份：03授課教師：廖明宏有無(wú)答案：無(wú)答案哈工大2005年春季學(xué)期數(shù)據(jù)結(jié)構(gòu)與算法試卷一填空題(每空1分，共10分)1.假定對(duì)線性表(3& 25, 74, 52, 48)進(jìn)行散列存儲(chǔ),采用H(K)二K %7作為散列函數(shù)，若分別采用線性探查法和鏈接法處理沖突，則對(duì)各自散列表進(jìn)行查找的平均查找長(zhǎng)度分別為和O2.假定一組記錄的排序碼為(46, 79, 56, 38, 40, 80),對(duì)其進(jìn)行歸并排序的過程中, 第二趟歸并后的結(jié)果為，3. 在堆排序的過程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行調(diào)整運(yùn)算的時(shí)間復(fù)雜度為整個(gè)堆排序過程的時(shí)間復(fù)雜度為.4. 有向圖的鄰接矩陣

2、表示法中某一行非0元素的個(gè)數(shù)代表該頂點(diǎn)的,某一列非 0元素的個(gè)數(shù)是該頂點(diǎn)的。5. 對(duì)于下面的帶權(quán)圖G3,若從頂點(diǎn)vO出發(fā)，則按照普里姆(Prim)算法生成的最小生成樹中，依次得到的各條邊為=6. 由帶權(quán)為3, 9, 6, 2, 5的5個(gè)葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹，則帶權(quán)路徑長(zhǎng) 度為7. 由三個(gè)結(jié)點(diǎn)構(gòu)成的二義樹，共有種不同結(jié)構(gòu)。二. 選擇題(每題1分，共10分)1. 快速分類在的情況下不利于發(fā)揮其長(zhǎng)處.A.待分類的數(shù)據(jù)量太大B.待分類的數(shù)據(jù)相同值過多C.待分類的數(shù)據(jù)已基本有序D.待分類的數(shù)據(jù)值差過大.2. 兩路歸并排序中，歸并的趟數(shù)是。A. 0(n) B. 0(log2n) C. 0(nlog2n

3、) D. 0(n2)注意行為規(guī)范遵守考場(chǎng)紀(jì)律第1頁(yè)，共6頁(yè)3. 對(duì)外部分類的K路平衡歸并，采用敗者樹時(shí)，歸并的效率與K。A.有關(guān)B.無(wú)關(guān)C.不能確定D.都不對(duì)4. 對(duì)于一個(gè)索引順序文件，索引表中的每個(gè)索引項(xiàng)對(duì)應(yīng)主文件中的。)A. 一條記錄B.多條記錄C.所有記錄D.三條以上記錄5.若線性表采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占用4個(gè)存儲(chǔ)單元，笫一個(gè)元素的存 儲(chǔ)地址為100,則第12個(gè)元素的存儲(chǔ)地址時(shí)。6. 若頻繁地對(duì)線性表進(jìn)行插入和刪除操作，該線性表應(yīng)該采用存儲(chǔ)結(jié)構(gòu)。A.散列B.順序C.鏈?zhǔn)紻.索引7. 若長(zhǎng)度為n的非空線性表釆用順序儲(chǔ)存結(jié)構(gòu)，刪除表中第i個(gè)數(shù)據(jù)元素，需 要移動(dòng)表中個(gè)數(shù)據(jù)元素。+i +1

4、8. 棧和隊(duì)列的相同之處是。（A.元素的進(jìn)出滿足先進(jìn)后出B.元素的進(jìn)出滿足后進(jìn)先出C.只允許在端點(diǎn)進(jìn)行插入和刪除操作D.無(wú)共同點(diǎn)9. 在一棵高度為k的二義樹中，最多含有（）個(gè)結(jié)點(diǎn)。A. 2k-1 B. 2k-l C. 2k-1 D. k10. 任何一棵二義樹的葉結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對(duì)次序（）。A.發(fā)生改變B.不發(fā)生改變C.不能確定D.以上都不對(duì)三. 判斷題，正確的在括號(hào)內(nèi)畫V,錯(cuò)誤的在括號(hào)內(nèi)畫X。（每小題1分，共10分）1. 樹的父鏈表示就是用數(shù)組表示樹的存儲(chǔ)結(jié)構(gòu)。（）2. 任何二元樹都唯一對(duì)應(yīng)一個(gè)森林，反之亦然。.（）3. 有向圖的鄰接矩陣一定不是對(duì)稱的。（）4. A0E網(wǎng)中

5、，只有一個(gè)入度為0的頂點(diǎn)（起始點(diǎn)），只有一個(gè)出度為0的頂點(diǎn) （結(jié)束點(diǎn)）。（）5. 關(guān)鍵路徑可能不只一條，但縮短某一關(guān)鍵路徑一定能夠縮短工期。（）6. 順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。（）7. 用循環(huán)鏈表作為存儲(chǔ)結(jié)構(gòu)的隊(duì)列就是循環(huán)隊(duì)列。（）8. 倒排文件的主要優(yōu)點(diǎn)為便于節(jié)省空間（）。9. 一組記錄的關(guān)鍵字為（46, 79, 56, 38,40, 84），則利用快速排序的方法，以第 一個(gè)記錄為基準(zhǔn)元素得到的一次劃分結(jié)果為40, 38, 46, 56, 79, 84 （）。10.算法分析的口的是分析算法的易讀性（）。四. 簡(jiǎn)答題1. 簡(jiǎn)述如何用兩個(gè)棧模擬一個(gè)隊(duì)列的入隊(duì)和出隊(duì)操作.（6分）<2

6、. 對(duì)于圖G5所示的樹：（7分）（1）寫出先根遍歷得到的結(jié)點(diǎn)序列；（2）寫岀按層遍歷得到的結(jié)點(diǎn)序列；（3）畫出轉(zhuǎn)換后得到的二元樹1圖G5五. 算法設(shè)計(jì)1. 設(shè)二元樹采用左右鏈存儲(chǔ)，寫出后序遍歷該二元樹的非遞歸算法。（12分）2. 設(shè)圖中各邊上的權(quán)值均相等，試以鄰接表為存儲(chǔ)結(jié)構(gòu)，寫出求源點(diǎn)Vi到Vj的最 短路徑算法。（15分）.注意行為規(guī)范遵守考場(chǎng)紀(jì)律管導(dǎo)核字主領(lǐng)審簽-二Its八1八兒1,0'刀分?jǐn)?shù)一. 填牢題(每題2分，共28分)1. 假設(shè)個(gè)15階的上二角矩陣A按行優(yōu)先順用壓縮存儲(chǔ)在 維數(shù)組B中，則非零元素A99在B中的心儲(chǔ)位毀K=,(注，矩陣元素下標(biāo)從1開始)2. 設(shè)有廣義衣/ =

7、(M),.r),),(力),(c,仏(P)，則得到y(tǒng)的對(duì)廣義農(nóng)A的操作序列為.3. 對(duì)于個(gè)只有n個(gè)結(jié)點(diǎn)的單向鏈2乙在已如P所指結(jié)點(diǎn)后插入個(gè)新結(jié)點(diǎn)的吋的毀雜度為;在值域?yàn)榻o定值的結(jié)點(diǎn)后插入 個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為O4. 表達(dá)式2屯(1* 2)- 32+ ” 43的后綴表達(dá)式是a5. 設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空，元素。，b. c. d, c, F依次通過棧S, 個(gè)元索出棧后即進(jìn)入隊(duì)列Q,若這6個(gè)元索出隊(duì)列的順序是b, ct c, f, e. a,則棧 的容杲至少應(yīng)該是o6. 在完全二叉樹中，編號(hào)為i和j的兩個(gè)結(jié)亢處于同層的條件是-7設(shè)F足rhTl, T2, T3二棵樹組成的森林，與F對(duì)應(yīng)的二叉

8、樹為B,己如Tl, T2,T3的結(jié)點(diǎn)數(shù)分別為nl, n2, n3,則.叉樹B的左/*樹屮有個(gè)結(jié)點(diǎn),右了樹中冇個(gè)結(jié)點(diǎn)。8 有數(shù)據(jù)WG=(7. 19, 2, 6, 32, 3, 21, 10),則所建Huffman樹的樹高為,帶權(quán)路徑長(zhǎng)度WPL為。9. 在有n個(gè)定點(diǎn)的有向圖中，若任意兩點(diǎn)間對(duì)以h相到達(dá)，則至少需要條弧.10. 已知有序記錄(2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47),用折半査找算法査找關(guān)鍵字為7. 41的記錄時(shí)，比較次數(shù)分別為次和次。設(shè)有100個(gè)結(jié)點(diǎn)，用折半含找算法時(shí)，繪大比較次數(shù)為次。11. 對(duì) 俎記錄(50,

9、40, 95, 20, 15, 70, 60, 45, 80)進(jìn)行直接插入揩序吋,當(dāng)把第7個(gè)記錄60插入到有序表中時(shí).為尋找插入位豈需比較次.12. 若圖足可拓?fù)渑判虻?，則該圖中 處存任入讀和L11皮分別為的不同頂點(diǎn)。若某圖不能次完成拓?fù)渑判颍瑒t該何向圖必定或13. 假定K個(gè)斤健字互為同義詞，若用線性探測(cè)再散列法把這K個(gè)關(guān)諜字“入散列農(nóng)中，至少婆進(jìn)行次探測(cè).14在 棵樹中，度為1的結(jié)點(diǎn)的個(gè)數(shù)為度為2的結(jié)點(diǎn)的個(gè)數(shù)為乞，,度為m的結(jié)點(diǎn)的個(gè)數(shù)為心，則該樹冇個(gè)葉子結(jié)點(diǎn)。二、簡(jiǎn)答題（共30分）I.請(qǐng)分別御述在I）彷線索二叉樹中求菜結(jié)點(diǎn)P在曲序遍丿萬(wàn)順序下的戌接前驅(qū)（$尸）和氏接后 繼（PS ）的幕本世想

10、° （5分）試題：2008年春數(shù)據(jù)結(jié)構(gòu)A卷班號(hào)：姓名：2.諸簡(jiǎn)述利H Kruskal算注、Prim聲法和破圈法求圖的最小土成樹的基本思擔(dān)。（5為試題:2008年祚數(shù)據(jù)結(jié)構(gòu)A卷班小.R泡排仔過程中，冇的關(guān)儺7在某醞陽(yáng)Y：中可能朝帶與掖終排庁相反的方向務(wù)動(dòng)，試舉例悅明Z。亦爾辦湘快速博序過程中分別有這種現(xiàn)像嗎？如有,讒舉例說(shuō)明。（8分）4.棵一叉樹的前序、中丿沢后序序列如下,Jt中有部分未標(biāo)出,試填充完虧（6分）【精析P103】前序序列為：C D E _G _H_ I_K中序序列為：C7 RF A _ J¥L J G后序序列為:_ E FD B _ Jill_A第4頁(yè)（共7頁(yè)）

11、試題：200R年春 數(shù)據(jù)結(jié)構(gòu)A卷 班號(hào)：姓名：5H知紐關(guān)銖字狛（26, 36, 41, 38, 44, 15,68, 12, 06, 51, 25）,用餅地址法解決沖試題：2008年春數(shù)據(jù)結(jié)構(gòu)A卷班號(hào)：姓名：已知 組關(guān)鍵字為（26, 36, 41, 38, 44, 15, 68, 12, 06, 51, 25）,用鏈地址法解決沖突，假設(shè)裝填因了為a =0.75, Hash函數(shù)的形式為H（K）= K MODF ,試回答下列問題:（6分）【訂構(gòu)造Hash函數(shù)；【ii計(jì)算等概率情況下查找成功的平均査找長(zhǎng)度；iii計(jì)算等概率借況下住找失敢的平均杳找長(zhǎng)度。試趣：2008年春 數(shù)擁結(jié)構(gòu)-A卷 班號(hào):姓名:

12、五、算法設(shè)計(jì)（共20分）1. （10分）請(qǐng)?jiān)O(shè)計(jì)種隊(duì)列，要求*i隊(duì)列的大小不受限制，可根據(jù)實(shí)際需要進(jìn)行分配;隊(duì)列的入隊(duì)操作的時(shí)何效率足0（1），出隊(duì)操作的吋間救率足0（1）;iii無(wú)需額外的輔助空間來(lái)完成隊(duì)列的入隊(duì)和出隊(duì)操作:咸于上述要求，根拯你設(shè)計(jì)的隊(duì)列，實(shí)現(xiàn)下列操作：Ca隊(duì)列的初始化操作：lb 隊(duì)列的隊(duì)空和隊(duì)滿判啟操作；rd 隊(duì)列的入隊(duì)和出隊(duì)操作：試題：2008年春 數(shù)擁結(jié)構(gòu)A卷 班號(hào)：姓名：2. （10分）請(qǐng)寫出在中序線索一叉樹里找指總結(jié)點(diǎn)在后序下的前驅(qū)結(jié)點(diǎn)的算法，苴中要求: 【訂二叉樹采用左右孩了表示法，線索二叉樹是對(duì)基本結(jié)構(gòu)的相應(yīng)擴(kuò)展：【門給出存儲(chǔ)結(jié)構(gòu)描述，并以偽代碼或CI代碼方式給出

13、算法的棊本描述；哈工大數(shù)據(jù)結(jié)構(gòu)與算法2009年試題題號(hào)二三四總分分值2010103070得分一、填空題（每空2分f共20分）1.在情況下,等長(zhǎng)編碼是最優(yōu)前綴碼。意為范守場(chǎng)律 注行規(guī)遵考紗2設(shè)有兩個(gè)算法在同一機(jī)器上運(yùn)行.其執(zhí)行時(shí)間分別為100*和 2“ f要使前者快于后者"至少為o3 采用堆排序、快速排序、冒泡排序，對(duì)初態(tài)有序的表，鍛省時(shí)間的S4 .設(shè)二叉樹結(jié)點(diǎn)的先根序列為ABDECFGH ,中根序列為DEB AFCHG,則二叉樹中葉結(jié)點(diǎn)是5. 用下標(biāo)從0幵始的N個(gè)元素的數(shù)組實(shí)現(xiàn)循環(huán)隊(duì)列時(shí),為實(shí)現(xiàn)下標(biāo)變呈m加1后在數(shù)組有效下標(biāo)范圍內(nèi)循環(huán)，可采用的表達(dá)式是m二O6. 由帶權(quán)為3 , 9,

14、4,2 . 5的5個(gè)葉子結(jié)點(diǎn)構(gòu)成一棵哈夫曼樹.則帶權(quán)路徑長(zhǎng)度為O7對(duì)n個(gè)記錄的表進(jìn)行選擇排序，在最壞情況下所需要進(jìn)行的關(guān)鋌字 的比較次數(shù)為O8.任意一個(gè)有n個(gè)結(jié)點(diǎn)的二叉樹.已知它有m個(gè)葉結(jié)點(diǎn).則度數(shù)為2 的結(jié)點(diǎn)有O9個(gè)頂點(diǎn)的連通圖用鄰接矩陣表示時(shí)，該矩陣至少有個(gè)非零元素10.舉出兩種磁帶文件的分類方法二二、選擇題（每題1分，共10分）1設(shè)一組初始記錄關(guān)鍵字序列為(45 r 80,55.40.42,85) f則以 第一個(gè)記錄關(guān)鍵字45為基準(zhǔn)而得到一趟快速排序的結(jié)果是()。(A) 40 r 42,45 f 55 r 80,83 (B) 42,40,45,80,85.88(C) 42,40,55.8

15、0,45,85 (D) 42 f 40,45,85 r 55 , 802 數(shù)據(jù)的最小單位是()。(A)數(shù)據(jù)項(xiàng)(B)數(shù)據(jù)類型(C)數(shù)據(jù)元素(D)數(shù)據(jù)變雖3 關(guān)犍路徑是AOE網(wǎng)中()。A.從始點(diǎn)到終點(diǎn)的最邁路徑B. 從始點(diǎn)到終點(diǎn)的最長(zhǎng)路徑C. 從始點(diǎn)到終點(diǎn)的邊數(shù)晟多的路徑D. 從始點(diǎn)到終點(diǎn)的邊數(shù)最少的路徑4下列說(shuō)法正確的是()。A最小生成樹也是哈夫曼樹B最小生成樹是唯一的C 對(duì)于n個(gè)頂點(diǎn)的連通無(wú)向圖,Prim算法的時(shí)間復(fù)雜性為 Ofn2)D Kruskal算法比Prim算法更適合邊稠密的圖5 設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空.元素Els E2、E3S E4S E5和E6 依次通過棧S r 一個(gè)元素出棧

16、后即進(jìn)入隊(duì)列Q,若6個(gè)元素出列的 順序?yàn)镋2、E4、Em. E6、E5和El 則桟S的容呈至少應(yīng)該是()。(A) 6(B) 4(C) 3(D) 26. 將10階對(duì)稱矩陣壓縮存儲(chǔ)到一維數(shù)組A中.則數(shù)組A的長(zhǎng)度最 少為()。(A) 100 (B)40(C) 55 (D) 807. 若數(shù)據(jù)元素序列11 , 12 r 13 f 7 ; 8 , 9 f 23 , 4 f 5是采用下列排序 方法之一得到的第二趟排序結(jié)果，則該排序算法只能是()o8設(shè)哈希表長(zhǎng)m = 14.哈希函數(shù)H (key) =key%llo表中已有4個(gè)結(jié) 點(diǎn)：addr(15)=4 , addr(38)二5 f addr(61)二6 f

17、addr(84)=7 其余地址 為空。如果用二次探測(cè)再散列處理沖突，關(guān)犍字為49的結(jié)點(diǎn)的地址 是()A . 8 B .3 C. 5 D. 99有組記錄的輸入順序?yàn)?46.79 , 56 . 38,40 , 84 ).則利用堆排 序方法建立的初始堆為()A.79,46 ; 56 # 38,40,80 B .38,40 r 56 ; 79,46 # 84C. 84,79 f 56 # 46 r 40 r 38 D. 84,56 , 79,40,46.3810.下列敘述中.不符合m階B樹定義要求的是()A.根結(jié)點(diǎn)最多有m棵子樹 B.所有葉結(jié)點(diǎn)都在同一層上 C各結(jié)點(diǎn)內(nèi)的關(guān)鍵字有序 D.葉結(jié)點(diǎn)之間通過指

18、針鏈接三、簡(jiǎn)答題（10分）帶權(quán)圖（權(quán)值非負(fù)，表示邊連接的兩個(gè)頂點(diǎn)的距韶）的最短路徑問 題是找出初始頂點(diǎn)到目標(biāo)頂點(diǎn)之間的一條最短路徑。假設(shè)從初始頂點(diǎn)到 目標(biāo)頂點(diǎn)之間的存在路徑r現(xiàn)有一種解決該問題的方法：1 ）設(shè)最短路徑初始時(shí)僅包含初始頂點(diǎn),令當(dāng)前頂點(diǎn)u為初始頂點(diǎn)；2）選擇離u最近的且尚未在最短路徑中的一個(gè)頂點(diǎn)v ,加入到最短路徑中，修改當(dāng)前頂點(diǎn)U=v;3）重復(fù)步驟2） r直到是目標(biāo)頂點(diǎn)為止。請(qǐng)問上述方法能否求得最短路徑？若可行請(qǐng)證明之；否則，請(qǐng)舉例 說(shuō)明。四、算法設(shè)計(jì)：棧、隊(duì)列的存儲(chǔ)結(jié)構(gòu)、基本操作可以直接引用（共30分）1. 設(shè)二叉樹采用左右鏈方式存儲(chǔ)，設(shè)計(jì)一個(gè)判斷二叉樹是否是二叉 排序樹的算法

19、。（10分）2. 設(shè)有一個(gè)雙鏈表，每個(gè)結(jié)點(diǎn)中除有prior、data和next三個(gè)域外，還 有一個(gè)訪問頻度域freq f在璉表被起用之前r其值均初始化為零。 每當(dāng)在鏈表進(jìn)行一次LocateNode（L,x）is算時(shí)f令元素值為x的結(jié) 點(diǎn)中friq域的值加1 ,并調(diào)整表中結(jié)點(diǎn)的次序，使其按訪問頻度的 遞減序排列，以便使頻驚訪問的結(jié)點(diǎn)總是靠近表頭。試寫出符合上 述要求的LocateNode運(yùn)算的算法。（10分）3. 給定一個(gè)無(wú)向連通圖,寫一個(gè)算法找出半徑最小的生成樹（搜索起點(diǎn) 作為生成樹的根樹的半徑定義為從根到葉子的最大距離）。（10分）參考答案：一、填空題1. 等概率 2.15 3.冒泡 4.E

20、FH f 5.(m+l)%N 6.517. n(n+l)/2 , n(n-l)/2 8.m-l 9. 2 ( n-1) 10.平衡歸并、多階段歸并二、選擇題1C 2A 3B 4 C 5C 6C 7A 8 D 9B 10D三、簡(jiǎn)答題不可以。設(shè)初始頂點(diǎn)為1 ,目標(biāo)頂點(diǎn)為3 ,不能求出最短路徑。四、算法題1根據(jù)二叉排序樹中序遍歷所得結(jié)點(diǎn)值為增序的性質(zhì)，在遍歷 中將當(dāng)前遍歷結(jié)點(diǎn)與其前驅(qū)結(jié)點(diǎn)值比較，即可得出結(jié)論。為此 設(shè)全局指針變Spre(初值為null)和全局變量flag z初值為 trueo若非二叉排序樹，則置flag為false。void JudgeBSTfBSlree t,int *flag)|

21、判斷二叉樹是否是二叉排序樹，本算法結(jié)束后,在謂用程序中由flag得出結(jié)論=null && *flag)Judgebst(t->lchild,&flag) ；| 中序遍歷左子樹if(pre=null)pre=t;|中序遍歷的第一個(gè)結(jié)點(diǎn)不必判斷else if(pre->data<t->data) pre=t;|前驅(qū)指針指向當(dāng)前結(jié)點(diǎn) else*flag=false ; |不是完全二叉樹Judgebst(t->rchildF&flag) ;|中序遍歷右子樹|if HJudgeBST 算法結(jié)束本題的另一算法是按定義，二叉排序樹的左、右子樹都是

22、二叉排序樹，根結(jié)點(diǎn)的值大于左子樹中所有結(jié)點(diǎn)的值而小于右子樹中所有結(jié)點(diǎn)的值，即根結(jié)點(diǎn)大于左子樹的最大值而小于右子樹的最小值。算法如下：int JudgeBST(BSlree t)II判斷二叉樹t是否是二叉排序樹，若是，返回true ,否則,返回false if(t=null) return true ;if(Judgebst(t->lchild)&& judgebst(t->rchild)| 左右子樹均為二叉排序樹m=max(t->lchild) ; n=min(t->rchild) ;|左子樹中最大值和右子樹中最小值return(t->data&g

23、t;m && t->data<n);|ifIelse return false ; |不是二叉排序樹11廣 *痛婀& IX JL1.X J/ JLInt max(BSTree p) |求二叉樹左子樹的最大值if(p=null)return maxint; |返回機(jī)器最小整數(shù)elsewhile(p->rchild) p=p->rchild ; return p->data ；|while |endint min(BSTreep) |求二叉樹右子樹的最小值 if(p=null) return maxint ； |返回機(jī)器最大整數(shù) elsewhl

24、le(p->IchiId) p=p->lchild ； return p->data ；|while |endDList locate(DList L r Elemlype x)2II L是帶頭結(jié)點(diǎn)的按訪問頻度遞減的雙向鏈表|本算法先査找數(shù)據(jù)x,査找成功時(shí)結(jié)點(diǎn)的訪問頻度域增1 r煨后將該結(jié)點(diǎn)按頻度遞城 插入鏈表中 DUstp=L->next,q; |p為L(zhǎng)表的工作指針.q為p的前驅(qū).用于查找插入位 §while(p && p->data ! = x) p=p->next; | 査找值為 x 的結(jié)點(diǎn)lf(!p) prints不存在所查

25、結(jié)點(diǎn)n"); exit(O)：else p->freq+;|令元素值為x的結(jié)點(diǎn)的freq1p->next->pred=p->p佗d; |將p結(jié)點(diǎn)從鏈表上摘下 p->pred-> next=pAnext;q=p->pred;|以下查找p結(jié)點(diǎn)的插入位直while(q !=L && q->freq<p->freq) q=q->pred; p->next=q->next; q->next->pred=p;| 將 p 結(jié)點(diǎn)插入 p->pred=q; q->next=p ;ret

26、urn (p); 0返回值為x的結(jié)點(diǎn)的捋針 II算法結(jié)束3.采用廣度優(yōu)先遍歷，其鄰接點(diǎn)均已遍歷的結(jié)點(diǎn)是葉子結(jié)點(diǎn)，記下結(jié)點(diǎn) 的半徑(以分枝個(gè)數(shù)記)int MiiiiRadius(AdjList g,int v)IlSg以鄰接表形式存儲(chǔ),求半徑最小的生成樹。設(shè)頂點(diǎn)信息就是編號(hào)從頂 點(diǎn)Y開始遍歷typed" structbit v, level; Juode; |隊(duì)列元索lilt MAX二1 0設(shè)最大層次數(shù)imvisiedMAXl=O： |訪問數(shù)組node R.QH； |Q為隊(duì)列，容量足夠大R.v=v; R.level=l;Makeiiullt(Q); EiiQueue(Q,R);whil

27、e(!Emptv(Q)(R=DeQueuG(Q); | 出隊(duì)v=R.v; l=R.lcvel; p=gv.firstcage; flag=0; |flag 是頂點(diǎn)是否是葉子的標(biāo)記 while(p)up->adjvex;if(visitedw=O) flag=1; R.level=l+1； EnQueue(R); p=p->next;if(flag=O) |其鄰接點(diǎn)均已遺歷的頂點(diǎn)是葉子結(jié)點(diǎn)if(l<MAX) MAX=1; renim MAX;2010年春A卷一、填空題(每空1分，共15分)1.在順序存儲(chǔ)的二叉樹中，編號(hào)為i和j的兩個(gè)結(jié)點(diǎn)處在同一層的條件是。2.某二叉樹的前序遍歷

28、序列是ABCDEFG,中序遍歷序列是CBDAFGE,則其后序遍歷序列是。3. 在有n個(gè)葉子的哈夫曼樹中，分支結(jié)點(diǎn)總數(shù)為個(gè)。4.對(duì)于含有n個(gè)頂點(diǎn)e條邊的連通圖，利用Prim算法求最小生成樹的時(shí)間復(fù)雜度為°5. 表達(dá)式a*(b+c)-d的后綴表達(dá)式是6. 假左一棵二叉樹的結(jié)點(diǎn)數(shù)為18,則它的最小深度為,最大深度為O7. 設(shè)有一個(gè)n階的下三角矩陣A,如果按照行的順序?qū)⑾氯蔷仃囍械脑?包括對(duì)角線上元素)存放在n(n+l)個(gè)連續(xù)的存儲(chǔ)單元中，則Aij與A00之間 有 個(gè)數(shù)據(jù)元素。8. 設(shè)一組初始記錄關(guān)鍵字序列為(20, 18, 22, 16, 30, 19),則根據(jù)這些初始關(guān)鍵字序列建成的

29、初始堆為。9. 磁盤文件的歸并技術(shù)有、o 10. 設(shè)有向圖G中有向邊的集合E二<1, 2>, <2, 3>, <1, 4>, <4, 2>,<4, 3>,則該圖的一種拓?fù)湫蛄袨?1設(shè)一組初始記錄關(guān)鍵字序列為(345, 253, 674, 924, 627),則用基數(shù)排序需要進(jìn)行趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。12.利用Dijkstra算法求從有向圖頂點(diǎn)vl到其他各頂點(diǎn)的最短路徑要求I邊上權(quán)值O二、選擇題(每題1分，共15分)1. 若某線性表最常用的操作是存取任一指立序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用存儲(chǔ)方式

30、最節(jié)省時(shí)間。扎順序表B.雙鏈表C.單循環(huán)鏈表D.帶頭結(jié)點(diǎn)的雙循環(huán)鏈表02. 在一個(gè)具有n個(gè)單元的順序棧中，假左以地址低端(即下標(biāo)為0的單元)作為棧底，以top作為棧頂指針，當(dāng)出棧時(shí)，top的變化為 o A. 不變B. top二0;=top-l;D. top二top+1;3. 設(shè)一組初始關(guān)鍵字記錄關(guān)鍵字為(20, 15, 14, 18, 21, 36, 40, 10),則以20為基準(zhǔn)記錄的一趟快速排序結(jié)朿后的結(jié)果為o A、 10, 15, 14, 18, 21, 36, 40,20B、 10, 15, 14, 18, 20, 40, 36, 21C、 10, 15, 14, 20,18, 40,

31、 36, 21D、 15, 10, 14, 18, 20, 36, 40, 214. 任何一棵二叉樹的葉子結(jié)點(diǎn)在前序、中序、后序遍歷序列中的相對(duì)次序。扎肯宦不發(fā)生改變 B.肯左發(fā)生改變C.不能確定D.有時(shí)發(fā)生變化5.用有向無(wú)環(huán)圖描述表達(dá)式(A+B)*(A+B)/A),至少需要頂點(diǎn)的數(shù)目為。B. 6C. 8D. 96.對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須。A、以順序方式存儲(chǔ)B、以鏈接方式存儲(chǔ)C、以順序方式存儲(chǔ)，且數(shù)據(jù)元素有序D、以鏈接方式存儲(chǔ)，且數(shù)據(jù)方式有序7. 設(shè)散列表表長(zhǎng)m二14,散列函數(shù)H(k)=k mod 11。表中已有15、38、61、84四個(gè)元素，如果用線性探側(cè)法處理沖突，則元素4

32、9的存儲(chǔ)地址是o扎 8B. 3C. 5D. 98. 若需在0(nlog2n)的時(shí)間內(nèi)完成對(duì)數(shù)組的排序，且要求排序是穩(wěn)立的，則可選擇的排序方法是° A.快速排序B.堆排序C.歸并排序D.插入排序)9. 下面關(guān)于m階B樹的說(shuō)法正確的是。每個(gè)結(jié)點(diǎn)至少有兩株非空子樹樹中每個(gè)結(jié)點(diǎn)至多有m-1個(gè)關(guān)鍵字所有的葉子都在同一層上當(dāng)插入一個(gè)記錄引起B(yǎng)樹分裂后，樹增高一層扎B.C.D.10. 已知一個(gè)有序表為(12, 18, 24, 35, 47, 50, 62, 83, 90, 115,134),當(dāng)折半查找值為90的元素時(shí)，經(jīng)過次比較后查找成功。11能有效縮短關(guān)鍵路徑長(zhǎng)度的方法是A.縮短任意一個(gè)活動(dòng)的持

33、續(xù)時(shí)間B. 縮短關(guān)鍵路徑上任意一個(gè)關(guān)鍵活動(dòng)的持續(xù)時(shí)間C. 縮短多條關(guān)鍵路徑上共有的任意一個(gè)關(guān)鍵活動(dòng)的持續(xù)時(shí)間D.縮短所有關(guān)鍵路徑上共有的任意一個(gè)關(guān)鍵活動(dòng)的持續(xù)時(shí)間12.在采用線性探測(cè)法處理沖突所構(gòu)成的 閉散列表上進(jìn)行查找，可能要探測(cè)多個(gè)位置，在査找成功的情況下，所探測(cè)的這些位宜的關(guān)鍵字值o扎一能都是同義詞B.定都不是同義詞 C.不一定都是同義詞 D.都相同13. 設(shè)哈夫曼編碼的長(zhǎng)度不超過4,若已對(duì)兩個(gè)字符編碼為1和01,則最多還可以對(duì)個(gè)字符編碼。A. 2 B. 3 C. 4 D. 514. 已知圖的鄰接表如下所示，根據(jù)算法，則從頂點(diǎn)0出發(fā)深度優(yōu)先遍歷的結(jié)點(diǎn)序列是o1 3 2B. 0 2 3 1

34、C. 0 3 2 1D. 0 12 315. 在具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是。(1)(n)(n2)(nlog2n)三、簡(jiǎn)答題：每題10分，共20分1. 一個(gè)按數(shù)組元素有序的一維數(shù)組一泄是堆嗎請(qǐng)說(shuō)明理由。2.設(shè)有一組初始記錄關(guān)鍵字為（45, 80, 48, 40, 22, 78）,可以構(gòu)適岀一棵二叉排序樹，若不是平衡樹則調(diào)整平衡，并給岀其前序遍歷該樹的序列，并寫出右旋轉(zhuǎn) 函數(shù)算法。四、算法設(shè)計(jì)：每題10分，共20分 要求：描述算法設(shè)計(jì)的基本思想描述算法的詳細(xì)實(shí)現(xiàn)步驟根據(jù)設(shè)計(jì)思想和實(shí)現(xiàn)步驟，采用程序設(shè)訃語(yǔ)言描述算法（使用C或C+或JAVA語(yǔ)言實(shí)）,關(guān)鍵之處請(qǐng)給岀

35、簡(jiǎn)要注釋。（棧、隊(duì)列的存儲(chǔ)結(jié)構(gòu)、基本操作可以直接引用）1.對(duì)給定的序號(hào)j （lVjVn）,要求在無(wú)序記錄AlAn中找到按關(guān)鍵碼從小到大排在第j位上的記錄，試?yán)每焖倥判虻膭澐炙枷朐O(shè)汁算法實(shí)現(xiàn)上述查 找。2設(shè)計(jì)算法，判斷以鄰接表存儲(chǔ)的有向圖中是否存在由頂點(diǎn)vi到頂點(diǎn)vj的路徑（iHj）。參考答案:一. 填空：=logj3. n-14.0（n2）+*d-6.518（i+l）/2+j-l8.16 18 19 20 30 229.多路歸并、I/O并行處理初始?xì)w并段產(chǎn)生，4,2,311.312.非負(fù) 二、單選：1A2C3A4A5A6C7A8C9B10A11D12C13C14D15B三、簡(jiǎn)答：1.按數(shù)組元

36、素有序的一維數(shù)組一左是堆。（4分）,Kn,則滿足非升序數(shù)組一泄是最小堆為例說(shuō)明如下：假設(shè)非升序數(shù)組為KI, K2,KI W K2,W W Kn,則一定滿足：Ki W K2i且KiW K2i+b即滿足最小堆的左義。同理可知，非降序數(shù)組一左是最大堆。因此，按數(shù)組元素有序的一維數(shù)組一上 是堆。（6分）前序:右旋轉(zhuǎn)函數(shù)：2.二叉平衡樹為 48, 40, 80, 22, 45, 78（3 分）48, 40, 22, 45, 80, 78（3 分）void R_Rotate（BSTree &p） lc=p->lchild;p->lchild=lc->rchiId;lc->r

37、child=p;P=lc; 四、算法1.1、本算法不要求將整個(gè)記錄進(jìn)行排序，而只進(jìn)行查找第j個(gè)記錄。(1) 基本思想：改進(jìn)劃分算法，是一次劃分將基準(zhǔn)元素左位于k,如果k二巧，則找到第j小 的元素；否則，遞歸地在k的左邊或右邊進(jìn)行劃分，直到k=j為止。(2) 算法詳細(xì)步驟：略(3)算法如下：int Search ( int A , int n, int j )s =1; t = nk = Partition( A, s, t);while ( k ! = j )辻(k < j ) k = Partition (A,k+1, t);elsek = Partition (A, s, k-1 );returnAj;int Partition (int A , int low , int high )if (i < j )A i+ 二 A j ;i = low; j = high;pivot :=A low ;while(i < j ) while(Aj >= pivot && i < j )whi.le ( Aij < pivot && i < j ) i +；if (i < j )A j二 A i ;A i = pivot; return i;2. int visitedMAXSIZE; irstarc:p