【一】考試對象

　　本大綱適用于報考武漢學(xué)院軟件工程專業(yè)專升本的考生。

　　【 二】考試目標(biāo)

　　專升本《數(shù)據(jù)結(jié)構(gòu)》 旨在考查考生對各種線性(順序表、鏈表、 棧、隊列)和非線性(樹、圖)的基本數(shù)據(jù)結(jié)構(gòu)及其操作的掌握，并 能為程序處理的數(shù)據(jù)選擇合適的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及相應(yīng)算法，掌 握算法的時間和空間復(fù)雜度的分析技術(shù)，選拔優(yōu)秀高職高專畢業(yè)生升 入我校本科繼續(xù)鉆研學(xué)習(xí)。

　　【三】考試范圍

　　本考試屬于標(biāo)準(zhǔn)參考性學(xué)業(yè)水平類選拔考試。主要考核學(xué)生基于 問題的邏輯結(jié)構(gòu)、基于內(nèi)存物理存儲結(jié)構(gòu)，和基于結(jié)構(gòu)的數(shù)據(jù)各種操 作的實現(xiàn)及分析能力?？荚噧?nèi)容包括數(shù)據(jù)結(jié)構(gòu)及其分類，數(shù)據(jù)結(jié)構(gòu)與 算法的密切關(guān)系;各種基本數(shù)據(jù)結(jié)構(gòu)及其操作;根據(jù)實際問題要求來 選擇數(shù)據(jù)結(jié)構(gòu);設(shè)計算法的步驟與算法分析方法等。

　　【四】考試方式

　　本考試采用客觀試題與主觀試題相結(jié)合的方式，以閉卷筆試的形 式組織考試。試卷總分值為 150 分。

　　【五】考試時長

　　90 分鐘。

　　【六】考試內(nèi)容

　　第一章 緒論

　　考試內(nèi)容：數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語;算法的描述和分析。

　　考核要求：

　　1.掌握：數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語;算法的時間復(fù)雜度分析。

　　2.了解：算法的描述和分析。

　　第二章 線性表

　　考試內(nèi)容：線性表的邏輯結(jié)構(gòu);線性表的順序存儲結(jié)構(gòu);線性表 的鏈?zhǔn)酱鎯Y(jié)構(gòu);線性表的基本操作(初始化，插入，刪除等)，線 性表的運用。

　　考核要求：

　　1.掌握：線性表的順序存儲結(jié)構(gòu);線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu);線性 表的基本操作(初始化，插入，刪除等)，線性表的運用。

　　2.了解：線性表的基本特點和邏輯結(jié)構(gòu)。

　　第三章 棧和隊列

　　考試內(nèi)容：棧的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其相關(guān)算法;隊列的邏輯 結(jié)構(gòu)、存儲結(jié)構(gòu)及其相關(guān)算法; 棧和隊的運用。

　　考核要求：

　　1.掌握：棧的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其相關(guān)算法;隊列的邏輯結(jié) 構(gòu)、存儲結(jié)構(gòu)及其相關(guān)算法。

　　2.了解：棧和隊列的特點，棧和隊的運用。

　　第四章 樹和二叉樹

　　考試內(nèi)容：樹的常用術(shù)語及含義，不同表示方法;二叉樹的定義, 二叉樹的性質(zhì);二叉樹的存儲方法、特點及適用范圍;二叉樹的遍歷; 樹、森林、二叉樹之間的轉(zhuǎn)換方法;樹的各種存儲結(jié)構(gòu)及其特點，樹 的遍歷方法;哈夫曼樹及其應(yīng)用;樹、二叉樹的運用。

　　考核要求：

　　1.掌握：樹的常用術(shù)語及含義，不同表示方法;二叉樹的定義, 二叉樹的性質(zhì);二叉樹的存儲方法、特點及適用范圍;二叉樹的遍歷; 哈夫曼樹及其應(yīng)用。

　　2.了解：樹和森林的定義和基本概念;樹、森林、二叉樹之間的 轉(zhuǎn)換方法;樹的各種存儲結(jié)構(gòu)及其特點，樹的遍歷方法;樹、二叉樹 的運用。

　　第五章 圖

　　考試內(nèi)容：圖的邏輯結(jié)構(gòu)特征,圖的常用術(shù)語及含義;圖的鄰接 矩陣和鄰接表存儲結(jié)構(gòu);圖的遍歷，深度優(yōu)先搜索和廣度優(yōu)先搜索兩 種遍歷算法;圖的遍歷算法的應(yīng)用;生成樹和最小生成樹，深度優(yōu)先 和廣度優(yōu)先生成樹或生成森林，Prim 和Kruskal 算法;無向圖的連 通性;有向圖的強連通性;拓?fù)渑判?關(guān)鍵路徑;最短路徑，Dijkstra 算法，F(xiàn)loyd 算法。

　　考核要求：

　　1.掌握：圖的鄰接矩陣和鄰接表存儲結(jié)構(gòu);圖的遍歷，深度優(yōu)先 搜索和廣度優(yōu)先搜索兩種遍歷算法;圖的遍歷算法的應(yīng)用;生成樹和 最小生成樹 ，深度優(yōu)先和廣度優(yōu)先生成樹或生成森林 ，Prim 和 Kruskal 算法。

　　2.了解：圖的邏輯結(jié)構(gòu)特征,圖的常用術(shù)語及含義;無向圖的連 通性;有向圖的強連通性;拓?fù)渑判?關(guān)鍵路徑;最短路徑，Dijkstra 算法，F(xiàn)loyd 算法。

　　【七】參考教材

　　《數(shù)據(jù)結(jié)構(gòu)》(C 語言版)(第 2 版)，嚴(yán)蔚敏、李冬梅、吳偉民， 人民郵電出版社，ISBN:978-7-115-57666-8，2021.12 出版