2022年成都信息工程大學(xué)專升本數(shù)據(jù)結(jié)構(gòu)考試大綱

考試內(nèi)容：

(一) 緒論

1. 數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語(yǔ);

2. 抽象數(shù)據(jù)類型(ADT)的概念;

3. 算法的時(shí)間復(fù)雜性和空間復(fù)雜性分析方法。

(二) 線性表

1. 線性表的邏輯結(jié)構(gòu)特性和線性表的抽象數(shù)據(jù)類型(ADT)的設(shè) 計(jì);

2. 線性表的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)方法;

(1) 順序表的創(chuàng)建、查找、插入和刪除等基本操作及相關(guān)算法;

(2) 單鏈表的創(chuàng)建、查找、插入和刪除等基本操作及相關(guān)算法;

(3) 雙向鏈表的插入和刪除等基本操作及相關(guān)算法;

(4) 循環(huán)鏈表的特點(diǎn)及創(chuàng)建、查找、插入和刪除等基本操作及相關(guān)算法

3. 一元多項(xiàng)式的表示方法及相加算法。

(三) 棧與隊(duì)列

1. 棧與隊(duì)列的定義、 操作特點(diǎn);

2. 棧、隊(duì)列(包括循環(huán)隊(duì)列) 的表示和基本操作的實(shí)現(xiàn)。

3.棧和隊(duì)列在表達(dá)式求值、括號(hào)匹配、數(shù)制轉(zhuǎn)換、 舞伴問(wèn)題中的應(yīng)用。

(四) 樹(shù)和二叉樹(shù)

1.二叉樹(shù)的定義、結(jié)構(gòu)特點(diǎn)和性質(zhì);

2. 二叉樹(shù)的設(shè)計(jì)和實(shí)現(xiàn)： 二叉樹(shù)存儲(chǔ)結(jié)構(gòu)的特點(diǎn)， 三種遍歷方式 的遞歸算法，二叉樹(shù)的線索化過(guò)程和算法;

3. 樹(shù)的設(shè)計(jì)和實(shí)現(xiàn)、樹(shù)的各種表示方法及基本術(shù)語(yǔ)， 樹(shù)和森林與 二叉樹(shù)的轉(zhuǎn)換方法; 4. 哈夫曼樹(shù)的構(gòu)造算法、哈夫曼編碼。

(五) 圖

1. 圖的定義、術(shù)語(yǔ)和性質(zhì);

2.圖的設(shè)計(jì)和實(shí)現(xiàn)：

(1) 圖的鄰接矩陣、鄰接表的存儲(chǔ)結(jié)構(gòu)及其構(gòu)造方法;

(2) 圖的兩種遍歷方法：深度優(yōu)先遍歷和廣度優(yōu)先遍歷;

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

(1) 最小生成樹(shù)的算法;

(2) 構(gòu)造最短路徑的 Dijkstra 算法和 Floyd 算法。

(六) 查找

1.查找的基本概念

2. 線性表的查找

(1) 順序查找算法

(2) 折半查找算法

(3) 分塊查找算法

3.樹(shù)表的查找

(1) 二叉排序樹(shù)的定義和基本操作(創(chuàng)建、插入、刪除、查找);

(2) 平衡二叉樹(shù)的定義、平衡調(diào)整方法

4.Hash 表的查找

(1) Hash 查找的基本概念;

(2) Hash 函數(shù)的構(gòu)造方法、處理沖突的方法;

(3) Hash 表的查找算法

(七) 排序

1.排序的基本概念

2. 插入排序

(1) 直接插入排序算法

(2) 折半插入排序算法

(3) 希爾排序算法

3.交換排序

(1) 冒泡排序

(2) 快速排序

4.選擇排序

(1) 簡(jiǎn)單選擇排序

(2) 堆排序

考試題型：

1.選擇 ( 10 分)

2.判斷 ( 10 分)

3.應(yīng)用題

4.算法設(shè)計(jì)

(20 分)

(10 分)

參考書(shū)目：

1.《數(shù)據(jù)結(jié)構(gòu)》(C 語(yǔ)言版) 嚴(yán)蔚敏 吳偉民編 清華大學(xué)出版社

2.《數(shù)據(jù)結(jié)構(gòu)》(C 語(yǔ)言版|第 2 版) 嚴(yán)蔚敏 李冬梅 吳偉民編 人民郵電出版社