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

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

　　一、考試內容與要求

　　(一)基本理論知識

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

　　2.線性表的定義，在線性表上常進行的基本操作，這些操作在順序和鏈式存儲結構下的實現(xiàn)及復雜度分析。

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

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

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

　　6.樹的定義、基本術語和存儲結構，二叉樹的定義和性質、二叉樹的存儲結構及其各種操作，Huffman和Huffman編碼。

　　7.圖的定義和常用術語、圖的存儲結構及其遍歷操作，求最小生成樹、最短路徑的算法，拓撲排序。

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

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

　　(二)基本技能

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

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

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

　　（三）各章節(jié)學習目的要求和主要學習內容

　　第一章緒論

　　學習目的要求：掌握數(shù)據(jù)結構的定義、內容和方法，掌握算法的定義、描述和評價。

　　主要學習內容：

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

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

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

　　4.算法描述與分析

　　第二章線性表

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

　　主要學習內容：

　　1.線性數(shù)據(jù)結構的特點

　　2.線性表的邏輯結構

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

　　4.線性表的鏈式存儲和實現(xiàn)

　　5.應用舉例

　　第三章棧和隊列

　　學習目的要求：掌握棧和隊列的結構特征以及操作實現(xiàn)特點。

　　主要學習內容:

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

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

　　3.棧的應用舉例

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

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

　　6.隊列的應用

　　第四章串

　　學習目的要求：掌握串的定義、基本存儲結構和基本操作以及串的應用。

　　主要學習內容：

　　1.串的邏輯結構和意義

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

　　3.串的模式匹配算法

　　4.串的應用

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

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

　　主要學習內容：

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

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

　　3.特殊矩陣的壓縮存儲

　　4.廣義表的定義

　　5.廣義表的存儲結構

　　第六章樹和二叉樹

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

　　主要學習內容：

　　1.樹的定義和基本術語

　　2.二叉樹

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

　　4.樹和森林

　　5.哈夫曼樹及其應用

　　6.樹的應用舉例

　　第七章圖

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

　　主要學習內容

　　1.了解圖的定義和術語。

　　2.圖的存儲結構

　　3.圖的遍歷

　　4.圖的連通性

　　5.最短路徑

　　6.應用舉例

　　第九章查找

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

　　主要學習內容：

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

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

　　3.哈希表

　　4.應用舉例

　　第十章內部排序

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

　　主要學習內容：

　　1.插入排序

　　2.交換排序

　　3.選擇排序

　　4.歸并排序

　　5.基數(shù)排序

　　6.各種排序方法的比較

　　第十一章外部排序

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

　　主要學習內容

　　1.外存信息的存取

　　2.外部排序的方法

　　二、考試形式與及時間

　　1.答題方式為閉卷筆試

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

　　三、試題類型

　　1.單選題（40分）

　　2.填空題（40分）

　　3.判斷題（20分）

　　4.應用題（100分）

　　四、參考教材

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