吉林“專升本”數據結構課程考試大綱(試行)

一、考試內容

數據結構知識點難易程度及所占比例

1.數據結構基本概念及簡單的算法分析

(1)數據結構部分：

a.掌握數據結構基本概念;

b.了解抽象數據類型;

c.理解邏輯結構與存儲結構。

(2)算法部分：

a.了解算法的定義及算法的特性;

b.掌握算法的性能分析與度量方法。

2.線性表

(1)掌握線性表的定義及實現(xiàn)。

(2)掌握單鏈表和循環(huán)鏈表的定義及實現(xiàn)。- 81 -

(3)理解雙向鏈表的定義。

(4)掌握順序表的定義。

(5)掌握順序表的查找、插入和刪除算法的實現(xiàn)。

3.棧和隊列

(1)理解棧的邏輯結構與應用。

(2)掌握順序棧的表示和操作的實現(xiàn)。

(3)理解隊列的邏輯結構與應用。

(4)掌握鏈隊列的表示和操作的實現(xiàn)。

4.串和數組

(1)理解串的應用。

(2)掌握串的表示和實現(xiàn)。

(3)掌握數組的定義。

(4)掌握數組的順序表示和實現(xiàn)。

5.樹和二叉樹

(1)樹部分：

a.掌握樹的定義和基本概念;

b.掌握樹的遍歷;

c.理解樹的存儲結構。

(2)二叉樹部分：

a.掌握二叉樹的定義和基本形態(tài);- 82 -

b.掌握斜樹、滿二叉樹、完全二叉樹的特征;

c.掌握二叉樹的基本性質;

d.掌握二叉樹的遍歷及構造;

e.了解二叉樹的存儲結構及實現(xiàn)。

(3)了解樹、森林和二叉樹的轉換。

(4)掌握哈夫曼樹及哈夫曼編碼的構造。

6.圖

(1)掌握圖的定義、基本術語。

(2)掌握圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷。

(3)圖的應用：

a.了解最小生成樹;

b.了解拓撲排序;

c.理解單源點最短路徑;

d.理解關鍵路徑。

7.查找

(1)掌握查找的基本概念。

(2)掌握線性表的順序查找、折半查找的實現(xiàn)。

(3)理解二叉排序樹的基本概念及其查找算法。

(4)了解哈希查找的基本概念及哈希函數的構造方法，了解哈希查找算法。

8.排序

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

(2)掌握基本排序方法：冒泡排序、直接插入排序。

(3)了解快速排序、歸并排序、堆排序。

二、試卷結構

考試題型為單項選擇題、判斷題、填空題，基礎應用題、算法實現(xiàn)題，滿分100分。