數(shù)據(jù)結(jié)構(gòu)第九章-查找-習(xí)題及答案

整理文檔整理文檔第九章查找選擇題若查找每個記錄的概率均等， 則在具有n個記錄的連續(xù)順序文件中采用順序查找法查找一TOC\o"1-5"\h\z個記錄，其平均查找長度 ASL為（ ）。A．（n-1）/2 B.n/2 C.（n+1）/2 D.n下面關(guān)于二分查找的敘述正確的是 （ ）表必須有序，表可以順序方式存儲，也可以鏈表方式存儲C.表必須有序，而且只能從小到大排列表必須有序且表中數(shù)據(jù)必須是整型，實(shí)型或字符型 D.表必須有序，且表只能以順序方式存儲TOC\o"1-5"\h\z用二分（對半）查找表的元素的速度比用順序法 （ ）A．必然快 B.必然慢 C.相等 D.不能確定具有12個關(guān)鍵字的有序表，折半查找的平均查找長度（）A.3.1 B.4 C.2.5 D.5．當(dāng)采用分塊查找時，數(shù)據(jù)的組織方式為 （ ）A.數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序B.數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)不必有序，但塊間必須有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊數(shù)據(jù)分成若干塊，每塊內(nèi)數(shù)據(jù)有序，每塊內(nèi)最大（或最?。┑臄?shù)據(jù)組成索引塊數(shù)據(jù)分成若干塊，每塊（除最后一塊外）中數(shù)據(jù)個數(shù)需相同二叉查找樹的查找效率與二叉樹的（（1））有關(guān) ,在（（2））時其查找效率最低（1）: A.高度 B.結(jié)點(diǎn)的多少 C.樹型 D. 結(jié)點(diǎn)的位置（2）: A.結(jié)點(diǎn)太多 B.完全二叉樹 C.呈單枝樹 D. 結(jié)點(diǎn)太復(fù)雜。對大小均為n的有序表和無序表分別進(jìn)行順序查找 ,在等概率查找的情況下 ,對于查找失敗它們的平均查找長度是 （（1））,對于查找成功 ,他們的平均查找長度是 （（2））供選擇的答案 :A.相同的 B.不同的9．分別以下列序列構(gòu)造二叉排序樹，與用其它三個序列所構(gòu)造的結(jié)果不同的是 （ ）A．（A．（100，80，90，60， 120，110，130）C.（100，60，80，90，120，110，130）10.在平衡二叉樹中插入一個結(jié)點(diǎn)后造成了不平衡，B.（100，120，110，130，80，60，90）D.（100，80，60，90，120，130，110）設(shè)最低的不平衡結(jié)點(diǎn)為A,并已知A的左孩子的平衡因子為0右孩子的平衡因子為 1,孩子的平衡因子為0右孩子的平衡因子為 1,則應(yīng)作 （）型調(diào)整以使其平衡。A.LL B.LR.下面關(guān)于m階B-樹說法正確的是（①每個結(jié)點(diǎn)至少有兩棵非空子樹；③所有葉子在同一層上;長高一層。A．①②③ B.②③.m階B-樹是一棵（ ）A.m叉排序樹B.m叉平衡排序樹C.RL D.RR）②樹中每個結(jié)點(diǎn)至多有 m一1個關(guān)鍵字;④當(dāng)插入一個數(shù)據(jù)項(xiàng)引起 B樹結(jié)點(diǎn)分裂后，樹C.②③④ D.③C.m-1叉平衡排序樹 D.m+1叉平衡排序樹15.設(shè)有一組記錄的關(guān)鍵字為{19樹15.設(shè)有一組記錄的關(guān)鍵字為{19，14，23，1，68，20，84，27，55，11，10，79}，用鏈TOC\o"1-5"\h\z地址法構(gòu)造散列表，散列函數(shù)為 H（key）=keyMOD13,散列地址為1的鏈中有（ ）個記錄。A．1 B.2 C.3 D.416.關(guān)于哈希查找說法不正確的有幾個 （ ）（1）采用鏈地址法解決沖突時，查找一個元素的時間是相同的（2）采用鏈地址法解決沖突時，若插入規(guī)定總是在鏈?zhǔn)祝瑒t插入任一個元素的時間是相同的（3）用鏈地址法解決沖突易引起聚集現(xiàn)象（4）再哈希法不易產(chǎn)生聚集TOC\o"1-5"\h\zA.1 B.2 C.3 D.4.設(shè)哈希表長為14,哈希函數(shù)是H（key尸key%11,表中已有數(shù)據(jù)的關(guān)鍵字為 15,38,61,84共四個，現(xiàn)要將關(guān)鍵字為49的結(jié)點(diǎn)加到表中，用二次探測再散列法解決沖突， 則放入的位置是（ ）A.8 B.3 C.5D.9.假定哈希查找中k個關(guān)鍵字具有同一哈希值，若用線性探測法把這 k個關(guān)鍵字存入散列表中，至少要進(jìn)行多少次探測？ （ ）A.k-1次B.k次C.k+1次D.k（k+1）/2次.好的哈希函數(shù)有一個共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以 （ ）取其值域的每個值。A.最大概率 B.最小概率 C.平均概率 D.同等概率.將10個元素散列到100000個單元的哈希表中，則（ ）產(chǎn)生沖突。A.一定會 B.一定不會 C.仍可能會二、判斷題.采用線性探測法處理散列時的沖突，當(dāng)從哈希表刪除一個記錄時，不應(yīng)將這個記錄的所TOC\o"1-5"\h\z在位置置空，因?yàn)檫@會影響以后的查找。 （ ）.在散列檢索中，“比較”操作一般也是不可避免的。 （ ）.Hash表的平均查找長度與處理沖突的方法無關(guān)。 （ ）.散列法的平均檢索長度不隨表中結(jié)點(diǎn)數(shù)目的增加而增加， 而是隨負(fù)載因子的增大而增大。（）.在索引順序表中，實(shí)現(xiàn)分塊查找，在等概率查找情況下，其平均查找長度不僅與表中元素個數(shù)有關(guān)，而且與每塊中元素個數(shù)有關(guān)。 （ ）.就平均查找長度而言，分塊查找最小，折半查找次之，順序查找最大。（ ）.最佳二叉樹是AVL樹（平衡二叉樹）。（ ）.在查找樹（二叉樹排序樹）中插入一個新結(jié)點(diǎn)，總是插入到葉結(jié)點(diǎn)下面。 （ ）.二叉樹中除葉結(jié)點(diǎn)外，任一結(jié)點(diǎn)X,其左子樹根結(jié)點(diǎn)的值小于該結(jié)點(diǎn)（X）的值；其右子樹根結(jié)點(diǎn)的值》該結(jié)點(diǎn)（X）的值，則此二叉樹一定是二叉排序樹。 （ ）.有n個數(shù)存放在一維數(shù)組A[1..n]中，在進(jìn)行順序查找時，這n個數(shù)的排列有序或無序其平均查找長度不同。（ ）.N個結(jié)點(diǎn)的二叉排序樹有多種，其中樹高最小的二叉排序樹是最佳的。 （ ）.在任意一棵非空二叉排序樹中，刪除某結(jié)點(diǎn)后又將其插入，則所得二排序叉樹與原二排序叉樹相同。（ ）.B-W中所有結(jié)點(diǎn)的平衡因子都為零。 （）.在平衡二叉樹中，向某個平衡因子不為零的結(jié)點(diǎn)的樹中插入一新結(jié)點(diǎn)， 必引起平衡旋轉(zhuǎn)。（）三、填空題.順序查找n個元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為次；當(dāng)使用監(jiān)視哨時，若查找失敗，則比較關(guān)鍵字的次數(shù)為。A[12]的元素，所比較的元素下標(biāo)依次為.在有序表A[1..12]A[12]的元素，所比較的元素下標(biāo)依次為.在有序表A[1..20]中，按二分查找方法進(jìn)行查找，查找長度為 5的元素個數(shù)是.高度為4(含葉子結(jié)點(diǎn)層)的3階b-樹中，最多有個關(guān)鍵字。.在一棵m階B-樹中若在某結(jié)點(diǎn)中插入一個新關(guān)鍵字而引起該結(jié)點(diǎn)分裂 ，則此結(jié)點(diǎn)中原有的關(guān)鍵字的個數(shù)是；若在某結(jié)點(diǎn)中刪除一個關(guān)鍵字而導(dǎo)致結(jié)點(diǎn)合并 則該結(jié)點(diǎn)中原有的關(guān)鍵字的個數(shù)是。.在哈希函數(shù)H(key)。.如果按關(guān)鍵碼值遞增的順序依次將關(guān)鍵碼值插入到二叉排序樹中，則對這樣的二叉排序樹檢索時，平均比較次數(shù)為。.如果關(guān)鍵碼按值排序，而后用二分法依次檢索這些關(guān)鍵碼，并把檢索中遇到的在二叉樹中沒有出現(xiàn)的關(guān)鍵碼依次插入到二叉排序樹中， 則對這樣的二叉排序樹檢索時， 平均比較次數(shù)為。(提示：此時二叉排序樹與折半查找的二叉判定樹一樣了).平衡因子的定義是 .查找是非數(shù)值程序設(shè)計(jì)的一個重要技術(shù)問題，基本上分成 —⑴—查找，二(2)_查找和(3)查找。處理哈希沖突的方法有 _(4)、_(5)、(6)_和—⑺.具有N個關(guān)鍵字的B樹的查找路徑長度不會大于。在一棵有N個結(jié)點(diǎn)的非平衡二叉樹中進(jìn)行查找，平均時間復(fù)雜度的上限(即最壞情況平均時間復(fù)雜度) 為.高度為5(除葉子層之外)的三階 B-樹至少有個結(jié)點(diǎn)。.可以唯一的標(biāo)識一個記錄的關(guān)鍵字稱為。.動態(tài)查找表和靜態(tài)查找表的重要區(qū)別在于前者包含有和運(yùn)算，而后者不包含這兩種運(yùn)算。.已知N元整型數(shù)組a存放N個學(xué)生的成績，已按由大到小排序，以下算法是用對分(折半)查找方法統(tǒng)計(jì)成績大于或等于 X分的學(xué)生人數(shù)，請?zhí)羁帐怪晟啤?(提示：這時需要找的是最后一個大于等于 X的下標(biāo)，若查找成功其下標(biāo)若為 m,則有m個學(xué)生成績大于或等于X,若查找不成功，若這時 low所指向的值小于X,則有l(wèi)ow-1個學(xué)生成績大于或等于X,注意這時表中可能不止一個數(shù)值為 X的值，這時我們要查找的是下標(biāo)最大的 )#defineN/*學(xué)生人數(shù)*/intuprx(inta[N],intx) /*函數(shù)返回大于等于X分的學(xué)生人數(shù)*/{intlow=1,mid,high=N;do{mid=(low+high)/2;if(x<=a[mid])_(1)else_(2)_;}whilej(3)=);if(a[low]<x)returnlow-1;returnlow;}四、應(yīng)用題1.名詞解釋：哈希表敘述B-樹定義，主要用途是什么？平衡二叉樹(AVL樹)平衡因子平均查找長度(ASL).設(shè)有一組關(guān)鍵字{9,01,23,14,55,20,84,27},采用哈希函數(shù)：H(key)=keymod7,表長為10,用開放地址法的二次探測再散列方法解決沖突 Hi=(H(key)+di)mod10(di=12,22,32，…,)。要求：對該關(guān)鍵字序列構(gòu)造哈希表，并確定其裝填因子，查找成功所需的平均探查次數(shù)。.設(shè)一組數(shù)據(jù)為{1,14,27,29,55,68,10,11,23}現(xiàn)采用的哈希函數(shù)是 H(key尸keyMOD13,即關(guān)鍵字對13取模，沖突用鏈地址法解決，設(shè)哈希表的大小為 13(0..12),試畫出插入上述數(shù)據(jù)后的哈希表。7.設(shè)有一棵空的3階B-樹，依次插入關(guān)鍵字 30,20,10,40,80,58,47,50,29,22,56,98,99青畫出該樹。9.已知2棵2-3B-W如下(省略外結(jié)點(diǎn))：(1)對機(jī)(a)，請分別畫出先后插入26,85兩個新結(jié)點(diǎn)后的樹形;(b).輸入一個正整數(shù)序列(53,17,12,66,58,70,87,25,56,60,試完成下列各題。按次序構(gòu)造一棵二叉排序樹 BS。依此二叉排序樹，如何得到一個從大到小的有序序列？假定每個元素的查找概率相等，試計(jì)算該二叉排序樹的平均查找長度畫出在此二叉排序樹中刪除“ 66”后的樹結(jié)構(gòu)。.給定關(guān)鍵詞輸入序列{CAP,AQU,PIS,ARI,TAU,GEM,CAN,LIB,VIR,LEO,SCO} ，假定關(guān)鍵詞比較按英文字典序，試畫出從一棵空樹開始，依上述順序(從左到右)輸入關(guān)鍵詞，用平衡樹的查找和插入算法生成一棵平衡樹的過程，并說明生成過程中采用了何種轉(zhuǎn)動方式進(jìn)行平衡調(diào)整，標(biāo)出樹中各結(jié)點(diǎn)的平衡系數(shù)。.假定對有序表：(3,4,5,7,24,30,42,54,63,72,87,9進(jìn)行折半查找，試回答下列問題：(1)畫出描述折半查找過程的判定樹；(2)若查找元素54,需依次與那些元素比較？(3)若查找元素90,需依次與那些元素比較？(4)假定每個元素的查找概率相等，求查找成功時的平均查找長度。第9章查找.選擇題1.C2.D3D4.A5.B6.1C6.2C7.1B7.2A9.C10.C11.B12.B15.D16.B17.D18.D19.D20.C

.判斷題1V2V3.x4a/5.V6.x7V8.x9.x10.x11.V12.X13V14.X三.填空題1.nn+1 2.6,9,11,12 3.526(第4層是葉子結(jié)點(diǎn)，每個結(jié)點(diǎn)兩個關(guān)鍵字)m-1,「m/2u-1 9.2,4,3小于等于表長的最大素?cái)?shù)或不包含小于 20的質(zhì)因子的合數(shù)8.(n+1)/2 9.(n+1)/n*log2(n+1)-1 10.結(jié)點(diǎn)的左子樹的高度減去結(jié)點(diǎn)的右子樹的高度(1)靜態(tài)查找表(2)動態(tài)查找樹表(3)哈希表(4)開放定址方法(5)鏈地址方法(6)再哈希(7)建立公共溢出區(qū)n1logm2口(2)+1 ,(n+1)/2(最壞情況是每個結(jié)點(diǎn)只要一個孩子結(jié)點(diǎn)的情況，這時的平均時間復(fù)雜度為(n+1)/2，而10gH5(n1))2是通常情況下的ASL)31主關(guān)鍵字插入 刪除16(1)low=mid+1(2)high=mid-1(3)high>=low四.應(yīng)用題1.概念是基本知識的主要部分，要牢固掌握。這里只列出一部分，目的是引起重視，解答略。3.散列地址0123456789關(guān)鍵字140192384275520比較次數(shù)11123412查找成功平均查找長度： ASLsucc=(1+1+1+2+3+4+1+2)/8=15/8以關(guān)鍵字27為例：H(27)=27%7=6(沖突)Hi=(6+1)%10=7(沖突)H2=(6+22)%10=0(沖突) 七=(6+33)%10=5所以比較了4次。注意：計(jì)算查找失敗時的平均查找長度，必須計(jì)算不在表中的關(guān)鍵字，當(dāng)其哈希地址為 i(0WiWm-1)時的查找次數(shù)。如下例中 m=10。對于關(guān)鍵字集｛30,15,21,40,25,26,36,37若查找表的裝填因子為0.8,哈希函數(shù)為H(key)=key%7采用線性探測再散列方法解決沖突，則哈希表如下：散列地址0123456789關(guān)鍵字2115303625402637比較次數(shù)11131126故查找失敗時的平均查找長度為： ASLunsucc=(4+8+7+6+5+4+3+2+1+1 )/10=4.64.0123456789012-11XASL查找成功=18/137.如下圖：(1)當(dāng)插入26后的樹形為:插入85后樹形為:(2)刪除53后為:(4)刪除結(jié)點(diǎn)66(4)