【正文】 數(shù)據(jù)結(jié)構(gòu)練習(xí) 第八章 查找[19]中，第一個(gè)元素放A[1]中，現(xiàn)進(jìn)行二分查找，則查找A［3］的比較序列的下標(biāo)依次為( )A. 1，2，3 B. 9，5，2，3C. 9，5，3 D. 9，4，2，32．設(shè)二叉排序樹中有n個(gè)結(jié)點(diǎn)，則在二叉排序樹的平均平均查找長度為（ ）。A. O(1) B. O(log2n) C. O(n) D. O(n2)3．在二叉排序樹中插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為（ ）。A. O(1) B. O(n) C. O(log2n) D. O(n2)4．設(shè)有序順序表中有n個(gè)數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過（ ）。A. log2n+1 B. log2n1 C. log2n D. log2(n+1)5．設(shè)有序表中有1000個(gè)元素，則用二分查找查找元素X最多需要比較（ ）次。A. 25 B. 10 C. 7 D. 16．順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時(shí)間復(fù)雜度為（ ）。A. O(n) B. O(n2) C. O(n1/2) D. O(1og2n)7．設(shè)二叉排序樹上有n個(gè)結(jié)點(diǎn)，則在二叉排序樹上查找結(jié)點(diǎn)的平均時(shí)間復(fù)雜度為（ ）。A. O(n) B. O(n2) C. O(nlog2n) D. O(1og2n)8．（ ）二叉排序樹可以得到一個(gè)從小到大的有序序列。A. 先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 層次遍歷9．設(shè)一組初始記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個(gè)數(shù)為（ ）。A. 1 B. 2 C. 3 D. 410．設(shè)某散列表的長度為100，散列函數(shù)H(k)=k % P，則P通常情況下最好選擇（ ）。A. 99 B. 97 C. 91 D. 9311．在二叉排序樹中插入一個(gè)關(guān)鍵字值的平均時(shí)間復(fù)雜度為（ ）。A. O(n) B. O(1og2n) C. O(nlog2n) D. O(n2)12．設(shè)一個(gè)順序有序表A[1:14]中有14個(gè)元素，則采用二分法查找元素A[4]的過程中比較元素的順序?yàn)? )。A. A[1]，A[2]，A[3]，A[4] [1]，A[14]，A[7]，A[4][7]，A[3]，A[5]，A[4] D. A[7]，A[5] ，A[3]，A[4]13．設(shè)散列表中有m個(gè)存儲(chǔ)單元，散列函數(shù)H(key)= key % p，則p最好選擇（ ）。 A. 小于等于m的最大奇數(shù) B. 小于等于m的最大素?cái)?shù)C. 小于等于m的最大偶數(shù) D. 小于等于m的最大合數(shù)14．設(shè)順序表的長度為n，則順序查找的平均比較次數(shù)為（ ）。A. n B. n/2 C. (n+1)/2 D. (n1)/215．設(shè)有序表中的元素為(13，18，24，35，47，50，62)，則在其中利用二分法查找值為24的元素需要經(jīng)過（ ）次比較。A. 1 B. 2 C. 3 D. 416．設(shè)順序線性表的長度為30，分成5塊，每塊6個(gè)元素，如果采用分塊查找，則其平均查找長度為（ ）。A. 6 B. 11 C. 5 D. 17．設(shè)有一組初始記錄關(guān)鍵字序列為(34，76，45，18，26，54，92)，則由這組記錄關(guān)鍵字生成的二叉排序樹的深度為（ ）。A. 4 B. 5 C. 6 D. 718．二叉排序樹中左子樹上所有結(jié)點(diǎn)的值均（ ）根結(jié)點(diǎn)的值。A. B. C. = D. !=19．設(shè)有n個(gè)關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測(cè)法把這n個(gè)關(guān)鍵字映射到HASH表中需要做（ ）次線性探測(cè)。A. n2 B. n(n+1) C. n(n+1)/2 D. n(n1)/220．用散列函數(shù)求元素在散列表中的存儲(chǔ)位置時(shí)，可能會(huì)出現(xiàn)不同的關(guān)鍵字得到相同散列函數(shù)值的沖突現(xiàn)象。可用于解決上述問題的是( ) 21．22．在線性表的散列存儲(chǔ)中，若用m表示散列表的長度，n表示待散列存儲(chǔ)的元素的個(gè)數(shù)，則裝填因子a等于（ ）。A．n/m B．m/n C．n/(n+m) D．m/(n+m)23．從一棵B_樹刪除元素的過程中，若最終引起樹根結(jié)點(diǎn)的合并，則新樹高度是（ ）。A．原樹高度加1 B．原樹高度減1 C．原樹高度 D．不確定24．向二叉搜索樹中插入一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為（　?。?。（log2n） B. O(n) C. O(1) D. 0(nlog2n)25．5階B樹中，每個(gè)結(jié)點(diǎn)最多有（）個(gè)關(guān)鍵碼。A．2 B．3 C．4 D．526．對(duì)一棵二叉排序樹采用中根遍歷進(jìn)行輸出的數(shù)據(jù)一定是（　　） 27．一個(gè)有序表為{1，3，9，12，32，41，45，62，75，77，82，95，100}，當(dāng)二分查找值為82的結(jié)點(diǎn)時(shí)，查找成功時(shí)的比較次數(shù)為（　?。? 28．若構(gòu)造一棵具有n個(gè)結(jié)點(diǎn)的二叉排序樹，最壞的情況下其深度不超過( )A. B. n C. D. n+129．閉散列表中由于散列到同一個(gè)地址而引起的“堆積”現(xiàn)象，是( ) “溢出”引起的30．在對(duì)查找表的查找過程中，若被查找的數(shù)據(jù)元素不存在，則把該數(shù)據(jù)元素插入到集合中。這種方式主要適合于( ) 31．設(shè)一組記錄的關(guān)鍵字key值為{62，50，14，28，19，35，47，56，83}，散列函數(shù)為H(key)=key mod 13，則它的開散列表中散列地址為1的鏈中的結(jié)點(diǎn)個(gè)數(shù)是（ ）A．1 C．3 32．已知一個(gè)有序表為（13，18，24，35，47，50，62，83，90，115，134），當(dāng)二分檢索值為90的元素時(shí)，檢索成功需比較的次數(shù)是（　　?。? 33．閉散列表中由于散列到同一個(gè)地址而引起的“堆積”現(xiàn)象，是由（　　?。耙绯觥币鸬?4．在最壞的情況下，查找成功時(shí)二叉排序樹的平均查找長度（　　?。〢．小于順序表的平均查找長度 B．大于順序表的平均查找長度C．與順序表的平均查找長度相同 D．無法與順序表的平均查找長度比較35．閉散列表中由于散列到同一個(gè)地址而引起的“堆積”現(xiàn)象，是由（　　?。〢．同義詞之間發(fā)生沖突引起的B．非同義詞之間發(fā)生沖突引起的C．同義詞之間或非同義詞之間發(fā)生沖突引起的D．散列表“溢出”引起的36．設(shè)有100個(gè)元素，用二分法查找時(shí)，最大比較次數(shù)是（ ）。A．25 B．7 C．10 D．137．設(shè)有1000個(gè)元素，用二分法查找時(shí)，最小比較次數(shù)為（ ）A．0 B．1 C．10 D．50038．在一個(gè)長度為n的順序線性表中順序查找值為x的元素時(shí)，查找成功時(shí)的平均查找長度（即x與元素的平均比較次數(shù)，假定查找每個(gè)元素的概率都相等）為 ( )。A. n B. n/2 C. (n+1)/2 D. (n1)/239．對(duì)有14個(gè)數(shù)據(jù)元素的有序表R[14]進(jìn)行折半搜索，搜索到R[3]的關(guān)鍵碼等于給定值，此時(shí)元素比較順序依次為（ ）。A．R[0]，R[1]，R[2]，R[3] B．R[0]，R[13]，R[2]，R[3]C．R[6]，R[2]，R[4]，R[3] D．R[6]，R[4]，R[2]，R[3]40．在一個(gè)有N個(gè)元素的有序單鏈表中查找具有給定關(guān)鍵字的結(jié)點(diǎn)，平均情況下的時(shí)間復(fù)雜性為( B )(1) (N) （N2） (NlogN)41．對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須（B ） ,且數(shù)據(jù)元素有序 ,且數(shù)據(jù)元素有序42．下列二叉排序樹中查找效率最高的是( A ) 43．如果要求一個(gè)線性表既能較快地查找，又能適應(yīng)動(dòng)態(tài)變化的要求，可以采用下列哪一種查找方法。A A. 分塊 B. 順序 C. 折半 D. 哈希44．分別以下列序列構(gòu)造二叉排序樹，與用其它三個(gè)序列所構(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, 20,110,130) D.(100,80,60,90,120,130,110)45．下面關(guān)于B和B+樹的敘述中，不正確的是(C )A. B樹和B+樹都是平衡的多叉樹。 B. B樹和B+樹都可用于文件的索引結(jié)構(gòu)。C. B樹和B+樹都能有效地支持順序檢索。 D. B樹和B+樹都能有效地支持隨機(jī)檢索。46．m階B樹是一棵( B ) A. m叉排序樹 B. m叉平衡排序樹 C. m1叉平衡排序樹 +1叉平衡排序樹47．在一棵含有n個(gè)關(guān)鍵字的m階B樹中進(jìn)行查找，至多讀盤( C )次。48．一棵3階B樹中含有2047個(gè)關(guān)鍵字，包括葉子結(jié)點(diǎn)層，該樹的最大深度為( B )。A, 11 B. 12 C. 13 D. 14 49．關(guān)于雜湊查找說法不正確的有幾個(gè)( B ) （1）采用鏈地址法解決沖突時(shí)，查找一個(gè)元素的時(shí)間是相同的 （2）采用鏈地址法解決沖突時(shí)，若插入規(guī)定總是在鏈?zhǔn)?，則插入任一個(gè)元素的時(shí)間是相同的 （3）用鏈地址法解決沖突易引起聚集現(xiàn)象 （4）再哈希法不易產(chǎn)生聚集A. 1 B. 2 C. 3 D. 450．設(shè)哈希表長M=14，哈希函數(shù)H(KEY)=KEY MOD 11。表中已有4個(gè)結(jié)點(diǎn)：ADDR(15)=4， ADDR(38)=5，ADDR(61)=6，ADDR(84)=7，其余地址為空，如用二次探測(cè)再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)的地址是( D )。 A. 8 B. 3 C. 5 D. 951．散列函數(shù)有一個(gè)共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以( D )取其值域的每個(gè)值。A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率52．將10個(gè)元素散列到100000個(gè)單元的哈希表中，則（C ）產(chǎn)生沖突。A. 一定會(huì) B. 一定不會(huì) C. 仍可能會(huì)53．長度為10的按關(guān)鍵字有序的查找表采用順序組織方式。若采用折半查找方法，則在等概率情況下，查找失敗時(shí)的ASL值是（D ）54．在采用拉鏈法處理沖突所構(gòu)成的開散列表上查找某一關(guān)鍵字，在查找成功的情況下，所探測(cè)的這些位置上的鍵值（ A ） 55．二叉查找樹的查找效率與二叉樹的樹型有關(guān), 在 (C )時(shí)其查找效率最低。A. 結(jié)點(diǎn)太多 B. 完全二叉樹 C. 呈單枝樹 D. 結(jié)點(diǎn)太復(fù)雜。56．具有12個(gè)關(guān)鍵字的有序表，折半查找的平均查找長度（A ）A. B. 4 C. D. 557．哈希查找中k個(gè)關(guān)鍵字具有同一哈希值，若用線性探測(cè)法將這k個(gè)關(guān)鍵字對(duì)應(yīng)的記錄存入哈希表中，至少要進(jìn)行( C )次探測(cè)。A． k B. k+1 C. k(k+1)/2 +k(k+1)/258．對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須（B ） ,且數(shù)據(jù)元素有序 ,且數(shù)據(jù)元素有序59. 若查找每個(gè)元素的概率相等，則在長度為 n 的順序表上查找任一元素的平均查找長度為 ( D ) 。 A. n B. n+1 C. (n1)/2 D. (n+1)/260. 對(duì)長度為 10 的順序表進(jìn)行查找，若查找前面 5 個(gè)元素的概率相同，均為 1/8 ，查找后面 5 個(gè)元素的概率相同，均為 3/40 ，則查找任一元素的平均查找長度為 ( C ) 。 A. B. 5 D. 19/461. 對(duì)長度為 3 的順序表進(jìn)行查找，若查找