【正文】 采用線性探測法處理沖突的閉散列表中，假定裝填因子為 a ，則進行成功查找的平均查找長度為 ___________ 。 開放定址95. 對線性表 (18,25,63,50,42,32,90) 進行散列存儲時，若選用 H(K)=K % 9 作為散列函數(shù)，則散列地址為 0 的元素有 ________ 個，散列地址為 5 的元素有 ________ 個。292. 假定要對長度 n=100 的線性表進行散列存儲，并采用鏈接法處理沖突，則對于長度 m=20 的開散列表，每個散列地址的單鏈表的長度平均為 ________ 。 O (log 2 n)88. 根據(jù) n 個元素建立一棵二叉排序樹的時間復(fù)雜性大致為 ________ 。左子樹 查找成功 1183. 在一棵二叉排序樹中，每個分支結(jié)點的左子樹上所有結(jié)點的值一定 ________ 該結(jié)點的值，右子樹上所有結(jié)點的值一定 ________ 該結(jié)點的值。 理想平衡樹80. 假定對長度 n=50 的有序表進行二分查找，則對應(yīng)的判定樹高度為 ________ ，最后一層的結(jié)點數(shù)為 ________ 。 有序78. 從有序表 (12,18,30,43,56,78,82,95) 中分別二分查找 43 和 56 元素時，其查找長度分別為 ________ 和 ________ 。 插入 刪除73. 對于具有144 個記錄的文件，若采用分塊查找法，且每塊長度為8，則平均查找長度為__________. (5)鏈地址方法 (6)再哈希 (7)建立公共溢出區(qū)69. 在含有n個結(jié)點的二叉排序樹中查找一個關(guān)鍵字，進行關(guān)鍵字比較次數(shù)最大值是 。(1)45 (2)45 (3)46(塊內(nèi)順序查找)67. 假定有k個關(guān)鍵字互為同義詞，若用線性探測再散列法把這k個關(guān)鍵字存入散列表中，至少要進行__________次探測。2,4,364. 平衡二叉樹又稱_________，其定義是________。60. 順序查找n個元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為__ __次；當使用監(jiān)視哨時，若查找失敗，則比較關(guān)鍵字的次數(shù)為__ __。557．在線性表的散列存儲中，處理沖突有________和________兩種方法。253．在線性表的________存儲中，無法查找到一個元素的前驅(qū)或后繼元素。二叉搜索樹、理想平衡樹49．假定對長度n=50的有序表進行二分查找，則對應(yīng)的判定樹高度為________，判定樹中前5層的結(jié)點數(shù)為________，最后一層的結(jié)點數(shù)為________。O(log2n)45．以二分查找方法從長度為12的有序表中查找一個元素時，平均查找長度為________。O(n2)41．在線性表的________存儲中，對每一個元素只能采用順序查找。37．采用折半查找方法進行查找的數(shù)據(jù)序列應(yīng)為____順序存儲____且___有序_____。33．查找表的數(shù)據(jù)結(jié)構(gòu)有別于線性表、樹型結(jié)構(gòu)等，其邏輯結(jié)構(gòu)為____集合______。29．設(shè)順序表的表長為n，且查找每個元素的概率相等，則采用順序查找法查找表中任一元素，在查找成功時的平均查找長度為___(n+1)/2_______。插入 選擇25．對于線性表（18，25，63，50，41，32，90，66）進行散列存儲時，若選用H（K）=K%11作為散列函數(shù)，則散列地址為0的元素有______個，散列地址為3的元素有______個，散列地址為8的元素有______個。 有序序列 21．從有序表（12，18，30，43，56，78，82，95）中依次二分查找43和56元素時，其查找長度分別為___________和__________。開放定址法，鏈地址法17．在一棵m階B_樹上，每個非樹根結(jié)點的關(guān)鍵字數(shù)目最少為_______個，最多為_____個，其子樹數(shù)目最少為______，最多為____。tlchild=trchild=0。}bitree。19/715．下面程序段的功能是實現(xiàn)在二叉排序樹中插入一個新結(jié)點，請在下劃線處填上正確的內(nèi)容。4，1011．設(shè)在長度為20的有序表中進行二分查找，則比較一次查找成功的結(jié)點數(shù)有_________個，比較兩次查找成功有結(jié)點數(shù)有_________個。 else if(____________) high=mid1。}。_______________________。i++){s=(lklist *)malloc(sizeof(lklist))。im。} lklist。38．設(shè)散列函數(shù)H(k)=k mod p，解決沖突的方法為鏈地址法。else while (t!=0)if (tkey==k)_____________。 struct node *lchild。}if (_______________________ ) return(j)。while (hashtable[j].key!=kamp。 int others。增加13. 為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個問題是________________和_____________________。 A. 散列表長度 C. 4 A. 3 D. (d4)%m82. 在采用線性探測法處理沖突的閉散列表上，假定裝填因子 a 的值為 ，則查找任一元素的平均查找長度為 (B ) 。 B. 2 A. 1 ) 。 B .O (log 2 n ) D. O ( n log 2 n )75. 根據(jù) n 個元素建立一棵二叉搜索樹時，其時間復(fù)雜性大致為 ( B. O (1) ) 。A. O (n) D. h72. 從具有 n 個結(jié)點的二叉搜索樹中查找一個元素時，在平均情況下的時間復(fù)雜性大致為 ( B. log 2 n B. 12 A. 11 D. 7970. 在索引查找中，若用于保存數(shù)據(jù)元素的主表的長度為 117 ，它被均分為 9 子表，則索引查找的平均查找長度為 ( ) 。 B. (n/s+s)/2+1 C. O (1) A .20 A. n/2 D. 4/362. 對長度為 n 的單鏈有序表，若查找每個元素的概率相等，則查找任一元素的平均查找長度為 ( A A. ) 。A. n A． k B. k+1 C. k(k+1)/2 +k(k+1)/258．對線性表進行二分查找時，要求線性表必須（B ） ,且數(shù)據(jù)元素有序 ,且數(shù)據(jù)元素有序59. 若查找每個元素的概率相等，則在長度為 n 的順序表上查找任一元素的平均查找長度為 ( A. 8 B. 3 C. 5 D. 951．散列函數(shù)有一個共同的性質(zhì)，即函數(shù)值應(yīng)當以( D )取其值域的每個值。46．m階B樹是一棵( B ) A. m叉排序樹 B. m叉平衡排序樹 C. m1叉平衡排序樹 +1叉平衡排序樹47．在一棵含有n個關(guān)鍵字的m階B樹中進行查找，至多讀盤( C )次。A A. 分塊 B. 順序 C. 折半 D. 哈希44．分別以下列序列構(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, 20,110,130) D.(100,80,60,90,120,130,110)45．下面關(guān)于B和B+樹的敘述中，不正確的是(C )A. B樹和B+樹都是平衡的多叉樹。這種方式主要適合于( ) 31．設(shè)一組記錄的關(guān)鍵字key值為{62，50，14，28，19，35，47，56，83}，散列函數(shù)為H(key)=key mod 13，則它的開散列表中散列地址為1的鏈中的結(jié)點個數(shù)是（ ）A．1 C．3 32．已知一個有序表為（13，18，24，35，47，50，62，83，90，115，134），當二分檢索值為90的元素時，檢索成功需比較的次數(shù)是（　　?。? 33．閉散列表中由于散列到同一個地址而引起的“堆積”現(xiàn)象，是由（　　?。耙绯觥币鸬?4．在最壞的情況下，查找成功時二叉排序樹的平均查找長度（　　　）A．小于順序表的平均查找長度 B．大于順序表的平均查找長度C．與順序表的平均查找長度相同 D．無法與順序表的平均查找長度比較35．閉散列表中由于散列到同一個地址而引起的“堆積”現(xiàn)象，是由（　　?。〢．同義詞之間發(fā)生沖突引起的B．非同義詞之間發(fā)生沖突引起的C．同義詞之間或非同義詞之間發(fā)生沖突引起的D．散列表“溢出”引起的36．設(shè)有100個元素，用二分法查找時，最大比較次數(shù)是（ ）。A．n/m B．m/n C．n/(n+m) D．m/(n+m)23．從一棵B_樹刪除元素的過程中，若最終引起樹根結(jié)點的合并，則新樹高度是（ ）。A. 4 B. 5 C. 6 D. 718．二叉排序樹中左子樹上所有結(jié)點的值均（ ）根結(jié)點的值。 A. 小于等于m的最大奇數(shù) B. 小于等于m的最大素數(shù)C. 小于等于m的最大偶數(shù) D. 小于等于m的最大合數(shù)14．設(shè)順序表的長度為n，則順序查找的平均比較次數(shù)為（ ）。A. 1 B. 2 C. 3 D. 410．設(shè)某散列表的長度為100，散列函數(shù)H(k)=k % P，則P通常情況下最好選擇（ ）。A. 25 B. 10 C. 7 D. 16．順序查找不論在順序線性表中還是在鏈式線性表中的時間復(fù)雜度為（ ）。數(shù)據(jù)結(jié)構(gòu)練習 第八章 查找[19]中，第一個元素放A[1]中，現(xiàn)進行二分查找，則查找A［3］的比較序列的下標依次為( )A. 1，2，3 B. 9，5，2，3C. 9，5，3 D. 9，4，2，32．設(shè)二叉排序樹中有n個結(jié)點，則在二叉排序樹的平均平均查找長度為（ ）。A. log2n+1 B. log2n1 C. log2n D. log2(n+1)5．設(shè)有序表中有1000個元素，則用二分查找查找元素X最多需要比較（ ）次。A. 先序遍歷 B. 中序遍歷 C. 后序遍歷 D. 層次遍歷9．設(shè)一組初始記錄關(guān)鍵字序列為(13，18，24，35，47，50，62，83，90，115，134),則利用二分法查找關(guān)鍵字90需要比較的關(guān)鍵字個數(shù)為（ ）。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個存儲單元，散列函數(shù)H(key)= key % p，則p最好選擇（ ）。A. 6 B. 11 C. 5 D. 17．設(shè)有一組初始記錄關(guān)鍵字序列為(34，76，45，18，26，54，92)，則由這組記錄關(guān)鍵字生成的二叉排序樹的深度為（ ）?？捎糜诮鉀Q上述問題的是( ) 21．22．在線性表的散列存儲中，若用m表示散列表的長度，n表示待散列存儲的元素的個數(shù)，則裝填因子a等于（ ）。A．2 B．3 C．4 D．526．對一棵二叉排序樹采用中根遍歷進行輸出的數(shù)據(jù)一定是（　?。? 27．一個有序表為{1，3，9，12，32，41，45，62，75，77，82，95，100}，當二分查找值為82的結(jié)點時，查找成功時的比較次數(shù)為（　?。? 28．若構(gòu)造一棵具有n個結(jié)點的二叉排序樹，最壞的情況下其深度不超過( )A. B. n C. D. n+129．閉散列表中由于散列到同一個地址而引起的“堆積”現(xiàn)象，是( ) “溢出”引起的30．在對查找表的查找過程中，若被查找的數(shù)據(jù)元素不存在，則把該數(shù)據(jù)元素插入到集合中。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．在一個有N個元素的有序單鏈表中查找具有給定關(guān)鍵字的結(jié)點，平均情況下的時間復(fù)雜性為( B )(1) (N) （N2） (NlogN)41．對線性表進行二分查找時，要求線性表必須（B ）