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

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

一、考試內(nèi)容

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

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

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

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

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

c.理解邏輯結(jié)構(gòu)與存儲結(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.樹和二叉樹

(1)樹部分：

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

b.掌握樹的遍歷;

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

(2)二叉樹部分：

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

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

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

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

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

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

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

6.圖

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

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

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

a.了解最小生成樹;

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

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

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

7.查找

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

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

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

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

8.排序

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

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

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

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

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