數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)要點(diǎn)（嚴(yán)蔚敏版）(共3頁(yè))

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