長春理工大學

長春理工大學研究生入學考試《數據結構》考試大綱

一、考試科目：數據結構

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

三、參考書目：

1.《數據結構》(C語言版)嚴蔚敏 吳偉民 編著，清華大學出版社， 2011.11。

2.考試難度和形式可以參考計算機科學技術學院的《數據結構》課程考試：

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

四、考試內容：

(一)主要考查目標

1. 理解數據結構的基本概念，掌握數據的邏輯結構、存儲結構及其差異，以及基本操作及實現。

2. 掌握基本的數據處理原理和方法，能夠對算法進行設計和分析。

3. 能夠選擇合適的數據結構和方法進行問題求解。

(二) 知識點

1、線性表

1) 線性鏈表的順序存儲結構;線性鏈表的鏈式存儲結構;線性表的插入與刪除

2) 線性表的應用

2、棧和隊列

1) 棧的基本概念;棧的順序存儲結構;棧的鏈式存儲結構;棧的基本操作及應用

2) 隊列的基本概念;隊列的順序存儲結構;隊列的鏈式存儲結構;隊列的基本操作及應用

3、串

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

2)字符串的模式匹配

4、數組與廣義表

1) 特殊矩陣的壓縮存儲

2) 廣義表的概念和表示;廣義表存儲結構

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

5、樹與二叉樹

1) 樹的概念

2) 二叉樹的定義;二叉樹的性質;二叉樹的順序存儲結構和鏈式存儲結構

3) 二叉樹遍歷

4) 線索化二叉樹的構造

5) 樹的存儲結構;森林與二叉樹的轉換;樹與森林的遍歷

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

6、圖

1) 圖的基本概念

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

3) 圖的深度優先搜索;廣度優先搜索

4) 最小生成樹

5) 拓撲排序

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

7、查找

1)查找的基本概念

2)順序查找法

3)折半查找法

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

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

8、內部排序

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

2) 起泡排序

3)簡單選擇排序

4)希爾排序

5)快速排序

6) 堆排序

7) 歸并排序

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