【正文】 （23，38，15） 3. 堆排序、快速排序、歸并排序、歸并排序、快速排序、堆排序 4. 希爾排序、選擇排序、快速排序和堆排序 5. 快速排序、基數(shù)排序 6. 堆排序、快速排序 7. 插入排序、選擇排序 8. n1。(2)(12,70,33,65,24,56,48,92,86,33)(3)(103,97,56,38,66,23,42,12,30,52,06,20)(4)(05,56,20,23,40,38,29,61,35,76,28,100).習題答案 1. D 2. C 3. A 4. B 5. C 6. A 7. C 8. D 10. C 11. D 12. C 1. 5 2. 2。如果不是，則把它調(diào)整為堆（要求記錄交換次數(shù)最少）。 綜合題1. 以關鍵碼序列（503,087,512,061,908,170,897,275,653,426），為例，手工執(zhí)行以下排序算法，寫出每一趟排序結(jié)束時的關鍵碼狀態(tài)：（1） 直接插入排序；（2） 希爾排序（增量d[1]=5）；（3） 快速排序；（4） 堆排序；（5） 歸并排序；（6） 基數(shù)排序。7. 在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用____；若初始數(shù)據(jù)基本反序，則選用____。5. 在在插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中，平均比較次數(shù)最少的排序是____，需要內(nèi)存容量最多的是____。3. 在堆排序，快速排序和歸并排序中，若只從存儲空間考慮，則應首先選取____方法，其次選取____方法，最后選取____方法；若只從排序結(jié)果的穩(wěn)定性考慮，則應選取____方法；若只從平均情況下排序最快考慮，則應選取____方法；若只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮，則應選取____方法。A. 要排序的數(shù)據(jù)量太大 B. 要排序的數(shù)據(jù)中含有多個相同值 C. 要排序的數(shù)據(jù)已基本有序 D. 要排序的數(shù)據(jù)個數(shù)為奇數(shù) 填空題 （將正確的答案填在相應的空中）1. 在對一組記錄（54，38，96，23，15，72，60，45，83）進行直接插入排序時，當把第7個記錄60插入到有序表時，為尋找插入位置需比較____。A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序11. 下述幾種排序方法中，要求內(nèi)存量最大的是____。A. 希爾排序 B. 歸并排序 C. 插入排序 D. 選擇排序9. 用某種排序方法對線性表（ 25，84，21，47，15，27，68，35，20）進行排序時，元素序列的變化情況如下：⑴ 25，84，21，47，15，27，68，35，20⑵ 20，15，21，25，47，27，68，35，84⑶ 15，20，21，25，35，27，47，68，84⑷ 15，20，21，25，27，35，47，68，84則所采用的排序方法是____。A. 16，25，35，48，23，40，79，82，36，72 B. 16，25，35，48，79，82，23，36，40，72C. 16，25，48，35，79，82，23，36，40，72D. 16，25，35，48，79，23，36，40，72，827. 排序方法中，從未排序序列中依次取出元素與已排序序列（初始時為空）中的元素進行比較，將其放入已排序序列的正確位置上的方法，稱為____。A. 79，46，56，38，40，80 B. 38，46, 56，79， 40，84，C. 84，79，56，46，40，38 D. 84，56，79，40，46，385. 一組記錄的關鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結(jié)果為____。A. 起泡排序 B. 快速排序 C. 堆排序 D. 基數(shù)排序3. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是____。 習題答案 1．B 2．C 3．C 4．D 5．B 6．C 7．D 8．B 9．C 10．D 11．C 12．B 13．C 1. （n+1）/2 、((n+1)*log2(n+1))/n1 、1+（為裝填因子） 2. 哈希表查找法 3. 順序存儲結(jié)構、有序的 4. 3．7（依題意，構造一棵有序二叉樹，共12個結(jié)點，第一層1個結(jié)點，第二層2個結(jié)點，第三層4個結(jié)點，第四層5個結(jié)點，則：ASL=（1*1+2*2+3*4+4*5）/12=37/12） 5. O（n）、O(log2n) 6．3 7．結(jié)點個數(shù)n、生成過程 8．二叉排序樹 9．0、1 10．直接定址11．素數(shù)12．存取元素時發(fā)生沖突的可能性就越大、存取元素時發(fā)生沖突的可能性就越小習題9 排序 單項選擇題1. 在所有排序方法中，關鍵字比較的次數(shù)與記錄的初始排列次序無關的是____。用開放定址法處理沖突，di=i（（7k）MOD 10+1）（I=1，2，3，…）.試在010的散列地址空間中對關鍵字序列（22,41,53,46,30,13,01,67）造哈希表，并求等概率情況下查找成功時的平均查找長度。 綜合練習題:1. 畫出對長度為10的有序表進行折半查找的判定樹，并求其等概率時查找成功的平均查找長度。11．在散列函數(shù)H(key)=key%p中，p應取____。9．平衡二叉排序樹上任一結(jié)點的平衡因子只可能是 、 或 。7．二叉排序樹的查找長度不僅與 有關，也與二叉排序樹的 有關。4. 假設在有序線性表A[1..20]上進行折半查找，則比較一次查找成功的結(jié)點數(shù)為____，則比較二次查找成功的結(jié)點數(shù)為____，則比較三次查找成功的結(jié)點數(shù)為____，則比較四次查找成功的結(jié)點數(shù)為____，則比較五次查找成功的結(jié)點數(shù)為____，平均查找長度為____。，平均查找長度與結(jié)點個數(shù)n無關的查找方法是____。 D兩種表都不適合 。12．對于查找表的查找過程中，若被查找的數(shù)據(jù)元素不存在，則把該數(shù)據(jù)元素插入到集合中。10．解決散列法中出現(xiàn)的沖突問題常采用的方法是 。A. 8 B. 3 C. 5 D. 9，按二分查找法對該表進行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為____。 addr (61)=6。表中已有4個結(jié)點：addr (15)=4。A. 相同 B. 不相同{1，3，9，12，32，41，45，62，75，77，82，95，100}，當二分查找值82為的結(jié)點時，____次比較后查找成功。A. 以順序方式存儲 B. 以鏈接方式存儲C. 以順序方式存儲，且結(jié)點按關鍵字有序排序D. 以鏈接方式存儲，且結(jié)點按關鍵字有序排序，每個元素的平均查找長度為____.A. n B. n/2 C. (n+1)/2 D. (n1)/2，每個元素的平均查找長度為____。(3)關鍵路徑為：（V1，V2，V5，V7，V9）和（V1，V2， V5，V8，V9，）習題8 查找 單項選擇題。0 3. 1 ,v2,v3,v6,v5, v4；v1,v2,v5,v4,v3, v6 6. 將矩陣第i行全部置為零；O（e）（e為圖中的邊數(shù)）；O（e）；遍歷圖的順序不同；DFS采用棧存儲訪問過的結(jié)點，BFS采用隊列存儲訪問過的結(jié)點。(3)求出該AOE網(wǎng)的關鍵路徑。543223356abdfce5．已知AOE網(wǎng)有9個結(jié)點：V1，V2，V3，V4，V5，V6，V7，V8，V9，其鄰接矩陣如下：(1)請畫出該AOE圖。5一個有向圖badcef161115151516131412212．、： （1） 61213212495201516106154372（2） 3．。 綜合題1562431．，請給出該圖的:（1）每個頂點的入/出度；（2）鄰接距陣；（3）鄰接表；（4）逆鄰接表；（5）強連通分量。12．若無向圖G的頂點度數(shù)最小值大于等于 時，G至少有一條回路。10．一個圖的 表示法是唯一的，而 表示法是不唯一的。9．遍歷圖的過程實質(zhì)上是 。7．如果含n個頂點的圖形成一個環(huán)，則它有 棵生成樹。v1v3v2v4v5v6v2v5v4v3v5^^v6v4v6v3 圖G的鄰接表5．已知一個有向圖的鄰接矩陣表示，計算第i個結(jié)點的入度的方法是____。3．在無向圖G的鄰接矩陣A中，若A[i][j]等于1，則A[j][i ]等于____。 +k2 填空題（將正確的答案填在相應餓空中）1．n個頂點的連通圖至少____條邊。 +120．對于一個有向圖，若一個頂點的入度為k1,、出