數(shù)據(jù)結(jié)構(gòu)之集合

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

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