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

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

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

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

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

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

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

8、至少能將一個元素放到其最終位置上。A）快速排序 B）希爾排序 C）堆排序D）冒泡排序30.在以下排序方法中,關鍵字比較的次數與記錄的初始排列次序無關的是 。A）希爾排序B）冒泡排序C）插入排序D）直接選擇排序31.在排序算法中，每次從未排序的記錄中選取最小（或最大）關鍵字的記錄，加入到已排序記錄的末尾，該排序方法是 。A）希爾排序B）冒泡排序C）插入排序D）直接選擇排序32.采用直接選擇排列，比較次數與移動次數分別是 。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） 類排序，堆排序平均時間復雜度和需要附加的存儲空間復雜度分別是 （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個記錄的文件進行堆排序，最壞情況下的執行時間是 。A）O（log2n）

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

11、堆排序D）希爾排序41.快速排序在 情況下最不利于發揮其長處。A）要排序的數據量太大 B）要排序的數據中含有多個相同值C）要排序的數據個數為奇數D）要排序的數據已基本有序42.下列序列中，_是執行第一趟快速排序后得到的序列(關鍵字為字符串)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.一個記錄的關鍵字為46，79，56，38，40，84，采用快速排序以第一個記錄為基準得

12、到的第一次劃分結果為_。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.對下列關鍵字序列用快速排序法進行排序時，速度最快的情形是_。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.下列排序方法中， 在一趟結束后不一定能選出一個元素放在其最終位置上。A）直接選擇排序B）冒泡排序C）歸并排序D）堆排序46.將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數是 。A

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

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

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

16、在一片連續的存儲單元中。16.若哈希表的裝填因子a<<1,則可避免沖突的發生。17.哈希表的查找效率主要取決于哈希表造表時選取的哈希函數和處理沖突的方法。四、簡答題：1.若對具有n個元素的有序的順序表和無序的順序表分別進行順序查找，試在下述兩種情況下分別討論兩者在等概率時的平均查找長度；（1）查找不成功，即表中無關鍵字等于給定值k的記錄（2）查找成功，即表中有關鍵字等于給定值k的記錄2.已知一個有序表為12，18，20，25，29，32，40，62，83，90，95，98，當折半查找值 29和90的元素時，分別需要多少次比較才能查找成功？若采用順序查找時（從前往后找），分別需要多少

17、次比較才能成功？ 4，4，5，103.比較靜態查找表的3種查找方法4.請回答下列關于堆的問題（1）堆的存儲表示是順序的，還是鏈接的？（2）設有一個最小堆(小根堆)，即堆中任意結點的關鍵字均小于它的左孩子和右孩子的關鍵字。其具有最大關鍵字的元素可能在什么地方？ 葉子5.指出堆和二叉排序樹的區別。6.二叉排序樹的結構如圖所示，其中各結點的關鍵字依次為3240，請你標出各結點的關鍵字。7.關鍵字序列為：1，2，6，7，11，4，8，13，10，5，17，9，16，20，3，12，14，16，18，19，15，創建一棵5階B-樹，對于該B-樹，給出刪除8，16，15，4等4個關鍵字的過程。8.已知一組

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

19、方法，其次選取哪種排序方法，最后選取哪種排序方法？堆排序、快速排序、歸并排序（2）若只從排序結果的穩定性考慮，則應選取哪種排序方法？歸并排序（3）若只從平均情況下排序最快考慮，則應選取哪種排序方法？快速排序（4）若只從最壞情況下排序最快并且要節省內存考慮，則應選取哪種排序方法？堆排序13.判別以下序列是否是大頂堆，如果不是，則把它調整為大頂堆。 86，48，73，35，39，42，57，66，21，100不是14.已知哈希表地址空間為0到7，哈希函數為H(k)=k %8，采用線性探測再散列法和鏈地址法處理沖突，將以下各數依次存入該哈希表中，請分別構造哈希表，并分別計算平均查找長度。 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題數列構造一棵平衡的二叉排序樹，并計算ASL。ASL=(1+2*2+4*3+5*3)/10=32/10=3.216.有n個有序的數據構成一個數列，查找某個元素時最多要進行幾次比較？當n=12，在等概率情況下查找成功的平均查找長度是多少？ log2n+1ASL=(1+2*2+4*3+5*4)/12=37/1217.對如下數據：43，12，50，31，71，35，24，62，11，20（1）寫出采用快速排序算法的每一趟排

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