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

【指定參考書】

嚴(yán)蔚敏. 數(shù)據(jù)結(jié)構(gòu)(C語言版). 第二版, 人民郵電出版社

【考核目標(biāo)】

1.理解數(shù)據(jù)結(jié)構(gòu)的基本概念，比較系統(tǒng)地掌握數(shù)據(jù)結(jié)構(gòu)的理論基礎(chǔ)知識;

2.熟悉并掌握線性表、棧、隊(duì)列、串、數(shù)組、廣義表、樹和二叉樹、圖等的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和對數(shù)據(jù)的基本運(yùn)算;

3.熟悉并掌握抽象數(shù)據(jù)類型的表示、實(shí)現(xiàn)和在程序設(shè)計(jì)中的作用;

4.理解算法的基本概念、特性、設(shè)計(jì)要求以及性能分析;

5.理解查找和排序的基本概念，掌握各種查找和排序操作的基本思想和算法實(shí)現(xiàn);

6.學(xué)會根據(jù)計(jì)算機(jī)所處理數(shù)據(jù)對象的特性，確定與之相適應(yīng)的數(shù)據(jù)結(jié)構(gòu)和存儲結(jié)構(gòu)，并設(shè)計(jì)相應(yīng)的應(yīng)用算法。

【考核內(nèi)容】

一、緒論

1.考核知識點(diǎn)

數(shù)據(jù)結(jié)構(gòu);抽象數(shù)據(jù)類型;算法;算法的時間復(fù)雜度;算法的空間復(fù)雜度。

2.考核要求

(1)理解數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語;

(2)掌握抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn);

(3)掌握算法的基本概念和算法的性能分析方法。

必須重點(diǎn)掌握抽象數(shù)據(jù)類型的表示;算法的時間復(fù)雜性能分析的方法。

二、線性表

1.考核知識點(diǎn)

線性表;順序表;鏈表;順序存儲結(jié)構(gòu);鏈?zhǔn)酱鎯Y(jié)構(gòu)。

2.考核要求

(1)理解線性表的定義和邏輯結(jié)構(gòu)特性;

(2)掌握線性表的順序存儲方法和基本操作算法實(shí)現(xiàn);

(3)掌握線性表的鏈?zhǔn)酱鎯Ψ椒ê突静僮魉惴▽?shí)現(xiàn);

(4)了解用線性表表示一元多項(xiàng)式和稀疏多項(xiàng)式的方法，并理解稀疏多項(xiàng)式的基本操作實(shí)現(xiàn)。

必須重點(diǎn)掌握線性表的順序存儲結(jié)構(gòu)、鏈?zhǔn)酱鎯Y(jié)構(gòu)和順序表和各種鏈表的算法實(shí)現(xiàn)。

三、棧和隊(duì)列

1.考核知識點(diǎn)

棧;遞歸;鏈隊(duì)列;循環(huán)隊(duì)列。

2.考核要求

(1)熟練掌握棧的類型定義、表示和基本操作的實(shí)現(xiàn);

(2)靈活運(yùn)用棧的特性設(shè)計(jì)算法;

(3)掌握遞歸算法的設(shè)計(jì)方法和設(shè)計(jì)思路;

(4)熟練掌握隊(duì)列的類型定義、表示和基本操作的實(shí)現(xiàn)

必須重點(diǎn)掌握棧和隊(duì)列的特性、基本算法的實(shí)現(xiàn)以及應(yīng)用。

四、串

1.考核知識點(diǎn)

串，模式匹配算法。

2.考核要求

(1)掌握串類型的定義及其表示方法;

(2)掌握串基本算法的實(shí)現(xiàn)方法;

(3)了解串的應(yīng)用算法。

必須重點(diǎn)掌握串的表示方法、串的基本算法的實(shí)現(xiàn)。

五、數(shù)組和廣義表

1.考核知識點(diǎn)

數(shù)組;稀疏矩陣;壓縮存儲;廣義表。

2.考核要求

(1)了解數(shù)組的定義和數(shù)組的順序表示方法;

(2)數(shù)組元素順序存儲的地址計(jì)算;

(3)掌握特殊矩陣和稀疏矩陣的壓縮存儲方法;

(4)了解廣義表的定義和存儲結(jié)構(gòu)。

必須重點(diǎn)掌握數(shù)組元素的地址計(jì)算方法;特殊矩陣的壓縮存儲;稀疏矩陣的壓縮存儲。

六、樹和二叉樹

1.考核知識點(diǎn)

二叉樹的存儲結(jié)構(gòu)及其遍歷的方法;二叉樹的線索化;哈夫曼樹的構(gòu)造方法及其編碼的生成。

2.考核要求

(1)理解樹和二叉樹的定義、術(shù)語和基本邏輯結(jié)構(gòu)特性;

(2)理解二叉樹的基本性質(zhì);

(3)理解二叉樹存儲結(jié)構(gòu);

(4)理解二叉樹的遍歷算法思想，掌握遞歸和非遞歸遍歷算法實(shí)現(xiàn);

(5)掌握線索二叉樹的基本概念和相應(yīng)算法;

(6)了解樹和森林的存儲方法及與二叉樹的之間的轉(zhuǎn)換方法;

(7)掌握哈夫曼樹及其應(yīng)用。

必須重點(diǎn)掌握二叉樹的特性;二叉樹的遍歷;二叉樹的線索化;哈夫曼樹及哈夫曼編碼算法實(shí)現(xiàn)。

七、圖

1.考核知識點(diǎn)

圖的邏輯結(jié)構(gòu);鄰接表;深度優(yōu)先遍歷;廣度優(yōu)先遍歷;最小生成樹、拓?fù)渑判?、關(guān)鍵路徑、最短路徑。

2.考核要求

(1)理解并掌握圖的基本概念、術(shù)語和基本邏輯結(jié)構(gòu)特征;

(2)理解并掌握圖的存儲結(jié)構(gòu);

(3)掌握圖的深度優(yōu)先和廣度優(yōu)先遍歷算法;

(4)了解并掌握圖結(jié)構(gòu)的典型應(yīng)用，如最小生成樹、拓?fù)渑判?、關(guān)鍵路徑、最短路徑等。

必須重點(diǎn)掌握圖的邏輯結(jié)構(gòu);圖的存儲方法;圖的深度優(yōu)先、廣度優(yōu)先遍歷算法;圖的應(yīng)用。

八、查找

1.考核知識點(diǎn)

順序查找;折半查找;分塊查找;二叉排序樹;平衡二叉樹;哈希表。

2.考核要求

(1)理解靜態(tài)查找表、動態(tài)查找表和哈希查找的基本概念;

(2)掌握靜態(tài)查找表的各種查找方法如：順序查找、折半查找、分塊查找;

(3)掌握動態(tài)查找表的各種查找方法如二叉排序樹與平衡二叉樹，B樹等;

(4)掌握哈希表的概念和查找方法和哈希函數(shù)的構(gòu)造方法、解決沖突的基本方法;

(5)掌握各種查找算法的效率分析。

必須重點(diǎn)掌握折半查找、二叉排序樹、平衡二叉樹和哈希表的查找算法的實(shí)現(xiàn)。

九、排序

1.考核知識點(diǎn)

直接插入排序;希爾排序;冒泡排序;快速排序;堆排序;歸并排序;基數(shù)排序。

2.考核要求

(1)理解排序的基本概念;

(2)掌握基于插入思想的排序算法如：直接插入排序、希爾排序;

(3)掌握基于交換思想的排序算法如：冒泡排序、快速排序;

(4)掌握基于選擇思想的排序算法如：簡單選擇排序、堆排序;

(5)掌握其它排序算法如：歸并排序、基數(shù)排序;

(6)能夠?qū)Ω鞣N排序算法進(jìn)行分析比較。

必須重點(diǎn)掌握插入排序、快速排序、堆排序、合并排序、基數(shù)排序等算法的設(shè)計(jì)思想。

【考核方式】 筆試