《數(shù)據(jù)結(jié)構(gòu)》考試大綱

PAGEPAGE1《數(shù)據(jù)結(jié)構(gòu)》考試大綱基本參考書：《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》嚴(yán)蔚敏吳偉民清華大學(xué)出版社一、考試的基本要求用計(jì)算機(jī)解決一個(gè)問(wèn)題，要將反映問(wèn)題的數(shù)據(jù)信息存入計(jì)算機(jī)，和設(shè)計(jì)能解決問(wèn)題的算法。數(shù)據(jù)結(jié)構(gòu)學(xué)科就是回答計(jì)算機(jī)如何存儲(chǔ)各種數(shù)據(jù)及數(shù)據(jù)之間的關(guān)系，以及對(duì)數(shù)據(jù)作基本處理的算法實(shí)現(xiàn)。要求考生比較系統(tǒng)地理解數(shù)據(jù)結(jié)構(gòu)的基本概念和基本理論，掌握常用數(shù)據(jù)結(jié)構(gòu)及其基本算法，具有綜合運(yùn)用數(shù)據(jù)結(jié)構(gòu)知識(shí)解決問(wèn)題的能力。二、考試方法和考試時(shí)間考試采用閉卷、筆試形式，考試時(shí)間為180分鐘。三、對(duì)編程語(yǔ)言的要求試題中所有的算法，要求用C或C++語(yǔ)言描述。四、考試內(nèi)容和考試要求基本概念考試內(nèi)容數(shù)據(jù)結(jié)構(gòu)的基本概念；漸近算法分析方法?？荚囈髷?shù)據(jù)結(jié)構(gòu)包含數(shù)據(jù)元素集合和數(shù)據(jù)元素之間關(guān)系的集合。理解算法與數(shù)據(jù)結(jié)構(gòu)之間的關(guān)系。掌握漸近算法分析方法：估算算法時(shí)間復(fù)雜性的大O表示法。線性表和字符串考試內(nèi)容線性表的特點(diǎn)，線性表的順序?qū)崿F(xiàn)和鏈?zhǔn)綄?shí)現(xiàn)，線性表的應(yīng)用；字符串的基本運(yùn)算，字符串匹配算法?？荚囈罄斫饩€性表的結(jié)構(gòu)和特點(diǎn)，掌握線性表上基本操作的實(shí)現(xiàn)算法。掌握順序存儲(chǔ)線性表的存儲(chǔ)方式，掌握基本操作的實(shí)現(xiàn)算法。掌握鏈接存儲(chǔ)線性表的存儲(chǔ)方式。掌握單鏈表和循環(huán)鏈表的結(jié)構(gòu)，基本操作的實(shí)現(xiàn)算法。理解字符串的存儲(chǔ)結(jié)構(gòu)，字符串的基本運(yùn)算。掌握字符串簡(jiǎn)單匹配算法；理解字符串KMP匹配算法，掌握KMP算法的匹配過(guò)程，以及求模各字符失敗鏈接值的方法。棧和隊(duì)列考試內(nèi)容棧和隊(duì)列的基本運(yùn)算及其應(yīng)用。考試要求理解棧的定義和結(jié)構(gòu)特點(diǎn)，掌握其存儲(chǔ)方式(順序存儲(chǔ)與鏈接存儲(chǔ))和基本操作的實(shí)現(xiàn)算法。理解隊(duì)列的結(jié)構(gòu)和特點(diǎn)，掌握其存儲(chǔ)方式(順序存儲(chǔ)與鏈接存儲(chǔ))和基本操作的實(shí)現(xiàn)算法。遞歸考試內(nèi)容遞歸的基本概念，遞歸的簡(jiǎn)單應(yīng)用?？荚囈罄斫膺f歸的基本概念和實(shí)現(xiàn)原理，掌握用遞歸的思想描述問(wèn)題和構(gòu)造算法的方法。掌握求整數(shù)的階乘、漢諾塔等問(wèn)題的遞歸解法。掌握用棧改遞歸求解為非遞歸求解的方法。樹和二叉樹考試內(nèi)容樹和二叉樹?？荚囈罄斫鈽涞慕Y(jié)構(gòu)和定義，掌握樹的主要概念。理解各種二叉樹的結(jié)構(gòu)，掌握其特點(diǎn)，具有運(yùn)用二叉樹解決實(shí)際問(wèn)題的能力。掌握二叉樹的三種遍歷方法的實(shí)現(xiàn)原理和性質(zhì)，能將二叉樹的遍歷方法應(yīng)用于求解二叉樹的葉子結(jié)點(diǎn)個(gè)數(shù)、二叉樹計(jì)數(shù)等問(wèn)題，掌握遍歷的非遞歸實(shí)現(xiàn)方法。理解樹的存儲(chǔ)結(jié)構(gòu)，掌握樹的遍歷等方法的實(shí)現(xiàn)。理解霍夫曼編碼的基本原理，掌握基于霍夫曼樹生成霍夫曼編碼的方法。集合和搜索考試內(nèi)容集合、二叉搜索樹和AVL樹。考試要求1)理解集合的基本概念，掌握常用實(shí)現(xiàn)集合的各種存儲(chǔ)方法。掌握無(wú)序線性表的順序搜索、有序線性表的二分搜索。理解二叉搜索樹的定義和特點(diǎn)，掌握二叉搜索樹插入和刪除的算法。理解AVL樹的定義和特點(diǎn)，掌握AVL樹上插入新結(jié)點(diǎn)的方法。圖考試內(nèi)容圖的存儲(chǔ)，圖的遍歷，最小生成樹，最短路徑和活動(dòng)網(wǎng)絡(luò)。考試要求掌握?qǐng)D的基本概念，圖的鄰接矩陣存儲(chǔ)方式和鄰接表存儲(chǔ)方式。掌握?qǐng)D的深度優(yōu)先遍歷和廣度優(yōu)先搜索遍歷方法。掌握Kluskal和Prim生成最小生成樹的方法。掌握Dijkstra求單源最短路徑的方法。掌握AOV活動(dòng)網(wǎng)絡(luò)的拓?fù)渑判蛩惴?，AOE活動(dòng)網(wǎng)絡(luò)的關(guān)鍵路徑的方法。排序考試內(nèi)容插入排序，交換排序，選擇排序，歸并排序和基數(shù)排序?？荚囈罄斫飧鞣N排序方法的實(shí)現(xiàn)，掌握各種排序算法的特點(diǎn)和時(shí)間復(fù)雜性，能按指定的排序方法實(shí)現(xiàn)對(duì)數(shù)表作排序。索引結(jié)構(gòu)與散列考試內(nèi)容線性索引結(jié)構(gòu)、B－樹和B+樹索引結(jié)構(gòu)，散列?？荚囈罄斫饩€性