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

1、勻考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ì)算機(jī)科學(xué)中的 作用和意義；Wirth關(guān)于程序的定義公式。1.2數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)項(xiàng)、數(shù)據(jù) 結(jié)構(gòu)等概念的定義。1.3數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及數(shù)據(jù)運(yùn)算的含 義及其相互關(guān)系。1.4數(shù)據(jù)結(jié)構(gòu)的兩大類邏輯結(jié)構(gòu)和四種常用的存儲表示方法。2. 算法的描述和分析，要求達(dá)到“領(lǐng)會”層次。2.1算法、算法的時(shí)間復(fù)雜度和空間復(fù)雜度等概 念。2.2 一個(gè)完整算法需要滿足的五個(gè)準(zhǔn)則；算法與 程序的關(guān)系。2.3算法的分析方法；對于一般算法能分析其時(shí) 間復(fù)雜度。第2章線性表1.

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

3、問題， 要 求達(dá)到“綜合應(yīng)用”層次。5. 順序表和鏈表的比較，要求達(dá)到“領(lǐng)會”層次。 第3章棧和隊(duì)列1. 棧的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及相關(guān)算法，要求達(dá) 到“簡單應(yīng)用”層次。1.1棧的邏輯定義、特點(diǎn)及運(yùn)算。1.2順序棧和鏈棧上實(shí)現(xiàn)進(jìn)棧、退棧等基本運(yùn)1.3順序棧的上溢和下溢問題，如何防止溢出。2. 隊(duì)列的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及相關(guān)算法，要求 達(dá)到“簡單應(yīng)用”層次。2.1隊(duì)列的邏輯定義、特點(diǎn)及運(yùn)算。2.2順序循環(huán)隊(duì)列的表述；隊(duì)空和隊(duì)滿的判定； 順序循環(huán)隊(duì)列上入隊(duì)、出隊(duì)等基本算法。2.3鏈隊(duì)列的表述；帶頭結(jié)點(diǎn)和不帶頭結(jié)點(diǎn)兩種 情況下鏈隊(duì)列上的基本算法。3. 棧和隊(duì)列的應(yīng)用，要求達(dá)到“綜合應(yīng)用”層次。3.1圓

4、括號匹配的檢驗(yàn)問題。3.2字符串回文的判斷問題。3.3數(shù)制轉(zhuǎn)換。3.4利用棧實(shí)現(xiàn)程序的遞歸。3.5表達(dá)式求值。第4章多維數(shù)組和廣義表1. 多維數(shù)組及其運(yùn)算，要求達(dá)到“領(lǐng)會”層次。1.1多維數(shù)組的邏輯結(jié)構(gòu)表達(dá)及特征。1.2多維數(shù)組的順序存儲結(jié)構(gòu)及地址計(jì)算方法。1.3多維數(shù)組的常用運(yùn)算。2. 矩陣的壓縮存儲，要求達(dá)到“簡單應(yīng)用”層次。2.1特殊矩陣的類型和性質(zhì)；稀疏矩陣的概念。2.2用一維數(shù)組壓縮存儲特殊矩陣時(shí)，存儲地址 的計(jì)算。2.3稀疏矩陣的三元組表表示方法及常用算法。3. 廣義表，要求達(dá)到“領(lǐng)會”層次。3.1廣義表的定義及特性。3.2求廣義表的深度、表長、表頭和表尾運(yùn)算。 第5章樹和二叉樹1

5、. 樹的概念，要求達(dá)到“識記”層次。1.1樹的定義和表示方法。1.2樹的常用術(shù)語及其含義。2. 二叉樹的概念，要求達(dá)到“領(lǐng)會”層次。2.1二叉樹的遞歸定義。2.2二叉樹的性質(zhì)及其證明，兩種特殊形式的二 叉樹。2.3二叉樹的順序存儲和鏈?zhǔn)酱鎯Y(jié)構(gòu)。3. 二叉樹的運(yùn)算，要求達(dá)到“綜合應(yīng)用”層次。3.1二叉鏈表的生成。3.2二叉樹的遞歸遍歷算法和非遞歸遍歷算法。3.3二叉樹的應(yīng)用。4. 線索二叉樹，要求達(dá)到“簡單應(yīng)用”層次。4.1二叉樹線索化的含義、線索二叉樹結(jié)點(diǎn)的表 示方法。4.2對給定二叉樹進(jìn)行線索化的思想和實(shí)現(xiàn)。4.3二叉線索鏈表上的運(yùn)算：查找某結(jié)點(diǎn)的后繼 結(jié)點(diǎn)和線索二叉樹的遍歷。5. 樹和森

6、林，要求達(dá)到“領(lǐng)會”層次。5.1樹的三種存儲結(jié)構(gòu)表示方法。5.2樹、森林和二叉樹之間的相互轉(zhuǎn)換。5.3樹和森林的遍歷。6. 哈夫曼樹及其應(yīng)用，要求達(dá)到“簡單應(yīng)用”層 次。6.1最優(yōu)二叉樹的概念，哈夫曼算法的思想。6.2哈夫曼算法的實(shí)現(xiàn)。6.3編碼、前綴編碼、哈夫曼編碼的概念；根據(jù) 最優(yōu)二叉樹構(gòu)造對應(yīng)的哈夫曼編碼。第6章圖1. 圖的概念，要求達(dá)到“識記”層次。1.1圖的定義和表示方法。1.2圖的常用術(shù)語及其含義。2. 圖的存儲結(jié)構(gòu)，要求達(dá)到“領(lǐng)會”層次。2.1圖的鄰接矩陣表示法。2.2圖的鄰接表表示法。3. 圖的遍歷算法，要求達(dá)到“簡單應(yīng)用”層次。3.1深度優(yōu)先搜索遍歷的算法思想，以鄰接矩陣 和

7、鄰接表分表作為圖的存儲結(jié)構(gòu)，其深度優(yōu)先搜 索遍歷的算法實(shí)現(xiàn)及其時(shí)間復(fù)雜度。3.2廣度優(yōu)先搜索遍歷的算法思想，以鄰接矩陣 和鄰接表分別作為圖的存儲結(jié)構(gòu)，其廣度優(yōu)先搜 索遍歷的算法實(shí)現(xiàn)及其時(shí)間復(fù)雜度。3.3深度優(yōu)先搜索遍歷算法中遞歸的應(yīng)用和廣 度優(yōu)先搜索遍歷算法中隊(duì)列的應(yīng)用。3.4兩種遍歷算法的簡單應(yīng)用。4. 圖的生成樹和最小生成樹，要求達(dá)到"領(lǐng)會" 層次。4.1生成樹的概念。4.2對遍歷給定的圖，求其深度優(yōu)先和廣度優(yōu)先 生成樹。4.3最小生成樹的概念及其性質(zhì)。4.4 Prim算法和Kruskal算法的基本思想及其實(shí)現(xiàn)。5. 最短路徑，要求達(dá)到“領(lǐng)會”層次。5.1最短路徑問題的

8、描述。5.2 Dijkstra算法的基本思想及其實(shí)現(xiàn)過程。6. 拓?fù)渑判?，要求達(dá)到“簡單應(yīng)用”層次。6.1拓?fù)渑判虻膶?shí)際意義。6.2對有向圖構(gòu)造其頂點(diǎn)的拓?fù)湫蛄校袛嘤邢?圖中是否有環(huán)。6.3拓?fù)渑判虻幕舅枷爰捌渌惴▽?shí)現(xiàn)。 第7章排序1. 排序的基本概念，要求達(dá)到“識記”層次。1.1排序的定義及意義。1.2排序的分類。1.3穩(wěn)定的含義。1.4評價(jià)排序算法的標(biāo)準(zhǔn)。2. 插入排序，要求達(dá)到“綜合應(yīng)用”層次。2.1直接插入排序算法的基本思想及算法實(shí)現(xiàn)。2.2直接插入排序算法中哨兵的作用。2.3直接插入排序算法在最好、最好及平均情況 下的時(shí)間復(fù)雜度。2.4希爾排序算法的基本思想及算法實(shí)現(xiàn)。3. 交換

9、排序，要求達(dá)到“簡單應(yīng)用”層次。3.1冒泡排序的基本思想及算法實(shí)現(xiàn)；冒泡排序 算法的時(shí)間性能分析及其穩(wěn)定性。3.2快速排序的基本思想及算法實(shí)現(xiàn)，一趟快速 排序的具體操作。3.3快速排序的時(shí)間性能、空間性能及其穩(wěn)定 性。4. 選擇排序，要求達(dá)到“簡單應(yīng)用”層次4.1直接選擇排序算法的算法實(shí)現(xiàn)及時(shí)間性能 分析。4.2堆排序的原理及相關(guān)概念。4.3用篩選法構(gòu)造堆。4.4堆排序的算法實(shí)現(xiàn)及性能分析。5. 歸并排序的基本思想及其算法實(shí)現(xiàn)，要求達(dá)到 “綜合應(yīng)用”層次。6. 分配排序，要求達(dá)到“領(lǐng)會”層次。6.1分配排序的特點(diǎn)。6.2箱排序和基數(shù)排序的基本思想、算法實(shí)現(xiàn)和 時(shí)間性能分析。7. 各種內(nèi)部排序算

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