【正文】 _____ 。 296. 在開(kāi)散列表中插入一個(gè)元素的時(shí)間復(fù)雜性為 __________ ，查找一個(gè)元素的時(shí)間復(fù)雜性為 ________ ，假定裝填因子為 a 。 開(kāi)放定址95. 對(duì)線性表 (18,25,63,50,42,32,90) 進(jìn)行散列存儲(chǔ)時(shí)，若選用 H(K)=K % 9 作為散列函數(shù)，則散列地址為 0 的元素有 ________ 個(gè)，散列地址為 5 的元素有 ________ 個(gè)。n/m94. 在開(kāi)散列表中，處理沖突的方法為 ________ 法，在閉散列表中，處理沖突的方法為 ____________ 法。292. 假定要對(duì)長(zhǎng)度 n=100 的線性表進(jìn)行散列存儲(chǔ)，并采用鏈接法處理沖突，則對(duì)于長(zhǎng)度 m=20 的開(kāi)散列表，每個(gè)散列地址的單鏈表的長(zhǎng)度平均為 ________ 。190. 假定對(duì)線性表 (38,25,74,52,48) 進(jìn)行散列存儲(chǔ)，采用 H(K)=K % 7 作為散列函數(shù)，采用線性探測(cè)法處理沖突，則在建立閉散列表的過(guò)程中，將會(huì)碰到 ________ 次存儲(chǔ)沖突。 O (log 2 n)88. 根據(jù) n 個(gè)元素建立一棵二叉排序樹(shù)的時(shí)間復(fù)雜性大致為 ________ 。O (log 2 n) 左子樹(shù) 右子樹(shù)86. 向一棵二叉排序樹(shù)中插入一個(gè)元素時(shí)，若元素的值小于根結(jié)點(diǎn)的值，則接著向根結(jié)點(diǎn)的 ________ 插入，若元素的值大于根結(jié)點(diǎn)的值，則接著向根結(jié)點(diǎn)的 ________ 插入。查找成功 大于84. 對(duì)一棵二叉排序樹(shù)進(jìn)行中序遍歷時(shí)，得到的結(jié)點(diǎn)序列是一個(gè) ________ 。1183. 在一棵二叉排序樹(shù)中，每個(gè)分支結(jié)點(diǎn)的左子樹(shù)上所有結(jié)點(diǎn)的值一定 ________ 該結(jié)點(diǎn)的值，右子樹(shù)上所有結(jié)點(diǎn)的值一定 ________ 該結(jié)點(diǎn)的值。 1981. 假定在索引查找中，查找表長(zhǎng)度為 n ，每個(gè)子表的長(zhǎng)度相等，設(shè)為 s ，則進(jìn)行成功查找的平均查找長(zhǎng)度為 ____________ 。 理想平衡樹(shù)80. 假定對(duì)長(zhǎng)度 n=50 的有序表進(jìn)行二分查找，則對(duì)應(yīng)的判定樹(shù)高度為 ________ ，最后一層的結(jié)點(diǎn)數(shù)為 ________ 。 379. 二分查找所對(duì)應(yīng)的判定樹(shù)，既是一棵 _______ ，又是一棵 ________ 。 有序78. 從有序表 (12,18,30,43,56,78,82,95) 中分別二分查找 43 和 56 元素時(shí)，其查找長(zhǎng)度分別為 ________ 和 ________ 。677. 以二分查找方法在一個(gè)查找表上進(jìn)行查找時(shí)，該查找表必須組織成 ________ 存儲(chǔ)的 ________ 表。 (n+1)/2 插入 刪除73. 對(duì)于具有144 個(gè)記錄的文件，若采用分塊查找法，且每塊長(zhǎng)度為8，則平均查找長(zhǎng)度為_(kāi)_________. 2k171. 假定查找有序表A[1..12]中每個(gè)元素的概率相等，則進(jìn)行二分查找時(shí)的平均查找長(zhǎng)度為_(kāi)_________ (5)鏈地址方法 (6)再哈希 (7)建立公共溢出區(qū)69. 在含有n個(gè)結(jié)點(diǎn)的二叉排序樹(shù)中查找一個(gè)關(guān)鍵字，進(jìn)行關(guān)鍵字比較次數(shù)最大值是 。處理哈希沖突的方法有__(4)__、__(5)__、__(6)__和__(7)__。(1)45 (2)45 (3)46(塊內(nèi)順序查找)67. 假定有k個(gè)關(guān)鍵字互為同義詞，若用線性探測(cè)再散列法把這k個(gè)關(guān)鍵字存入散列表中，至少要進(jìn)行__________次探測(cè)。65. 在哈希函數(shù)H（key）=key%p中，p值最好取_________。2,4,364. 平衡二叉樹(shù)又稱_________，其定義是________。哈希查找 62. 在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比較的元素下標(biāo)依次為_(kāi)_________。60. 順序查找n個(gè)元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為_(kāi)_ __次；當(dāng)使用監(jiān)視哨時(shí)，若查找失敗，則比較關(guān)鍵字的次數(shù)為_(kāi)_ __。259．在堆排序的過(guò)程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行篩運(yùn)算的時(shí)間復(fù)雜度為_(kāi)________,整個(gè)堆排序過(guò)程的時(shí)間復(fù)雜度為_(kāi)_______________。557．在線性表的散列存儲(chǔ)中，處理沖突有________和________兩種方法。鏈接55．假定對(duì)線性表(38,25,74,52,48)進(jìn)行散列存儲(chǔ)，采用H(K)=K % 7作為散列函數(shù)，若分別采用線性探查法和鏈接法處理沖突，則對(duì)各自散列表進(jìn)行查找的平均查找長(zhǎng)度分別為_(kāi)______和________。253．在線性表的________存儲(chǔ)中，無(wú)法查找到一個(gè)元素的前驅(qū)或后繼元素。索引、開(kāi)始地址51．假定一個(gè)線性表為(12,23,74,55,63,40,82,36)，若按Key % 3條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個(gè)子表，則得到的三個(gè)子表分別為_(kāi)_______、________和________。二叉搜索樹(shù)、理想平衡樹(shù)49．假定對(duì)長(zhǎng)度n=50的有序表進(jìn)行二分查找，則對(duì)應(yīng)的判定樹(shù)高度為_(kāi)_______，判定樹(shù)中前5層的結(jié)點(diǎn)數(shù)為_(kāi)_______，最后一層的結(jié)點(diǎn)數(shù)為_(kāi)_______。順序、有序47．從有序表(12,18,30,43,56,78,82,95)中依次二分查找43和56元素時(shí)，其查找長(zhǎng)度分別為_(kāi)_______和________。O(log2n)45．以二分查找方法從長(zhǎng)度為12的有序表中查找一個(gè)元素時(shí)，平均查找長(zhǎng)度為_(kāi)_______。（n+1）/243．以順序查找方法從長(zhǎng)度為n的線性表中查找一個(gè)元素時(shí)，平均查找長(zhǎng)度為_(kāi)_______，時(shí)間復(fù)雜度為_(kāi)_______。O(n2)41．在線性表的________存儲(chǔ)中，對(duì)每一個(gè)元素只能采用順序查找。39．對(duì)于具有n個(gè)元素的數(shù)據(jù)序列，采用順序查找法，其平均查找長(zhǎng)度為_(kāi)___(n+1)/2______。37．采用折半查找方法進(jìn)行查找的數(shù)據(jù)序列應(yīng)為_(kāi)___順序存儲(chǔ)____且___有序_____。35．在開(kāi)散列表上查找某元素時(shí)，通常分兩步進(jìn)行，首先必須計(jì)算該鍵值的散列地址，然后在地址指針?biāo)竉________同義詞子表_______中查找該結(jié)點(diǎn)。33．查找表的數(shù)據(jù)結(jié)構(gòu)有別于線性表、樹(shù)型結(jié)構(gòu)等，其邏輯結(jié)構(gòu)為_(kāi)___集合______。31．一棵平衡二叉樹(shù)中任一結(jié)點(diǎn)的平衡因子只可能是__1，0，1_____。29．設(shè)順序表的表長(zhǎng)為n，且查找每個(gè)元素的概率相等，則采用順序查找法查找表中任一元素，在查找成功時(shí)的平均查找長(zhǎng)度為_(kāi)__(n+1)/2_______。27．在一棵二叉排序樹(shù)上按_____中序_______遍歷得到的結(jié)點(diǎn)序列是一個(gè)有序序列。插入 選擇25．對(duì)于線性表（18，25，63，50，41，32，90，66）進(jìn)行散列存儲(chǔ)時(shí)，若選用H（K）=K%11作為散列函數(shù)，則散列地址為0的元素有______個(gè)，散列地址為3的元素有______個(gè)，散列地址為8的元素有______個(gè)。13， O()23．一棵B樹(shù)中的所有葉子結(jié)點(diǎn)均處在_____________上。 有序序列 21．從有序表（12，18，30，43，56，78，82，95）中依次二分查找43和56元素時(shí)，其查找長(zhǎng)度分別為_(kāi)__________和__________。查找成功、左子樹(shù)、右子樹(shù)19．對(duì)于二分查找所對(duì)應(yīng)的判定樹(shù)，它既是一棵_ ____，又是一棵_____ __ ___。開(kāi)放定址法，鏈地址法17．在一棵m階B_樹(shù)上，每個(gè)非樹(shù)根結(jié)點(diǎn)的關(guān)鍵字?jǐn)?shù)目最少為_(kāi)______個(gè)，最多為_(kāi)____個(gè)，其子樹(shù)數(shù)目最少為_(kāi)_____，最多為_(kāi)___。else__________________________。tlchild=trchild=0。t,int k){if(t==0) {____________________________。}bitree。struct node *lchild。19/715．下面程序段的功能是實(shí)現(xiàn)在二叉排序樹(shù)中插入一個(gè)新結(jié)點(diǎn)，請(qǐng)?jiān)谙聞澗€處填上正確的內(nèi)容。h13．設(shè)散列表的長(zhǎng)度為8，散列函數(shù)H(k)=k % 7，用線性探測(cè)法解決沖突，則根據(jù)一組初始關(guān)鍵字序列(8，15，16，22，30，32)構(gòu)造出的散列表的平均查找長(zhǎng)度是________。4，1011．設(shè)在長(zhǎng)度為20的有序表中進(jìn)行二分查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)有_________個(gè)，比較兩次查找成功有結(jié)點(diǎn)數(shù)有_________個(gè)。 } return(0)。 else if(____________) high=mid1。 while(low=high){ ________________________________。}。struct record{int key。_______________________。k=a[i] % p。i++){s=(lklist *)malloc(sizeof(lklist))。for(i=0。im。 lklist *s。} lklist。typedef struct node {int key。38．設(shè)散列函數(shù)H(k)=k mod p，解決沖突的方法為鏈地址法。 else_____________。else while (t!=0)if (tkey==k)_____________。}bitree。 struct node *lchild。} j+1，hashtable[j].key==k6．下列算法實(shí)現(xiàn)在二叉排序樹(shù)上查找關(guān)鍵值k，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。}if (_______________________ ) return(j)。hashtable[j].flag!=0){j=(____) %m。while (hashtable[j].key!=kamp。int hashsqsearch(struct record hashtable[ ],int k){int i,j。 int others。75．下列算法實(shí)現(xiàn)在順序散列表中查找值為x的關(guān)鍵字，請(qǐng)?jiān)谙聞澗€處填上正確的語(yǔ)句。增加13. 為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個(gè)問(wèn)題是________________和_____________________。 D. 處理沖突方法85. 對(duì)順序表進(jìn)行二分查找時(shí)，要求順序表必須： ，且數(shù)據(jù)元素有序 ，且數(shù)據(jù)元素有序【解答】B86. 下列二叉排序樹(shù)中查找效率最高的是： 【解答】A二、填空題1．假定一個(gè)線性表為(12,23,74,55,63,40)，若按Key % 4條件進(jìn)行劃分，使得同一余數(shù)的元素成為一個(gè)子表，則得到的四個(gè)子表分別為_(kāi)____________、___________、________和___________。 A. 散列表長(zhǎng)度 D. 84. 在散列查找中，平均查找長(zhǎng)度主要與 ( C. 4 A. 3 ) 。 B. D. (d4)%m82. 在采用線性探測(cè)法處理沖突的閉散列表上，假定裝填因子 a 的值為 ，則查找任一元素的平均查找長(zhǎng)度為 (B C . (d+4)%m ) 。C B. d+1 A. d D. 480. 若根據(jù)查找表建立長(zhǎng)度為 m 的閉散列表，采用線性探測(cè)法處理沖突，假定對(duì)一個(gè)元素第一次計(jì)算的散列地址為 d ，則下一次的散列地址為 (D B. 2 A. 1 ) 。 C. 3 ) 。 C. 12 ) 。 B. 2 ~ 2 D .O ( n log 2 n )76. 在一棵平衡二叉排序樹(shù)中，每個(gè)結(jié)點(diǎn)的平衡因子的取值范圍是 ( B .O (log 2 n ) D. O ( n log 2 n )75. 根據(jù) n 個(gè)元素建立一棵二叉搜索樹(shù)時(shí)，其時(shí)間復(fù)雜性大致為 ( B .O (log 2 n ) D. O (n 2 )74. 向具有 n 個(gè)結(jié)點(diǎn)的二叉搜索樹(shù)中插入一個(gè)元素時(shí)，其時(shí)間復(fù)雜性大致為 ( B. O (1) ) 。 C. O (log 2 n) A. O (n) C D. h72. 從具有 n 個(gè)結(jié)點(diǎn)的二叉搜索樹(shù)中查找一個(gè)元素時(shí)，在平均情況下的時(shí)間復(fù)雜性大致為 ( B. log 2 n D. 971. 在一棵深度為 h 的具有 n 個(gè)元素的二叉排序樹(shù)中，查找所有元素的最長(zhǎng)查找長(zhǎng)度為 ( B. 12 A. 11 B D. 7970. 在索引查找中，若用于保存數(shù)據(jù)元素的主表的長(zhǎng)度為 117 ，它被均分為 9 子表，則索引查找的平均查找長(zhǎng)度為 ( B. 24 A .13 ) 。 B. (n/s+s)/2+1 A. (n+s)/2 D. (k+n/k)/2+168. 在索引查找中，若用于保存數(shù)據(jù)元素的主表的長(zhǎng)度為 n ，它被均分為若干個(gè)子表，每個(gè)子表的長(zhǎng)度均為 s ，則索引查找的平均查找長(zhǎng)度為 ( ) 。 C. O (1) D D. 566. 對(duì)具有 n 個(gè)元素的有序表采用二分查找，則算法的時(shí)間復(fù)雜性為 ( C. 4 B. 3 ) 。 ) 。 C. 25 A .20 ) 的 9 分之一。A. n/2 D. 4/362. 對(duì)長(zhǎng)度為 n 的單鏈有序表，若查找每個(gè)元素的概率相等，則查找任一元素的平均查找長(zhǎng)度為 ( C. 7/3 B .2 A D. 19/461. 對(duì)長(zhǎng)度為 3 的順序表進(jìn)行查找，若查找第一個(gè)元素的概率為 1/2 ，查找第二個(gè)元素的概率為 1/3 ，查找第三個(gè)元素的概率為 1/6 ，則查找任一元素的平均查找長(zhǎng)度為 ( A. ) 。 A. n A． k