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

1、1第第10-12章章習(xí)題課習(xí)題課宋國(guó)杰宋國(guó)杰北京大學(xué)信息科學(xué)技術(shù)學(xué)院北京大學(xué)信息科學(xué)技術(shù)學(xué)院第第10章章 檢索檢索第第11章章 索引索引第第12章章 高級(jí)數(shù)據(jù)結(jié)構(gòu)高級(jí)數(shù)據(jù)結(jié)構(gòu)2第1題請(qǐng)?jiān)O(shè)計(jì)一個(gè)字典，支持下列的操作：INSERT x：插入一個(gè)字符串 xFIND x：返回一個(gè) bool 值，表示字符串是否存在 請(qǐng)?jiān)O(shè)計(jì)一個(gè)這樣的字典，并且介紹其優(yōu)點(diǎn)和缺點(diǎn)。 注意：字符串本身可能比較長(zhǎng)；字符串的個(gè)數(shù)在105 個(gè)左右。3答案考查知識(shí)點(diǎn)：考查知識(shí)點(diǎn)：開(kāi)散列開(kāi)散列方案：考慮到字符串很多的因素，采用方案：考慮到字符串很多的因素，采用拉鏈?zhǔn)嚼準(zhǔn)紿ash表表解決，解決，用一個(gè)用一個(gè)Hash函數(shù)進(jìn)行尋址函數(shù)進(jìn)行尋

2、址；考慮到字符串很長(zhǎng)的因素，考慮到字符串很長(zhǎng)的因素，在插入的時(shí)候用另一個(gè)在插入的時(shí)候用另一個(gè)Hash函數(shù)來(lái)給每一個(gè)字符串一個(gè)函數(shù)來(lái)給每一個(gè)字符串一個(gè)ID，相同的字符串相同的字符串ID一定相同，不同的字符串也有一定概率一定相同，不同的字符串也有一定概率ID相同，相同，在查找時(shí)，僅需考慮在查找時(shí)，僅需考慮ID相同的串來(lái)確定是否串相同的串來(lái)確定是否串X存在存在，避免了大范圍的查找，和大量長(zhǎng)字符串匹配，避免了大范圍的查找，和大量長(zhǎng)字符串匹配。4第2題現(xiàn)在有一個(gè)文本編輯器，具有如下的操作：現(xiàn)在有一個(gè)文本編輯器，具有如下的操作：MOVE k：將光標(biāo)移動(dòng)到第：將光標(biāo)移動(dòng)到第k個(gè)字符之前，如果個(gè)字符之前，如果

3、k=0，那么移動(dòng)到文檔開(kāi)頭，那么移動(dòng)到文檔開(kāi)頭PRINT n：輸出光標(biāo)之后的：輸出光標(biāo)之后的n個(gè)字符個(gè)字符PREV：光標(biāo)前移一位：光標(biāo)前移一位NEXT：光標(biāo)后移一位：光標(biāo)后移一位5（1）請(qǐng)基于線性數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)一套合理的算法，來(lái)實(shí)）請(qǐng)基于線性數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)一套合理的算法，來(lái)實(shí)現(xiàn)這些操作，并且分析每個(gè)操作的性能。假定：文本現(xiàn)這些操作，并且分析每個(gè)操作的性能。假定：文本最大的長(zhǎng)度為最大的長(zhǎng)度為L(zhǎng)h2：15那么，為了滿足紅黑樹(shù)性質(zhì)，我們令那么，為了滿足紅黑樹(shù)性質(zhì)，我們令T2的根結(jié)點(diǎn)為的根結(jié)點(diǎn)為多多(h1-h2+1)黑結(jié)點(diǎn)。我們可以利用紅黑樹(shù)的刪除算黑結(jié)點(diǎn)。我們可以利用紅黑樹(shù)的刪除算法中對(duì)雙黑結(jié)點(diǎn)處理的方

4、法同樣處理法中對(duì)雙黑結(jié)點(diǎn)處理的方法同樣處理T2的根結(jié)點(diǎn)，的根結(jié)點(diǎn)，即令其從即令其從(h1-h2+1)黑結(jié)點(diǎn)，變?yōu)楹诮Y(jié)點(diǎn)，變?yōu)?h1-h2)黑結(jié)點(diǎn)黑結(jié)點(diǎn)直直至為單黑結(jié)點(diǎn)，那么就變成了一棵正常的紅黑樹(shù)。至為單黑結(jié)點(diǎn)，那么就變成了一棵正常的紅黑樹(shù)。16雙黑結(jié)點(diǎn)的調(diào)整雙黑結(jié)點(diǎn)的調(diào)整假設(shè)假設(shè)X是左子結(jié)點(diǎn)（若是左子結(jié)點(diǎn)（若X為右子結(jié)點(diǎn)，處理方法類似，不重述）為右子結(jié)點(diǎn)，處理方法類似，不重述）情況情況1：雙黑結(jié)點(diǎn)的兄弟C是紅色，執(zhí)行旋轉(zhuǎn)操作（黑紅）！推出：推出：B結(jié)點(diǎn)也一定是黑色，結(jié)點(diǎn)也一定是黑色， 和和也是黑色也是黑色旋轉(zhuǎn)：兄弟節(jié)點(diǎn)為根變黑，父節(jié)點(diǎn)變紅旋轉(zhuǎn)：兄弟節(jié)點(diǎn)為根變黑，父節(jié)點(diǎn)變紅X結(jié)點(diǎn)仍是結(jié)點(diǎn)仍是“

5、雙黑雙黑”結(jié)點(diǎn)，轉(zhuǎn)化為情況結(jié)點(diǎn)，轉(zhuǎn)化為情況2,317BCXXBC雙黑結(jié)點(diǎn)情況情況2：兄弟是黑色, 且有兩個(gè)黑子結(jié)點(diǎn)（黑黑黑）執(zhí)行換色操作，把執(zhí)行換色操作，把C著紅色，著紅色，B著黑色著黑色如果如果B原為紅色，則算法結(jié)束原為紅色，則算法結(jié)束否則，對(duì)否則，對(duì)B繼續(xù)作繼續(xù)作“雙黑雙黑”調(diào)整（調(diào)整（為什么？為什么？）BXEDCBCEDX18有可能繼續(xù)雙黑處理雙黑結(jié)點(diǎn)的調(diào)整雙黑結(jié)點(diǎn)的調(diào)整情況情況3：兄弟C是黑色，且子結(jié)點(diǎn)有紅色(黑黑紅)(a)旋轉(zhuǎn)重構(gòu)：旋轉(zhuǎn)重構(gòu)：侄子紅結(jié)點(diǎn)八字外撇侄子紅結(jié)點(diǎn)八字外撇將兄弟結(jié)點(diǎn)將兄弟結(jié)點(diǎn)C提上去，繼承原父結(jié)點(diǎn)的顏色提上去，繼承原父結(jié)點(diǎn)的顏色然后把然后把B著為黑色，著為黑色，

6、D著為黑色，其他顏色不變即可著為黑色，其他顏色不變即可19BDXCDXBC單旋轉(zhuǎn)調(diào)整單旋轉(zhuǎn)調(diào)整(b)旋轉(zhuǎn)重構(gòu)：旋轉(zhuǎn)重構(gòu)：侄子紅結(jié)點(diǎn)同邊順侄子紅結(jié)點(diǎn)同邊順將將C結(jié)點(diǎn)旋轉(zhuǎn)為結(jié)點(diǎn)旋轉(zhuǎn)為D結(jié)點(diǎn)的父結(jié)點(diǎn)，結(jié)點(diǎn)的父結(jié)點(diǎn)，C繼承原子根繼承原子根B的顏的顏色，色，B著為黑色著為黑色BXEDCDBCXE2011.6.3 插入算法插入算法先調(diào)用先調(diào)用BST的插入算法，將待插記錄定位的插入算法，將待插記錄定位新記錄X著色為紅色若父結(jié)點(diǎn)是黑色，則算法結(jié)束若父結(jié)點(diǎn)是黑色，則算法結(jié)束否則，否則，雙紅調(diào)整XAAX插入插入4 421雙紅調(diào)整雙紅調(diào)整1：紅黑旋轉(zhuǎn)紅黑旋轉(zhuǎn)情況情況1：新增結(jié)點(diǎn)X的叔父結(jié)點(diǎn)是黑色，或者NIL調(diào)整后：

7、祖節(jié)點(diǎn)變?yōu)楹?，父、叔?jié)點(diǎn)變?yōu)榧t！調(diào)整后：祖節(jié)點(diǎn)變?yōu)楹冢?、叔?jié)點(diǎn)變?yōu)榧t！每個(gè)結(jié)點(diǎn)的階都保持原值，調(diào)整完成每個(gè)結(jié)點(diǎn)的階都保持原值，調(diào)整完成保持樹(shù)的穩(wěn)定性！保持樹(shù)的穩(wěn)定性！以祖結(jié)點(diǎn)為軸旋以祖結(jié)點(diǎn)為軸旋轉(zhuǎn)父結(jié)點(diǎn)轉(zhuǎn)父結(jié)點(diǎn)224種形式的結(jié)構(gòu)調(diào)整種形式的結(jié)構(gòu)調(diào)整原則：保持原則：保持BST的中序性質(zhì)的中序性質(zhì)23提升操作旋轉(zhuǎn)操作雙紅調(diào)整雙紅調(diào)整2：紅紅換色紅紅換色情況情況2：新增結(jié)點(diǎn)X的叔父結(jié)點(diǎn)也是紅色父祖換色父祖換色叔父變黑叔父變黑24對(duì)B繼續(xù)紅紅檢查如果B是根節(jié)點(diǎn)，則只叔父節(jié)點(diǎn)變色，根節(jié)點(diǎn)不變！25第第10章章 檢索檢索第第11章章 索引索引第第12章章 高級(jí)數(shù)據(jù)結(jié)構(gòu)高級(jí)數(shù)據(jù)結(jié)構(gòu)26提供廣義表的下列操作

8、提供廣義表的下列操作make_GList(a,b,c.);將任意多個(gè)廣義表連接成一個(gè)新的廣將任意多個(gè)廣義表連接成一個(gè)新的廣義表義表head(gList);取廣義表頭取廣義表頭tail(gList);取廣義表尾；取廣義表尾；要求設(shè)計(jì)一個(gè)算法，將廣義表置逆，不能使用其他要求設(shè)計(jì)一個(gè)算法，將廣義表置逆，不能使用其他數(shù)據(jù)結(jié)構(gòu)。比如，對(duì)于廣義表數(shù)據(jù)結(jié)構(gòu)。比如，對(duì)于廣義表(a,(a,b,c),(b,(d),置逆置逆之后的結(jié)果為：之后的結(jié)果為：(d),b),(c,b,a),a);27解：直接用遞歸即可。解：直接用遞歸即可。GList reverse(gList) Return make_Glist(reve

9、rse(tail(gList),reverse(head(gList)282.假定經(jīng)過(guò)分詞后的網(wǎng)頁(yè)已經(jīng)形成了倒排索引，使用假定經(jīng)過(guò)分詞后的網(wǎng)頁(yè)已經(jīng)形成了倒排索引，使用trie樹(shù)作為詞典，葉子結(jié)點(diǎn)會(huì)有指向倒排表的指針，樹(shù)作為詞典，葉子結(jié)點(diǎn)會(huì)有指向倒排表的指針，倒排表是按照網(wǎng)頁(yè)文檔倒排表是按照網(wǎng)頁(yè)文檔id（連續(xù)的整數(shù)值）排好序（連續(xù)的整數(shù)值）排好序的?，F(xiàn)在需要系統(tǒng)支持簡(jiǎn)單的布爾查詢。請(qǐng)寫出以的?，F(xiàn)在需要系統(tǒng)支持簡(jiǎn)單的布爾查詢。請(qǐng)寫出以下算法的代碼或偽代碼，并分析復(fù)雜度下算法的代碼或偽代碼，并分析復(fù)雜度29I. Keyword1 and keyword2II. Keyword2 and not ke

10、yword2III.如果需要支持相鄰查詢，例如如果需要支持相鄰查詢，例如keyword and keword2 near distance，distance代表詞與詞代表詞與詞之間的距離，需要怎樣更改倒排索引表，支之間的距離，需要怎樣更改倒排索引表，支持這一需求？持這一需求？30答案答案1、用用 trie 樹(shù)可以在樹(shù)可以在 O(length(string)的時(shí)間內(nèi)找到的時(shí)間內(nèi)找到單詞所對(duì)應(yīng)的倒排表的位置。單詞所對(duì)應(yīng)的倒排表的位置。根據(jù)這一點(diǎn)，設(shè)計(jì)如下代碼。根據(jù)這一點(diǎn)，設(shè)計(jì)如下代碼。設(shè)設(shè) A1.AN 為第一個(gè)單詞的文檔，為第一個(gè)單詞的文檔，B1.BM 為第二個(gè)為第二個(gè)單詞的文檔單詞的文檔3132

11、33343.AVL樹(shù)和紅黑樹(shù)的高度樹(shù)和紅黑樹(shù)的高度A. 高度為高度為h的的AVL樹(shù)上的最少結(jié)點(diǎn)個(gè)數(shù)是多少？最多樹(shù)上的最少結(jié)點(diǎn)個(gè)數(shù)是多少？最多結(jié)點(diǎn)個(gè)數(shù)是多少？結(jié)點(diǎn)個(gè)數(shù)是多少？B. 高度為高度為h的紅黑樹(shù)上的最少結(jié)點(diǎn)個(gè)數(shù)是多少？最多的紅黑樹(shù)上的最少結(jié)點(diǎn)個(gè)數(shù)是多少？最多結(jié)點(diǎn)個(gè)數(shù)是多少？結(jié)點(diǎn)個(gè)數(shù)是多少？35363721h21hBBh=5，為奇數(shù)時(shí)，樹(shù)的階為，為奇數(shù)時(shí)，樹(shù)的階為k=inth/221 12kk 21 12kk k=2k=112*21kkiinth/2 2233821h21hh=6，為偶數(shù)時(shí)，樹(shù)的階為，為偶數(shù)時(shí)，樹(shù)的階為k=inth/221 12kk k=3B112*221kikiinth/

12、23*23k=2k=13921h21hBh=6，為偶數(shù)時(shí)，樹(shù)的階為，為偶數(shù)時(shí)，樹(shù)的階為k=inth/221 12kk k=3k=2B22*23kkiinth/2 2254. KD樹(shù)和樹(shù)和PR四分樹(shù)都可以支持區(qū)域四分樹(shù)都可以支持區(qū)域查找。請(qǐng)問(wèn)兩者有什么優(yōu)劣勢(shì)？查找。請(qǐng)問(wèn)兩者有什么優(yōu)劣勢(shì)？401、k-d樹(shù)樹(shù) k-d樹(shù)是一種用于多維檢索的樹(shù)結(jié)構(gòu)，它的每樹(shù)是一種用于多維檢索的樹(shù)結(jié)構(gòu)，它的每一層都根據(jù)特定關(guān)鍵碼將對(duì)象空間分解為兩一層都根據(jù)特定關(guān)鍵碼將對(duì)象空間分解為兩個(gè)個(gè)頂層結(jié)點(diǎn)按一個(gè)維劃分頂層結(jié)點(diǎn)按一個(gè)維劃分第二層結(jié)點(diǎn)按照另一維進(jìn)行劃分第二層結(jié)點(diǎn)按照另一維進(jìn)行劃分以此類推在各個(gè)維之間反復(fù)進(jìn)行劃分以此類推

13、在各個(gè)維之間反復(fù)進(jìn)行劃分 最終當(dāng)一個(gè)結(jié)點(diǎn)中的點(diǎn)數(shù)少于給點(diǎn)的最大點(diǎn)數(shù)時(shí)，最終當(dāng)一個(gè)結(jié)點(diǎn)中的點(diǎn)數(shù)少于給點(diǎn)的最大點(diǎn)數(shù)時(shí)，劃分結(jié)束劃分結(jié)束 識(shí)別器( discriminator ) 在每一層用來(lái)進(jìn)行決策的關(guān)鍵碼稱為識(shí)別器在每一層用來(lái)進(jìn)行決策的關(guān)鍵碼稱為識(shí)別器對(duì)于對(duì)于k維關(guān)鍵碼，在第維關(guān)鍵碼，在第i層把識(shí)別器定義為層把識(shí)別器定義為i mod k例如，對(duì)一個(gè)三維的關(guān)鍵碼做檢索，例如，對(duì)一個(gè)三維的關(guān)鍵碼做檢索，3個(gè)關(guān)鍵碼個(gè)關(guān)鍵碼（x，y，z）標(biāo)號(hào)分別為）標(biāo)號(hào)分別為0、1、2第一層是第一層是0 mod 3=0，所以使用關(guān)鍵碼，所以使用關(guān)鍵碼x，第二層是第二層是1 mod 3=1，所以使用關(guān)鍵碼，所以使用關(guān)鍵碼

14、y結(jié)點(diǎn)的分配結(jié)點(diǎn)的分配在結(jié)點(diǎn)分配的時(shí)候首先比較該層的識(shí)別器在結(jié)點(diǎn)分配的時(shí)候首先比較該層的識(shí)別器如果關(guān)鍵碼小于識(shí)別器的值就放到左子樹(shù)中如果關(guān)鍵碼小于識(shí)別器的值就放到左子樹(shù)中否則放到右子樹(shù)否則放到右子樹(shù)然后在下一層使用新的識(shí)別器來(lái)判斷每個(gè)結(jié)然后在下一層使用新的識(shí)別器來(lái)判斷每個(gè)結(jié)點(diǎn)的歸屬點(diǎn)的歸屬識(shí)別器的值應(yīng)該盡量使得被劃分的結(jié)點(diǎn)大約識(shí)別器的值應(yīng)該盡量使得被劃分的結(jié)點(diǎn)大約一半落在左子樹(shù)，另一半落在右子樹(shù)一半落在左子樹(shù)，另一半落在右子樹(shù)K-DK-D樹(shù)示例樹(shù)示例K-D樹(shù)的空間分解樹(shù)的空間分解上圖是一個(gè)二維的上圖是一個(gè)二維的k-d樹(shù)，取值范圍為樹(shù)，取值范圍為100100之內(nèi)之內(nèi)k-dk-d樹(shù)的每個(gè)內(nèi)部結(jié)點(diǎn)樹(shù)

15、的每個(gè)內(nèi)部結(jié)點(diǎn)把當(dāng)前的空間劃分為兩塊，交替地對(duì)兩個(gè)維進(jìn)行劃分把當(dāng)前的空間劃分為兩塊，交替地對(duì)兩個(gè)維進(jìn)行劃分根結(jié)點(diǎn)把空間劃分成兩部分根結(jié)點(diǎn)把空間劃分成兩部分其子結(jié)點(diǎn)進(jìn)一步把空間劃分成更小的部分其子結(jié)點(diǎn)進(jìn)一步把空間劃分成更小的部分子結(jié)點(diǎn)的劃分線不會(huì)穿過(guò)根結(jié)點(diǎn)的劃分線子結(jié)點(diǎn)的劃分線不會(huì)穿過(guò)根結(jié)點(diǎn)的劃分線 k-d樹(shù)中的這些結(jié)點(diǎn)最終把空間分解為矩形樹(shù)中的這些結(jié)點(diǎn)最終把空間分解為矩形這些矩形是結(jié)點(diǎn)可能落到的各子樹(shù)范圍這些矩形是結(jié)點(diǎn)可能落到的各子樹(shù)范圍K-D樹(shù)的不足 其結(jié)構(gòu)與輸入數(shù)據(jù)的順序也是有關(guān)的其結(jié)構(gòu)與輸入數(shù)據(jù)的順序也是有關(guān)的有可能導(dǎo)致它每個(gè)子樹(shù)的元素分配不均衡有可能導(dǎo)致它每個(gè)子樹(shù)的元素分配不均衡Ben

16、tley和和Friedman發(fā)明了發(fā)明了adaptive k-d樹(shù)，樹(shù)，類似于類似于BST所有的數(shù)據(jù)記錄都存儲(chǔ)在葉結(jié)點(diǎn)所有的數(shù)據(jù)記錄都存儲(chǔ)在葉結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn)只是用來(lái)在各個(gè)維之間導(dǎo)航內(nèi)部結(jié)點(diǎn)只是用來(lái)在各個(gè)維之間導(dǎo)航每一個(gè)識(shí)別器的選擇不再依賴于輸入的數(shù)據(jù)每一個(gè)識(shí)別器的選擇不再依賴于輸入的數(shù)據(jù)盡量選擇讓左右子樹(shù)的記錄數(shù)目相等的值 2、PR四分樹(shù)四分樹(shù) PR四分樹(shù)，即點(diǎn)四分樹(shù)，即點(diǎn)-區(qū)域四分樹(shù)（區(qū)域四分樹(shù)（Point-Region Quadtree） ：每個(gè)內(nèi)部結(jié)點(diǎn)都恰好有四個(gè)子結(jié)點(diǎn)每個(gè)內(nèi)部結(jié)點(diǎn)都恰好有四個(gè)子結(jié)點(diǎn)每個(gè)內(nèi)部結(jié)點(diǎn)將當(dāng)前空間均等地劃分為四個(gè)區(qū)域每個(gè)內(nèi)部結(jié)點(diǎn)將當(dāng)前空間均等地劃分為四個(gè)區(qū)域NWNW

17、（西北）、（西北）、NENE（東北）、（東北）、SWSW（西南）和（西南）和SESE（東南）（東南）PR四分樹(shù)也是對(duì)對(duì)象空間的劃分四分樹(shù)也是對(duì)對(duì)象空間的劃分完全四叉樹(shù)完全四叉樹(shù) PR四分樹(shù)對(duì)空間的劃分四分樹(shù)對(duì)空間的劃分每個(gè)內(nèi)部結(jié)點(diǎn)將當(dāng)前空間均等地劃分為四個(gè)每個(gè)內(nèi)部結(jié)點(diǎn)將當(dāng)前空間均等地劃分為四個(gè)區(qū)區(qū)如果子區(qū)域包含的數(shù)據(jù)點(diǎn)數(shù)大于如果子區(qū)域包含的數(shù)據(jù)點(diǎn)數(shù)大于1，那么就把該區(qū)，那么就把該區(qū)域繼續(xù)均等地劃分為四個(gè)區(qū)域域繼續(xù)均等地劃分為四個(gè)區(qū)域依次類推，直到每個(gè)區(qū)域所包含的數(shù)據(jù)點(diǎn)不超過(guò)依次類推，直到每個(gè)區(qū)域所包含的數(shù)據(jù)點(diǎn)不超過(guò)一個(gè)為止一個(gè)為止 PR樹(shù)的圖示PR樹(shù)的劃分樹(shù)的劃分上圖所表示的上圖所表示的PR四

18、分樹(shù)，其對(duì)象空間為四分樹(shù)，其對(duì)象空間為128 128 ，并包含點(diǎn)并包含點(diǎn)A、B、C、D、E、F和和G 根結(jié)點(diǎn)的四個(gè)子結(jié)點(diǎn)把整個(gè)空間平分為四份根結(jié)點(diǎn)的四個(gè)子結(jié)點(diǎn)把整個(gè)空間平分為四份大小為大小為64 64的子空間的子空間NW，NE，SW，SE NW（包含三個(gè)數(shù)據(jù)點(diǎn)）和（包含三個(gè)數(shù)據(jù)點(diǎn)）和SE(包含兩個(gè)數(shù)據(jù)點(diǎn)包含兩個(gè)數(shù)據(jù)點(diǎn)) 需要進(jìn)一步分裂需要進(jìn)一步分裂 PR樹(shù)的插入如果這個(gè)位置的葉結(jié)點(diǎn)沒(méi)有包含其他的數(shù)據(jù)點(diǎn)如果這個(gè)位置的葉結(jié)點(diǎn)沒(méi)有包含其他的數(shù)據(jù)點(diǎn)那么我們就把記錄插入這里；那么我們就把記錄插入這里；如果這個(gè)葉結(jié)點(diǎn)中已經(jīng)包含如果這個(gè)葉結(jié)點(diǎn)中已經(jīng)包含P了了(或者一個(gè)具有或者一個(gè)具有P的坐的坐標(biāo)的記錄標(biāo)的記

19、錄)那么就報(bào)告記錄重復(fù)；那么就報(bào)告記錄重復(fù)；如果葉結(jié)點(diǎn)已經(jīng)包含另一條記錄如果葉結(jié)點(diǎn)已經(jīng)包含另一條記錄X那么就必須繼續(xù)分解這個(gè)結(jié)點(diǎn)，直到已存在的記錄那么就必須繼續(xù)分解這個(gè)結(jié)點(diǎn)，直到已存在的記錄X和和P分分別進(jìn)入不同的結(jié)點(diǎn)為止別進(jìn)入不同的結(jié)點(diǎn)為止 PR樹(shù)的刪除產(chǎn)生的合并刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)D導(dǎo)致的區(qū)域合并導(dǎo)致的區(qū)域合并PR樹(shù)的不足無(wú)法做到有效率的插入刪除，很有可能出現(xiàn)最壞情無(wú)法做到有效率的插入刪除，很有可能出現(xiàn)最壞情況；況；空間動(dòng)態(tài)分配，但是增加空間動(dòng)態(tài)分配，但是增加/減少的量并不穩(wěn)定；減少的量并不穩(wěn)定；處理分布比較均勻的情況時(shí)，效果并不差。處理分布比較均勻的情況時(shí)，效果并不差。53考試大綱考試大綱5

20、4關(guān)于考試時(shí)間和地點(diǎn)時(shí)間和地點(diǎn)時(shí)間：時(shí)間：2015年年1月月7日日 上午上午8:30-10:30地點(diǎn)：一教地點(diǎn)：一教 201考試題型考試題型填空、選擇、辨析與簡(jiǎn)答、數(shù)據(jù)結(jié)構(gòu)或算法的設(shè)計(jì)和分析填空、選擇、辨析與簡(jiǎn)答、數(shù)據(jù)結(jié)構(gòu)或算法的設(shè)計(jì)和分析、數(shù)學(xué)證明、數(shù)學(xué)證明（1）數(shù)據(jù)結(jié)構(gòu)）數(shù)據(jù)結(jié)構(gòu)/算法設(shè)計(jì)與分析題只要寫明基本思想、無(wú)算法設(shè)計(jì)與分析題只要寫明基本思想、無(wú)歧義即可，必要時(shí)加上足夠的注釋。歧義即可，必要時(shí)加上足夠的注釋。（2）對(duì)于算法中直接使用的類和函數(shù)（例如棧、隊(duì)列的）對(duì)于算法中直接使用的類和函數(shù)（例如棧、隊(duì)列的函數(shù)），應(yīng)該先寫函數(shù)），應(yīng)該先寫ADT，并簡(jiǎn)單說(shuō)明算法中用到的重要函，并簡(jiǎn)單說(shuō)明算

21、法中用到的重要函數(shù)的功能、入口參數(shù)、出口參數(shù)。數(shù)的功能、入口參數(shù)、出口參數(shù)。范圍：范圍：1-12章章55考場(chǎng)安排和注意事項(xiàng)考場(chǎng)安排和注意事項(xiàng) 請(qǐng)隨身帶好您的學(xué)生證，筆和涂改工具參加考試。請(qǐng)隨身帶好您的學(xué)生證，筆和涂改工具參加考試。 考試形式為閉卷，可以使用計(jì)算器考試形式為閉卷，可以使用計(jì)算器 考前考前10分鐘，請(qǐng)大家把書包等放在教室前面的講臺(tái)和窗臺(tái)上分鐘，請(qǐng)大家把書包等放在教室前面的講臺(tái)和窗臺(tái)上，注意在試卷紙和有效答題紙上寫上姓名和學(xué)號(hào)。，注意在試卷紙和有效答題紙上寫上姓名和學(xué)號(hào)。 統(tǒng)一發(fā)草稿紙，不夠可以隨時(shí)舉手要。統(tǒng)一發(fā)草稿紙，不夠可以隨時(shí)舉手要。 請(qǐng)大家注意考場(chǎng)紀(jì)律，不要交頭接耳，私下討論

22、。考試時(shí)對(duì)請(qǐng)大家注意考場(chǎng)紀(jì)律，不要交頭接耳，私下討論。考試時(shí)對(duì)試題有疑問(wèn)，可以舉手，待監(jiān)考老師來(lái)到旁邊時(shí)，再請(qǐng)向監(jiān)試題有疑問(wèn)，可以舉手，待監(jiān)考老師來(lái)到旁邊時(shí)，再請(qǐng)向監(jiān)考老師詢問(wèn)?？祭蠋熢儐?wèn)。 監(jiān)考老師收卷清點(diǎn)無(wú)誤，并宣布監(jiān)考老師收卷清點(diǎn)無(wú)誤，并宣布“全班同學(xué)都可以離開(kāi)了全班同學(xué)都可以離開(kāi)了”以后方可集體離開(kāi)。注意，不要把試卷題帶出考場(chǎng)，否則將以后方可集體離開(kāi)。注意，不要把試卷題帶出考場(chǎng)，否則將計(jì)零分。計(jì)零分。56第第1章章 概論概論一一. 重要概念重要概念1. 抽象數(shù)據(jù)結(jié)構(gòu)抽象數(shù)據(jù)結(jié)構(gòu) 2. 數(shù)據(jù)邏輯結(jié)構(gòu)數(shù)據(jù)邏輯結(jié)構(gòu) 3.數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)數(shù)據(jù)存儲(chǔ)結(jié)構(gòu) 4. 算法算法 5. 算法分析算法分析(時(shí)間代

23、價(jià)、空間代價(jià)時(shí)間代價(jià)、空間代價(jià)) 二二. 方法方法1. 根據(jù)二元組畫出圖示邏輯結(jié)構(gòu)根據(jù)二元組畫出圖示邏輯結(jié)構(gòu)(注意邊的方向注意邊的方向) 2. 根據(jù)要求設(shè)計(jì)數(shù)據(jù)結(jié)根據(jù)要求設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)構(gòu) 3. 算法的漸進(jìn)分析方法算法的漸進(jìn)分析方法 4. 大大O表示法表示法（不要求掌握大（不要求掌握大、大、大表示法）表示法）57第第2章章 線性表線性表一一. 概念概念1. 線性表線性表 2. 單鏈表單鏈表 3. 雙鏈表雙鏈表 4. 循環(huán)表循環(huán)表二二. 方法方法1. 順序表上實(shí)現(xiàn)的運(yùn)算順序表上實(shí)現(xiàn)的運(yùn)算 2.鏈表上實(shí)現(xiàn)的運(yùn)算鏈表上實(shí)現(xiàn)的運(yùn)算(指針操作的正確性指針操作的正確性) 3. 順序表和鏈表的比較順序表和鏈表的

24、比較58第第3章章 棧與隊(duì)列棧與隊(duì)列一一. 概念概念1. 棧棧 2. 隊(duì)列隊(duì)列 3. 循環(huán)隊(duì)列循環(huán)隊(duì)列二二. 方法方法 1. 棧的性質(zhì)，用棧來(lái)生成序列棧的性質(zhì)，用棧來(lái)生成序列 2. 隊(duì)列的性質(zhì)，用隊(duì)列隊(duì)列的性質(zhì)，用隊(duì)列 生成生成 序列序列 3. 棧的順序?qū)崿F(xiàn)棧的順序?qū)崿F(xiàn) 4. 循環(huán)隊(duì)列的實(shí)現(xiàn)循環(huán)隊(duì)列的實(shí)現(xiàn)5. 表達(dá)式求值表達(dá)式求值 (中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式的算法、中綴表達(dá)式轉(zhuǎn)后綴表達(dá)式的算法、后綴表達(dá)式求值算法后綴表達(dá)式求值算法)6. 棧在遞歸調(diào)用及轉(zhuǎn)換中的應(yīng)用棧在遞歸調(diào)用及轉(zhuǎn)換中的應(yīng)用59第第4章章 字符串字符串一一. 概念概念1. 串串 2. 模式匹配模式匹配二二. 方法方法1. 串的基本

25、操作串的基本操作2. 串的存儲(chǔ)及運(yùn)算串的存儲(chǔ)及運(yùn)算 3. 串的串的KMP快速模式匹配算法，求特征向量數(shù)快速模式匹配算法，求特征向量數(shù)組（組（N數(shù)組）和利用數(shù)組）和利用N向量完成匹配的方法向量完成匹配的方法60第第5章章 二叉樹(shù)二叉樹(shù)一一. 概念概念1. 二叉樹(shù)二叉樹(shù) 2.二叉樹(shù)的深度優(yōu)先周游二叉樹(shù)的深度優(yōu)先周游 3. 二叉排序樹(shù)二叉排序樹(shù) 4. 堆堆 5. Huffman樹(shù)、樹(shù)、Huffman編碼編碼各種結(jié)構(gòu)的節(jié)點(diǎn)個(gè)數(shù)與高度、層次、度等關(guān)系換算各種結(jié)構(gòu)的節(jié)點(diǎn)個(gè)數(shù)與高度、層次、度等關(guān)系換算 二二. 方法方法1二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)（1）二叉鏈表）二叉鏈表（2）帶父指針的三重鏈表）帶父指

26、針的三重鏈表612. 二叉樹(shù)的順序存儲(chǔ)二叉樹(shù)的順序存儲(chǔ)完全二叉樹(shù)的順序存儲(chǔ)完全二叉樹(shù)的順序存儲(chǔ) 3. 二叉樹(shù)的深度優(yōu)先周游二叉樹(shù)的深度優(yōu)先周游 4. BST樹(shù)的插入與刪除樹(shù)的插入與刪除 5. 構(gòu)造構(gòu)造Huffman樹(shù)樹(shù)和和Huffman編碼編碼 6. 堆的建立與維護(hù)過(guò)程堆的建立與維護(hù)過(guò)程62636465第第6章章 樹(shù)樹(shù)一一. 概念概念樹(shù)、森林樹(shù)、森林 、先根、后根、層次周游先根、后根、層次周游 K叉樹(shù)叉樹(shù) 二二. 方法方法 1. 森林與二叉樹(shù)相互轉(zhuǎn)換森林與二叉樹(shù)相互轉(zhuǎn)換2森林的鏈?zhǔn)酱鎯?chǔ)森林的鏈?zhǔn)酱鎯?chǔ) (1) 轉(zhuǎn)換為相應(yīng)的二叉樹(shù)，用二叉鏈表表示轉(zhuǎn)換為相應(yīng)的二叉樹(shù)，用二叉鏈表表示(2) 父指針表示

27、法、(3) 子結(jié)點(diǎn)表表示法(4)等價(jià)類和并查算法的應(yīng)用66 3. 森林的深度優(yōu)先周游（遞歸），可能結(jié)合應(yīng)用森林的深度優(yōu)先周游（遞歸），可能結(jié)合應(yīng)用 4. 森林的順序存儲(chǔ)森林的順序存儲(chǔ)及其構(gòu)造及其構(gòu)造5. 二叉樹(shù)和森林的層次周游二叉樹(shù)和森林的層次周游(用隊(duì)列用隊(duì)列)，可能結(jié)合應(yīng)用，可能結(jié)合應(yīng)用67第第7章章 圖圖一一. 概念概念1. 圖的相關(guān)概念：圖的相關(guān)概念：連通性、連通分量、邊與頂點(diǎn)關(guān)系等連通性、連通分量、邊與頂點(diǎn)關(guān)系等2. 深度周游深度周游、寬度周游寬度周游 3. 圖的生成樹(shù)、生成樹(shù)林、最小生成樹(shù)圖的生成樹(shù)、生成樹(shù)林、最小生成樹(shù)二二. 方法及算法方法及算法1. 圖的存儲(chǔ)方法圖的存儲(chǔ)方法:（

28、1） 相鄰矩陣相鄰矩陣 （2） 鄰接表鄰接表2. 圖的周游圖的周游: 1） 深度優(yōu)先深度優(yōu)先 （2） 寬度優(yōu)先寬度優(yōu)先683. 圖的生成樹(shù)與最小生成樹(shù)圖的生成樹(shù)與最小生成樹(shù)從某一點(diǎn)出發(fā)，按深度優(yōu)先或?qū)挾葍?yōu)先周游的生成樹(shù)從某一點(diǎn)出發(fā)，按深度優(yōu)先或?qū)挾葍?yōu)先周游的生成樹(shù)最小生成樹(shù)最小生成樹(shù) Prim算法算法 Kruskal算法算法(避圈法避圈法)4. 拓?fù)渑判蛲負(fù)渑判?: 給定圖，找出若干個(gè)或所有拓?fù)湫蛄薪o定圖，找出若干個(gè)或所有拓?fù)湫蛄?. 最短路徑最短路徑: Dijkstra算法、算法、Floyd算法算法6. Dijkstra算法、算法、Prim算法、算法、Kruskal算法都是典型算法都是典型的

29、貪心法（退化的動(dòng)態(tài)規(guī)劃法）的貪心法（退化的動(dòng)態(tài)規(guī)劃法）69第第8章章 內(nèi)排序內(nèi)排序 1. 重點(diǎn)排序算法：直接插入法、重點(diǎn)排序算法：直接插入法、Shell排序、快排序、快速排序、基數(shù)排序、歸并排序速排序、基數(shù)排序、歸并排序 2. 算法分析算法分析基于比較次數(shù)和移位次數(shù)分析最好、最壞的時(shí)間、空間基于比較次數(shù)和移位次數(shù)分析最好、最壞的時(shí)間、空間直接插入法、二分法插入排序、起泡排序、直接選擇、快直接插入法、二分法插入排序、起泡排序、直接選擇、快速排序、基數(shù)排序、歸并排序速排序、基數(shù)排序、歸并排序記住各種排序方法的平均時(shí)間記住各種排序方法的平均時(shí)間 3. 各種排序方法的局部修改和混合應(yīng)用各種排序方法的局

30、部修改和混合應(yīng)用70第9章 文件管理和外排序方法及算法方法及算法 1. 置換選擇排序置換選擇排序 2. 多路歸并多路歸并 (敗者樹(shù)，最佳歸并樹(shù)，多路歸并的讀敗者樹(shù)，最佳歸并樹(shù)，多路歸并的讀盤和寫盤次數(shù)盤和寫盤次數(shù))71第10章 檢索一一. 概念概念1. 平均檢索長(zhǎng)度平均檢索長(zhǎng)度 2. 二分法檢索二分法檢索 3. 散列表、同義詞、碰散列表、同義詞、碰撞、堆積撞、堆積二二. 方法方法1. 二分法檢索的判定樹(shù)、查找某個(gè)結(jié)點(diǎn)的比較次數(shù)二分法檢索的判定樹(shù)、查找某個(gè)結(jié)點(diǎn)的比較次數(shù)2. 散列表散列表: 1) 散列函數(shù)選擇散列函數(shù)選擇(除余法、平方取中法、折疊法除余法、平方取中法、折疊法)2) 沖突處理方法(分離同義詞子表、線性探測(cè)、雙散列函數(shù)) 三三. 散列算法（查找、插入、刪除，對(duì)墓碑的處理散列算法（查找、插入、刪除，對(duì)墓碑的處理72第11章 索引技術(shù)一一. 概念概念 1. 順序文件順序文件 2. 散列文件散列文件 3. 倒排文件倒排文件 4. 靜態(tài)索引結(jié)構(gòu)靜態(tài)索引結(jié)構(gòu) 5.動(dòng)動(dòng)態(tài)索引結(jié)構(gòu)態(tài)索引結(jié)構(gòu)(B樹(shù)樹(shù)) 6. 紅黑樹(shù)紅黑樹(shù)二二. 方法（不考算法）方法（不考算法）1. B樹(shù)、樹(shù)、B+樹(shù)的插入與刪除樹(shù)的