2020年成都信息工程大學(xué)專(zhuān)升本計(jì)算機(jī)類(lèi)（數(shù)據(jù)結(jié)構(gòu)）考試大綱

考試說(shuō)明：計(jì)算機(jī)類(lèi)綜合考試總分 100 分，包括《 C 語(yǔ)言程序設(shè)計(jì)》和《 數(shù)據(jù)結(jié)構(gòu) 》，每門(mén)課程各占 50 分。考試時(shí)間總計(jì) 120 分鐘。

考試內(nèi)容：

(一）緒論

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

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

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

(二）線(xiàn)性表

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

2.線(xiàn)性表的順序存儲(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ù)的線(xiàn)索化過(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. 線(xiàn)性表的查找

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

2 、判斷( 1 0 分)

3、應(yīng)用題 （20 分)

4、 算法設(shè)計(jì)( 10 分)

參考書(shū)目：

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

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

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