?2022年成都信息工程大學專升本數(shù)據(jù)結構考試大綱

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

考試內容：

(一) 緒論

1. 數(shù)據(jù)結構的基本概念和術語;

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

3. 算法的時間復雜性和空間復雜性分析方法。

(二) 線性表

1. 線性表的邏輯結構特性和線性表的抽象數(shù)據(jù)類型(ADT)的設 計;

2. 線性表的順序存儲結構和鏈式存儲結構實現(xiàn)方法;

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

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

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

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

3. 一元多項式的表示方法及相加算法。

(三) 棧與隊列

1. 棧與隊列的定義、 操作特點;

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

3.棧和隊列在表達式求值、括號匹配、數(shù)制轉換、 舞伴問題中的應用。

(四) 樹和二叉樹

1.二叉樹的定義、結構特點和性質;

2. 二叉樹的設計和實現(xiàn)： 二叉樹存儲結構的特點， 三種遍歷方式 的遞歸算法，二叉樹的線索化過程和算法;

3. 樹的設計和實現(xiàn)、樹的各種表示方法及基本術語， 樹和森林與 二叉樹的轉換方法; 4. 哈夫曼樹的構造算法、哈夫曼編碼。

(五) 圖

1. 圖的定義、術語和性質;

2.圖的設計和實現(xiàn)：

(1) 圖的鄰接矩陣、鄰接表的存儲結構及其構造方法;

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

3.圖的應用：

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

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

(六) 查找

1.查找的基本概念

2. 線性表的查找

(1) 順序查找算法

(2) 折半查找算法

(3) 分塊查找算法

3.樹表的查找

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

(2) 平衡二叉樹的定義、平衡調整方法

4.Hash 表的查找

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

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

(3) Hash 表的查找算法

(七) 排序

1.排序的基本概念

2. 插入排序

(1) 直接插入排序算法

(2) 折半插入排序算法

(3) 希爾排序算法

3.交換排序

(1) 冒泡排序

(2) 快速排序

4.選擇排序

(1) 簡單選擇排序

(2) 堆排序

考試題型：

1.選擇 ( 10 分)

2.判斷 ( 10 分)

3.應用題

4.算法設計

(20 分)

(10 分)

參考書目：

1.《數(shù)據(jù)結構》(C 語言版) 嚴蔚敏 吳偉民編 清華大學出版社

2.《數(shù)據(jù)結構》(C 語言版|第 2 版) 嚴蔚敏 李冬梅 吳偉民編 人民郵電出版社