長春理工大學研究生入學考試《數(shù)據(jù)結(jié)構(gòu)》考試大綱

一、考試科目：數(shù)據(jù)結(jié)構(gòu)

二、適用專業(yè)：計算機科學技術學院所有專業(yè)

三、參考書目：

1.《數(shù)據(jù)結(jié)構(gòu)》(C語言版)嚴蔚敏 吳偉民 編著，清華大學出版社， 2011.11。

2.考試難度和形式可以參考計算機科學技術學院的《數(shù)據(jù)結(jié)構(gòu)》課程考試：

(http://cs.cust.edu.cn/ArticleShow.asp?ArticleID=2880)。

四、考試內(nèi)容：

(一)主要考查目標

1. 理解數(shù)據(jù)結(jié)構(gòu)的基本概念，掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其差異，以及基本操作及實現(xiàn)。

2. 掌握基本的數(shù)據(jù)處理原理和方法，能夠?qū)λ惴ㄟM行設計和分析。

3. 能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進行問題求解。

(二) 知識點

1、線性表

1) 線性鏈表的順序存儲結(jié)構(gòu);線性鏈表的鏈式存儲結(jié)構(gòu);線性表的插入與刪除

2) 線性表的應用

2、棧和隊列

1) 棧的基本概念;棧的順序存儲結(jié)構(gòu);棧的鏈式存儲結(jié)構(gòu);棧的基本操作及應用

2) 隊列的基本概念;隊列的順序存儲結(jié)構(gòu);隊列的鏈式存儲結(jié)構(gòu);隊列的基本操作及應用

3、串

1) 字符串的基本操作及應用

2)字符串的模式匹配

4、數(shù)組與廣義表

1) 特殊矩陣的壓縮存儲

2) 廣義表的概念和表示;廣義表存儲結(jié)構(gòu)

3)數(shù)組及廣義表的基本操作和應用

5、樹與二叉樹

1) 樹的概念

2) 二叉樹的定義;二叉樹的性質(zhì);二叉樹的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)

3) 二叉樹遍歷

4) 線索化二叉樹的構(gòu)造

5) 樹的存儲結(jié)構(gòu);森林與二叉樹的轉(zhuǎn)換;樹與森林的遍歷

6) 哈夫曼(Huffman)樹和哈夫曼編碼;樹的基本應用

6、圖

1) 圖的基本概念

2) 圖的鄰接矩陣;鄰接表

3) 圖的深度優(yōu)先搜索;廣度優(yōu)先搜索

4) 最小生成樹

5) 拓撲排序

6)最短路徑;關鍵路徑;圖的基本應用

7、查找

1)查找的基本概念

2)順序查找法

3)折半查找法

4)散列(Hash)表及其查找;散列表與散列方法

5)各種查找方法的比較和應用

8、內(nèi)部排序

1) 直接插入排序;折半插入排序

2) 起泡排序

3)簡單選擇排序

4)希爾排序

5)快速排序

6) 堆排序

7) 歸并排序

8)各種排序方法比較及應用