算法與數(shù)據(jù)結(jié)構(gòu)各章學(xué)習(xí)要點

1、算法與數(shù)據(jù)結(jié)構(gòu)各章學(xué)習(xí)要點第1章概論一、學(xué)習(xí)要點：1、 熟練掌握各基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)的定義。2、 掌握邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)的基本分類。3、 掌握算法的基本特性4、 理解算法效率的評價指標(biāo)（時間復(fù)雜度、空間復(fù)雜度），能夠評價簡單算法的時間復(fù)雜度。二、作業(yè)練習(xí)：1、P10：一、二、三。第2章線性表一、學(xué)習(xí)要點：1、 掌握線性結(jié)構(gòu)的特點、線性表的定義，理解線性表的基本術(shù)語：表長、空表、直接前驅(qū)、直接后繼。2、 掌握順序表的定義和特點，掌握順序表中第i 個元素的地址計算公式3、 能夠用 C 語言描述順序表的類型并熟練應(yīng)用，熟練掌握順

2、序表的基本運算及實現(xiàn)：初始化、插入、刪除、按值查找。4、 掌握鏈表的定義，理解：頭指針、頭結(jié)點、首元結(jié)點(第一結(jié)點 )的區(qū)別。5、 能夠用 C 語言描述單鏈表結(jié)點類型并熟練應(yīng)用，熟練掌握單鏈表的基本運算及實現(xiàn)：建立（頭部建立、尾部建立）、求表長、查找（按序號查找、按值查找）、插入、刪除。6、 理解循環(huán)鏈表、雙向鏈表的算法實現(xiàn)特點。7、 掌握順序表和鏈表存儲結(jié)構(gòu)的比較。8、 能夠運用順序表和單鏈表、循環(huán)單鏈表進行算法設(shè)計。二、作業(yè)練習(xí) ：P41：一、二、三（1， 3， 4）第3章 棧與隊列一、學(xué)習(xí)要點：1、 掌握棧的定義和特點，掌握棧的基本術(shù)語：棧頂、棧底、空棧。2、 能夠根據(jù)棧的特點，描述同一

3、輸入下的不同輸出順序。3、 能夠用 C 語言描述順序棧結(jié)點類型并熟練應(yīng)用，掌握順序棧的基本運算及實現(xiàn)：置空棧、判?？铡⑷霔?、出棧、取棧頂元素。4、 掌握隊列的定義和特點，掌握隊列的基本術(shù)語：隊頭、隊尾，掌握循環(huán)隊列的目的。5、 理解循環(huán)隊列區(qū)分隊滿和隊空的方法，能夠根據(jù)解決的方法設(shè)計數(shù)據(jù)結(jié)構(gòu)，并實現(xiàn)循環(huán)隊列的基本運算：置空隊、入隊、出隊、判隊空、判隊滿、求隊列的長度。6、 能夠利用棧和隊列結(jié)構(gòu)設(shè)計算法。二、作業(yè)練習(xí)：P64 一、二、三（ 2， 3）第4章 串一、學(xué)習(xí)要點：1、 掌握串的定義和特點，掌握串的基本術(shù)語：串長、子串、主串、子串的位置、串相等、空串和空格串。2、 掌握串模式匹配的定義，

4、掌握KMP 模式匹配的思想及next 函數(shù)值的計算方法。二、作業(yè)練習(xí)：P77:一、二、三第 5 章 數(shù)組和廣義表1、 掌握數(shù)組邏輯結(jié)構(gòu)的特點以及通常做的操作。2、 掌握二維數(shù)組存儲地址計算。3、 能夠進行能夠特殊矩陣壓縮存儲地址計算公式的推導(dǎo)。4、 掌握稀疏矩陣的三元組表示。5、 掌握廣義表以及表頭、表尾的定義。二、作業(yè)練習(xí)：P89:一、二、三（ 1,2）第 6 章 樹和二叉樹一、學(xué)習(xí)要點：1、 掌握二叉樹的定義，熟悉二叉樹的五種基本形態(tài)。2、 掌握樹、二叉樹的基本術(shù)語：結(jié)點的度、樹的度、葉結(jié)點、分枝結(jié)點、孩子、兄弟、雙親、深度、層次、滿二叉樹、完全二叉樹。3、 掌握二叉樹的性質(zhì)以及相應(yīng)的證明

5、方法。4、 掌握二叉樹的順序存儲、二叉鏈表存儲，能夠繪制示意圖。5、 能夠熟練運用二叉鏈表的存儲結(jié)構(gòu)，掌握二叉樹遞歸遍歷算法，能夠給出遍歷結(jié)果。6、 能夠利用二叉樹的先序遍歷進行二叉樹的各種算法設(shè)計。7、 掌握由前序序列（或后序序列）和中序序列可唯一確定該二叉樹的方法。8、 掌握由前序序列構(gòu)造二叉樹的方法，能夠進行算法實現(xiàn)。9、 掌握線索、線索二叉樹的定義，并能將二叉樹轉(zhuǎn)換為線索二叉樹（示意圖）。10、掌握哈夫曼樹的定義，能夠根據(jù)給定的權(quán)值圖示哈夫曼樹構(gòu)造過程并進行哈夫曼編碼，并計算WPL 。11、掌握樹的定義，能夠圖示樹的雙親表示法、孩子鏈表法、雙親孩子表示法、孩子兄弟表示法。12、能夠進行

6、樹和二叉樹的轉(zhuǎn)換、森林和二叉樹的轉(zhuǎn)換。二、作業(yè) 練習(xí)：P121：一、二、三、四（17 ）第7章圖一、學(xué)習(xí)要點：1、 掌握圖的基本概念：有向圖、無向圖、網(wǎng)絡(luò)、連通分量、生成樹、度、出度、入度、完全圖、子圖。2、 能夠圖示圖的存儲結(jié)構(gòu)：鄰接矩陣、鄰接表、逆鄰接表。3、 掌握圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷的定義，能夠根據(jù)圖或鄰接表寫出遍歷順序。4、 掌握兩種最小生成樹生成最小生成樹思想和過程示意圖。5、 理解 Dijkstra 單源最短路徑算法思想。6、 能夠根據(jù)給定有向無環(huán)圖進行拓?fù)渑判?、尋找關(guān)鍵路徑。二、作業(yè)練習(xí)：P156：一、二、三、四（14）第8章查找一、學(xué)習(xí)要點：1. 掌握查找表的數(shù)據(jù)結(jié)構(gòu)

7、的特點：邏輯結(jié)構(gòu)、核心運算。2.掌握平均查找長度ASL 的定義，能夠計算各種查找算法的ASL 值。3. 能夠?qū)崿F(xiàn)順序查找算法，理解“監(jiān)視哨”的作用。4. 掌握三種靜態(tài)查找算法的比較。5.能夠用遞歸和非遞歸方法實現(xiàn)折半查找，能夠繪制折半查找的判定樹，并根據(jù)判定樹計算ASL 值。6. 理解分塊查找的思想，掌握分塊方法。7. 掌握二叉排序樹的定義，能夠根據(jù)給定的序列圖示二叉排序樹的創(chuàng)建過程。8. 掌握二叉排序樹的查找、插入的遞歸和非遞歸算法。9. 掌握平衡二叉樹、平衡因子的定義，能夠判斷失衡的原因。10. 掌握散列表的常用構(gòu)造方法和沖突處理方法，能夠根據(jù)給定哈希函數(shù)和沖突處理方法構(gòu)造哈希表。二、作業(yè)練習(xí)：P196：一、二、三、四（1,2,4,5）、五（ 1）第9章排序一、學(xué)習(xí)要點：1、 掌握排序方法穩(wěn)定和不穩(wěn)定的定義，堆、大頂堆、小頂堆的定義。2、 掌握 5 種內(nèi)部排序插入排序、交換排序、選擇排序、2路歸并、基數(shù)排序的基本思想。3、 掌握各種排序