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

1、1第第10-12章章習(xí)題課習(xí)題課宋國杰宋國杰北京大學(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)。 注意：字符串本身可能比較長；字符串的個(gè)數(shù)在105 個(gè)左右。3答案考查知識(shí)點(diǎn)：考查知識(shí)點(diǎn)：開散列開散列方案：考慮到字符串很多的因素，采用方案：考慮到字符串很多的因素，采用拉鏈?zhǔn)嚼準(zhǔn)紿ash表表解決，解決，用一個(gè)用一個(gè)Hash函數(shù)進(jìn)行尋址函數(shù)進(jìn)行尋

2、址；考慮到字符串很長的因素，考慮到字符串很長的因素，在插入的時(shí)候用另一個(gè)在插入的時(shí)候用另一個(gè)Hash函數(shù)來給每一個(gè)字符串一個(gè)函數(shù)來給每一個(gè)字符串一個(gè)ID，相同的字符串相同的字符串ID一定相同，不同的字符串也有一定概率一定相同，不同的字符串也有一定概率ID相同，相同，在查找時(shí)，僅需考慮在查找時(shí)，僅需考慮ID相同的串來確定是否串相同的串來確定是否串X存在存在，避免了大范圍的查找，和大量長字符串匹配，避免了大范圍的查找，和大量長字符串匹配。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)到文檔開頭，那么移動(dòng)到文檔開頭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ì)一套合理的算法，來實(shí)）請(qǐng)基于線性數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)一套合理的算法，來實(shí)現(xiàn)這些操作，并且分析每個(gè)操作的性能。假定：文本現(xiàn)這些操作，并且分析每個(gè)操作的性能。假定：文本最大的長度為最大的長度為Lh2：15那么，為了滿足紅黑樹性質(zhì)，我們令那么，為了滿足紅黑樹性質(zhì)，我們令T2的根結(jié)點(diǎn)為的根結(jié)點(diǎn)為多多(h1-h2+1)黑結(jié)點(diǎn)。我們可以利用紅黑樹的刪除算黑結(jié)點(diǎn)。我們可以利用紅黑樹的刪除算法中對(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)，那么就變成了一棵正常的紅黑樹。至為單黑結(jié)點(diǎn)，那么就變成了一棵正常的紅黑樹。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)整完成保持樹的穩(wěn)定性！保持樹的穩(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)過分詞后的網(wǎng)頁已經(jīng)形成了倒排索引，使用假定經(jīng)過分詞后的網(wǎng)頁已經(jīng)形成了倒排索引，使用trie樹作為詞典，葉子結(jié)點(diǎn)會(huì)有指向倒排表的指針，樹作為詞典，葉子結(jié)點(diǎn)會(huì)有指向倒排表的指針，倒排表是按照網(wǎng)頁文檔倒排表是按照網(wǎng)頁文檔id（連續(xù)的整數(shù)值）排好序（連續(xù)的整數(shù)值）排好序的?，F(xiàn)在需要系統(tǒng)支持簡單的布爾查詢。請(qǐng)寫出以的?，F(xiàn)在需要系統(tǒng)支持簡單的布爾查詢。請(qǐng)寫出以下算法的代碼或偽代碼，并分析復(fù)雜度下算法的代碼或偽代碼，并分析復(fù)雜度29I. Keyword1 and keyword2II. Keyword2 and not ke

10、yword2III.如果需要支持相鄰查詢，例如如果需要支持相鄰查詢，例如keyword and keword2 near distance，distance代表詞與詞代表詞與詞之間的距離，需要怎樣更改倒排索引表，支之間的距離，需要怎樣更改倒排索引表，支持這一需求？持這一需求？30答案答案1、用用 trie 樹可以在樹可以在 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樹和紅黑樹的高度樹和紅黑樹的高度A. 高度為高度為h的的AVL樹上的最少結(jié)點(diǎn)個(gè)數(shù)是多少？最多樹上的最少結(jié)點(diǎn)個(gè)數(shù)是多少？最多結(jié)點(diǎn)個(gè)數(shù)是多少？結(jié)點(diǎn)個(gè)數(shù)是多少？B. 高度為高度為h的紅黑樹上的最少結(jié)點(diǎn)個(gè)數(shù)是多少？最多的紅黑樹上的最少結(jié)點(diǎn)個(gè)數(shù)是多少？最多結(jié)點(diǎn)個(gè)數(shù)是多少？結(jié)點(diǎn)個(gè)數(shù)是多少？35363721h21hBBh=5，為奇數(shù)時(shí)，樹的階為，為奇數(shù)時(shí)，樹的階為k=inth/221 12kk 21 12kk k=2k=112*21kkiinth/2 2233821h21hh=6，為偶數(shù)時(shí)，樹的階為，為偶數(shù)時(shí)，樹的階為k=inth/221 12kk k=3B112*221kikiinth/

12、23*23k=2k=13921h21hBh=6，為偶數(shù)時(shí)，樹的階為，為偶數(shù)時(shí)，樹的階為k=inth/221 12kk k=3k=2B22*23kkiinth/2 2254. KD樹和樹和PR四分樹都可以支持區(qū)域四分樹都可以支持區(qū)域查找。請(qǐng)問兩者有什么優(yōu)劣勢(shì)？查找。請(qǐng)問兩者有什么優(yōu)劣勢(shì)？401、k-d樹樹 k-d樹是一種用于多維檢索的樹結(jié)構(gòu)，它的每樹是一種用于多維檢索的樹結(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 ) 在每一層用來進(jìn)行決策的關(guān)鍵碼稱為識(shí)別器在每一層用來進(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í)別器的值就放到左子樹中如果關(guān)鍵碼小于識(shí)別器的值就放到左子樹中否則放到右子樹否則放到右子樹然后在下一層使用新的識(shí)別器來判斷每個(gè)結(jié)然后在下一層使用新的識(shí)別器來判斷每個(gè)結(jié)點(diǎn)的歸屬點(diǎn)的歸屬識(shí)別器的值應(yīng)該盡量使得被劃分的結(jié)點(diǎn)大約識(shí)別器的值應(yīng)該盡量使得被劃分的結(jié)點(diǎn)大約一半落在左子樹，另一半落在右子樹一半落在左子樹，另一半落在右子樹K-DK-D樹示例樹示例K-D樹的空間分解樹的空間分解上圖是一個(gè)二維的上圖是一個(gè)二維的k-d樹，取值范圍為樹，取值范圍為100100之內(nèi)之內(nèi)k-dk-d樹的每個(gè)內(nèi)部結(jié)點(diǎn)樹

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ì)穿過根結(jié)點(diǎn)的劃分線子結(jié)點(diǎn)的劃分線不會(huì)穿過根結(jié)點(diǎn)的劃分線 k-d樹中的這些結(jié)點(diǎn)最終把空間分解為矩形樹中的這些結(jié)點(diǎn)最終把空間分解為矩形這些矩形是結(jié)點(diǎn)可能落到的各子樹范圍這些矩形是結(jié)點(diǎn)可能落到的各子樹范圍K-D樹的不足 其結(jié)構(gòu)與輸入數(shù)據(jù)的順序也是有關(guān)的其結(jié)構(gòu)與輸入數(shù)據(jù)的順序也是有關(guān)的有可能導(dǎo)致它每個(gè)子樹的元素分配不均衡有可能導(dǎo)致它每個(gè)子樹的元素分配不均衡Ben

16、tley和和Friedman發(fā)明了發(fā)明了adaptive k-d樹，樹，類似于類似于BST所有的數(shù)據(jù)記錄都存儲(chǔ)在葉結(jié)點(diǎn)所有的數(shù)據(jù)記錄都存儲(chǔ)在葉結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn)只是用來在各個(gè)維之間導(dǎo)航內(nèi)部結(jié)點(diǎn)只是用來在各個(gè)維之間導(dǎo)航每一個(gè)識(shí)別器的選擇不再依賴于輸入的數(shù)據(jù)每一個(gè)識(shí)別器的選擇不再依賴于輸入的數(shù)據(jù)盡量選擇讓左右子樹的記錄數(shù)目相等的值 2、PR四分樹四分樹 PR四分樹，即點(diǎn)四分樹，即點(diǎn)-區(qū)域四分樹（區(qū)域四分樹（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四分樹也是對(duì)對(duì)象空間的劃分四分樹也是對(duì)對(duì)象空間的劃分完全四叉樹完全四叉樹 PR四分樹對(duì)空間的劃分四分樹對(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)不超過依次類推，直到每個(gè)區(qū)域所包含的數(shù)據(jù)點(diǎn)不超過一個(gè)為止一個(gè)為止 PR樹的圖示PR樹的劃分樹的劃分上圖所表示的上圖所表示的PR四

18、分樹，其對(duì)象空間為四分樹，其對(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樹的插入如果這個(gè)位置的葉結(jié)點(diǎn)沒有包含其他的數(shù)據(jù)點(diǎn)如果這個(gè)位置的葉結(jié)點(diǎn)沒有包含其他的數(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樹的刪除產(chǎn)生的合并刪除結(jié)點(diǎn)刪除結(jié)點(diǎn)D導(dǎo)致的區(qū)域合并導(dǎo)致的區(qū)域合并PR樹的不足無法做到有效率的插入刪除，很有可能出現(xiàn)最壞情無法做到有效率的插入刪除，很有可能出現(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考試題型考試題型填空、選擇、辨析與簡答、數(shù)據(jù)結(jié)構(gòu)或算法的設(shè)計(jì)和分析填空、選擇、辨析與簡答、數(shù)據(jù)結(jié)構(gòu)或算法的設(shè)計(jì)和分析、數(shù)學(xué)證明、數(shù)學(xué)證明（1）數(shù)據(jù)結(jié)構(gòu)）數(shù)據(jù)結(jié)構(gòu)/算法設(shè)計(jì)與分析題只要寫明基本思想、無算法設(shè)計(jì)與分析題只要寫明基本思想、無歧義即可，必要時(shí)加上足夠的注釋。歧義即可，必要時(shí)加上足夠的注釋。（2）對(duì)于算法中直接使用的類和函數(shù)（例如棧、隊(duì)列的）對(duì)于算法中直接使用的類和函數(shù)（例如棧、隊(duì)列的函數(shù)），應(yīng)該先寫函數(shù)），應(yīng)該先寫ADT，并簡單說明算法中用到的重要函，并簡單說明算

21、法中用到的重要函數(shù)的功能、入口參數(shù)、出口參數(shù)。數(shù)的功能、入口參數(shù)、出口參數(shù)。范圍：范圍：1-12章章55考場安排和注意事項(xià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)大家注意考場紀(jì)律，不要交頭接耳，私下討論

22、。考試時(shí)對(duì)請(qǐng)大家注意考場紀(jì)律，不要交頭接耳，私下討論?？荚嚂r(shí)對(duì)試題有疑問，可以舉手，待監(jiān)考老師來到旁邊時(shí)，再請(qǐng)向監(jiān)試題有疑問，可以舉手，待監(jiān)考老師來到旁邊時(shí)，再請(qǐng)向監(jiān)考老師詢問?？祭蠋熢儐?。 監(jiān)考老師收卷清點(diǎn)無誤，并宣布監(jiān)考老師收卷清點(diǎn)無誤，并宣布“全班同學(xué)都可以離開了全班同學(xué)都可以離開了”以后方可集體離開。注意，不要把試卷題帶出考場，否則將以后方可集體離開。注意，不要把試卷題帶出考場，否則將計(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ì)，用棧來生成序列棧的性質(zhì)，用棧來生成序列 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章章 二叉樹二叉樹一一. 概念概念1. 二叉樹二叉樹 2.二叉樹的深度優(yōu)先周游二叉樹的深度優(yōu)先周游 3. 二叉排序樹二叉排序樹 4. 堆堆 5. Huffman樹、樹、Huffman編碼編碼各種結(jié)構(gòu)的節(jié)點(diǎn)個(gè)數(shù)與高度、層次、度等關(guān)系換算各種結(jié)構(gòu)的節(jié)點(diǎn)個(gè)數(shù)與高度、層次、度等關(guān)系換算 二二. 方法方法1二叉樹的鏈?zhǔn)酱鎯?chǔ)二叉樹的鏈?zhǔn)酱鎯?chǔ)（1）二叉鏈表）二叉鏈表（2）帶父指針的三重鏈表）帶父指

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

28、1） 相鄰矩陣相鄰矩陣 （2） 鄰接表鄰接表2. 圖的周游圖的周游: 1） 深度優(yōu)先深度優(yōu)先 （2） 寬度優(yōu)先寬度優(yōu)先683. 圖的生成樹與最小生成樹圖的生成樹與最小生成樹從某一點(diǎn)出發(fā)，按深度優(yōu)先或?qū)挾葍?yōu)先周游的生成樹從某一點(diǎn)出發(fā)，按深度優(yōu)先或?qū)挾葍?yōu)先周游的生成樹最小生成樹最小生成樹 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ù))71第10章 檢索一一. 概念概念1. 平均檢索長度平均檢索長度 2. 二分法檢索二分法檢索 3. 散列表、同義詞、碰散列表、同義詞、碰撞、堆積撞、堆積二二. 方法方法1. 二分法檢索的判定樹、查找某個(gè)結(jié)點(diǎn)的比較次數(shù)二分法檢索的判定樹、查找某個(gè)結(jié)點(diǎn)的比較次數(shù)2. 散列表散列表: 1) 散列函數(shù)選擇散列函數(shù)選擇(除余法、平方取中法、折疊法除余法、平方取中法、折疊法)2) 沖突處理方法(分離同義詞子表、線性探測、雙散列函數(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樹樹) 6. 紅黑樹紅黑樹二二. 方法（不考算法）方法（不考算法）1. B樹、樹、B+樹的插入與刪除樹的