【正文】 ,且數(shù)據(jù)元素有序 ,且數(shù)據(jù)元素有序42．下列二叉排序樹中查找效率最高的是( A ) 43．如果要求一個(gè)線性表既能較快地查找，又能適應(yīng)動(dòng)態(tài)變化的要求，可以采用下列哪一種查找方法。 D. B樹和B+樹都能有效地支持隨機(jī)檢索。表中已有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 )。若采用折半查找方法，則在等概率情況下，查找失敗時(shí)的ASL值是（D ）54．在采用拉鏈法處理沖突所構(gòu)成的開散列表上查找某一關(guān)鍵字，在查找成功的情況下，所探測(cè)的這些位置上的鍵值（ A ）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è)。D B. n+1 D. (n+1)/260. 對(duì)長(zhǎng)度為 10 的順序表進(jìn)行查找，若查找前面 5 個(gè)元素的概率相同，均為 1/8 ，查找后面 5 個(gè)元素的概率相同，均為 3/40 ，則查找任一元素的平均查找長(zhǎng)度為 ( ) 。 C. (n1)/2 A B. 18 B C ) 。A. O (n) D B. k+n/k C. (k+n/k)/2 B ) 。 D . (n/s+s)/269. 在索引查找中，若用于保存數(shù)據(jù)元素的主表的長(zhǎng)度為 144 ，它被均分為 12 子表，每個(gè)子表的長(zhǎng)度均為 12 ，則索引查找的平均查找長(zhǎng)度為 ( C .13 ) 。A. n D. O (n 2 )73. 從具有 n 個(gè)結(jié)點(diǎn)的二叉搜索樹中查找一個(gè)元素時(shí)，在最壞情況下的時(shí)間復(fù)雜性為 ( AA. O (n) B ) 。 C. O (n) A. O (n) ) 。 D. 0 ~ 177. 若根據(jù)查找表 (23,44,36,48,52,73,64,58) 建立開散列表，采用 h(K)=K%13 計(jì)算散列地址，則元素 64 的散列地址為 ( CA. 4 B. 8 B B .2 C. 3 ) 。 C. (d+1)/m D. (d+1)%m81. 若根據(jù)查找表建立長(zhǎng)度為 m 的閉散列表，采用二次探測(cè)法處理沖突，假定對(duì)一個(gè)元素第一次計(jì)算的散列地址為 d ，則第四次計(jì)算的散列地址為 ( A. (d+1)%m A. 1 C. 2 A B. C ) 有關(guān)。 B. 散列元素的個(gè)數(shù) C. 裝填因子 （12，40），（ ），（74），（23,55，63）2．向一棵B_樹插入元素的過(guò)程中，若最終引起樹根結(jié)點(diǎn)的分裂，則新樹比原樹的高度___________。struct record{int key。 j=i=k % p。 if (i==j) return(1)。typedef struct node{int key。bitree *bstsearch(bitree *t, int k){ if (t==0 ) return(0)。} return(t)，t=trchild7．根據(jù)初始關(guān)鍵字序列(19，22，01，38，10)建立的二叉排序樹的高度為____________。 struct node *next。for(i=0。in。 snext=hashtable[k]。 int others。 if(r[mid].key==k) return(mid+1)。} mid=(low+high)/2，r[mid].keyk10．設(shè)需要對(duì)5個(gè)不同的記錄關(guān)鍵字進(jìn)行排序，則至少需要比較_____________次，至多需要比較_____________次。8/314．設(shè)一組初始記錄關(guān)鍵字序列為(20，12，42，31，18，14，28)，則根據(jù)這些記錄關(guān)鍵字構(gòu)造的二叉排序樹的平均查找長(zhǎng)度是_______________________________。struct node *rchild。tdata=k。} t=(bitree *)malloc(sizeof(bitree))，bstinsert(trchild,k)16．解決散列表沖突的兩種方法是________________和__________________。二叉搜索樹、理想平衡樹20．二叉搜索樹的中序遍歷得到的結(jié)點(diǎn)序列為____ ____。同一層24．每次從無(wú)序表中順序取出一個(gè)元素，把它插入到有序表中的適當(dāng)位置，此種排序方法叫做_______排序；每次從無(wú)序表中挑選出一個(gè)最大或最小元素，把它交換到有序表中的一端，此種排序方法叫做_________排序。28．實(shí)現(xiàn)二分查找的存儲(chǔ)結(jié)構(gòu)僅限于順序存儲(chǔ)結(jié)構(gòu)，且其中元素排列必須是____有序的。32．二分查找的時(shí)間復(fù)雜度為__O(log2n)_____。36．對(duì)二叉排序樹進(jìn)行__中序______遍歷，可得到排好序的遞增結(jié)點(diǎn)序列。40．快速排序算法在最差的情況下其時(shí)間復(fù)雜度是 。(n+1)/O(n)44．以二分查找方法從長(zhǎng)度為n的線性有序表中查找一個(gè)元素時(shí)，平均查找長(zhǎng)度小于等于________，時(shí)間復(fù)雜度為________。348．對(duì)于二分查找所對(duì)應(yīng)的判定樹，它既是一棵_______，又是一棵________。(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)度分別為________、________和________。7/556．假定要對(duì)長(zhǎng)度n=100的線性表進(jìn)行散列存儲(chǔ)，并采用鏈接法處理沖突，則對(duì)于長(zhǎng)度m=20的散列表，每個(gè)散列地址的單鏈表的長(zhǎng)度平均為________。O（log2n）、O(nlog2n)。6,9,11,1263. 己知有序表為(12,18,24,35,47,50,62,83,90,115，134)當(dāng)用二分法查找90時(shí)，需__________次查找成功，47時(shí)__________成功，查100時(shí)，需__________次才能確定不成功。小于等于表長(zhǎng)的最大素?cái)?shù)或不包含小于20的質(zhì)因子的合數(shù)66. 有一個(gè)2000項(xiàng)的表，欲采用等分區(qū)間順序查找方法進(jìn)行查找，則每塊的理想長(zhǎng)度是__(1)___，分成__(2)___塊最為理想，平均查找長(zhǎng)度是__(3)___。(1)順序表 (2)樹表 (3)哈希表 (4)開放定址方法(1) 37/1272. 動(dòng)態(tài)查找表和靜態(tài)查找表的重要區(qū)別在于前者包含有__________和__________運(yùn)算，而后者不包含這兩種運(yùn)算。 O(n)75. 假定一個(gè)順序表的長(zhǎng)度為 40 ，并假定查找每個(gè)元素的概率都相同，則在查找成功情況下的平均查找長(zhǎng)度 ________ ，在查找不成功情況下的平均查找長(zhǎng)度 ________ 。順序 二叉排序樹 (n/s+s)/2+182. 在索引查找中，假定查找表（即主表）的長(zhǎng)度為 96 ，被等分為 8 個(gè)子表，則進(jìn)行索引查找的平均查找長(zhǎng)度為 ________ 。有序序列85. 從一棵二叉排序樹中查找一個(gè)元素時(shí)，若元素的值等于根結(jié)點(diǎn)的值，則表明 _______ ，若元素的值小于根結(jié)點(diǎn)的值，則繼續(xù)向 ________ 查找，若元素的值大于根結(jié)點(diǎn)的值，則繼續(xù)向 ________ 查找。 5 91. 假定對(duì)線性表 (38,25,74,52,48) 進(jìn)行散列存儲(chǔ)，采用 H(K)=K % 7 作為散列函數(shù)，采用線性探測(cè)法處理沖突，則平均查找長(zhǎng)度為 ________ 。鏈接 1 哈希查找法三、判斷題1．（ ）分塊查找的平均查找長(zhǎng)度不僅與索引表的長(zhǎng)度有關(guān)，而且與塊的長(zhǎng)度有關(guān)。T5．（ ）如果兩個(gè)關(guān)鍵字的值不等但哈希函數(shù)值相等，則稱這兩個(gè)關(guān)鍵字為同義詞。F9．( )折半查找法的前提之一是線性表有序。 13．（ ）裝載因子是散列表的一個(gè)重要參數(shù)，它反映了散列表的裝滿程度。17．（ ）折半查找與二元查找樹的時(shí)間性能在最壞的情況下是相同的。21．（ ）N個(gè)結(jié)點(diǎn)的二叉排序樹有多種，其中樹高最小的二叉排序樹是最佳的?！?5．（ ）B+樹既能索引查找也能順序查找?！?9．（ ）若把堆看成是一棵完全二叉樹，則該樹一定是一棵二叉排序樹。√32．（ ）非空的平衡二叉樹中插入一個(gè)結(jié)點(diǎn),原有結(jié)點(diǎn)中至少一個(gè)結(jié)點(diǎn)的平衡因子會(huì)改變。34．（ ）若裝填因子α為1，則向散列表中散列元素時(shí)一定會(huì)產(chǎn)生沖突?！?38．（ ）對(duì)無(wú)序表用二分法查找比順序查找快。如果用哈希函數(shù)計(jì)算的地址分布均勻，則沖突的可能性較小，如果裝填因子α較小，則哈希表較稀疏，發(fā)生沖突的可能性較小。（8分）元素下標(biāo)12345678910比較次數(shù)【解答】8．一個(gè)線性表為B=（12，23，45，57，20，03，78，31，15，36），設(shè)散列表為HT[0..12]，散列函數(shù)為H（key）= key % 13并用線性探查法解決沖突，請(qǐng)畫出散列表，并計(jì)算等概率情況下查找成功的平均查找長(zhǎng)度。10. 回答問(wèn)題并填空（1）（2分）散列表存儲(chǔ)的基本思想是什么？（2）（4分）散列表存儲(chǔ)中解決碰撞的基本方法有哪些？其基本思想是什么？（3）（４分）用分離的同義詞子表解決碰撞和用結(jié)合的同義詞表解決碰撞屬于哪種基本方法？他們各有何特點(diǎn)？（4）（３分）用線性探查法解決碰撞時(shí)，如何處理被刪除的結(jié)點(diǎn)？為什么？（5）（２分）散列法的平均檢索長(zhǎng)度不隨( )的增加而增加，而是隨( )的增大而增加。k2(k≤m/2) 稱為二次探測(cè)再散列，它減少了聚集，但不容易探測(cè)到全部表空間，只有當(dāng)表長(zhǎng)為形如4j+3(j為整數(shù))的素?cái)?shù)時(shí)才有可能。 ③ 鏈地址法 將關(guān)鍵字為同義詞的記錄存儲(chǔ)在同一鏈表中，散列表地址區(qū)間用H[0..m1]表示，分量初始值為空指針。 ④ 建立公共溢出區(qū) 設(shè)H[0..m1]為基本表，凡關(guān)鍵字為同義詞的記錄，都填入溢出區(qū)O[0..m1]。節(jié)省了空間，但易產(chǎn)生“堆積”，查找效率低?！灸暇┖娇蘸教齑髮W(xué) 1996 （6分）】【解答】評(píng)價(jià)哈希函數(shù)優(yōu)劣的因素有：能否將關(guān)鍵字均勻影射到哈?？臻g上，有無(wú)好的解決沖突的方法，計(jì)算哈希函數(shù)是否簡(jiǎn)單高效。哈希地址為i(0≤i≤m1)的關(guān)鍵字，和為解決沖突形成的探測(cè)序列i的同義詞，都爭(zhēng)奪哈希地址i。14. 簡(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)鍵字。試在０６的散列地址空間內(nèi)對(duì)關(guān)鍵字序列｛31,23,17,27,19,11,13,91,61,41｝構(gòu)造哈希表，并計(jì)算在等概率下成功查找的平均查找長(zhǎng)度。WED 注:%是求余數(shù)運(yùn)算(=mod) Hi=(Hi1+REV(key+1)%11+1) % 13。 【清華大學(xué)2000八(13分）】【解答】(1)散列地址0123456789101112關(guān)鍵字27532另外，B+樹還可以在最下層從最小關(guān)鍵字開始，從左往右進(jìn)行順序查找，B樹則不能作順序查找?！緩B門大學(xué) 2002 （5分）】【解答】22. 在查找和排序算法中，監(jiān)視哨的作用是什么？【解答】監(jiān)視哨的作用是免去查找過(guò)程中每次都要檢測(cè)整個(gè)表是否查找完畢，提高了查找效率?！就瑵?jì)大學(xué)2001一(10分)】【解答】24. 設(shè)二叉排序樹中關(guān)鍵字由1到1000的整數(shù)組成，現(xiàn)要查找關(guān)鍵字為363的結(jié)點(diǎn)，下述關(guān)鍵字序列哪一個(gè)不可能是在二叉排序樹中查到的序列？說(shuō)明原因?！窘獯稹?,ASL=91*1+2*2+3*4+4*2)=25/92．設(shè)有一組初始記錄關(guān)鍵字為(45，80，48，40，22，78)，要求構(gòu)造一棵二叉排序樹并給出構(gòu)造過(guò)程。 ….沖突H(15)=15 mod 7=1。H(63)=63 mod 7=0?！窘獯稹緼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)度。 9．設(shè)散列表為HT[13]，散列函數(shù)為H(key)=key%13，用閉散列法解決沖突，對(duì)下列關(guān)鍵碼序列12，23，45，57，20，3，78，31，15，36造表。①試畫出生成之后的二叉搜索樹；②對(duì)該二叉搜索樹進(jìn)行中序遍歷，試寫出遍歷序列。題32圖【解答】不是AVL樹?！窘獯稹?7．假定查找有序表A[25]中每一元素的概率相等，試分別求出進(jìn)行順序、二分查找每一元素時(shí)的平均查