【正文】 B. 37/12 C. 39/12 D. 43/129．對(duì)于靜態(tài)表的順序查找法，若在表頭設(shè)置崗哨，則正確的查找方式為 。10．解決散列法中出現(xiàn)的沖突問題常采用的方法是 。、除余法、平方取中法、除余法、線性探測(cè)法、線性探測(cè)法、多重散列法、多重散列法、鏈地址法11．采用線性探測(cè)法解決沖突問題，所產(chǎn)生的一系列后繼散列地址 。12．對(duì)于查找表的查找過程中，若被查找的數(shù)據(jù)元素不存在，則把該數(shù)據(jù)元素插入到集合中。這種方式主要適合于 。 D兩種表都不適合 。 填空題（將正確的答案填在相應(yīng)的空中）；折半查找法的平均查找長(zhǎng)度為____；哈希表查找法采用鏈接法處理沖突時(shí)的平均查找長(zhǎng)度為____。，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無關(guān)的查找方法是____。，且是____。4. 假設(shè)在有序線性表A[1..20]上進(jìn)行折半查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為____，則比較二次查找成功的結(jié)點(diǎn)數(shù)為____，則比較三次查找成功的結(jié)點(diǎn)數(shù)為____，則比較四次查找成功的結(jié)點(diǎn)數(shù)為____，則比較五次查找成功的結(jié)點(diǎn)數(shù)為____，平均查找長(zhǎng)度為____。5. 對(duì)于長(zhǎng)度為n的線性表，若進(jìn)行順序查找，則時(shí)間復(fù)雜度為____；若采用折半法查找，則時(shí)間復(fù)雜度為____；6．已知有序表為（12，18，24，35，47，50，62，83，90，115，134），當(dāng)用折半查找90時(shí)，需進(jìn)行 次查找可確定成功；查找47時(shí)，需進(jìn)行 次查找成功；查找100時(shí)，需進(jìn)行 次查找才能確定不成功。7．二叉排序樹的查找長(zhǎng)度不僅與 有關(guān)，也與二叉排序樹的 有關(guān)。8．一個(gè)無序序列可以通過構(gòu)造一棵 樹而變成一個(gè)有序樹，構(gòu)造樹的過程即為對(duì)無序序列進(jìn)行排序的過程。9．平衡二叉排序樹上任一結(jié)點(diǎn)的平衡因子只可能是 、 或 。10． 法構(gòu)造的哈希函數(shù)肯定不會(huì)發(fā)生沖突。11．在散列函數(shù)H(key)=key%p中，p應(yīng)取____。12．在散列存儲(chǔ)中，裝填因子的值越大，則____；的值越小，則____。 綜合練習(xí)題:1. 畫出對(duì)長(zhǎng)度為10的有序表進(jìn)行折半查找的判定樹，并求其等概率時(shí)查找成功的平均查找長(zhǎng)度。4. 選取哈稀函數(shù)H（k）=（3k）MOD 11。用開放定址法處理沖突，di=i（（7k）MOD 10+1）（I=1，2，3，…）.試在010的散列地址空間中對(duì)關(guān)鍵字序列（22,41,53,46,30,13,01,67）造哈希表，并求等概率情況下查找成功時(shí)的平均查找長(zhǎng)度。5. 已知一組關(guān)鍵字{49，38，65，97，76，13，27，44，82，35，50}，畫出由此生成的二叉排序樹，注意邊插入邊平衡。 習(xí)題答案 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. 順序存儲(chǔ)結(jié)構(gòu)、有序的 4. 3．7（依題意，構(gòu)造一棵有序二叉樹，共12個(gè)結(jié)點(diǎn)，第一層1個(gè)結(jié)點(diǎn)，第二層2個(gè)結(jié)點(diǎn)，第三層4個(gè)結(jié)點(diǎn)，第四層5個(gè)結(jié)點(diǎn)，則：ASL=（1*1+2*2+3*4+4*5）/12=37/12） 5. O（n）、O(log2n) 6．3 7．結(jié)點(diǎn)個(gè)數(shù)n、生成過程 8．二叉排序樹 9．0、1 10．直接定址11．素?cái)?shù)12．存取元素時(shí)發(fā)生沖突的可能性就越大、存取元素時(shí)發(fā)生沖突的可能性就越小習(xí)題9 排序 單項(xiàng)選擇題1. 在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是____。A. 希爾排序 B. 起泡排序 C. 插入排序 D. 選擇排序2. 設(shè)有1000個(gè)無序的元素，希望用最快的速度挑選出其中前10個(gè)最大的元素，最好選用____排序法。A. 起泡排序 B. 快速排序 C. 堆排序 D. 基數(shù)排序3. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是____。A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序4. 一組記錄的排序碼為（46，79，56，38，40，84），則利用堆排序的方法建立的初始堆為____。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. 一組記錄的關(guān)鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一次劃分結(jié)果為____。A. 38，40，46，56，79，84 B. 40，38，46，79，56，84C. 40，38，46，56，79，84 D. 40，38，46，84，56，796. 一組記錄的排序碼為（25，48，16，35，79，82，23，40，36，72），其中含有5個(gè)長(zhǎng)度為2的有序表，按歸并排序的方法對(duì)該序列進(jìn)行一趟歸并后的結(jié)果為____。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. 排序方法中，從未排序序列中依次取出元素與已排序序列（初始時(shí)為空）中的元素進(jìn)行比較，將其放入已排序序列的正確位置上的方法，稱為____。A. 希爾排序 B. 起泡排序 C. 插入排序 D. 選擇排序8. 排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列（初始時(shí)為空）的一端的方法，稱為____。A. 希爾排序 B. 歸并排序 C. 插入排序 D. 選擇排序9. 用某種排序方法對(duì)線性表（ 25，84，21，47，15，27，68，35，20）進(jìn)行排序時(shí)，元素序列的變化情況如下：⑴ 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. 選擇排序 B. 希爾排序 C. 歸并排序 D. 快速排序10. 下述幾種排序方法中，平均查找長(zhǎng)度最小的是____。A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序11. 下述幾種排序方法中，要求內(nèi)存量最大的是____。A. 插入排序 B. 選擇排序 C. 快速排序 D. 歸并排序12. 快速排序方法在____情況下最不利于發(fā)揮其長(zhǎng)處。A. 要排序的數(shù)據(jù)量太大 B. 要排序的數(shù)據(jù)中含有多個(gè)相同值 C. 要排序的數(shù)據(jù)已基本有序 D. 要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù) 填空題 （將正確的答案填在相應(yīng)的空中）1. 在對(duì)一組記錄（54，38，96，23，15，72，60，45，83）進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置需比較____。2. 在利用快速排序方法對(duì)一組記錄（54，38，96，23，15，72，60，45，83）進(jìn)行快速排序時(shí)，遞歸調(diào)用而使用的棧所能達(dá)到的最大深度為____，共需遞歸調(diào)用的次數(shù)為____，其中第二次遞歸調(diào)用是對(duì)____一組記錄進(jìn)行快速排序。3. 在堆排序，快速排序和歸并排序中，若只從存儲(chǔ)空間考慮，則應(yīng)首先選取____方法，其次選取____方法，最后選取____方法；若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng)選取____方法；若只從平均情況下排序最快考慮，則應(yīng)選取____方法；若只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮，則應(yīng)選取____方法。4. 在插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中，排序是不穩(wěn)定的有____。5. 在在插入排序、希爾排序、選擇排序、快速排序、堆排序、歸并排序和基數(shù)排序中，平均比較次數(shù)最少的排序是____，需要內(nèi)存容量最多的是____。6. 在堆排序和快速排序中，若原始記錄接近正序或反序，則選用____，若原始記錄無序，則最好選用____。7. 在插入和選擇排序中，若初始數(shù)據(jù)基本正序，則選用____；若初始數(shù)據(jù)基本反序，則選用____。8. 對(duì)n個(gè)元素的序列進(jìn)行起泡排序時(shí)，最少的比較次數(shù)是____。 綜合題1. 以關(guān)鍵碼序列（503,087,512,061,908,170,897,275,653,426），為例，手工執(zhí)行以下排序算法，寫出每一趟排序結(jié)束時(shí)的關(guān)鍵碼狀態(tài)：（1） 直接插入排序；（2） 希爾排序（增量d[1]=5）；（3） 快速排序；（4） 堆排序；（5） 歸并排序；（6） 基數(shù)排序。2. 判別以下序列是否為堆（小頂堆或大頂堆）。如果不是，則把它調(diào)整為堆（要求記錄交換次數(shù)最少）。(1）(100,86,48,73,35,39,42,57,66,21)。(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).習(xí)題答案 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。 4。 （23，38，15） 3. 堆排序、快速排序、歸并排序、歸并排序、快速排序、堆排序 4. 希爾排序、選擇排序、快速排序和堆排序 5. 快速排序、基數(shù)排序 6. 堆排序、快速排序 7. 插入排序、選擇排序 8. n1