吉林“專升本”數(shù)據(jù)結(jié)構(gòu)課程考試大綱(試行)

一、考試內(nèi)容

數(shù)據(jù)結(jié)構(gòu)知識(shí)點(diǎn)難易程度及所占比例

1.數(shù)據(jù)結(jié)構(gòu)基本概念及簡(jiǎn)單的算法分析

(1)數(shù)據(jù)結(jié)構(gòu)部分：

a.掌握數(shù)據(jù)結(jié)構(gòu)基本概念;

b.了解抽象數(shù)據(jù)類型;

c.理解邏輯結(jié)構(gòu)與存儲(chǔ)結(jié)構(gòu)。

(2)算法部分：

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

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

2.線性表

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

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

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

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

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

3.棧和隊(duì)列

(1)理解棧的邏輯結(jié)構(gòu)與應(yīng)用。

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

(3)理解隊(duì)列的邏輯結(jié)構(gòu)與應(yīng)用。

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

4.串和數(shù)組

(1)理解串的應(yīng)用。

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

(3)掌握數(shù)組的定義。

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

5.樹(shù)和二叉樹(shù)

(1)樹(shù)部分：

a.掌握樹(shù)的定義和基本概念;

b.掌握樹(shù)的遍歷;

c.理解樹(shù)的存儲(chǔ)結(jié)構(gòu)。

(2)二叉樹(shù)部分：

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

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

c.掌握二叉樹(shù)的基本性質(zhì);

d.掌握二叉樹(shù)的遍歷及構(gòu)造;

e.了解二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及實(shí)現(xiàn)。

(3)了解樹(shù)、森林和二叉樹(shù)的轉(zhuǎn)換。

(4)掌握哈夫曼樹(shù)及哈夫曼編碼的構(gòu)造。

6.圖

(1)掌握?qǐng)D的定義、基本術(shù)語(yǔ)。

(2)掌握?qǐng)D的深度優(yōu)先遍歷和廣度優(yōu)先遍歷。

(3)圖的應(yīng)用：

a.了解最小生成樹(shù);

b.了解拓?fù)渑判?

c.理解單源點(diǎn)最短路徑;

d.理解關(guān)鍵路徑。

7.查找

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

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

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

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

8.排序

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

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

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

二、試卷結(jié)構(gòu)

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