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

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

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

3、隊(duì)列棧的邏輯結(jié)構(gòu)、存儲(chǔ)結(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順序棧的上溢和下溢問題，如何防止溢出。隊(duì)列的邏輯結(jié)構(gòu)、存儲(chǔ)結(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ì)列上的基本算法。棧和隊(duì)列的應(yīng)用，要求達(dá)到“綜合應(yīng)用”層次。3.1圓括號(hào)匹配的檢驗(yàn)問題。3.2字符串回文的判斷問題。3.3數(shù)制轉(zhuǎn)換。3.4利用棧實(shí)現(xiàn)程序的遞歸。3.5表達(dá)式求值。第4章多

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

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

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

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

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

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