蘭州交通大學(xué)博文學(xué)院2021年專升本數(shù)據(jù)結(jié)構(gòu)考試大綱

　　即將參加2021甘肅專升本的考生伙伴們注意了，很多報考計算機(jī)科學(xué)與技術(shù)、網(wǎng)絡(luò)工程、物聯(lián)網(wǎng)工程專業(yè)的考生都會問，2021甘肅專升本數(shù)據(jù)結(jié)構(gòu)專業(yè)課考綱內(nèi)容都有哪些呢？今天小編就來回答大家這個問題。跟隨小編的步伐一起來看看2021蘭州交通大學(xué)博文學(xué)院專升本數(shù)據(jù)結(jié)構(gòu)考試大綱。 

　　一、考試內(nèi)容與要求

　　(一)基本理論知識

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

　　2.線性表的定義，在線性表上常進(jìn)行的基本操作，這些操作在順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)下的實現(xiàn)及復(fù)雜度分析。

　　3.棧和隊列的定義、特點、表示方法和實現(xiàn)。

　　4.串的定義及其基本操作。

　　5.數(shù)組的定義、運算和存儲、稀疏矩陣的壓縮存儲、廣義表的定義和基本操作。

　　6.樹的定義、基本術(shù)語和存儲結(jié)構(gòu)，二叉樹的定義和性質(zhì)、二叉樹的存儲結(jié)構(gòu)及其各種操作，Huffman和Huffman編碼。

　　7.圖的定義和常用術(shù)語、圖的存儲結(jié)構(gòu)及其遍歷操作，求最小生成樹、最短路徑的算法，拓?fù)渑判颉?

　　8.各種查找方法的算法、適用范圍及時間復(fù)雜度的分析。

　　9.各種內(nèi)排序算法的基本思想和算法的時間復(fù)雜度分析，不同排序方法比較。

　　(二)基本技能

　　1.能閱讀用類C語言編寫的算法。

　　2.能分析算法所實現(xiàn)的功能、運行結(jié)果和時間、空間復(fù)雜度。

　　3.能根據(jù)要求用類C語言編寫一些經(jīng)典、常用算法。

　?。ㄈ└髡鹿?jié)學(xué)習(xí)目的要求和主要學(xué)習(xí)內(nèi)容

　　第一章緒論

　　學(xué)習(xí)目的要求：掌握數(shù)據(jù)結(jié)構(gòu)的定義、內(nèi)容和方法，掌握算法的定義、描述和評價。

　　主要學(xué)習(xí)內(nèi)容：

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

　　2.基本數(shù)據(jù)類型

　　3.抽象數(shù)據(jù)類型的表示與實現(xiàn)

　　4.算法描述與分析

　　第二章線性表

　　學(xué)習(xí)目的要求：掌握線性表的抽象數(shù)據(jù)類型定義和兩種存儲方式，以及在相應(yīng)存儲結(jié)構(gòu)上的線性表運算。

　　主要學(xué)習(xí)內(nèi)容：

　　1.線性數(shù)據(jù)結(jié)構(gòu)的特點

　　2.線性表的邏輯結(jié)構(gòu)

　　3.線性表的順序存儲和實現(xiàn)

　　4.線性表的鏈?zhǔn)酱鎯蛯崿F(xiàn)

　　5.應(yīng)用舉例

　　第三章棧和隊列

　　學(xué)習(xí)目的要求：掌握棧和隊列的結(jié)構(gòu)特征以及操作實現(xiàn)特點。

　　主要學(xué)習(xí)內(nèi)容:

　　1.棧的抽象數(shù)據(jù)類型

　　2.棧的表示和實現(xiàn)

　　3.棧的應(yīng)用舉例

　　4.隊列的抽象數(shù)據(jù)類型及定義

　　5.循環(huán)隊列和鏈隊列

　　6.隊列的應(yīng)用

　　第四章串

　　學(xué)習(xí)目的要求：掌握串的定義、基本存儲結(jié)構(gòu)和基本操作以及串的應(yīng)用。

　　主要學(xué)習(xí)內(nèi)容：

　　1.串的邏輯結(jié)構(gòu)和意義

　　2.串的表示和實現(xiàn)

　　3.串的模式匹配算法

　　4.串的應(yīng)用

　　第五章數(shù)組和廣義表

　　學(xué)習(xí)目的要求：掌握數(shù)組和廣義表的定義和實現(xiàn)，加深對這兩種特殊的線性結(jié)構(gòu)的理解。

　　主要學(xué)習(xí)內(nèi)容：

　　1.數(shù)組的定義和運算

　　2.數(shù)組的順序存儲和實現(xiàn)

　　3.特殊矩陣的壓縮存儲

　　4.廣義表的定義

　　5.廣義表的存儲結(jié)構(gòu)

　　第六章樹和二叉樹

　　學(xué)習(xí)目的要求：掌握樹型特征、存儲及其操作實現(xiàn)。

　　主要學(xué)習(xí)內(nèi)容：

　　1.樹的定義和基本術(shù)語

　　2.二叉樹

　　3.二叉樹的遍歷和線索二叉樹

　　4.樹和森林

　　5.哈夫曼樹及其應(yīng)用

　　6.樹的應(yīng)用舉例

　　第七章圖

　　學(xué)習(xí)目的要求：掌握圖在計算機(jī)中的存儲和實現(xiàn)，并且利用圖來解決實際問題

　　主要學(xué)習(xí)內(nèi)容

　　1.了解圖的定義和術(shù)語。

　　2.圖的存儲結(jié)構(gòu)

　　3.圖的遍歷

　　4.圖的連通性

　　5.最短路徑

　　6.應(yīng)用舉例

　　第九章查找

　　學(xué)習(xí)目的要求：掌握數(shù)據(jù)的查找技術(shù)和表示和實現(xiàn)方法。

　　主要學(xué)習(xí)內(nèi)容：

　　1.順序查找，有序表的查找

　　2.索引順序查找，二分查找法

　　3.哈希表

　　4.應(yīng)用舉例

　　第十章內(nèi)部排序

　　學(xué)習(xí)目的要求：掌握數(shù)據(jù)結(jié)構(gòu)中排序的基本概念和五類重要的排序方法。

　　主要學(xué)習(xí)內(nèi)容：

　　1.插入排序

　　2.交換排序

　　3.選擇排序

　　4.歸并排序

　　5.基數(shù)排序

　　6.各種排序方法的比較

　　第十一章外部排序

　　學(xué)習(xí)目的要求:了解對外存信息進(jìn)行存取的特點，掌握外部排序的方法及實現(xiàn)。

　　主要學(xué)習(xí)內(nèi)容

　　1.外存信息的存取

　　2.外部排序的方法

　　二、考試形式與及時間

　　1.答題方式為閉卷筆試

　　2.答卷時間為120分鐘，滿分200分

　　三、試題類型

　　1.單選題（40分）

　　2.填空題（40分）

　　3.判斷題（20分）

　　4.應(yīng)用題（100分）

　　四、參考教材

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