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

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

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

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

4、中，每個結(jié)點的平衡因子的取值范圍是 B) -2 2C) 1 213.具有5層結(jié)點的AVL樹至少有個結(jié)點A) 10B) 12C) 1514.在含有15個結(jié)點的平衡二叉樹上，查找關(guān)鍵字為D) 0 1D) 1728的結(jié)點，則依次比較的關(guān)鍵字可能是A) 30，36B) 38，48，28C)48，18，38，28D) 60，30，50，40，38，3615. 一棵深度為k的平衡二叉樹，其每個非葉子結(jié)點的平衡因子均為0,則該樹共有個結(jié)點。A) 2k-1-1B) 2k-1C) 2k-1 +1D)2k-116. 查找效率最高的二叉排序樹是 A. 所有結(jié)點的左子樹都為空的二叉排序樹B. 所有節(jié)點的右子樹都為空的

5、二叉排序樹 匚平衡二叉樹D.沒有左子樹的二叉排序樹17. 下面關(guān)于B-樹和B+樹的敘述中，不正確的結(jié)論是 oA) B-樹和B+樹都能有效地支持順序查找B) B-樹和B+樹都能有效地支持隨機查找C) B-樹和B+樹都是平衡的多分支樹D) B-樹和B+樹都可用于文件索引結(jié)構(gòu)18. 設(shè)有n個關(guān)鍵字，哈希查找法的平均查找長度是 oA) 0( 1)B) O( n)C) O (log 2n)D 0( n2)19. 將10個元素散列到100000個單元的哈希表，則 產(chǎn)生沖突。A） 定會B） 定不會O仍可能會D）以上都不對20. 設(shè)哈希表長 m=14，哈希函數(shù) H（ key） =key Mod 11.表中已有

6、4個結(jié)點 H （15）=4，H（38） =5，H （61）=6，H （84）=7,其余地址為空，如用二次探測再散列法處理沖突，則關(guān)鍵字為 49的結(jié)點的地址是 。A） 8B） 3C） 5D） 921. 假設(shè)有k個關(guān)鍵字互為同義詞，若用線性探測再散列法把這k個關(guān)鍵字存入哈希表中，至少要進行 次探查。A） k-1B） kC） k+1D） k（ k+1） /222. 若采用鏈地執(zhí)法構(gòu)造哈希表，哈希函數(shù)為H（ key） =key Mod17,則需（1）個鏈表，這些鏈表的首指針構(gòu)成一個指針數(shù)組，該數(shù)組的下標(biāo)范圍為2）(1) A) 17B) 13C) 16D）任意(2) A) 017B) 1 17C)016

7、D 11623.直接插入排序在最好情況下的時間復(fù)雜度為。A)o( nb)O (nlog 2n)C)O (log 2n)2D) O(n)24.穩(wěn)定的排序算法是A接插入排序B）直接選擇排序 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進行排序，進行趟后數(shù)據(jù)的排序變?yōu)?，15, 7, 8,20, -1 , 4，則采用的是算法。A）直接選擇排序B）冒泡排序C）直接插入排序D）堆排序27. 以下排序方法中，在初始序列已

8、基本有序的情況下，排序效率最咼。A）歸并排序直接插入排序C）快速排序D）堆排序28. 不穩(wěn)定的排序方法是。A）冒泡排序B）直接插入排序C）希爾排序 D ）歸并排序29. 以下排序算法中，不能保證每趟排序至少能將一個元素放到其最終位置上。A）快速排序希爾排序C ）堆排序D）冒泡排序30. 在以下排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)的是。A)希爾排序B)冒泡排序C)插入排序DT直接選擇排序31. 在排序算法中，每次從未排序的記錄中選取最小(或最大)關(guān)鍵字的記錄,加入到已排序記錄的末尾，該排序方法是 OA)希爾排序B)冒泡排序C)插入排序D)直接選擇排序32. 采用直接選擇排列，比較

9、次數(shù)與移動次數(shù)分別是 oA) O(n), O( log 2n)B) 0( log 2n), 0 (n?)O0 (n2), 0(n)D) 0 (n log 2n), 0 (n)33. 以下序列不是堆的是oA) 100,85,98,77, 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)類排序，堆排序平均時間復(fù)雜度和需要

10、附加的存儲空間復(fù)雜度分別是(2)o(1) .A)插入B)交換(2) .A) O (n2)和 0( 1)C O (nlog 2n)和 O (n)C)歸并|D)選擇b)O (nIog2n)和 0( 1)2D) O ( n )和 O (n)35. 對n個記錄的文件進行堆排序，最壞情況下的執(zhí)行時間是 oA)0( log 2n)B)(n)C)O(nlog2n)D)O(n2)36. 設(shè)有1000個無序的元素，希望用最快的速度挑選出其中前10個最大的元素，最好選用_排序法。A)冒泡排序B)快速排序 C堆排序D)基數(shù)排序37. 在非空m階B樹上，除根結(jié)點以外的所有其他非終端結(jié)點 oA)至少有 m/2棵子樹B)

11、至多有 m/2棵子樹0少有 m/2棵子樹 C )至少有 m/2棵子樹38. 對于哈希函數(shù)H(key)=key%13,被稱為同義詞的關(guān)鍵字是 。A) 35 和 41B) 23 和 39C) 15 和 44D) 25 和 5139. 堆的形狀是一棵oA）二叉排序樹B）滿二叉樹C）完全二叉樹40. 以下法在數(shù)據(jù)基本有序時效率最好。A）快速排序B）冒泡排序C）堆排序41. 快速排序在情況下最不利于發(fā)揮其長處。D）不是二叉樹D）希爾排序A）要排序的數(shù)據(jù)量太大B）要排序的數(shù)據(jù)中含有多個相同值C）要排序的數(shù)據(jù)個數(shù)為奇數(shù)D）要排序的數(shù)據(jù)已基本有序42. 下列序列中， 是執(zhí)行第一趟快速排序后得到的序列（關(guān)鍵字為

12、字符串）A. da,ax,eb,cd,bbffha,gcB. cd,eb,ax,daffha,gc,bbC. gc,ax,eb,cd,bbffda,haD. ax,bb,cd,daffeb,gc,ha43. 一個記錄的關(guān)鍵字為46，79, 56, 38, 40, 84，采用快速排序以第一個 記錄為基準(zhǔn)得到的第一次劃分結(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)鍵字序列用快速排序法進行排序時，速度最快的情形是A） 21，25，5，17，9，23，30B） 2

13、5,23,30,17,21,5,9C） 21,9,17,30,25,23,5D） 5,9,17,21,23,25,3045. 下列排序方法中，在一趟結(jié)束后不一定能選出一個元素放在其最終位置上。A）直接選擇排序B）冒泡排序C）歸并排序D）堆排序46. 將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是。nB） 2n-1C） 2nD） n-1二、填空題：1. 在n個記錄的有序順序表中進行折半查找，最大的比較次數(shù)是log 2n +1_。2. 設(shè)線性表a 1，,，a2,，a5oo的元素的值從小到大排列，對一個給定的 K的 值用二分法查找線性表，在查找不成功的情況下至多需要比較 _ log

14、2n +1 次3. 在直接插入排序、希爾排序、直接選擇排序、快速排序、堆排序和歸并排序 中，平均比較次數(shù)最少的排序方法是 快速排序4. 一棵深度為h的B-樹，任一個葉子結(jié)點所處的層數(shù)為_Jh，當(dāng)向B-樹插入一個新關(guān)鍵字時，為檢索插入位置需讀取h-1個結(jié)點。5. 評價哈希表好壞的標(biāo)準(zhǔn)是_哈希表的均勻性。6. 在各種查找方法中，其平均查找長度與結(jié)點個數(shù)n無關(guān)的查找方法是哈希表查找。7. 設(shè)用希爾排序?qū)?shù)序98，36, -9，0，47, 23，1, 8, 10，7進行排序，給出的不長（也稱增量序列）依次是 4、2、1,則排序需 二趟，寫出第一趟結(jié)束后，數(shù)序中數(shù)據(jù)的排列次序是 10,7,-9,0,47

15、,23,1,8,98,36。三、判斷題肛順序查找法適用于存儲結(jié)構(gòu)為順序或鏈?zhǔn)酱鎯Φ木€性表2順序查找方法只能在順序存儲結(jié)構(gòu)上進行3.折半查找可以在有序的雙向鏈表上進行4!分塊查找的效率與線性表被分成多少塊有關(guān)忙在二叉排序樹中，每個結(jié)點的關(guān)鍵字都比左孩子關(guān)鍵字大，比右孩子關(guān)鍵 字小6. 每個結(jié)點的關(guān)鍵字都比左孩子關(guān)鍵字大，比右孩子關(guān)鍵字小，這樣的二叉樹都是二叉排序樹7. 在二叉排序樹中，新插入的關(guān)鍵字總是處于最低層8!在二叉排序樹中，新結(jié)點總是作為葉子結(jié)點來插入的9L二叉排序樹的查找效率和二叉排序樹的高度有關(guān)10.在平衡二叉排序樹中，每個結(jié)點的平衡因子值都是相等的 迅在平衡二叉排序樹中，以每個分支

16、結(jié)點為根的子樹都是平衡的。12. 哈希存儲法只能存儲數(shù)據(jù)元素的值，不能存儲數(shù)據(jù)元素之間的關(guān)系。13. 哈希沖突是指同一個關(guān)鍵字對應(yīng)多個不同的哈希地址。14. 哈希查找過程中，關(guān)鍵字的比較次數(shù)和哈希表中關(guān)鍵字的個數(shù)直接相關(guān)。15. 在用線性探測法處理沖突的哈希表中，哈希函數(shù)值相同的關(guān)鍵字總是存在 一片連續(xù)的存儲單元中。16. 若哈希表的裝填因子a| 35 |/x1201 H1 ll AlASL= （1+1+1+1+2+1+2+3 /8=12/8=0.7515.請為17題數(shù)列構(gòu)造一棵平衡的二叉排序樹，并計算ASL二f|2l I+2j4H】刖MASL=（1+2*2+4*3+5*3）/10=32/10

17、=3.216.有n個有序的數(shù)據(jù)構(gòu)成一個數(shù)列，查找某個元素時最多要進行幾次比較?當(dāng)n=12,在等概率情況下查找成功的平均查找長度是多少?log 2n+1ASL=（1+2*2+4*3+5*4）/12=37/1217. 對如下數(shù)據(jù)：43，12，50，31，71，35，24，62，11，20（1）寫出采用快速排序算法的每一趟排序的結(jié)果（2）寫出執(zhí)行直接插入排序算法，每趟排序的結(jié)果（3） 寫出執(zhí)行希爾排序算法，每趟排序的結(jié)果（增量序列為5、3、1）（4）寫出執(zhí)行選擇排序算法，每趟排序的結(jié)果（1） 43 ，12，50，31，71，35，24，62，11，20201211312435 42627150111

18、2 20312435 42627150111220243135 42627150111220243135 42506271(2) 431243124350123143501231435071123135435071122431354350711224313543506271111224313543506271111220243135435062 71(3) 43, 12,50, 31, 71, 35,24, 62,11,2035 12 5011 20 43 24 6231 7111 12 3124 20 43 35 6250 7111 12 2024 31 35 43 5062 71(4) 43, 12,50, 31, 71, 35,24, 62,11,201112503171352462432011125031713524624320111220317135246243501112202471353162435011122024313571624350111220243135716243501112202431354362715011122024313543507162