2020年成都信息工程大學專升本計算機類（數(shù)據(jù)結構）考試大綱

考試說明：計算機類綜合考試總分 100 分，包括《 C 語言程序設計》和《 數(shù)據(jù)結構 》，每門課程各占 50 分?？荚嚂r間總計 120 分鐘。

考試內容：

(一）緒論

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

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

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

(二）線性表

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

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 、選擇( 1 0 分)

2 、判斷( 1 0 分)

3、應用題 （20 分)

4、 算法設計( 10 分)

參考書目：

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

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

想要獲得更多資訊，點擊”專升本社區(qū)“你就知道！