第10-12章習(xí)題課課件

1第10-12章

習(xí)題課宋國(guó)杰北京大學(xué)信息科學(xué)技術(shù)學(xué)院gjsong@北京大學(xué)信息科學(xué)技術(shù)學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法第10章

檢索第11章索引第12章高級(jí)數(shù)據(jù)結(jié)構(gòu)2第1題請(qǐng)?jiān)O(shè)計(jì)一個(gè)字典，支持下列的操作：INSERTx：插入一個(gè)字符串

xFINDx：返回一個(gè)

bool值，表示字符串是否存在

請(qǐng)?jiān)O(shè)計(jì)一個(gè)這樣的字典，并且介紹其優(yōu)點(diǎn)和缺點(diǎn)。

注意：字符串本身可能比較長(zhǎng)；字符串的個(gè)數(shù)在10^5個(gè)左右。3答案考查知識(shí)點(diǎn)：開(kāi)散列方案：考慮到字符串很多的因素，采用拉鏈?zhǔn)紿ash表解決，用一個(gè)Hash函數(shù)進(jìn)行尋址；考慮到字符串很長(zhǎng)的因素，在插入的時(shí)候用另一個(gè)Hash函數(shù)來(lái)給每一個(gè)字符串一個(gè)ID，相同的字符串ID一定相同，不同的字符串也有一定概率ID相同，在查找時(shí)，僅需考慮ID相同的串來(lái)確定是否串X存在，避免了大范圍的查找，和大量長(zhǎng)字符串匹配。4第2題現(xiàn)在有一個(gè)文本編輯器，具有如下的操作：MOVEk：將光標(biāo)移動(dòng)到第k個(gè)字符之前，如果k=0，那么移動(dòng)到文檔開(kāi)頭PRINTn：輸出光標(biāo)之后的n個(gè)字符PREV：光標(biāo)前移一位NEXT：光標(biāo)后移一位5（1）請(qǐng)基于線性數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)一套合理的算法，來(lái)實(shí)現(xiàn)這些操作，并且分析每個(gè)操作的性能。假定：文本最大的長(zhǎng)度為L(zhǎng)<10^6（2）添加2個(gè)操作：

INSERTn,s：在當(dāng)前光標(biāo)之后插入長(zhǎng)度為n的字符串sDELETEn：刪除光標(biāo)之后的n個(gè)字符

此時(shí)數(shù)據(jù)結(jié)構(gòu)應(yīng)當(dāng)作出什么樣的改變來(lái)適應(yīng)這一變化？6第1題持久動(dòng)態(tài)集合是這樣的集合，每當(dāng)集合被更新（插入元素或刪除元素）時(shí)，仍然需要維護(hù)該集合的一個(gè)較舊的版本。下圖就展示了一個(gè)二叉查找樹(shù)的持久動(dòng)態(tài)集合，對(duì)于每個(gè)版本，都會(huì)有一個(gè)對(duì)應(yīng)的根結(jié)點(diǎn)，所有根結(jié)點(diǎn)處在一個(gè)可維護(hù)的鏈表中，可以通過(guò)該鏈表訪問(wèn)所有的根結(jié)點(diǎn)，進(jìn)而訪問(wèn)所有的版本。該二叉樹(shù)結(jié)點(diǎn)沒(méi)有父結(jié)點(diǎn)域。9101、對(duì)一個(gè)持久二叉查找樹(shù)，插入或刪除一個(gè)關(guān)鍵字z的，需要改變哪些結(jié)點(diǎn)？答案不需要改變?nèi)魏谓Y(jié)點(diǎn)，只需要復(fù)制從根結(jié)點(diǎn)開(kāi)始到插入/刪除結(jié)點(diǎn)路徑上的所有結(jié)點(diǎn)。11寫(xiě)出向持久二叉查找樹(shù)中插入一個(gè)結(jié)點(diǎn)的過(guò)程，如果持久二叉查找樹(shù)的高度為h，則實(shí)現(xiàn)上述過(guò)程的時(shí)間和空間復(fù)雜性如何？答案

與BST插入類似1213第2題現(xiàn)有紅黑樹(shù)T1、T2和關(guān)鍵碼z，T1中的關(guān)鍵碼都比z小，T2中的關(guān)鍵碼都比z大。試將T1、T2和z合并成一棵新的紅黑樹(shù)T3。樹(shù)中的關(guān)鍵碼不重復(fù)。N是操作結(jié)點(diǎn)總數(shù)的上限，請(qǐng)分析你的算法的時(shí)間代價(jià)，如果高于O(logN)，請(qǐng)調(diào)整你的算法。在不給定關(guān)鍵碼z的情況下，實(shí)現(xiàn)兩棵紅黑樹(shù)的合并操作14答案首先生成如下形式的紅黑樹(shù)，這里不妨設(shè)T1的階為h1，T2的階為h2，且h1>h2：15那么，為了滿足紅黑樹(shù)性質(zhì)，我們令T2的根結(jié)點(diǎn)為多(h1-h2+1)黑結(jié)點(diǎn)。我們可以利用紅黑樹(shù)的刪除算法中對(duì)雙黑結(jié)點(diǎn)處理的方法同樣處理T2的根結(jié)點(diǎn)，即令其從(h1-h2+1)黑結(jié)點(diǎn)，變?yōu)?h1-h2)黑結(jié)點(diǎn)…直至為單黑結(jié)點(diǎn)，那么就變成了一棵正常的紅黑樹(shù)。16雙黑結(jié)點(diǎn)的調(diào)整假設(shè)X是左子結(jié)點(diǎn)（若X為右子結(jié)點(diǎn)，處理方法類似，不重述）情況1：雙黑結(jié)點(diǎn)的兄弟C是紅色，執(zhí)行旋轉(zhuǎn)操作（黑紅）！推出：B結(jié)點(diǎn)也一定是黑色，α和β也是黑色旋轉(zhuǎn)：兄弟節(jié)點(diǎn)為根變黑，父節(jié)點(diǎn)變紅X結(jié)點(diǎn)仍是“雙黑”結(jié)點(diǎn)，轉(zhuǎn)化為情況2,317北京大學(xué)信息科學(xué)技術(shù)學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法BCXβαXBCαβ雙黑結(jié)點(diǎn)情況2：兄弟是黑色,且有兩個(gè)黑子結(jié)點(diǎn)（黑黑黑）執(zhí)行換色操作，把C著紅色，B著黑色如果B原為紅色，則算法結(jié)束否則，對(duì)B繼續(xù)作“雙黑”調(diào)整（為什么？？）BXEDCBCEDX18北京大學(xué)信息科學(xué)技術(shù)學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法有可能繼續(xù)雙黑處理雙黑結(jié)點(diǎn)的調(diào)整情況3：兄弟C是黑色，且子結(jié)點(diǎn)有紅色(黑黑紅)(a)旋轉(zhuǎn)重構(gòu)：侄子紅結(jié)點(diǎn)八字外撇將兄弟結(jié)點(diǎn)C提上去，繼承原父結(jié)點(diǎn)的顏色然后把B著為黑色，D著為黑色，其他顏色不變即可19BDXCαDXBCα單旋轉(zhuǎn)調(diào)整北京大學(xué)信息科學(xué)技術(shù)學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法(b)旋轉(zhuǎn)重構(gòu)：侄子紅結(jié)點(diǎn)同邊順將C結(jié)點(diǎn)旋轉(zhuǎn)為D結(jié)點(diǎn)的父結(jié)點(diǎn)，C繼承原子根B的顏色，B著為黑色BXEDCβαDBCXαEβ20北京大學(xué)信息科學(xué)技術(shù)學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法11.6.3插入算法先調(diào)用BST的插入算法，將待插記錄定位新記錄X著色為紅色若父結(jié)點(diǎn)是黑色，則算法結(jié)束否則，雙紅調(diào)整6386384XAAX插入421北京大學(xué)信息科學(xué)技術(shù)學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法雙紅調(diào)整1：紅黑旋轉(zhuǎn)情況1：新增結(jié)點(diǎn)X的叔父結(jié)點(diǎn)是黑色，或者NIL調(diào)整后：祖節(jié)點(diǎn)變?yōu)楹?，父、叔?jié)點(diǎn)變?yōu)榧t！每個(gè)結(jié)點(diǎn)的階都保持原值，調(diào)整完成保持樹(shù)的穩(wěn)定性！Xα以祖結(jié)點(diǎn)為軸旋轉(zhuǎn)父結(jié)點(diǎn)AXBBACCα22北京大學(xué)信息科學(xué)技術(shù)學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法4種形式的結(jié)構(gòu)調(diào)整原則：保持BST的中序性質(zhì)24662426423提升操作旋轉(zhuǎn)操作北京大學(xué)信息科學(xué)技術(shù)學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法雙紅調(diào)整2：紅紅換色情況2：新增結(jié)點(diǎn)X的叔父結(jié)點(diǎn)也是紅色X父祖換色叔父變黑AXBBACCαα24對(duì)B繼續(xù)紅紅檢查北京大學(xué)信息科學(xué)技術(shù)學(xué)院數(shù)據(jù)結(jié)構(gòu)與算法如果B是根節(jié)點(diǎn)，則只叔父節(jié)點(diǎn)變色，根節(jié)點(diǎn)不變！25第10章

檢索第11章索引第12章高級(jí)數(shù)據(jù)結(jié)構(gòu)26提供廣義表的下列操作make_GList(a,b,c...);將任意多個(gè)廣義表連接成一個(gè)新的廣義表head(gList);取廣義表頭tail(gList);取廣義表尾；要求設(shè)計(jì)一個(gè)算法，將廣義表置逆，不能使用其他數(shù)據(jù)結(jié)構(gòu)。比如，對(duì)于廣義表(a,(a,b,c),(b,(d))),置逆之后的結(jié)果為：(((d),b),(c,b,a),a);27解：直接用遞歸即可。GListreverse(gList){Returnmake_Glist(reverse(tail(gList)),reverse(head(gList)))}282.假定經(jīng)過(guò)分詞后的網(wǎng)頁(yè)已經(jīng)形成了倒排索引，使用trie樹(shù)作為詞典，葉子結(jié)點(diǎn)會(huì)有指向倒排表的指針，倒排表是按照網(wǎng)頁(yè)文檔id（連續(xù)的整數(shù)值）排好序的?，F(xiàn)在需要系統(tǒng)支持簡(jiǎn)單的布爾查詢。請(qǐng)寫(xiě)出以下算法的代碼或偽代碼，并分析復(fù)雜度29Keyword1andkeyword2Keyword2andnotkeyword2如果需要支持相鄰查詢，例如keywordandkeword2neardistance，distance代表詞與詞之間的距離，需要怎樣更改倒排索引表，支持這一需求？30答案1、用trie樹(shù)可以在O(length(string))的時(shí)間內(nèi)找到單詞所對(duì)應(yīng)的倒排表的位置。根據(jù)這一點(diǎn)，設(shè)計(jì)如下代碼。設(shè)A1..AN為第一個(gè)單詞的文檔，B1..BM為第二個(gè)單詞的文檔313233343.AVL樹(shù)和紅黑樹(shù)的高度高度為h的AVL樹(shù)上的最少結(jié)點(diǎn)個(gè)數(shù)是多少？最多結(jié)點(diǎn)個(gè)數(shù)是多少？高度為h的紅黑樹(shù)上的最少結(jié)點(diǎn)個(gè)數(shù)是多少？最多結(jié)點(diǎn)個(gè)數(shù)是多少？353637BBh=5，為奇數(shù)時(shí)，樹(shù)的階為k=int[h/2]k=2k=138h=6，為偶數(shù)時(shí)，樹(shù)的階為k=int[h/2]k=3Bk=2k=139Bh=6，為偶數(shù)時(shí)，樹(shù)的階為k=int[h/2]k=3k=2B4.KD樹(shù)和PR四分樹(shù)都可以支持區(qū)域查找。請(qǐng)問(wèn)兩者有什么優(yōu)劣勢(shì)？401、k-d樹(shù)

k-d樹(shù)是一種用于多維檢索的樹(shù)結(jié)構(gòu)，它的每一層都根據(jù)特定關(guān)鍵碼將對(duì)象空間分解為兩個(gè)頂層結(jié)點(diǎn)按一個(gè)維劃分第二層結(jié)點(diǎn)按照另一維進(jìn)行劃分…以此類推在各個(gè)維之間反復(fù)進(jìn)行劃分

最終當(dāng)一個(gè)結(jié)點(diǎn)中的點(diǎn)數(shù)少于給點(diǎn)的最大點(diǎn)數(shù)時(shí)，劃分結(jié)束

識(shí)別器(discriminator)

在每一層用來(lái)進(jìn)行決策的關(guān)鍵碼稱為識(shí)別器對(duì)于k維關(guān)鍵碼，在第i層把識(shí)別器定義為imodk例如，對(duì)一個(gè)三維的關(guān)鍵碼做檢索，3個(gè)關(guān)鍵碼（x，y，z）標(biāo)號(hào)分別為0、1、2第一層是0mod3=0，所以使用關(guān)鍵碼x，第二層是1mod3=1，所以使用關(guān)鍵碼y……結(jié)點(diǎn)的分配在結(jié)點(diǎn)分配的時(shí)候首先比較該層的識(shí)別器如果關(guān)鍵碼小于識(shí)別器的值就放到左子樹(shù)中否則放到右子樹(shù)然后在下一層使用新的識(shí)別器來(lái)判斷每個(gè)結(jié)點(diǎn)的歸屬識(shí)別器的值應(yīng)該盡量使得被劃分的結(jié)點(diǎn)大約一半落在左子樹(shù)，另一半落在右子樹(shù)K-D樹(shù)示例K-D樹(shù)的空間分解上圖是一個(gè)二維的k-d樹(shù)，取值范圍為100×100之內(nèi)k-d樹(shù)的每個(gè)內(nèi)部結(jié)點(diǎn)把當(dāng)前的空間劃分為兩塊，交替地對(duì)兩個(gè)維進(jìn)行劃分根結(jié)點(diǎn)把空間劃分成兩部分其子結(jié)點(diǎn)進(jìn)一步把空間劃分成更小的部分子結(jié)點(diǎn)的劃分線不會(huì)穿過(guò)根結(jié)點(diǎn)的劃分線

k-d樹(shù)中的這些結(jié)點(diǎn)最終把空間分解為矩形這些矩形是結(jié)點(diǎn)可能落到的各子樹(shù)范圍K-D樹(shù)的不足

其結(jié)構(gòu)與輸入數(shù)據(jù)的順序也是有關(guān)的有可能導(dǎo)致它每個(gè)子樹(shù)的元素分配不均衡Bentley和Friedman發(fā)明了adaptivek-d樹(shù)，類似于BST所有的數(shù)據(jù)記錄都存儲(chǔ)在葉結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn)只是用來(lái)在各個(gè)維之間導(dǎo)航每一個(gè)識(shí)別器的選擇不再依賴于輸入的數(shù)據(jù)盡量選擇讓左右子樹(shù)的記錄數(shù)目相等的值

2、PR四分樹(shù)

PR四分樹(shù)，即點(diǎn)-區(qū)域四分樹(shù)（Point-RegionQuadtree）：每個(gè)內(nèi)部結(jié)點(diǎn)都恰好有四個(gè)子結(jié)點(diǎn)每個(gè)內(nèi)部結(jié)點(diǎn)將當(dāng)前空間均等地劃分為四個(gè)區(qū)域NW（西北）、NE（東北）、SW（西南）和SE（東南）PR四分樹(shù)也是對(duì)對(duì)象空間的劃分完全四叉樹(shù)

PR四分樹(shù)對(duì)空間的劃分每個(gè)內(nèi)部結(jié)點(diǎn)將當(dāng)前空間均等地劃分為四個(gè)區(qū)如果子區(qū)域包含的數(shù)據(jù)點(diǎn)數(shù)大于1，那么就把該區(qū)域繼續(xù)均等地劃分為四個(gè)區(qū)域依次類推，直到每個(gè)區(qū)域所包含的數(shù)據(jù)點(diǎn)不超過(guò)一個(gè)為止

PR樹(shù)的圖示PR樹(shù)的劃分上圖所表示的PR四分樹(shù)，其對(duì)象空間為128128

，并包含點(diǎn)A、B、C、D、E、F和G

根結(jié)點(diǎn)的四個(gè)子結(jié)點(diǎn)把整個(gè)空間平分為四份大小為6464的子空間NW，NE，SW，SE

NW（包含三個(gè)數(shù)據(jù)點(diǎn)）和SE(包含兩個(gè)數(shù)據(jù)點(diǎn))

需要進(jìn)一步分裂

PR樹(shù)的插入如果這個(gè)位置的葉結(jié)點(diǎn)沒(méi)有包含其他的數(shù)據(jù)點(diǎn)那么我們就把記錄插入這里；如果這個(gè)葉結(jié)點(diǎn)中已經(jīng)包含P了(或者一個(gè)具有P的坐標(biāo)的記錄)那么就報(bào)告記錄重復(fù)；如果葉結(jié)點(diǎn)已經(jīng)包含另一條記錄X那么就必須繼續(xù)分解這個(gè)結(jié)點(diǎn)，直到已存在的記錄X和P分別進(jìn)入不同的結(jié)點(diǎn)為止

PR樹(shù)的刪除產(chǎn)生的合并刪除結(jié)點(diǎn)D導(dǎo)致的區(qū)域合并PR樹(shù)的不足無(wú)法做到有效率的插入刪除，很有可能出現(xiàn)最壞情況；空間動(dòng)態(tài)分配，但是增加/減少的量并不穩(wěn)定；處理分布比較均勻的情況時(shí)，效果并不差。53考試大綱54關(guān)于考試時(shí)間和地點(diǎn)時(shí)間：2015年1月7日上午8:30-10:30地點(diǎn)：一教201考試題型填空、選擇、辨析與簡(jiǎn)答、數(shù)據(jù)結(jié)構(gòu)或算法的設(shè)計(jì)和分析、數(shù)學(xué)證明（1）數(shù)據(jù)結(jié)構(gòu)/算法設(shè)計(jì)與分析題只要寫(xiě)明基本思想、無(wú)歧義即可，必要時(shí)加上足夠的注釋。（2）對(duì)于算法中直接使用的類和函數(shù)（例如棧、隊(duì)列的函數(shù)），應(yīng)該先寫(xiě)ADT，并簡(jiǎn)單說(shuō)明算法中用到的重要函數(shù)的功能、入口參數(shù)、出口參數(shù)。范圍：1-12章55考場(chǎng)安排和注意事項(xiàng)請(qǐng)隨身帶好您的學(xué)生證，筆和涂改工具參加考試?？荚囆问綖殚]卷，可以使用計(jì)算器考前10分鐘，請(qǐng)大家把書(shū)包等放在教室前面的講臺(tái)和窗臺(tái)上，注意在試卷紙和有效答題紙上寫(xiě)上姓名和學(xué)號(hào)。統(tǒng)一發(fā)草稿紙，不夠可以隨時(shí)舉手要。請(qǐng)大家注意考場(chǎng)紀(jì)律，不要交頭接耳，私下討論?？荚嚂r(shí)對(duì)試題有疑問(wèn)，可以舉手，待監(jiān)考老師來(lái)到旁邊時(shí)，再請(qǐng)向監(jiān)考老師詢問(wèn)。監(jiān)考老師收卷清點(diǎn)無(wú)誤，并宣布“全班同學(xué)都可以離開(kāi)了”以后方可集體離開(kāi)。注意，不要把試卷題帶出考場(chǎng)，否則將計(jì)零分。56第1章概論一.重要概念1.抽象數(shù)據(jù)結(jié)構(gòu)2.數(shù)據(jù)邏輯結(jié)構(gòu)3.數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)

4.算法★5.算法分析(時(shí)間代價(jià)、空間代價(jià))二.方法1.根據(jù)二元組畫(huà)出圖示邏輯結(jié)構(gòu)(注意邊的方向)★2.根據(jù)要求設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)★3.算法的漸進(jìn)分析方法★4.大O表示法（不要求掌握大Ω、大Θ表示法）57第2章線性表一.概念1.線性表2.單鏈表3.雙鏈表4.循環(huán)表二.方法1.順序表上實(shí)現(xiàn)的運(yùn)算★2.鏈表上實(shí)現(xiàn)的運(yùn)算(指針操作的正確性)3.順序表和鏈表的比較58第3章棧與隊(duì)列一.概念1.棧2.隊(duì)列3.循環(huán)隊(duì)列二.方法★1.棧的性質(zhì)，用棧來(lái)生成序列★2.隊(duì)列的性質(zhì)，用隊(duì)列生成序列★3.棧的順序?qū)崿F(xiàn)4.循環(huán)隊(duì)列的實(shí)現(xiàn)5.表達(dá)式求值(中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式的算法、后綴表達(dá)式求值算法)6.棧在遞歸調(diào)用及轉(zhuǎn)換中的應(yīng)用59第4章字符串一.概念1.串2.模式匹配二.方法1.串的基本操作2.串的存儲(chǔ)及運(yùn)算★

3.串的KMP快速模式匹配算法，求特征向量數(shù)組（N數(shù)組）和利用N向量完成匹配的方法60第5章二叉樹(shù)一.概念1.二叉樹(shù)2.二叉樹(shù)的深度優(yōu)先周游3.二叉排序樹(shù)4.堆5.Huffman樹(shù)、Huffman編碼各種結(jié)構(gòu)的節(jié)點(diǎn)個(gè)數(shù)與高度、層次、度等關(guān)系換算

二.方法1．二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)（1）二叉鏈表（2）帶父指針的三重鏈表612.二叉樹(shù)的順序存儲(chǔ)完全二叉樹(shù)的順序存儲(chǔ)★3.二叉樹(shù)的深度優(yōu)先周游★4.BST樹(shù)的插入與刪除★5.構(gòu)造Huffman樹(shù)和Huffman編碼★6.堆的建立與維護(hù)過(guò)程62636465第6章樹(shù)一.概念樹(shù)、森林

、先根、后根、層次周游★K叉樹(shù)二.方法★1.森林與二叉樹(shù)相互轉(zhuǎn)換2．森林的鏈?zhǔn)酱鎯?chǔ)★(1)轉(zhuǎn)換為相應(yīng)的二叉樹(shù)，用二叉鏈表表示(2)父指針表示法、(3)子結(jié)點(diǎn)表表示法(4)等價(jià)類和并查算法的應(yīng)用66★3.森林的深度優(yōu)先周游（遞歸），可能結(jié)合應(yīng)用★4.森林的順序存儲(chǔ)及其構(gòu)造5.二叉樹(shù)和森林的層次周游(用隊(duì)列)，可能結(jié)合應(yīng)用67第7章圖一.概念1.圖的相關(guān)概念：連通性、連通分量、邊與頂點(diǎn)關(guān)系等2.深度周游、寬度周游3.圖的生成樹(shù)、生成樹(shù)林、最小生成樹(shù)★二.方法及算法★1.圖的存儲(chǔ)方法:（1）相鄰矩陣（2）鄰接表2.圖的周游:1）深度優(yōu)先（2）寬度優(yōu)先683.圖的生成樹(shù)與最小生成樹(shù)從某一點(diǎn)出發(fā)，按深度優(yōu)先或?qū)挾葍?yōu)先周游的生成樹(shù)最小生成樹(shù)①Prim算法②Kruskal算法(避圈法)4.拓?fù)渑判?給定圖，找出若干個(gè)或所有拓?fù)湫蛄?.最短路徑:Dijkstra算法、Floyd算法6.Dijkstra算法、Prim算法、Kruskal算法都是典型的貪心法（退化的動(dòng)態(tài)規(guī)劃法）69第8章內(nèi)排序

1.重點(diǎn)排序算法：直接插入法、★Shell排序、★快速排序、★基數(shù)排序、歸并排序

2.算法分析基于比較次數(shù)和移位次數(shù)分析最好、最壞的時(shí)間、空間直接插入法、二分法插入排序、起泡排序、直接選擇、快速排序、基數(shù)排序、歸并排序記住各種排序方法的平均時(shí)間

3.各種排序方法的局部修改和混合應(yīng)用70第9章文件管理和外排序方法及算法

1.★置換選擇排序

2.★多路歸并(敗者樹(shù)，最佳歸并樹(shù)，多路歸并的讀盤(pán)和寫(xiě)盤(pán)次數(shù))71第10章檢索一.概念1.平均檢索長(zhǎng)度2.二分法檢索

★3.散列表、同義詞、碰撞、堆積二.方法1.二分法檢索的判定樹(shù)、查找某個(gè)結(jié)點(diǎn)的比較次數(shù)2.散列表:1)散列函數(shù)選擇(除余法、平方取中法、折疊法)2)沖突處理方法(分離同義詞子表、線性探測(cè)、雙散列函數(shù))★三.散列算法（查找、插入、刪除，對(duì)墓碑的處理72第11章索引技術(shù)一.概念

1.順序文件2.散列文件3.