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

815數(shù)據(jù)結(jié)構(gòu)考試大綱【指定參考書(shū)】嚴(yán)蔚敏.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）.清華大學(xué)出版社.2007.9【考核目標(biāo)】知識(shí)；圖等的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和對(duì)數(shù)據(jù)的基本運(yùn)算；熟悉并掌握抽象數(shù)據(jù)類型的表示、實(shí)現(xiàn)和在程序設(shè)計(jì)中的作用；理解算法的基本概念、特性、設(shè)計(jì)要求以與性能分析；想和算法實(shí)現(xiàn)；結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)，并設(shè)計(jì)相應(yīng)的應(yīng)用算法?！究己藘?nèi)容】一、緒論1數(shù)據(jù)結(jié)構(gòu)；抽象數(shù)據(jù)類型；算法；算法的時(shí)間復(fù)雜度；算法的空間復(fù)雜度?？己艘?2(3)掌握算法的基本概念和算法的性能分析方法。必須重點(diǎn)掌握抽象數(shù)據(jù)類型的表示；算法的時(shí)間復(fù)雜性能分析的方法。二、線性表1．考核知識(shí)點(diǎn)線性表；順序表；鏈表；順序存儲(chǔ)結(jié)構(gòu)；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。2．考核要求理解線性表的定義和邏輯結(jié)構(gòu)特性；(3(4)了解用線性表表示一元多項(xiàng)式和稀疏多項(xiàng)式的方法，并理解稀疏多項(xiàng)式的基本操作實(shí)現(xiàn)。必須重點(diǎn)掌握線性表的順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和順序表和各種鏈表的算法實(shí)現(xiàn)。三、棧和隊(duì)列1．考核知識(shí)點(diǎn)棧；遞歸；鏈隊(duì)列；循環(huán)隊(duì)列。2．考核要求(1)熟練掌握棧的類型定義、表示和基本操作的實(shí)現(xiàn)；(2)靈活運(yùn)用棧的特性設(shè)計(jì)算法；掌握遞歸算法的設(shè)計(jì)方法和設(shè)計(jì)思路；熟練掌握隊(duì)列的類型定義、表示和基本操作的實(shí)現(xiàn)必須重點(diǎn)掌握棧和隊(duì)列的特性、基本算法的實(shí)現(xiàn)以與應(yīng)用。四、串1串，模式匹配算法。2．考核要求(1)掌握串類型的定義與其表示方法；(2)掌握串基本算法的實(shí)現(xiàn)方法；(3)了解串的應(yīng)用算法。五、數(shù)組和廣義表考核知識(shí)點(diǎn)數(shù)組；稀疏矩陣；壓縮存儲(chǔ)；廣義表。2．考核要求(2)數(shù)組元素順序存儲(chǔ)的地址計(jì)算；(3(4)了解廣義表的定義和存儲(chǔ)結(jié)構(gòu)。必須重點(diǎn)掌握數(shù)組元素的地址計(jì)算方法；特殊矩陣的壓縮存儲(chǔ)；稀疏矩陣的壓縮存儲(chǔ)。六、樹(shù)和二叉樹(shù)1．考核知識(shí)點(diǎn)二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)與其遍歷的方法；二叉樹(shù)的線索化；哈夫曼樹(shù)的構(gòu)造方法與其編碼的生成?？己艘?2)理解二叉樹(shù)的基本性質(zhì)；理解二叉樹(shù)存儲(chǔ)結(jié)構(gòu)；(5)掌握線索二叉樹(shù)的基本概念和相應(yīng)算法；(6)了解樹(shù)和森林的存儲(chǔ)方法與與二叉樹(shù)的之間的轉(zhuǎn)換方法；(7)掌握哈夫曼樹(shù)與其應(yīng)用。必須重點(diǎn)掌握二叉樹(shù)的特性；二叉樹(shù)的遍歷；二叉樹(shù)的線索化；哈夫曼樹(shù)與哈夫曼編碼算法實(shí)現(xiàn)。七、圖1圖的邏輯結(jié)構(gòu)；鄰接表；深度優(yōu)先遍歷；廣度優(yōu)先遍歷；最小生成樹(shù)、拓?fù)渑判颉㈥P(guān)鍵路徑、最短路徑?？己艘?2)理解并掌握?qǐng)D的存儲(chǔ)結(jié)構(gòu)；掌握?qǐng)D的深度優(yōu)先和廣度優(yōu)先遍歷算法；鍵路徑、最短路徑等。必須重點(diǎn)掌握?qǐng)D的邏輯結(jié)構(gòu)；圖的存儲(chǔ)方法；圖的深度優(yōu)先、廣度優(yōu)先遍歷算法；圖的應(yīng)用。八、查找1順序查找；折半查找；分塊查找；二叉排序樹(shù)；平衡二叉樹(shù)；哈希表。考核要求理解靜態(tài)查找表、動(dòng)態(tài)查找表和哈希查找的基本概念；塊查找；B突的基本方法；掌握各種查找算法的效率分析。找算法的實(shí)現(xiàn)。九、排序1直接插入排序；希爾排序；冒泡排序；快速排序；堆排序；歸并排序；基數(shù)排序?？己艘罄斫馀判虻幕靖拍睿?3)掌握基于交換思想的排序算法如：冒泡排序、快速排序；(4)掌握基于選擇思想的排序算法如：簡(jiǎn)單選擇排序、堆排序；(5)掌握其它排序算法如：歸并排序、基數(shù)