自考02331數(shù)據(jù)結(jié)構(gòu)大綱

1、第1章概論數(shù)據(jù)結(jié)構(gòu)的作用、意義、基本概念和術(shù)語，要求達(dá)到“識記”層次。1.1數(shù)據(jù)結(jié)構(gòu)所研究的內(nèi)容；在計算機(jī)科學(xué)中的作用和意義；Wirth關(guān)于程序的定義公式。1.2數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)項、數(shù)據(jù)結(jié)構(gòu)等概念的定義。1.3數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及數(shù)據(jù)運算的含義及其相互關(guān)系。1.4數(shù)據(jù)結(jié)構(gòu)的兩大類邏輯結(jié)構(gòu)和四種常用的存儲表示方法。算法的描述和分析，要求達(dá)到“領(lǐng)會”層次。2.1算法、算法的時間復(fù)雜度和空間復(fù)雜度等概念。2.2 一個完整算法需要滿足的五個準(zhǔn)則；算法與程序的關(guān)系。2.3算法的分析方法；對于一般算法能分析其時間復(fù)雜度。第2章線性表線性表的邏輯結(jié)構(gòu)，要求達(dá)到“識記”層次。1.1線性表的

2、邏輯定義和性質(zhì)。1.2線性表上定義的基本運算。線性表的順序存儲結(jié)構(gòu)和基本運算，要求達(dá)到“領(lǐng)會”層次。2.1順序表的定義及特點。2.2順序表上進(jìn)行插入和刪除操作的實現(xiàn)及時間性能分析。2.3理解求順序表逆置和極值及定位兩種算法的實現(xiàn)過程。線性表鏈?zhǔn)酱鎯Y(jié)構(gòu)的不同形式及基本運算，要求達(dá)到“領(lǐng)會”層次。3.1單鏈表、循環(huán)鏈表、雙向鏈表的定義及特點。3.2單鏈表上實現(xiàn)建表、查找、插入和刪除等基本算法，并分析其時間復(fù)雜度。3.3用尾指針表示單循環(huán)鏈表的意義。3.4雙向鏈表上的插入和刪除操作。利用順序表和鏈表設(shè)計算法解決應(yīng)用問題，要求達(dá)到“綜合應(yīng)用”層次。順序表和鏈表的比較，要求達(dá)到“領(lǐng)會”層次。第3章棧和

3、隊列棧的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及相關(guān)算法，要求達(dá)到“簡單應(yīng)用”層次。1.1棧的邏輯定義、特點及運算。1.2順序棧和鏈棧上實現(xiàn)進(jìn)棧、退棧等基本運算。1.3順序棧的上溢和下溢問題，如何防止溢出。隊列的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及相關(guān)算法，要求達(dá)到“簡單應(yīng)用”層次。2.1隊列的邏輯定義、特點及運算。2.2順序循環(huán)隊列的表述；隊空和隊滿的判定；順序循環(huán)隊列上入隊、出隊等基本算法。2.3鏈隊列的表述；帶頭結(jié)點和不帶頭結(jié)點兩種情況下鏈隊列上的基本算法。棧和隊列的應(yīng)用，要求達(dá)到“綜合應(yīng)用”層次。3.1圓括號匹配的檢驗問題。3.2字符串回文的判斷問題。3.3數(shù)制轉(zhuǎn)換。3.4利用棧實現(xiàn)程序的遞歸。3.5表達(dá)式求值。第4章多

4、維數(shù)組和廣義表多維數(shù)組及其運算，要求達(dá)到“領(lǐng)會”層次。1.1多維數(shù)組的邏輯結(jié)構(gòu)表達(dá)及特征。1.2多維數(shù)組的順序存儲結(jié)構(gòu)及地址計算方法。1.3多維數(shù)組的常用運算。矩陣的壓縮存儲，要求達(dá)到“簡單應(yīng)用”層次。2.1特殊矩陣的類型和性質(zhì)；稀疏矩陣的概念。2.2用一維數(shù)組壓縮存儲特殊矩陣時，存儲地址的計算。2.3稀疏矩陣的三元組表表示方法及常用算法。廣義表，要求達(dá)到“領(lǐng)會”層次。3.1廣義表的定義及特性。3.2求廣義表的深度、表長、表頭和表尾運算。第5章樹和二叉樹樹的概念，要求達(dá)到“識記”層次。1.1樹的定義和表示方法。1.2樹的常用術(shù)語及其含義。二叉樹的概念，要求達(dá)到“領(lǐng)會”層次。2.1二叉樹的遞歸定

5、義。2.2二叉樹的性質(zhì)及其證明，兩種特殊形式的二叉樹。2.3二叉樹的順序存儲和鏈?zhǔn)酱鎯Y(jié)構(gòu)。二叉樹的運算，要求達(dá)到“綜合應(yīng)用”層次。3.1二叉鏈表的生成。3.2二叉樹的遞歸遍歷算法和非遞歸遍歷算法。3.3二叉樹的應(yīng)用。線索二叉樹，要求達(dá)到“簡單應(yīng)用”層次。4.1二叉樹線索化的含義、線索二叉樹結(jié)點的表示方法。4.2對給定二叉樹進(jìn)行線索化的思想和實現(xiàn)。4.3二叉線索鏈表上的運算：查找某結(jié)點的后繼結(jié)點和線索二叉樹的遍歷。樹和森林，要求達(dá)到“領(lǐng)會”層次。5.1樹的三種存儲結(jié)構(gòu)表示方法。5.2樹、森林和二叉樹之間的相互轉(zhuǎn)換。5.3樹和森林的遍歷。哈夫曼樹及其應(yīng)用，要求達(dá)到“簡單應(yīng)用”層次。6.1最優(yōu)二叉

6、樹的概念，哈夫曼算法的思想。6.2哈夫曼算法的實現(xiàn)。6.3編碼、前綴編碼、哈夫曼編碼的概念；根據(jù)最優(yōu)二叉樹構(gòu)造對應(yīng)的哈夫曼編碼。第6章圖圖的概念，要求達(dá)到“識記”層次。1.1圖的定義和表示方法。1.2圖的常用術(shù)語及其含義。圖的存儲結(jié)構(gòu)，要求達(dá)到“領(lǐng)會”層次。2.1圖的鄰接矩陣表示法。2.2圖的鄰接表表示法。圖的遍歷算法，要求達(dá)到“簡單應(yīng)用”層次。3.1深度優(yōu)先搜索遍歷的算法思想，以鄰接矩陣和鄰接表分表作為圖的存儲結(jié)構(gòu)，其深度優(yōu) 先搜索遍歷的算法實現(xiàn)及其時間復(fù)雜度。3.2廣度優(yōu)先搜索遍歷的算法思想，以鄰接矩陣和鄰接表分別作為圖的存儲結(jié)構(gòu)，其廣度優(yōu) 先搜索遍歷的算法實現(xiàn)及其時間復(fù)雜度。3.3深度優(yōu)

7、先搜索遍歷算法中遞歸的應(yīng)用和廣度優(yōu)先搜索遍歷算法中隊列的應(yīng)用。圖的生成樹和最小生成樹，要求達(dá)到“領(lǐng)會”層次。4.1生成樹的概念。4.2對遍歷給定的圖，求其深度優(yōu)先和廣度優(yōu)先生成樹。4.3最小生成樹的概念及其性質(zhì)。4.4 Prim算法和Kruskal算法的基本思想及其實現(xiàn)。最短路徑，要求達(dá)到“領(lǐng)會”層次。5.1最短路徑問題的描述。Dijkstra算法的基本思想及其實現(xiàn)過程。拓?fù)渑判?，要求達(dá)到“簡單應(yīng)用”層次。6.1拓?fù)渑判虻膶嶋H意義。6.2對有向圖構(gòu)造其頂點的拓?fù)湫蛄?，判斷有向圖中是否有環(huán)。拓?fù)渑判虻幕舅枷爰捌渌惴▽崿F(xiàn)。第7章排序排序的基本概念，要求達(dá)到“識記”層次。1.1 排序的定義及意義。

8、1.2排序的分類。1.3穩(wěn)定的含義。1.4評價排序算法的標(biāo)準(zhǔn)。插入排序，要求達(dá)到“綜合應(yīng)用”層次。2.1直接插入排序算法的基本思想及算法實現(xiàn)。2.2直接插入排序算法中哨兵的作用。2.3直接插入排序算法在最好、最好及平均情況下的時間復(fù)雜度。2.4希爾排序算法的基本思想及算法實現(xiàn)。交換排序，要求達(dá)到“簡單應(yīng)用”層次。3.1冒泡排序的基本思想及算法實現(xiàn)；冒泡排序算法的時間性能分析及其穩(wěn)定性。3.2快速排序的基本思想及算法實現(xiàn)，一趟快速排序的具體操作。3.3快速排序的時間性能、空間性能及其穩(wěn)定性。選擇排序，要求達(dá)到“簡單應(yīng)用”層次。4.1直接選擇排序算法的算法實現(xiàn)及時間性能分析。4.3用篩選法構(gòu)造堆。

9、4.4堆排序的算法實現(xiàn)及性能分析。歸并排序的基本思想及其算法實現(xiàn)，要求達(dá)到“綜合應(yīng)用”層次。分配排序，要求達(dá)到“領(lǐng)會”層次。6.1分配排序的特點。6.2箱排序和基數(shù)排序的基本思想、算法實現(xiàn)和時間性能分析。各種內(nèi)部排序算法的分析比較，要求達(dá)到“簡單應(yīng)用”層次。7.1在分別考慮時間復(fù)雜度、穩(wěn)定性、空間復(fù)雜度的情況下，對各種內(nèi)部排序算法進(jìn)行比較。7.2選擇排序算法時需要考慮的因素及如何根據(jù)實際問題選擇合適的排序算法。第8章查找查找的基本概念，要求達(dá)到“識記”層次。1.1查找的重要意義，內(nèi)查找和外查找的含義。1.2平均查找長度的計算公式。順序表的查找，要求達(dá)到“簡單應(yīng)用”層次。2.1順序查找、二分查找和索引順序查找的基本思想及算法實現(xiàn)。2.2二分查找算法需要的條件，二叉判定樹的含義。2.3索引順序查找算法需要條件。2.4三種順序表查找算法的性能分析及比較。樹表的查找，要求達(dá)到“簡單應(yīng)用”層次。3.1二叉排序的性質(zhì)及定義，二叉