數(shù)據(jù)結(jié)構(gòu)練習(xí)3答案

1、數(shù)據(jù)結(jié)構(gòu)練習(xí)（三）參考一、選擇題1.順序查找法適合于存儲(chǔ)結(jié)構(gòu)為 的線性表A）哈希存儲(chǔ) B）順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)C）壓縮存儲(chǔ) D）索引存儲(chǔ)2.一個(gè)長(zhǎng)度為100的已排好序的表，用二分查找法進(jìn)行查找，若查找不成功，至少比較_次。A）9B）8C）7D）63.采用順序查找方法查找長(zhǎng)度為n的線性表時(shí)，平均比較次數(shù)為 。A）n B）n/2C）（n+1）/2D）（n-1）/24.對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須 。A）以順序方式存儲(chǔ)B）以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列C）以鏈表方式存儲(chǔ)D）以鏈表方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排列5.采用二分查找法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為 。A）

2、O（n2）B）O（nlog2n）C）O（n）D）O（log2n）6.有一個(gè)長(zhǎng)度為12的有序表R011，按折半查找法對(duì)該表進(jìn)行查找，在表內(nèi)各元素等概率查找情況下查找成功所需的平均比較次數(shù)為 。A）35/12B）37/12C）39/12D）43/127.有一個(gè)有序表為1，3，9，12，32，41，45，62，75，77，82，95，99，當(dāng)采用折半查找法查找關(guān)鍵字為82的元素時(shí)， 次比較后查找成功。A）1B.2C）4D）88.當(dāng)采用分塊查找時(shí)，數(shù)據(jù)的組織方式為 。A）數(shù)據(jù)分成若干塊，每塊內(nèi)存數(shù)據(jù)有序B）數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序，每塊內(nèi)最大(或最小)的數(shù)據(jù)組成索引塊C）數(shù)據(jù)

3、分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大（或最小）的數(shù)據(jù)組成索引塊D）數(shù)據(jù)分成若干塊，每塊（出最后一塊外）中的數(shù)據(jù)個(gè)數(shù)需相同9.采用分塊查找時(shí)，若線性表中共有625個(gè)元素，查找每個(gè)元素的概率相同，假設(shè)采用順序查找來(lái)確定結(jié)點(diǎn)所在的塊時(shí)，每塊應(yīng)有 個(gè)結(jié)點(diǎn)最佳。A）10B）25C）6D）62510. 不能生成右圖所示二叉排序樹(shù)的關(guān)鍵字序列是_。A）45312B）42531C）45213D）4231511.按_遍歷二叉排序樹(shù)，可以得到按值遞增或遞減次序的關(guān)鍵碼序列。A）先序B）中序C）后序D）層序12.在一棵平衡二叉樹(shù)中，每個(gè)結(jié)點(diǎn)的平衡因子的取值范圍是 。A）-11B）-22C）12D）0113.具有5

4、層結(jié)點(diǎn)的AVL樹(shù)至少有 個(gè)結(jié)點(diǎn)A）10B）12C）15D）1714.在含有15個(gè)結(jié)點(diǎn)的平衡二叉樹(shù)上，查找關(guān)鍵字為28的結(jié)點(diǎn)，則依次比較的關(guān)鍵字可能是 。A）30，36B）38，48，28C）48，18，38，28 D）60，30，50，40，38，3615.一棵深度為k的平衡二叉樹(shù)，其每個(gè)非葉子結(jié)點(diǎn)的平衡因子均為0，則該樹(shù)共有 個(gè)結(jié)點(diǎn)。A）2k-1-1 B）2k-1 C）2k-1 +1 D）2k-116.查找效率最高的二叉排序樹(shù)是 。A所有結(jié)點(diǎn)的左子樹(shù)都為空的二叉排序樹(shù)B所有節(jié)點(diǎn)的右子樹(shù)都為空的二叉排序樹(shù)C平衡二叉樹(shù)D沒(méi)有左子樹(shù)的二叉排序樹(shù)17.下面關(guān)于B-樹(shù)和B+樹(shù)的敘述中，不正確的結(jié)論是

5、。A）B-樹(shù)和B+樹(shù)都能有效地支持順序查找B）B-樹(shù)和B+樹(shù)都能有效地支持隨機(jī)查找C）B-樹(shù)和B+樹(shù)都是平衡的多分支樹(shù)D）B-樹(shù)和B+樹(shù)都可用于文件索引結(jié)構(gòu)18.設(shè)有n個(gè)關(guān)鍵字，哈希查找法的平均查找長(zhǎng)度是 。A）O（1）B）O（n）C）O（log2n）D）O（n2）19.將10個(gè)元素散列到100000個(gè)單元的哈希表，則 產(chǎn)生沖突。A）一定會(huì)B）一定不會(huì)C）仍可能會(huì)D）以上都不對(duì)20.設(shè)哈希表長(zhǎng) m=14，哈希函數(shù)H（key）=key Mod 11.表中已有4個(gè)結(jié)點(diǎn)H（15）=4，H（38）=5，H（61）=6，H（84）=7，其余地址為空，如用二次探測(cè)再散列法處理沖突，則關(guān)鍵字為49的結(jié)點(diǎn)的地

6、址是 。A）8B）3C）5D）921.假設(shè)有k個(gè)關(guān)鍵字互為同義詞，若用線性探測(cè)再散列法把這k個(gè)關(guān)鍵字存入哈希表中，至少要進(jìn)行 次探查。A）k-1B）kC）k+1D）k（k+1）/222.若采用鏈地執(zhí)法構(gòu)造哈希表，哈希函數(shù)為H（key）=key Mod 17，則需 （1） 個(gè)鏈表，這些鏈表的首指針構(gòu)成一個(gè)指針數(shù)組，該數(shù)組的下標(biāo)范圍為 （2）。（1）A）17B）13C）16D）任意（2）A）017 B）117 C）016 D）11623.直接插入排序在最好情況下的時(shí)間復(fù)雜度為 。A）O（n）B）O（nlog2n）C）O（log2n）D）O（n2）24.穩(wěn)定的排序算法是 。A）直接插入排序B）直接選

7、擇排序 C）堆排序D）快速排序25.數(shù)據(jù)序列8，9，10，4，5，6，20，1，2只能是 算法的兩趟排序后的結(jié)果。A）直接選擇排序B）冒泡排序C）直接插入排序D）堆排序26.對(duì)數(shù)據(jù)序列15，9，7，8，20，-1，4進(jìn)行排序，進(jìn)行一趟后數(shù)據(jù)的排序變?yōu)?，15，7，8，20，-1，4，則采用的是 算法。A）直接選擇排序 B）冒泡排序C）直接插入排序D）堆排序27.以下排序方法中， 在初始序列已基本有序的情況下，排序效率最高。A）歸并排序B）直接插入排序C）快速排序D）堆排序28.不穩(wěn)定的排序方法是 。A）冒泡排序B）直接插入排序 C）希爾排序 D）歸并排序29.以下排序算法中， 不能保證每趟排序

8、至少能將一個(gè)元素放到其最終位置上。A）快速排序 B）希爾排序 C）堆排序D）冒泡排序30.在以下排序方法中,關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)的是 。A）希爾排序B）冒泡排序C）插入排序D）直接選擇排序31.在排序算法中，每次從未排序的記錄中選取最?。ɑ蜃畲螅╆P(guān)鍵字的記錄，加入到已排序記錄的末尾，該排序方法是 。A）希爾排序B）冒泡排序C）插入排序D）直接選擇排序32.采用直接選擇排列，比較次數(shù)與移動(dòng)次數(shù)分別是 。A）O（n），O（log2n）B）O（log2n），O（n2）C）O（n2），O（n）D）O（n log2n），O（n）33.以下序列不是堆的是 。A）100，85，98，77

9、，80，60，82，40，20，10，66B）100，98，85，82，80，77，66，60，40，20，10C）10，20，40，60，66，77，80，82，85，98，100D）100，85，40，77，80，60，66，98，82，10，2034.堆排序是 （1） 類排序，堆排序平均時(shí)間復(fù)雜度和需要附加的存儲(chǔ)空間復(fù)雜度分別是 （2） 。（1）.A）插入 B）交換 C）歸并 D）選擇（2）.A）O（n2）和O（1） B）O（nlog2n）和O（1）C）O（nlog2n）和O（n） D）O（n2）和O（n）35.對(duì)n個(gè)記錄的文件進(jìn)行堆排序，最壞情況下的執(zhí)行時(shí)間是 。A）O（log2n）

10、B）（n） C）O（nlog2n） D）O（n2）36.設(shè)有1000個(gè)無(wú)序的元素，希望用最快的速度挑選出其中前10個(gè)最大的元素，最好選用 排序法。A）冒泡排序 B）快速排序 C）堆排序 D）基數(shù)排序37.在非空m階B樹(shù)上，除根結(jié)點(diǎn)以外的所有其他非終端結(jié)點(diǎn) 。A）至少有棵子樹(shù) B）至多有棵子樹(shù)C）至少有棵子樹(shù) C）至少有棵子樹(shù)38.對(duì)于哈希函數(shù)H(key)=key%13，被稱為同義詞的關(guān)鍵字是_。A）35和41B）23和39C）15和44D）25和5139.堆的形狀是一棵_。A）二叉排序樹(shù)B）滿二叉樹(shù)C）完全二叉樹(shù)D）不是二叉樹(shù)40.以下 法在數(shù)據(jù)基本有序時(shí)效率最好。A）快速排序B）冒泡排序C）

11、堆排序D）希爾排序41.快速排序在 情況下最不利于發(fā)揮其長(zhǎng)處。A）要排序的數(shù)據(jù)量太大 B）要排序的數(shù)據(jù)中含有多個(gè)相同值C）要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù)D）要排序的數(shù)據(jù)已基本有序42.下列序列中，_是執(zhí)行第一趟快速排序后得到的序列(關(guān)鍵字為字符串)A. da,ax,eb,cd,bbffha,gc B. cd,eb,ax,daffha,gc,bbC. gc,ax,eb,cd,bbffda,ha D. ax,bb,cd,daffeb,gc,ha43.一個(gè)記錄的關(guān)鍵字為46，79，56，38，40，84，采用快速排序以第一個(gè)記錄為基準(zhǔn)得到的第一次劃分結(jié)果為_(kāi)。A）38,40,46,56,38,79,84B）

12、40,38,46,79,56,84C）40,38,46,56,79,84D）40,38,46,56,7944.對(duì)下列關(guān)鍵字序列用快速排序法進(jìn)行排序時(shí)，速度最快的情形是_。A）21，25，5，17，9，23，30B）25,23,30,17,21,5,9C）21,9,17,30,25,23,5D）5,9,17,21,23,25,3045.下列排序方法中， 在一趟結(jié)束后不一定能選出一個(gè)元素放在其最終位置上。A）直接選擇排序B）冒泡排序C）歸并排序D）堆排序46.將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是 。A）n B）2n-1 C）2n D）n-1二、填空題：1.在n個(gè)記錄的有序

13、順序表中進(jìn)行折半查找,最大的比較次數(shù)是 log2n +1 。2.設(shè)線性表a1，a2，a500的元素的值從小到大排列，對(duì)一個(gè)給定的K的值用二分法查找線性表，在查找不成功的情況下至多需要比較 log2n +1 次3.在直接插入排序、希爾排序、直接選擇排序、快速排序、堆排序和歸并排序中，平均比較次數(shù)最少的排序方法是 快速排序 。4.一棵深度為h的B-樹(shù)，任一個(gè)葉子結(jié)點(diǎn)所處的層數(shù)為 h ，當(dāng)向B-樹(shù)插入一個(gè)新關(guān)鍵字時(shí)，為檢索插入位置需讀取 h-1 個(gè)結(jié)點(diǎn)。5.評(píng)價(jià)哈希表好壞的標(biāo)準(zhǔn)是 哈希表的均勻性 。6.在各種查找方法中，其平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方法是 哈希表查找 。7.設(shè)用希爾排序?qū)?shù)序

14、98，36，-9，0，47，23，1，8，10，7進(jìn)行排序，給出的不長(zhǎng)（也稱增量序列）依次是4、2、1，則排序需 3 趟，寫(xiě)出第一趟結(jié)束后，數(shù)序中數(shù)據(jù)的排列次序是 10,7,-9,0,47,23,1,8,98,36 。三、判斷題1.順序查找法適用于存儲(chǔ)結(jié)構(gòu)為順序或鏈?zhǔn)酱鎯?chǔ)的線性表2.順序查找方法只能在順序存儲(chǔ)結(jié)構(gòu)上進(jìn)行3.折半查找可以在有序的雙向鏈表上進(jìn)行4.分塊查找的效率與線性表被分成多少塊有關(guān)5.在二叉排序樹(shù)中，每個(gè)結(jié)點(diǎn)的關(guān)鍵字都比左孩子關(guān)鍵字大，比右孩子關(guān)鍵字小6.每個(gè)結(jié)點(diǎn)的關(guān)鍵字都比左孩子關(guān)鍵字大，比右孩子關(guān)鍵字小，這樣的二叉樹(shù)都是二叉排序樹(shù)7.在二叉排序樹(shù)中，新插入的關(guān)鍵字總是處于最

15、低層8.在二叉排序樹(shù)中，新結(jié)點(diǎn)總是作為葉子結(jié)點(diǎn)來(lái)插入的9.二叉排序樹(shù)的查找效率和二叉排序樹(shù)的高度有關(guān)10.在平衡二叉排序樹(shù)中，每個(gè)結(jié)點(diǎn)的平衡因子值都是相等的11.在平衡二叉排序樹(shù)中，以每個(gè)分支結(jié)點(diǎn)為根的子樹(shù)都是平衡的。12.哈希存儲(chǔ)法只能存儲(chǔ)數(shù)據(jù)元素的值，不能存儲(chǔ)數(shù)據(jù)元素之間的關(guān)系。13.哈希沖突是指同一個(gè)關(guān)鍵字對(duì)應(yīng)多個(gè)不同的哈希地址。14.哈希查找過(guò)程中，關(guān)鍵字的比較次數(shù)和哈希表中關(guān)鍵字的個(gè)數(shù)直接相關(guān)。15.在用線性探測(cè)法處理沖突的哈希表中，哈希函數(shù)值相同的關(guān)鍵字總是存在一片連續(xù)的存儲(chǔ)單元中。16.若哈希表的裝填因子a1,則可避免沖突的發(fā)生。17.哈希表的查找效率主要取決于哈希表造表時(shí)選取的

16、哈希函數(shù)和處理沖突的方法。四、簡(jiǎn)答題：1.若對(duì)具有n個(gè)元素的有序的順序表和無(wú)序的順序表分別進(jìn)行順序查找，試在下述兩種情況下分別討論兩者在等概率時(shí)的平均查找長(zhǎng)度；（1）查找不成功，即表中無(wú)關(guān)鍵字等于給定值k的記錄（2）查找成功，即表中有關(guān)鍵字等于給定值k的記錄2.已知一個(gè)有序表為12，18，20，25，29，32，40，62，83，90，95，98，當(dāng)折半查找值 29和90的元素時(shí)，分別需要多少次比較才能查找成功？若采用順序查找時(shí)（從前往后找），分別需要多少次比較才能成功？ 4，4，5，103.比較靜態(tài)查找表的3種查找方法4.請(qǐng)回答下列關(guān)于堆的問(wèn)題（1）堆的存儲(chǔ)表示是順序的，還是鏈接的？（2）設(shè)

17、有一個(gè)最小堆(小根堆)，即堆中任意結(jié)點(diǎn)的關(guān)鍵字均小于它的左孩子和右孩子的關(guān)鍵字。其具有最大關(guān)鍵字的元素可能在什么地方？ 葉子5.指出堆和二叉排序樹(shù)的區(qū)別。6.二叉排序樹(shù)的結(jié)構(gòu)如圖所示，其中各結(jié)點(diǎn)的關(guān)鍵字依次為3240，請(qǐng)你標(biāo)出各結(jié)點(diǎn)的關(guān)鍵字。7.關(guān)鍵字序列為：1，2，6，7，11，4，8，13，10，5，17，9，16，20，3，12，14，16，18，19，15，創(chuàng)建一棵5階B-樹(shù)，對(duì)于該B-樹(shù)，給出刪除8，16，15，4等4個(gè)關(guān)鍵字的過(guò)程。8.已知一組關(guān)鍵字為21，33，12，40，68，59，25，51，試依次插入關(guān)鍵字生成一棵3階B-樹(shù)；如果此后刪除40，畫(huà)出每一步執(zhí)行后B-樹(shù)的狀態(tài)。

18、9.已知哈希函數(shù)H(k)=2*k Mod 11，用二次探測(cè)再散列法處理沖突，為關(guān)鍵字序列（6，8，10，17，20，23，53，41，54，57）構(gòu)造哈希表，并計(jì)算查找成功、不成功時(shí)的平均查找長(zhǎng)度。10.比較直接插入排序和希爾排序的不同點(diǎn)。11.在實(shí)現(xiàn)插入排序過(guò)程中，可以用折半查找來(lái)確定第i個(gè)元素在前i-1個(gè)元素中的可能插入位置，這樣做能否改善插入排序的時(shí)間復(fù)雜度？為什么？12.在堆排序、快速排序和歸并排序中：（1）若只從存儲(chǔ)空間考慮，則應(yīng)首先選取哪種排序方法，其次選取哪種排序方法，最后選取哪種排序方法？堆排序、快速排序、歸并排序（2）若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng)選取哪種排序方法？歸并排序

19、（3）若只從平均情況下排序最快考慮，則應(yīng)選取哪種排序方法？快速排序（4）若只從最壞情況下排序最快并且要節(jié)省內(nèi)存考慮，則應(yīng)選取哪種排序方法？堆排序13.判別以下序列是否是大頂堆，如果不是，則把它調(diào)整為大頂堆。 86，48，73，35，39，42，57，66，21，100不是14.已知哈希表地址空間為0到7，哈希函數(shù)為H(k)=k %8，采用線性探測(cè)再散列法和鏈地址法處理沖突，將以下各數(shù)依次存入該哈希表中，請(qǐng)分別構(gòu)造哈希表，并分別計(jì)算平均查找長(zhǎng)度。 240,29,345,189,100,20,21,35ASL=（1+1+1+2+1+4+6+1）/8=17/8ASL=（1+1+1+1+2+1+2+3

20、）/8=12/8=0.7515.請(qǐng)為17題數(shù)列構(gòu)造一棵平衡的二叉排序樹(shù)，并計(jì)算ASL。ASL=(1+2*2+4*3+5*3)/10=32/10=3.216.有n個(gè)有序的數(shù)據(jù)構(gòu)成一個(gè)數(shù)列，查找某個(gè)元素時(shí)最多要進(jìn)行幾次比較？當(dāng)n=12，在等概率情況下查找成功的平均查找長(zhǎng)度是多少？ log2n+1ASL=(1+2*2+4*3+5*4)/12=37/1217.對(duì)如下數(shù)據(jù)：43，12，50，31，71，35，24，62，11，20（1）寫(xiě)出采用快速排序算法的每一趟排序的結(jié)果（2）寫(xiě)出執(zhí)行直接插入排序算法，每趟排序的結(jié)果（3）寫(xiě)出執(zhí)行希爾排序算法，每趟排序的結(jié)果（增量序列為5、3、1）（4）寫(xiě)出執(zhí)行選擇排

21、序算法，每趟排序的結(jié)果(1) 43，12，50，31，71，35，24，62，11，20 20 12 11 31 24 35 42 62 71 50 11 12 20 31 24 35 42 62 71 50 11 12 20 24 31 35 42 62 71 50 11 12 20 24 31 35 42 50 62 71（2） 43 12 43 12 43 50 12 31 43 50 12 31 43 50 71 12 31 35 43 50 71 12 24 31 35 43 50 71 12 24 31 35 43 50 62 71 11 12 24 31 35 43 50 62 71 11 12 2