【正文】 【解答】17．假定查找有序表A[25]中每一元素的概率相等，試分別求出進(jìn)行順序、二分查找每一元素時(shí)的平均查找長(zhǎng)度。①試畫出生成之后的二叉搜索樹；②對(duì)該二叉搜索樹進(jìn)行中序遍歷，試寫出遍歷序列?！窘獯稹緼SL=(1*1+2*2+3*4)/7=17/76．設(shè)散列表的長(zhǎng)度為8，散列函數(shù)H(k)=k mod 7，初始記錄關(guān)鍵字序列為(25，31，8，27，13，68)，要求分別計(jì)算出用線性探測(cè)法和鏈地址法作為解決沖突方法的平均查找長(zhǎng)度。 ….沖突H(15)=15 mod 7=1。【同濟(jì)大學(xué)2001一(10分)】【解答】24. 設(shè)二叉排序樹中關(guān)鍵字由1到1000的整數(shù)組成，現(xiàn)要查找關(guān)鍵字為363的結(jié)點(diǎn)，下述關(guān)鍵字序列哪一個(gè)不可能是在二叉排序樹中查到的序列？說(shuō)明原因。另外，B+樹還可以在最下層從最小關(guān)鍵字開(kāi)始，從左往右進(jìn)行順序查找，B樹則不能作順序查找。 注:%是求余數(shù)運(yùn)算(=mod) Hi=(Hi1+REV(key+1)%11+1) % 13。WED14. 簡(jiǎn)要敘述B樹與B+樹的區(qū)別? 【解答】m階的B+樹和B樹主要區(qū)別有三：(1)有n棵子樹的結(jié)點(diǎn)中含有n(B樹中n1)個(gè)關(guān)鍵字；(2)B+樹葉子結(jié)點(diǎn)包含了全部關(guān)鍵字信息，及指向含關(guān)鍵字記錄的指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵字大小自小到大順序鏈接；(3)B+樹的非終端結(jié)點(diǎn)可以看成是索引部分，結(jié)點(diǎn)中只含其子樹(根結(jié)點(diǎn))中最大(或最小)關(guān)鍵字。哈希地址為i(0≤i≤m1)的關(guān)鍵字，和為解決沖突形成的探測(cè)序列i的同義詞，都爭(zhēng)奪哈希地址i。節(jié)省了空間，但易產(chǎn)生“堆積”，查找效率低。 ③ 鏈地址法 將關(guān)鍵字為同義詞的記錄存儲(chǔ)在同一鏈表中，散列表地址區(qū)間用H[0..m1]表示，分量初始值為空指針。10. 回答問(wèn)題并填空（1）（2分）散列表存儲(chǔ)的基本思想是什么？（2）（4分）散列表存儲(chǔ)中解決碰撞的基本方法有哪些？其基本思想是什么？（3）（４分）用分離的同義詞子表解決碰撞和用結(jié)合的同義詞表解決碰撞屬于哪種基本方法？他們各有何特點(diǎn)？（4）（３分）用線性探查法解決碰撞時(shí)，如何處理被刪除的結(jié)點(diǎn)？為什么？（5）（２分）散列法的平均檢索長(zhǎng)度不隨( )的增加而增加，而是隨( )的增大而增加。如果用哈希函數(shù)計(jì)算的地址分布均勻，則沖突的可能性較小，如果裝填因子α較小，則哈希表較稀疏，發(fā)生沖突的可能性較小。34．（ ）若裝填因子α為1，則向散列表中散列元素時(shí)一定會(huì)產(chǎn)生沖突?！?9．（ ）若把堆看成是一棵完全二叉樹，則該樹一定是一棵二叉排序樹。21．（ ）N個(gè)結(jié)點(diǎn)的二叉排序樹有多種，其中樹高最小的二叉排序樹是最佳的。 13．（ ）裝載因子是散列表的一個(gè)重要參數(shù)，它反映了散列表的裝滿程度。T5．（ ）如果兩個(gè)關(guān)鍵字的值不等但哈希函數(shù)值相等，則稱這兩個(gè)關(guān)鍵字為同義詞。1 5 91. 假定對(duì)線性表 (38,25,74,52,48) 進(jìn)行散列存儲(chǔ)，采用 H(K)=K % 7 作為散列函數(shù)，采用線性探測(cè)法處理沖突，則平均查找長(zhǎng)度為 ________ 。 (n/s+s)/2+182. 在索引查找中，假定查找表（即主表）的長(zhǎng)度為 96 ，被等分為 8 個(gè)子表，則進(jìn)行索引查找的平均查找長(zhǎng)度為 ________ 。順序 37/1272. 動(dòng)態(tài)查找表和靜態(tài)查找表的重要區(qū)別在于前者包含有__________和__________運(yùn)算，而后者不包含這兩種運(yùn)算。小于等于表長(zhǎng)的最大素?cái)?shù)或不包含小于20的質(zhì)因子的合數(shù)66. 有一個(gè)2000項(xiàng)的表，欲采用等分區(qū)間順序查找方法進(jìn)行查找，則每塊的理想長(zhǎng)度是__(1)___，分成__(2)___塊最為理想，平均查找長(zhǎng)度是__(3)___。O（log2n）、O(nlog2n)。(12,63,36)、(55,40,82)、(23,74)52．假定一個(gè)線性表為(”abcd”,”baabd”,”bcef”,”cfg”,”ahij”,”bkwte”,”ccdt”,”aayb”)，若按照字符串的第一個(gè)字母進(jìn)行劃分，使得同一個(gè)字母被劃分在一個(gè)子表中，則得到的a,b,c三個(gè)子表的長(zhǎng)度分別為_(kāi)_______、________和________。(n+1)/O(n)44．以二分查找方法從長(zhǎng)度為n的線性有序表中查找一個(gè)元素時(shí)，平均查找長(zhǎng)度小于等于________，時(shí)間復(fù)雜度為_(kāi)_______。36．對(duì)二叉排序樹進(jìn)行__中序______遍歷，可得到排好序的遞增結(jié)點(diǎn)序列。28．實(shí)現(xiàn)二分查找的存儲(chǔ)結(jié)構(gòu)僅限于順序存儲(chǔ)結(jié)構(gòu)，且其中元素排列必須是____有序的。二叉搜索樹、理想平衡樹20．二叉搜索樹的中序遍歷得到的結(jié)點(diǎn)序列為_(kāi)___ ____。tdata=k。8/314．設(shè)一組初始記錄關(guān)鍵字序列為(20，12，42，31，18，14，28)，則根據(jù)這些記錄關(guān)鍵字構(gòu)造的二叉排序樹的平均查找長(zhǎng)度是_______________________________。 if(r[mid].key==k) return(mid+1)。 snext=hashtable[k]。for(i=0。} return(t)，t=trchild7．根據(jù)初始關(guān)鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為_(kāi)___________。typedef struct node{int key。 j=i=k % p。（12，40），（ ），（74），（23,55，63）2．向一棵B_樹插入元素的過(guò)程中，若最終引起樹根結(jié)點(diǎn)的分裂，則新樹比原樹的高度___________。 B. 散列元素的個(gè)數(shù) CA C. 2 C. (d+1)/m ) 。 B .2 C) 。 C. O (n) A. O (n) D. O (n 2 )73. 從具有 n 個(gè)結(jié)點(diǎn)的二叉搜索樹中查找一個(gè)元素時(shí)，在最壞情況下的時(shí)間復(fù)雜性為 ( A. n C .13 B. k+n/k ) 。 A ) 。 D. (n+1)/260. 對(duì)長(zhǎng)度為 10 的順序表進(jìn)行查找，若查找前面 5 個(gè)元素的概率相同，均為 1/8 ，查找后面 5 個(gè)元素的概率相同，均為 3/40 ，則查找任一元素的平均查找長(zhǎng)度為 ( B. n+1 56．具有12個(gè)關(guān)鍵字的有序表，折半查找的平均查找長(zhǎng)度（A ）A. B. 4 C. D. 557．哈希查找中k個(gè)關(guān)鍵字具有同一哈希值，若用線性探測(cè)法將這k個(gè)關(guān)鍵字對(duì)應(yīng)的記錄存入哈希表中，至少要進(jìn)行( C )次探測(cè)。表中已有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．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)變化的要求，可以采用下列哪一種查找方法?？捎糜诮鉀Q上述問(wèn)題的是( ) 21．22．在線性表的散列存儲(chǔ)中，若用m表示散列表的長(zhǎng)度，n表示待散列存儲(chǔ)的元素的個(gè)數(shù)，則裝填因子a等于（ ）。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. 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. 小于等于m的最大奇數(shù) B. 小于等于m的最大素?cái)?shù)C. 小于等于m的最大偶數(shù) D. 小于等于m的最大合數(shù)14．設(shè)順序表的長(zhǎng)度為n，則順序查找的平均比較次數(shù)為（ ）。A．n/m B．m/n C．n/(n+m) D．m/(n+m)23．從一棵B_樹刪除元素的過(guò)程中，若最終引起樹根結(jié)點(diǎn)的合并，則新樹高度是（ ）。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+樹都是平衡的多叉樹。 A. 8 B. 3 C. 5 D. 951．散列函數(shù)有一個(gè)共同的性質(zhì)，即函數(shù)值應(yīng)當(dāng)以( D )取其值域的每個(gè)值。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è)元素的概率相等，則在長(zhǎng)度為 n 的順序表上查找任一元素的平均查找長(zhǎng)度為 ( A. n A. ) 。 D. 7970. 在索引查找中，若用于保存數(shù)據(jù)元素的主表的長(zhǎng)度為 117 ，它被均分為 9 子表，則索引查找的平均查找長(zhǎng)度為 ( A. 11 B. 12 B. log 2 n D. h72. 從具有 n 個(gè)結(jié)點(diǎn)的二叉搜索樹中查找一個(gè)元素時(shí)，在平均情況下的時(shí)間復(fù)雜性大致為 ( A. O (n) B .O (log 2 n ) ) 。 ) 。 C. 4 增加13. 為了能有效地應(yīng)用HASH查找技術(shù)，必須解決的兩個(gè)問(wèn)題是________________和_____________________。while (hashtable[j].key!=kamp。 struct node *lchild。38．設(shè)散列函數(shù)H(k)=k mod p，解決沖突的方法為鏈地址法。im。_______________________。 else if(____________) high=mid1。19/715．下面程序段的功能是實(shí)現(xiàn)在二叉排序樹中插入一個(gè)新結(jié)點(diǎn)，請(qǐng)?jiān)谙聞澗€處填上正確的內(nèi)容。tlchild=trchild=0。 有序序列 21．從有序表（12，18，30，43，56，78，82，95）中依次二分查找43和56元素時(shí)，其查找長(zhǎng)度分別為_(kāi)__________和__________。29．設(shè)順序表的表長(zhǎng)為n，且查找每個(gè)元素的概率相等，則采用順序查找法查找表中任一元素，在查找成功時(shí)的平均查找長(zhǎng)度為_(kāi)__(n+1)/2_______。37．采用折半查找方法進(jìn)行查找的數(shù)據(jù)序列應(yīng)為_(kāi)___順序存儲(chǔ)____且___有序_____。O(log2n)45．以二分查找方法從長(zhǎng)度為12的有序表中查找一個(gè)元素時(shí)，平均查找長(zhǎng)度為_(kāi)_______。253．在線性表的________存儲(chǔ)中，無(wú)法查找到一個(gè)元素的前驅(qū)或后繼元素。60. 順序查找n個(gè)元素的順序表，若查找成功，則比較關(guān)鍵字的次數(shù)最多為_(kāi)_ __次；當(dāng)使用監(jiān)視哨時(shí)，若查找失敗，則比較關(guān)鍵字的次數(shù)為_(kāi)_ __。(1)45 (2)45 (3)46(塊內(nèi)順序查找)67. 假定有k個(gè)關(guān)鍵字互為同義詞，若用線性探測(cè)再散列法把這k個(gè)關(guān)鍵字存入散列表中，至少要進(jìn)行__________次探測(cè)。插入 刪除73. 對(duì)于具有144 個(gè)記錄的文件，若采用分塊查找法，且每塊長(zhǎng)度為8，則平均查找長(zhǎng)度為_(kāi)_________. 有序78. 從有序表 (12,18,30,43,56,78,82,95) 中分別二分查找 43 和 56 元素時(shí)，其查找長(zhǎng)度分別為 ________ 和 ________ 。1183. 在一棵二叉排序樹中，每個(gè)分支結(jié)點(diǎn)的左子樹上所有結(jié)點(diǎn)的值一定 ________ 該結(jié)點(diǎn)的值，右子樹上所有結(jié)點(diǎn)的值一定 ________ 該結(jié)點(diǎn)的值。左子樹 292. 假定要對(duì)長(zhǎng)度 n=100 的線性表進(jìn)行散列存儲(chǔ)，并采用鏈接法處理沖突，則對(duì)于長(zhǎng)度 m=20 的開(kāi)散列表，每個(gè)散列地址的