數(shù)據(jù)結(jié)構(gòu)第9章_查找答案

《數(shù)據(jù)結(jié)構(gòu)第9章_查找答案》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第9章集合一．選擇題1.C2.A3.1D3.2C4.D5.B6.D7.D8.C9.A10.D11.B12.1C12.2C13.1C13.2D13.3G13.4H14.1E14.2B14.3E14.4B14.5B15.1B15.2A16.A17.C18.C19.C20.D21.B22.C23.B24.C25.1B25.2F25.3I26.A27.D28.C29.1A29.2C30.B31.D32.D33.C34.D35.1D35.2C36.C二．判斷題1.√2.√3.×4.×5.×6.√7.√8.×9.×10.×11.×12.√13.√

2、14.×15.×16.×17.√18.×19.√20.×21.×22.×23.×24.×25.√26.×27.×28.√29.√30.×31.×32.√33.√34.×35.√36.√部分答案解釋如下。4．不能說(shuō)哪種哈希函數(shù)的選取方法最好，各種選取方法有自己的適用范圍。8．哈希表的結(jié)點(diǎn)中可以包括指針，指向其元素。11．單鏈表不能使用折半查找方法。20．按插入后中序遍歷是遞增序列的原則，若某結(jié)點(diǎn)只有右子樹(shù)，而插入元素的關(guān)鍵字小于該結(jié)點(diǎn)的關(guān)鍵字，則會(huì)插入到該結(jié)點(diǎn)的左側(cè)，成為其左孩子。這種插入就不是插入到葉子下面。21．從平衡因子定義看，完

3、全二叉樹(shù)任一結(jié)點(diǎn)的平衡因子的絕對(duì)值確實(shí)是小于等于1。但是，平衡二叉樹(shù)本質(zhì)上是二叉排序樹(shù)，完全二叉樹(shù)不一定是排序樹(shù)。故不能說(shuō)完全二叉樹(shù)是平衡二叉樹(shù)。23．某結(jié)點(diǎn)的左子樹(shù)根結(jié)點(diǎn)不一定是它的中序前驅(qū)，其右子樹(shù)根結(jié)點(diǎn)也不一定是它的中序后繼。24．在等概率下，查找成功時(shí)的平均查找長(zhǎng)度相同，查找失敗時(shí)的平均查找長(zhǎng)度不相同。26．只有被刪除結(jié)點(diǎn)是葉子結(jié)點(diǎn)時(shí)命題才正確。三．填空題1．nn+12．43．6,9,11,124．55．26（第4層是葉子結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)兩個(gè)關(guān)鍵字）6．1,3,6,8,11,13,16,197．5,968．m-1,「m/2ù-1

4、9．2,4,310．(1)哈希函數(shù)(2)解決沖突的方法(3)選擇好的哈希函數(shù)(4)處理沖突的方法(5)均勻(6)簡(jiǎn)單11．AVL樹(shù)（高度平衡樹(shù)，高度平衡的二叉排序樹(shù)），或?yàn)榭斩鏄?shù)，或二叉樹(shù)中任意結(jié)點(diǎn)左子樹(shù)高度與右子樹(shù)高度差的絕對(duì)值小于等于1。12．小于等于表長(zhǎng)的最大素?cái)?shù)或不包含小于20的質(zhì)因子的合數(shù)13．1614．?㏒2n」+115．(1)45(2)45(3)46（塊內(nèi)順序查找）16．k(k+1)/217．30，31.5（塊內(nèi)順序查找）18．(1)順序存儲(chǔ)或鏈?zhǔn)酱鎯?chǔ)(2)順序存儲(chǔ)且有序(3)塊內(nèi)順序存儲(chǔ)，塊間有序(4)散列存儲(chǔ)19．

5、(n+1)/220．(n+1)/n*log2(n+1)-121．結(jié)點(diǎn)的左子樹(shù)的高度減去結(jié)點(diǎn)的右子樹(shù)的高度22．(1)順序表(2)樹(shù)表(3)哈希表(4)開(kāi)放定址方法(5)鏈地址方法(6)再哈希(7)建立公共溢出區(qū)23．直接定址法24．logém/2ù()+125．O(N)26．n(n+1)/227．5428．3129．37/1230．主關(guān)鍵字31．左子樹(shù)右子樹(shù)32．插入刪除33．1434．(1)126(2)64(3)33(4)6535．（1）low<=high(2)(low+hig)DIV2(3)binsrch:=mid(4)binsr

6、ch:=036．(1)k(2)Irear38．(1)p!=null(2)pf=p(3)p!=*t(4)*t=null四．應(yīng)用題1．概念是基本知識(shí)的主要部分，要牢固掌握。這里只列出一部分，目的是引起重視，解答略。2．（1）散列表存儲(chǔ)的基本思想是用關(guān)鍵字的值決定數(shù)據(jù)元素的存儲(chǔ)地址（2）散列表存儲(chǔ)中解決碰撞的基本方法：①開(kāi)放定址法形成地址序列的公式是：Hi=（H（key）+di）%m，其中m是表長(zhǎng)，di是增量。根據(jù)di取法不同，又分為三種：a．di=1，2，…

7、，m-1稱(chēng)為線(xiàn)性探測(cè)再散列，其特點(diǎn)是逐個(gè)探測(cè)表空間，只要散列表中有空閑空間，就可解決碰撞，缺點(diǎn)是容易造成“聚集”，即不是同義詞的關(guān)鍵字爭(zhēng)奪同一散列地址。b．di=12，-12，22，-22，…，±k2（k≤m/2）稱(chēng)為二次探測(cè)再散列，它減少了聚集，但不容易探測(cè)到全部表空間，只有當(dāng)表長(zhǎng)為形如4j+3（j為整數(shù)）的素?cái)?shù)時(shí)才有可能。c．di=偽隨機(jī)數(shù)序列，稱(chēng)為隨機(jī)探測(cè)再散列。②再散列法Hi=RHi（key）i=1，2，…，k，是不同的散列函數(shù)，即在同義詞產(chǎn)生碰撞時(shí)，用另一散列函數(shù)計(jì)算散列地址，直到解決碰撞。該方法不易產(chǎn)生“聚集”，但增加了計(jì)

8、算時(shí)間。③鏈地址法將關(guān)鍵字為同義詞的記錄存儲(chǔ)在同一鏈表中，散列表地址區(qū)間用H[0..m-1]表示，分量初始值為空指針。凡散列地址為i（0≤i≤m-1）的記錄均插在以H[i]為頭指針的鏈表中。這種解決方法中數(shù)據(jù)元素個(gè)數(shù)不受