河海大學(xué)《算法與數(shù)據(jù)結(jié)構(gòu)》期末試題a卷及答案

1、專業(yè)課復(fù)習(xí)資料（最新版） 專業(yè)課復(fù)習(xí)資料（最新版）封面8. 對(duì)于一個(gè)具有 n 個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表示，則矩陣大小為________。9. 對(duì)于一個(gè)具有 n 個(gè)頂點(diǎn)和 e 條邊的連通圖，其生成樹中的頂點(diǎn)數(shù)和邊數(shù)分別為________和________。10．二分查找過程所對(duì)應(yīng)的判定樹既是一棵_______，又是一棵________。11. 若對(duì)長(zhǎng)度 n=1000 的線性表進(jìn)行二級(jí)索引存儲(chǔ)， 每級(jí)索引表中的索引項(xiàng)是下一級(jí) 10個(gè)記錄

2、的索引，則一級(jí)索引表的長(zhǎng)度為________，二級(jí)索引表的長(zhǎng)度為________。12．在一棵 13 階的 B_樹中，每個(gè)非樹根結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)目最少允許為________個(gè)， 最多允許為________個(gè)。13． 每次直接或通過基準(zhǔn)元素間接比較兩個(gè)元素， 若出現(xiàn)逆序排列時(shí)就交換它們的位置，此種排序方法叫做________排序； 每次使兩個(gè)相鄰的有序表合并成一個(gè)有序表的排序方法叫做________排序。14. 在歸并排序中， 進(jìn)行每趟歸并

3、的時(shí)間復(fù)雜度為________， 整個(gè)排序過程的時(shí)間復(fù)雜度為________，空間復(fù)雜度為________。三、運(yùn)算題（每小題 6 分，共 24 分）1. 假定一棵二叉樹廣義表表示為 A(B(,D),C(E(G),F))， 分別寫出對(duì)它進(jìn)行先序、 中序、按層遍歷的結(jié)果。先序：中序：按層：2．已知一個(gè)有向圖的頂點(diǎn)集 V 和邊集 G 分別為：V={a,b,c,d,e,f,g,h};E={,,,,,,,,,};假定該圖采用鄰接矩陣表示， 則分

4、別寫出從頂點(diǎn) a 出發(fā)進(jìn)行深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列。深度優(yōu)先搜索序列：廣度優(yōu)先搜索序列：3．假定對(duì)線性表(38,25,74,52,48,65,36)進(jìn)行散列存儲(chǔ)，采用 H(K)=K % 9 作為散列函數(shù)，若分別采用線性探查法和鏈接法處理沖突，則對(duì)應(yīng) 的平均查找長(zhǎng)度分別為_______和________。4. 假定一組記錄的排序碼為(46,79,56,38,40,80,25,34,57,21)， 則對(duì)其進(jìn)行快速排序