數(shù)據結構之集合

第九章復習題1.若查找每個記錄的概率均等，則在具有n個記錄的連續(xù)順序文件中采用順序查找法查找一個記錄，其平均查找長度ASL為(C)。A.(n-1)/2B.n/2C.(n+1)/2D.n2.對線性表進行二分查找時，要求線性表必須（B）A.以順序方式存儲B.以順序方式存儲,且數(shù)據元素有序C.以鏈接方式存儲D.以鏈接方式存儲,且數(shù)據元素有序13.具有12個關鍵字的有序表，折半查找的平均查找長度（A）A.3.1B.4C.2.5D.54.哈查找中k個關鍵字具有同一哈希值，若用線性探測法將這k個關鍵字對應的記錄存入哈希表中，至少要進行(C)次探測。A．kB.k+1C.k(k+1)/2D.1+k(k+1)/225．分別以下列序列構造二叉排序樹，與用其它三個序列所構造的結果不同的是(C)A．（100，80，90，60，120，110，130）B.（100，120，110，130，80，60，90）C.（100，60，80，90，120，110，130）D.(100，80，60，90，120，130，110)6.將10個元素散列到100000個單元的哈希表中，則（C）產生沖突。A.一定會B.一定不會C.仍可能會37.下面關于m階B樹說法正確的是(B)①每個結點至少有兩棵非空子樹；②樹中每個結點至多有m一1個關鍵字;③所有葉子在同一層上;④當插入一個數(shù)據項引起B(yǎng)樹結點分裂后，樹長高一層。A．①②③B.②③C.②③④D.③48.設哈希表長為14，哈希函數(shù)是H(key)=key%11,表中已有數(shù)據的關鍵字為15，38，61，84共四個，現(xiàn)要將關鍵字為49的結點加到表中，用二次探測再散列法解決沖突，則放入的位置是(D)A．8B．3C．5D．99.在順序表（8,11,15,19,25,26,30,33,42,48,50）中，用二分（折半）法查找關鍵碼值20，需做的關鍵碼比較次數(shù)為__4__.510．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比較的元素下標依次為___6,9,11,12____。11.高度為4的3階b-樹中，最多有__26_個關鍵字。12.在一棵m階B-樹中,若在某結點中插入一個新關鍵字而引起該結點分裂,則此結點中原有的關鍵字的個數(shù)是__m-1,___;若在某結點中刪除一個關鍵字而導致結點合并,則該結點中原有的關鍵字的個數(shù)是___「m/2

-1____。613.___直接定址法___法構造的哈希函數(shù)肯定不會發(fā)生沖突。14.高度為8的平衡二叉樹的結點數(shù)至少有_54______個。15.高度為5（除葉子層之外）的三階B-樹至少有___31___個結點。7第十章復習題1．某內排序方法的穩(wěn)定性是指(D)。A．該排序算法不允許有相同的關鍵字記錄B．該排序算法允許有相同的關鍵字記錄C．平均時間為0（nlogn）的排序方法D．以上都不對2．下列排序算法中，其中（D）是穩(wěn)定的。A.堆排序，冒泡排序B.快速排序，堆排序C.直接選擇排序，歸并排序D.歸并排序，冒泡排序83．若需在O(nlog2n)的時間內完成對數(shù)組的排序，且要求排序是穩(wěn)定的，則可選擇的排序方法是（C）。A.快速排序B.堆排序C.歸并排序D.直接插入排序4．排序趟數(shù)與序列的原始狀態(tài)有關的排序方法是(CD)排序法。A．插入B.選擇C.冒泡D.快速95．對下列四種排序方法，在排序中關鍵字比較次數(shù)同記錄初始排列無關的是(B)。A．直接插入B.二分法插入C.快速排序D.歸并排序6．數(shù)據序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中的(C)的兩趟排序后的結果。A.選擇排序B.冒泡排序C.插入排序D.堆排序107．數(shù)據序列（2，1，4，9，8，10，6，20）只能是下列排序算法中的(A)的兩趟排序后的結果。A.快速排序B.冒泡排序C.選擇排序D.插入排序8．對一組數(shù)據（84，47，25，15，21）排序，數(shù)據的排列次序在排序的過程中的變化為（1）8447251521（2）1547258421（3）1521258447（4）1521254784則采用的排序是(A)。A.選擇B.冒泡C.快速D.插入119．對序列{15，9，7，8，20，-1，4}進行排序，進行一趟后數(shù)據的排列變?yōu)閧4，9，-1，8，20，7，15}；則采用的是（C）排序。A.選擇B.快速C.希爾D.冒泡10．若上題的數(shù)據經一趟排序后的排列為{9，15，7，8，20，-1，4}，則采用的是（C）排序。A．選擇B.堆C.直接插入D.冒泡1211．下列排序算法中(B)不能保證每趟排序至少能將一個元素放到其最終的位置上。A.快速排序B.shell排序C.堆排序D.冒泡排序12．一組記錄的關鍵碼為（46，79，56，38，40，84），則利用快速排序的方法，以第一個記錄為基準得到的一次劃分結果為（C）。A．(38,40,46,56,79,84)B.(40,38,46,79,56,84)C．(40,38,46,56,79,84)D.(40,38,46,84,56,79)1313．下列排序算法中，在待排序數(shù)據已有序時，花費時間反而最多的是(C)排序。A．冒泡B.希爾C.快速D.堆14.就平均性能而言，目前最好的內排序方法是(D)排序法。A.冒泡B.希爾插入C.交換D.快速1415．下列排序算法中，（D）算法可能會出現(xiàn)下面情況：在最后一趟開始之前，所有元素都不在其最終的位置上。A.堆排序B.冒泡排序C.快速排序D.插入排序16．從未排序序列中依次取出一個元素與已排序序列中的元素依次進行比較，然后將其放在已排序序列的合適位置，該排序方法稱為(A)排序法。A.插入B.選擇C.希爾D.二路歸并1517.在排序算法中，每次從未排序的記錄中挑出最小關鍵碼字的記錄，加入到已排序記錄的末尾，該排序方法是（A）。A.選擇B.冒泡C.插入D.堆18．將兩個各有N個元素的有序表歸并成一個有序表,其最少的比較次數(shù)是(A)A．NB．2N-1C．2ND．N-11619.歸并排序中，歸并的趟數(shù)是(B)。A．O（n）B．O(logn)C．O(nlogn)D．O(n*n)20.有一組數(shù)據（15，9，7，8，20，-1，7，4），用堆排序的篩選方法建立的初始堆為（C）A．-1，4，8，9，20，7，15，7B．-1，7，15，7，4，8，20，9C．-1，4，7，8，20，15，7，9D．A，B，C均不對。1721．對n個記錄的文件進行堆排序，最壞情況下的執(zhí)行時間是多少？（C）A．O（log2n）B．O（n）C．O（nlog2n）D．O（n*n）22．下列四個序列中，哪一個是堆（C）。A.75,65,30,15,25,45,20,10B.75,65,45,10,30,25,20,15C.75,45,65,30,15,25,20,10D.75,45,65,10,25,30,20,151823．對關鍵碼序列28，16，32，12，60，2，5，72快速排序，從小到大一次劃分結果為（B）。A.(2,5,12,16)28(60,32,72)B.(5,16,2,12)28(60,32,72)C.(2,16,12,5)28(60,32,72)D.(5,16,2,12)28(32,60,72)24.對序列{15，9，7，8，20，-1，4，}用希爾排序方法排序，經一趟后序列變?yōu)閧15，-l，4，8，20，9，7}則該次采用的增量是(B)A.lB.4C.3D.219作業(yè)題1.已知如下11個數(shù)據元素的有序表：{05,13,19,21,37,56,64,75,80,88,92}現(xiàn)采用折半查找，給出查找21和85的過程，畫出折半查找判定樹，求出平均查找長度。2.對給定的數(shù)列R={7,16,4,8,20,9,6,18,5}構造一棵平衡二叉樹。3.已知一組關鍵字為（39,23,41,38,44,15,68,12,06,51），哈希函數(shù)H（key）=key%13。（1）用二次探測處理沖突構造出哈希表HT[0..14]。（2）用鏈地址法處理沖突構造出哈希表。20作業(yè)題寫出從頂點v1出發(fā)深度優(yōu)先遍歷序列寫出從頂點v1出發(fā)廣度優(yōu)先遍歷序列v7v5v6v2v3v1v4v821作業(yè)題從頂點v1出發(fā)，構造下面連通網的最小生成樹。v7v5v6v2v3v1v4604550