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

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

2、O（n2）B）O（nlog2n）C）O（n）D）O（log2n）6.有一個(gè)長度為12的有序表R011，按折半查找法對該表進(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è)采用順序查找來確定結(jié)點(diǎn)所在的塊時(shí)，每塊應(yīng)有 個(gè)結(jié)點(diǎn)最佳。A）10B）25C）6D）62510. 不能生成右圖所示二叉排序樹的關(guān)鍵字序列是_。A）45312B）42531C）45213D）4231511.按_遍歷二叉排序樹，可以得到按值遞增或遞減次序的關(guān)鍵碼序列。A）先序B）中序C）后序D）層序12.在一棵平衡二叉樹中，每個(gè)結(jié)點(diǎn)的平衡因子的取值范圍是 。A）-11B）-22C）12D）0113.具有5

4、層結(jié)點(diǎn)的AVL樹至少有 個(gè)結(jié)點(diǎn)A）10B）12C）15D）1714.在含有15個(gè)結(jié)點(diǎn)的平衡二叉樹上，查找關(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的平衡二叉樹，其每個(gè)非葉子結(jié)點(diǎn)的平衡因子均為0，則該樹共有 個(gè)結(jié)點(diǎn)。A）2k-1-1 B）2k-1 C）2k-1 +1 D）2k-116.查找效率最高的二叉排序樹是 。A所有結(jié)點(diǎn)的左子樹都為空的二叉排序樹B所有節(jié)點(diǎn)的右子樹都為空的二叉排序樹C平衡二叉樹D沒有左子樹的二叉排序樹17.下面關(guān)于B-樹和B+樹的敘述中，不正確的結(jié)論是

5、。A）B-樹和B+樹都能有效地支持順序查找B）B-樹和B+樹都能有效地支持隨機(jī)查找C）B-樹和B+樹都是平衡的多分支樹D）B-樹和B+樹都可用于文件索引結(jié)構(gòu)18.設(shè)有n個(gè)關(guān)鍵字，哈希查找法的平均查找長度是 。A）O（1）B）O（n）C）O（log2n）D）O（n2）19.將10個(gè)元素散列到100000個(gè)單元的哈希表，則 產(chǎn)生沖突。A）一定會B）一定不會C）仍可能會D）以上都不對20.設(shè)哈希表長 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，其余地址為空，如用二次探測再散列法處理沖突，則關(guān)鍵字為49的結(jié)點(diǎn)的地

6、址是 。A）8B）3C）5D）921.假設(shè)有k個(gè)關(guān)鍵字互為同義詞，若用線性探測再散列法把這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.對數(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ù)與記錄的初始排列次序無關(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ù)雜度和需要附加的存儲空間復(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.對n個(gè)記錄的文件進(jìn)行堆排序，最壞情況下的執(zhí)行時(shí)間是 。A）O（log2n）

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

11、堆排序D）希爾排序41.快速排序在 情況下最不利于發(fā)揮其長處。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)得

12、到的第一次劃分結(jié)果為_。A）38,40,46,56,38,79,84B）40,38,46,79,56,84C）40,38,46,56,79,84D）40,38,46,56,7944.對下列關(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

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

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

15、每個(gè)結(jié)點(diǎn)的關(guān)鍵字都比左孩子關(guān)鍵字大，比右孩子關(guān)鍵字小，這樣的二叉樹都是二叉排序樹7.在二叉排序樹中，新插入的關(guān)鍵字總是處于最低層8.在二叉排序樹中，新結(jié)點(diǎn)總是作為葉子結(jié)點(diǎn)來插入的9.二叉排序樹的查找效率和二叉排序樹的高度有關(guān)10.在平衡二叉排序樹中，每個(gè)結(jié)點(diǎn)的平衡因子值都是相等的11.在平衡二叉排序樹中，以每個(gè)分支結(jié)點(diǎn)為根的子樹都是平衡的。12.哈希存儲法只能存儲數(shù)據(jù)元素的值，不能存儲數(shù)據(jù)元素之間的關(guān)系。13.哈希沖突是指同一個(gè)關(guān)鍵字對應(yīng)多個(gè)不同的哈希地址。14.哈希查找過程中，關(guān)鍵字的比較次數(shù)和哈希表中關(guān)鍵字的個(gè)數(shù)直接相關(guān)。15.在用線性探測法處理沖突的哈希表中，哈希函數(shù)值相同的關(guān)鍵字總是存

16、在一片連續(xù)的存儲單元中。16.若哈希表的裝填因子a<<1,則可避免沖突的發(fā)生。17.哈希表的查找效率主要取決于哈希表造表時(shí)選取的哈希函數(shù)和處理沖突的方法。四、簡答題：1.若對具有n個(gè)元素的有序的順序表和無序的順序表分別進(jìn)行順序查找，試在下述兩種情況下分別討論兩者在等概率時(shí)的平均查找長度；（1）查找不成功，即表中無關(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í)（從前往后找），分別需要多少

17、次比較才能成功？ 4，4，5，103.比較靜態(tài)查找表的3種查找方法4.請回答下列關(guān)于堆的問題（1）堆的存儲表示是順序的，還是鏈接的？（2）設(shè)有一個(gè)最小堆(小根堆)，即堆中任意結(jié)點(diǎn)的關(guān)鍵字均小于它的左孩子和右孩子的關(guān)鍵字。其具有最大關(guān)鍵字的元素可能在什么地方？ 葉子5.指出堆和二叉排序樹的區(qū)別。6.二叉排序樹的結(jié)構(gòu)如圖所示，其中各結(jié)點(diǎn)的關(guān)鍵字依次為3240，請你標(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-樹，對于該B-樹，給出刪除8，16，15，4等4個(gè)關(guān)鍵字的過程。8.已知一組

18、關(guān)鍵字為21，33，12，40，68，59，25，51，試依次插入關(guān)鍵字生成一棵3階B-樹；如果此后刪除40，畫出每一步執(zhí)行后B-樹的狀態(tài)。9.已知哈希函數(shù)H(k)=2*k Mod 11，用二次探測再散列法處理沖突，為關(guān)鍵字序列（6，8，10，17，20，23，53，41，54，57）構(gòu)造哈希表，并計(jì)算查找成功、不成功時(shí)的平均查找長度。10.比較直接插入排序和希爾排序的不同點(diǎn)。11.在實(shí)現(xiàn)插入排序過程中，可以用折半查找來確定第i個(gè)元素在前i-1個(gè)元素中的可能插入位置，這樣做能否改善插入排序的時(shí)間復(fù)雜度？為什么？12.在堆排序、快速排序和歸并排序中：（1）若只從存儲空間考慮，則應(yīng)首先選取哪種排序

19、方法，其次選取哪種排序方法，最后選取哪種排序方法？堆排序、快速排序、歸并排序（2）若只從排序結(jié)果的穩(wěn)定性考慮，則應(yīng)選取哪種排序方法？歸并排序（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，采用線性探測再散列法和鏈地址法處理沖突，將以下各數(shù)依次存入該哈希表中，請分別構(gòu)造哈希表，并分別計(jì)算平均查找長度。 240,2

20、9,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）/8=12/8=0.7515.請為17題數(shù)列構(gòu)造一棵平衡的二叉排序樹，并計(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，在等概率情況下查找成功的平均查找長度是多少？ log2n+1ASL=(1+2*2+4*3+5*4)/12=37/1217.對如下數(shù)據(jù)：43，12，50，31，71，35，24，62，11，20（1）寫出采用快速排序算法的每一趟排

21、序的結(jié)果（2）寫出執(zhí)行直接插入排序算法，每趟排序的結(jié)果（3）寫出執(zhí)行希爾排序算法，每趟排序的結(jié)果（增量序列為5、3、1）（4）寫出執(zhí)行選擇排序算法，每趟排序的結(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