《數(shù)據(jù)結(jié)構(gòu)期末復習要點（嚴蔚敏版）(共3頁)》由會員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)期末復習要點（嚴蔚敏版）(共3頁)（5頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)期末復習要點第一章 緒論1、掌握基本概念和術(shù)語，看教材P4P6部分內(nèi)容；2、看P10P11關(guān)于類C的語法描述，算法設(shè)計寫代碼時可用到；3、掌握算法的特征（5個）和要求（5個）（P13P14），能夠結(jié)合具體算法分析算法的時間復雜度和空間復雜度（比如線性表的插入、刪除操作，查找、排序等操作），理解O(n)、O(1)等時間復雜度的具體含義（P14P17）。第二章 線性表1、看教材P21P26，掌握有關(guān)線性表順序存儲的內(nèi)容：（1）順序表的隨機存取（P21計算地址的公式）；（2）順序表的表示（P22的Typedef）；（3）順序表為空、為滿的判定，插入和刪除操作的特征以
2、及時間復雜度的分析（P23P25）；（4）有關(guān)順序表的編程題。2、看教材P27P30，掌握有關(guān)線性表鏈式存儲的內(nèi)容：（1）單鏈表的表示（P28的Typedef）；（2）單鏈表為空的判定（帶頭結(jié)點、不帶頭結(jié)點）；（3）單鏈表插入、刪除操作的特征（操作點的確定以和指針的修改）以及時間復雜度分析（P29P30）；（4）有關(guān)單鏈表的編程。3、為節(jié)約時間，循環(huán)鏈表、雙向鏈表以及多項式加法可以不看；4、算法設(shè)計題要求寫代碼，在本章體現(xiàn)的可能性比較大。第三章 棧和隊列1、順序棧的表示，棧操作的特點以及為空、為滿的判定（P46P47）；2、棧的應用舉例看個標題就足夠了；3、鏈隊列的表示以及入隊、出隊操作（P6
3、1P62）；4、循環(huán)隊列為空、為滿的判定（P65的代碼中）；5、離散事件模擬這節(jié)不用看；6、第四章只需要看P70就夠了，掌握串的特點（元素受限），串長度、空串、串的位置、串相等幾個概念即可。 第六章 樹和二叉樹1、看教材P120，了解有關(guān)樹的概念和術(shù)語；2、了解二叉樹的鏈式存儲結(jié)構(gòu)（P127），掌握二叉樹的性質(zhì)（P123P125），并會做題（參考課件或指導書相關(guān)內(nèi)容）； 3、掌握二叉樹的各種遍歷算法（P128P129或課件）：（1）能夠根據(jù)二叉樹寫出各種遍歷序列；（2）能夠由兩種遍歷序列（必須包含中序序列）恢復二叉樹；（3）理解二叉樹遍歷算法的遞歸代碼，能夠讀懂代碼含義。4、線索二叉樹、樹和森
4、林的遍歷略看即可，涉及不多；樹與等價問題沒講不用看；5、掌握Huffman樹的相關(guān)內(nèi)容（P144P148）：（1）給定字符及頻率構(gòu)造Huffman樹，設(shè)計Huffman編碼；（2）掌握前綴編碼的概念，能判定一組編碼是否前綴編碼。6、回溯法和樹的計數(shù)這兩節(jié)不用看；7、注意：要能夠分析遞歸程序的執(zhí)行結(jié)果（不局限于二叉樹的遞歸算法）。第七章 圖1、看教材P157P159，熟悉圖的定義和術(shù)語；2、看教材P161P164，掌握圖的鄰接矩陣和鄰接表兩種存儲結(jié)構(gòu)：（1）掌握存儲結(jié)構(gòu)的特點（是否對陣、求邊數(shù)、求結(jié)點度等）；（2）能夠畫出給定圖的存儲結(jié)構(gòu)，或者根據(jù)存儲結(jié)構(gòu)畫出圖的邏輯結(jié)構(gòu)；（3）能夠?qū)懗鲈趦煞N存
5、儲結(jié)構(gòu)上進行深度優(yōu)先和廣度優(yōu)先遍歷的序列；（4）十字鏈表和鄰接多重表不用看了。3、看教材P173P176，掌握構(gòu)造最小生成樹的Prim算法和Kruskal算法，能夠按照考研指導書P199和P201所示的步驟構(gòu)造最小生成樹；4、對于拓撲排序算法和關(guān)鍵路徑算法，前者可能要求寫出拓撲排序序列，后者無法以大題考查，略看即可；5、知道求最短路徑的兩個算法的名稱和能解決的問題即可，不必太費時間。第九章 查找1、理解順序查找的過程，分析索引順序查找的性能，不用看靜態(tài)樹表查找；2、看教材P218P221，掌握折半查找算法：（1）折半查找的前提；（2）折半查找的過程；（3）折半查找的判定樹；（4）折半查找的AS
6、L。3、掌握二叉排序樹算法：（1）BST的定義和構(gòu)造（P227P229）；（2）BST的查找分析（P231）；（3）平衡二叉樹（AVL）的定義和BBST的判定（P233）。4、了解B-樹（P238P239）和B+樹（P246）的定義，不看鍵樹；5、掌握哈希表的構(gòu)造和哈希查找的過程：（1）哈希函數(shù)掌握“除留余數(shù)法”（P255）；（2）沖突處理函數(shù)掌握“開放定址法”中的線性探測再散列和二次探測再散列（P257），能夠?qū)⒔o定的關(guān)鍵字填入哈希表的適當位置；（3）分析查找過程中關(guān)鍵字的比較次數(shù)。第十章 內(nèi)部排序1、看教材P263P264，掌握學習排序算法的總體思路：（1）算法思想（排序原則和排序過程）；
7、（2）算法性能（時間和空間復雜度）；（3）算法穩(wěn)定性（取決于算法本身）；（4）算法的特殊性（適用前提、排序結(jié)果）；（5）注意橫向分析比較各種排序算法。2、掌握直接插入排序的算法思想（讀懂代碼、模擬流程），能夠進行性能分析（P265P266）；3、折半插入排序、2-路插入排序、表插入排序和希爾排序略看即可；4、能夠模擬起泡排序的執(zhí)行過程，分析起泡排序的時間性能，把握起泡排序的結(jié)果特征（P273）；5、看教材P273P276，掌握快速排序的基本思想（選取樞軸，逆序交換，遞歸完成），分析快速排序的時間性能（最好、最壞），把握快速排序的適用場合（何時最佳），調(diào)整快速排序的執(zhí)行環(huán)境（三者取中法）；6、理解簡單選擇排序和樹形選擇排序的基本思想，重點掌握堆排序算法（P277P282）：（1）堆的定義（小頂堆和大頂堆）和堆排序（初始建堆+重建堆）；（2）能夠用完全二叉樹的形式完成初始建堆和重建堆（篩選）；（3）明確何時創(chuàng)建什么樣的堆（降序創(chuàng)建小頂堆，升序創(chuàng)建大頂堆）；（4）分析堆排序的特點和性能。7、理解歸并排序的特點和性能（穩(wěn)定的、先進的）（P283P284）；8、了解基數(shù)排序的基本思想（以“分配”和“收集”代替關(guān)鍵字的比較），分析基數(shù)排序的性能（P286P287）專心-專注-專業(yè)
數(shù)據(jù)結(jié)構(gòu)期末復習要點（嚴蔚敏版）(共3頁)
