數(shù)據(jù)結(jié)構(gòu)第六章

1、一、 單項選擇題1.已知一個長度為16的順序L，氣元素按關(guān)鍵字有序排列，或采用折半查找法查找一個不在L中存在的元素，則關(guān)鍵字的比較次數(shù)最多的是（ ）。A4 B. 5C. 6 D. 72.順序查找適合于存儲結(jié)構(gòu)為（ ）的線性表。A.順序存儲結(jié)構(gòu)或鏈?zhǔn)酱鎯Y(jié)構(gòu) B.散列存儲結(jié)構(gòu)C.索引存儲結(jié)構(gòu) D.壓縮存儲結(jié)構(gòu)3.對長度為n的有序單鏈表，若查找每個元素的概率相等，則順序查找表中任意一個元素的查找成功的平均查找長度為（ ）。A.n/2 B.(n+1)/2C.(n-1)/2 D.n/44.對長度為3的順序表進行查找，若查找的第一個元素概率為1/2，查找第二個元素的概率為1/3，查找第三個元素的概率為1

2、/6，則查找表中任意一個元素的平均查找長度為( )。A.5/3 B.2C.7/3 D.4/35.當(dāng)采用分塊查找時，數(shù)據(jù)的組織方式為（ ）。A.數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序B.數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊C. 數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊D. 數(shù)據(jù)分成若干塊，每塊（除最后一塊外）中數(shù)據(jù)個數(shù)需相同6.下列關(guān)于二分查找的敘述中，正確的是（ ）。A表必須有序，表可以順序方式存儲，也可以鏈表方式存儲B. 表必須有序且表中數(shù)據(jù)必須是整型，實型或字符型C. 表必須有序，而且只能從小到大排列D表必須有序，且表

3、只能以順序方式存儲7.使用二分（折半）查找元素的速度比用順序法（ ）。A.必然快 B.必然慢C.相等 D.不能確定8.已知一個長度為16的順序表，其元素按關(guān)鍵字有序排列，若采用折半查找查找一個不存在的元素，則比較的次數(shù)至少是（ ），至多是（ ）。A.4 B.5C.6 D.79.已知一個有序表（13,18,24,35,47,50,62,83,90,115,134），當(dāng)二分查找值為90的元素師，查找成功的比較次數(shù)為（ ）。A.1 B.2C.4 D.610.折半查找過程所對應(yīng)的判定樹是一顆（ ）。A.最小二叉樹 B.平衡二叉樹C.完全二叉樹 D.滿二叉樹11.在有11個元素的 有序表A1,2,3，1

4、1中折半查找(),查找元素為A11時，被比較元素的下標(biāo)依次是（ ）。A.6，8，10，11 B.6，9，10，11C.6，7，9，11 D.6，8，9，1112.具有12個關(guān)鍵字的有序表中，對每個關(guān)鍵字的查找概率相同，遮半查找查找成功的平均查找長度為（ ），折半查找查找失敗的平均查找長度為（ ）。A.37/12 B.35/12C.39/13 D.49/1313.對有2500個記錄的索引順序表（分塊表）進行查找，最理想的塊長為（ ）。A.50 B.125C.500 D. 14.為提高查找效率，對有65025個元素的有序順序表建立索引順序結(jié)構(gòu)，在最好情況下查找到表中已有元素最多需要執(zhí)行（ ）次關(guān)鍵

5、字比較。A.10 B.14C.16 D.2115.設(shè)順序存儲的某線性表共有123個元素，按分塊查找的要求等分為3塊。若對索引表采用順序查找法來確定子塊，且確定的字塊中也采用順序查找法，則在等概率情況下，分塊查找成功的平均查找長度為（ ）。A.21 B.23C.41 D.62 16.對長為n的有序表進行折半查找，其判定樹的高度為（ ）。A. B. C. D. 17.下列敘述中，不符合m介B樹定義要求的是（ ）。A.根節(jié)點最多的有m課子樹 B.所有葉節(jié)點都在同一層上C.各節(jié)點內(nèi)關(guān)鍵字均升序或者降序排列 D.葉節(jié)點之間通過指針連接18.下列關(guān)于m介B-樹的說法錯誤的是（ ）。A.根節(jié)點至多有m棵子樹

6、B.所有節(jié)點都在用一層次上C.非葉節(jié)點至少有m/2(m為偶數(shù))或m/2+1(m為奇數(shù))棵子樹D.根節(jié)點中的數(shù)據(jù)是有序的19.當(dāng)在一顆m階B樹中做插入操作時，若一個結(jié)點中的關(guān)鍵字等于（ ），則必須分裂成兩個結(jié)點，當(dāng)向一顆樹m階的B樹做刪除操作時，若一個結(jié)點中的關(guān)鍵字個數(shù)等于（ ），則可能需要同它的做兄弟或有兄弟結(jié)點合并成一個結(jié)點。A. B. C. D. 20.下列關(guān)于m階B樹的說法正確的是（ ）。I. 每個結(jié)點至少有兩顆非空子樹II. 樹中每個結(jié)點至多有m-1個關(guān)鍵字III. 所有葉結(jié)點都在同一層IV. 當(dāng)插入一個元素引起B(yǎng)樹結(jié)點分裂后，樹長高一層A.I、II B.II、IIIC.III、IV

7、D.I、II、IV21.下列關(guān)于B樹和B+樹敘述中，不正確的是（ ）。A. B樹和B+樹都能有效支持順序查找B. B樹和B+樹都能有效支持隨機查找C. B樹和B+樹都是平衡的多叉樹D. B樹和B+樹都可以用于文件索引結(jié)構(gòu)22.含有n個非葉結(jié)點的m階B-樹中至少包含（ ）個關(guān)鍵字。A. B. C. D. 23.已知一課3階B樹中有2047個關(guān)鍵字，則此B樹的最大高度為（ ），最小高度為（ ）。A.11 B.10C.8 D.724.高度為5的3階B樹至少有（ ）個結(jié)點，至少有（ ）個結(jié)點。A.32 B.31C.120 D.12125.已知一棵5階B樹中共有53個關(guān)鍵字，則樹的最大高度為（ ），最小

8、高度為（ ）。A.2 .B.3C.4 D.526.具有n個關(guān)鍵字的m階B-樹，應(yīng)有（ ）個葉結(jié)點。A.n+1 B.n-1C.mn D.nm/227.設(shè)有一個含有200個表項的散列表，用線性探測法解決沖突，按關(guān)鍵字查詢時找到一個表項的平均探測次數(shù)不超過1.5，則散列表項應(yīng)能夠容納（ ）個表項。（設(shè)查找成功的平均查找長度為，其中填裝因子）A400 B. 526C624 D. 67628.在開址法中散列到同一個地址而引起的“堆積”問題是由于（ ）引起的。A.同義詞之間發(fā)生沖突 B. 同義詞之間發(fā)生沖突之間發(fā)生沖突C.同義詞或同義詞之間發(fā)生沖突之間發(fā)生沖突D.散列表“溢出”29.Hash查找一般適用于

9、（ ）情況下的查找。A.查找表為鏈表 B. 查找表為有序表C.關(guān)鍵字集合比地址集合大得多 D. 關(guān)鍵字集合比地址集合存在對應(yīng)關(guān)系30.假定有K個關(guān)鍵字互為同義詞，若用線性探測法把這K個關(guān)鍵字填入Hash表中，至少要進行（ ）次探測。A.K-1 B. KC.K+1 D. K(K+1)/2B A B A二 綜合應(yīng)用題1.若對有N個元素的有序順序表和無序順序表進行順序查找，試就下列三種情況討論兩者在相等查找概率時的平均查找長度是否相同？1).查找失敗。2).查找成功，且表中只有一個關(guān)鍵字等于給定值k的元素。3).查找成功，且表中只有若干個關(guān)鍵字等于給定值k的元素，要求一次能查找所有的元素。2.設(shè)有序

10、順序表中的元素依次為017、094、154、170、275、503、509、512、553、612、677、765、897、908。1) 試畫出對其進行折半查找的判定樹。2) 若查找275或684的元素，將依次與表中那些元素比較？3) 計算查找成功的平均查找長度和查找不成功的平均查找長度。3已知一個有序順序表 的表廠為8N，并且表中沒有關(guān)鍵字相同的數(shù)據(jù)元素。假設(shè)按如下所述的方法查找一個關(guān)鍵字值等于給定值X的數(shù)據(jù)元素：先在A7,A15,A23,A8K-1,A8N-1中進行順序查找，若查找成功，則算法報告成功位置并返回；若不成功，時，則可以確定一個縮小的查找范圍，然后可以再這個范圍內(nèi)執(zhí)行折半查找。

11、特殊情況：若的關(guān)鍵字，則查找失敗。 1)畫出上述查找過程的判定樹。 2)計算相等查找概率下查找成功的平均查找長度。4.類比二分查找法，設(shè)計K分查找法（k為大于2的整數(shù)）如下：首先檢查n/k處（n為查找表的長度）的元素是否等于要搜索的值，然后檢查2n/k處的元素這樣，或者找到要查找的元素，或者把集合縮小到原來的1/k,如果未找到要查找的元素，則繼續(xù)在得到的集合上進行K分查找；如此進行，直到找到要查找的元素或者查找失敗。試求，查找成功和查找失敗的時間復(fù)雜度。5.線性表中各結(jié)點的檢索概率不等，則可用如下策略提高順序檢索的效率：若找到指定的結(jié)點，將該結(jié)點和其前驅(qū)結(jié)點交換，使經(jīng)常被檢索的結(jié)點盡量位于表的

12、前端。是設(shè)計在順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)的線性表實現(xiàn)上述策略的順序檢索算法。6.一個長度為的升序序列S，處在第個位置的數(shù)為S的中位數(shù)。例如，若序列S1=(11，13，15，17，19)，則S1的中位數(shù)是15，兩個序列的中位數(shù)是含他們所有元素的的升序序列的中位數(shù)。例如，若S2=(2，4，6，8，20),則S1和S2的中位數(shù)是11。現(xiàn)在有兩個等長升序序列A和B，試設(shè)計一個在時間和空間兩方面都盡可能高效的算法，找出兩個序列A和B的中位數(shù)。要求：（1）給出算法的基本思想。（2）根據(jù)設(shè)計思想，采用C或者C+或JAVA語言描述算法，關(guān)鍵之處給注釋。（3）說明你所涉及的算法的時間復(fù)雜度和空間復(fù)雜度。7.寫出折半查找

13、的遞歸算法。初始調(diào)用時，low為1，high為ST.length8.利用B樹做文件索引時，若假設(shè)磁盤的頁塊的大小是4000字節(jié)（實際應(yīng)該是2的次冪，為了計算方便），指示磁盤地址的指針需要五個字節(jié)?，F(xiàn)有20000000個記錄構(gòu)成的文件，每個記錄為200字節(jié)，其中包括五個關(guān)鍵字節(jié)。試問在次采用B樹做索引的文件中，B樹的階數(shù)應(yīng)為多少？假定文件數(shù)據(jù)部分未按關(guān)鍵字有序排列，則索引部分需要占多少磁盤頁塊？9.假定把關(guān)鍵字key散列到有n個表項（從0到n-1編址）的散列表中。對于下面的每一個散列函數(shù)H(key)(key為整數(shù))，這些函數(shù)能夠當(dāng)做散列函數(shù)嗎？如果能夠，他是好的散列函數(shù)嗎？請說明理由。設(shè)函數(shù)ra

14、ndom(n)返回一個0到n-1之間的隨機整數(shù)1）H(key)=key/n。2）H(key)=1.3）H(key)=(key+random(n)%n。4）H(key)=key%p(n);其中p(n)是不大于n的最大素數(shù)。10.使用散列函數(shù)H(key)=key%11，把一個整數(shù)值轉(zhuǎn)換成散列列表的下標(biāo)，現(xiàn)在要把數(shù)據(jù)1,13,34,38,33,27,22依次插入到散列表中。1）使用線性探測在散列法來構(gòu)造散列表。2）使用鏈表地址法構(gòu)造散列表。 答案部分一、 選擇題1-10 B A B A B D D AB B B11-20 B AD A C B A D C A B21-30 A D AD BD CB

15、A A C D D二、 綜合題1解答：(1)平均查找長度不同。因為有序順序表查找到其關(guān)鍵字值比要查找值大的元素時就停止查找，并報告失敗信息，不必查找到表尾；而無需表必須查找到表尾才能確定查找失敗。(2)平均查找長度相同。兩者查找到表中元素的關(guān)鍵字值等于給定值時就停止查找。(3)平均查找長度不同。有序順序表中關(guān)鍵字相等的元素相繼排列在一起，只要查找到第一個就可以連續(xù)查找到其他關(guān)鍵字相同的元素。而無序順序表必須查找全部表中元素才能才能確定相同關(guān)鍵字的元素都找出來，所需時間就不相同了。2解答：1）判定樹如下圖所示。2)若查找元素275，依次與表中元素509、154、275進行比較，共比較3次。若查找

16、684，依次與表中元素509、677、897、765進行比較，共進行四次。3)在查找功能時，會找到圖中某個圓形結(jié)點，其平均長度為在查找失敗時，會找到圖中某個方形結(jié)點，但這個結(jié)點是虛構(gòu)的，最后一次的比較元素為其父節(jié)點（圓形結(jié)點），故其平均長度為1. 解答：1)相應(yīng)的判定樹如下圖所示。其中，每個關(guān)鍵字下的數(shù)字為其查找成功時的關(guān)鍵字比較次數(shù)。2)查找成功的平均查找長度為4解答：與二分法查找類似，k分查找法可用k叉樹來描述。K分查找法在查找成功時進行比較的關(guān)鍵字個數(shù)最多不超過根的深度，而具有n個結(jié)點的k叉樹的深度為，所以k分查找法在查找成功時和給定值比較的關(guān)鍵字個數(shù)至多為，即時間復(fù)雜度為。同理，查找不

17、成功時，和給定值進行比較的關(guān)鍵字個數(shù)至多為，故時間復(fù)雜度也為。5 解答：算法的基本思想：檢索時可從開頭開始向后順序掃描，若找到指定結(jié)點，將該結(jié)點和其前驅(qū)結(jié)點（若存在）交換。采用順序結(jié)構(gòu)的存儲結(jié)構(gòu)的算法實現(xiàn)如下：int seqsrch(RcdType R,ElemType k)/順序查找線性表，找到后和前面的元素交換Int i=0;While (Ri.key!=k)&&(i<n) i+ if(i<n&&i>0) /找到 ，交換 temp=Ri;Ri=Ri-1;Ri-1=temp;Return -i; /返回交換后位置else return -1;

18、 /查找失敗鏈表的實現(xiàn)方式類比這個方式自己完成。6 解答：（1）算法的基本思想如下：分別求出序列A和B的中位數(shù)，設(shè)為a和b，求序列A和B的中位數(shù)的過程如下：1）若a=b,則a或者b即為所求的中位數(shù)，算法結(jié)束。2）若a<b,則舍棄序列A中較小的一半，同時舍棄B中較大一半，要求舍棄長度相等。3）若a>b，則舍棄序列A中較大的一半，同時舍棄B中較小一半，要求舍棄長度相等。在保留兩個升序序列中，重復(fù)過程1,2,3，直到兩個序列中只含一個元素為止，較小者即為所求的中位數(shù)。(2)算法實現(xiàn)如下：Int M_search(int A,int B,int n) int s1=0,d1=n-1,m1,

19、s2=1,d2=n-1,m2;/分別表示序列A和B中的首位數(shù)、末尾數(shù)和中位數(shù) While (s1!=d1|s2!=d2) m1=(s1+d1)/2; m2=(s2+d2)/2; if(Am1)=Bm1) return Am1; /滿足條件1if(Am1)<Bm1) /滿足條件2 if(s1+d1)%2=0) /若元素個數(shù)為奇數(shù) s1=m1;/舍棄A中間點以前的部分且保留中間點 d2=m2;/舍棄 B中間點以后的部分且保留中間點 else /元素個數(shù)為偶數(shù) s1=m1+1; /舍棄A中間點及中間點以前的部分 d2=m2; /舍棄B中間點以后的部分且保留中間點 else /滿足條件3 if(

20、s1+d1)%2=0)/若元素為奇數(shù) d1=m1; /舍棄A中間點以后的部分且保留中間點 s2=m2; /舍棄B中間點以前的部分且保留中間點 else /元素個數(shù)為偶數(shù) d1=m1+1; /舍棄A中間點以前的部分且保留中間點 s2=m2; /舍棄B中間點及中間點的以前部分 return As1<Bs2?As1:Bs2;(3) 算法的時間復(fù)雜度為，空間復(fù)雜度。7 解答：算法的基本思想：根據(jù)查找的起始位置和終止位置，將查找序列一分為二，判斷所查找的關(guān)鍵在那一部分，然后用新的序列起始位置和終止位置遞歸求解。算法代碼：Typedef struct/查找表的數(shù)據(jù)結(jié)構(gòu) ElemType *elem;

21、 /存儲空間基址，建表時按實際長度分配，0號留空 int length;/表的長度SSTableInt BinsearchRec(SSTable ST, ElemType key ,int low,int high)/在有序表中遞歸折半查找其關(guān)鍵字為key的元素，返回在表中的序號If(low>high) return 0;mid=(low+high)/2; /取中間位置if(key>ST.elemmid) /向后半部分查找 Search(ST,key,mid+1,high);Else if (key< ST.elemmid) /向前半部分查找 Search(ST,key,lo

22、w,mid-1);Else /查找成功 Return mid;算法把規(guī)模為n復(fù)雜問題經(jīng)過多次遞歸調(diào)用轉(zhuǎn)化我規(guī)模減半的子問題求解。時間復(fù)雜度為，算法中用到了一個遞歸工作棧，其規(guī)模于遞歸深度有關(guān)，也是8 解答：根據(jù)B樹的概念，一個索引結(jié)點應(yīng)適應(yīng)操作系統(tǒng)一次讀寫的物理記錄大小，其大小應(yīng)取不超過單最接近一個磁盤頁塊的大小。假設(shè)B樹為M階，一個B樹最多存放m-1個關(guān)鍵字（5個字節(jié)）和對應(yīng)的記錄地址（5字節(jié)）、m個子樹指針（5個字節(jié)）和一個指示結(jié)點中實際關(guān)鍵字個數(shù)的整數(shù)（2字節(jié)）。則有：計算結(jié)果，。一個索引結(jié)點最多可存放m-1=256個索引項，最少可存放個索引項。全部有n=20000000個記錄，每個記錄占用空間200個字節(jié)，每個頁塊可存放4000/200=20個記錄，則全部記錄分布在