數(shù)據(jù)結(jié)構(gòu)練習(xí)-查找

1、數(shù)據(jù)結(jié)構(gòu)練習(xí)第八章 查找1. 若有 18個(gè)元素的有序表存放在一維數(shù)組A19 中，第一個(gè)元素放A1 中，現(xiàn)進(jìn)行二分查找，則查找A 3的比較序列的下標(biāo)依次為()A. 1 ，2，3B. 9 ，5，2，3C. 9 ，5，3D. 9 ，4，2，32設(shè)二叉排序樹(shù)中有n 個(gè)結(jié)點(diǎn)，則在二叉排序樹(shù)的平均平均查找長(zhǎng)度為() 。A. O(1)B. O(log 2n)C. O(n)D. O(n2)3在二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為() 。2A. O(1)B. O(n)C. O(log 2n) D. O(n 2)4 .設(shè)有序順序表中有n個(gè)數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的最多比較次數(shù)不超過(guò)() 。A.

2、log 2n+1B. log 2n-1C. log2nD. log2(n+1)5 .設(shè)有序表中有1000個(gè)元素，則用二分查找查找元素X最多需要比較()次。A. 25B. 10C. 7D. 16順序查找不論在順序線性表中還是在鏈?zhǔn)骄€性表中的時(shí)間復(fù)雜度為() 。A. O(n)B. O(n2)C. O(n 1/2)D. O(1og 2n)7設(shè)二叉排序樹(shù)上有n 個(gè)結(jié)點(diǎn)，則在二叉排序樹(shù)上查找結(jié)點(diǎn)的平均時(shí)間復(fù)雜度為( ) 。A. O(n)B. O(n2)C. O(nlog 2n) D. O(1og2n)8 ()二叉排序樹(shù)可以得到一個(gè)從小到大的有序序列。A. 先序遍歷B. 中序遍歷C. 后序遍歷D. 層次遍

3、歷9設(shè)一組初始記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90，115，134), 則利用二分法查找關(guān)鍵字90 需要比較的關(guān)鍵字個(gè)數(shù)為() 。A. 1B. 2C. 3 D. 410.設(shè)某散列表的長(zhǎng)度為100,散列函數(shù)H(k)=k %P,則P通常情況下最好選擇()。A. 99B. 97C. 91D. 9311在二叉排序樹(shù)中插入一個(gè)關(guān)鍵字值的平均時(shí)間復(fù)雜度為() 。A. O(n)B. O(1og2n)C. O(nlog2n) D. O(n2)12設(shè)一個(gè)順序有序表A1:14 中有 14個(gè)元素，則采用二分法查找元素A4 的過(guò)程中比較元素的順序?yàn)? ) 。A. A1 ， A2 ，

4、A3 ， A4B.A1 ， A14， A7， A4C. A7 ， A3 ， A5 ， A4 D. A7， A5 ， A3 ， A413 .設(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è)順序表的長(zhǎng)度為n,則順序查找的平均比較次數(shù)為()。A. nB. n/2C. (n+1)/2D. (n-1)/215設(shè)有序表中的元素為(13， 18， 24， 35， 47， 50， 62)，則在其中利用二分法查找值為24 的元素需要經(jīng)過(guò)()次比較。A. 1 B. 2C. 3D

5、. 416 .設(shè)順序線性表的長(zhǎng)度為30,分成5塊，每塊6個(gè)元素，如果采用分塊查找， 則其平均查找長(zhǎng)度為（）。A. 6B. 11C. 5D. 6.517 .設(shè)有一組初始記錄關(guān)鍵字序列為（34, 76, 45, 18, 26, 54, 92）,則由這組 記錄關(guān)鍵字生成的二叉排序樹(shù)的深度為（）。A. 4B. 5C. 6D. 718 .二叉排序樹(shù)中左子樹(shù)上所有結(jié)點(diǎn)的值均（）根結(jié)點(diǎn)的值。A <B. >C. =D. !=19 .設(shè)有n個(gè)關(guān)鍵字具有相同的Hash函數(shù)值，則用線性探測(cè)法把這 n個(gè)關(guān)鍵字 映射到HASHft中需要做（）次線性探測(cè)。A. n 2 B. n（n+1）C. n（n+1）/2

6、D. n（n-1）/220 .用散列函數(shù)求元素在散列表中的存儲(chǔ)位置時(shí)，可能會(huì)出現(xiàn)不同的關(guān)鍵字得到相同散列函數(shù)值的沖突現(xiàn)象?？捎糜诮鉀Q上述問(wèn)題的是（）A.線性探測(cè)法B.除留余數(shù)法C.平方取中法D.折疊法21 .22 .在線性表的散列存儲(chǔ)中，若用 m表示散列表的長(zhǎng)度，n表示待散列存儲(chǔ)的元 素的個(gè)數(shù)，則裝填因子等于（）。A. n/mB . m/n C , n/（n+m） D , m/（n+m）23 .從一棵B別刪除元素的過(guò)程中，若最終引起樹(shù)根結(jié)點(diǎn)的合并，則新樹(shù)高度是（）。A.原樹(shù)高度加1B ,原樹(shù)高度減1C.原樹(shù)高度D.不確定24 .向二叉搜索樹(shù)中插入一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為（）。A .O （

7、log 2n）B. O（n） C. O（1）D. 0（nlog2n）25 . 5階B樹(shù)中，每個(gè)結(jié)點(diǎn)最多有（）個(gè)關(guān)鍵碼。A. 2 B . 3C. 4 D . 526 .對(duì)一棵二叉排序樹(shù)采用中根遍歷進(jìn)行輸出的數(shù)據(jù)一定是（）A.遞增或遞減序列B.遞減序列C.無(wú)序序列D.遞增序列27 . 一個(gè)有序表為1 , 3, 9, 12, 32, 41, 45, 62, 75, 77, 82, 95, 100,當(dāng) 二分查找值為82的結(jié)點(diǎn)時(shí)，查找成功時(shí)的比較次數(shù)為（）A.1B.2C.4D.828 .若構(gòu)造一棵具有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)，最壞的情況下其深度不超過(guò)（）A. 1B. n C. D. n+129 .閉散列表中由于散列到同一個(gè)地址而引起的“堆積”現(xiàn)象，是 （）A.由同義詞之間發(fā)