蘭州交通大學博文學院是甘肅省2020年招生院校之一。數(shù)據(jù)結(jié)構(gòu)是蘭州交通大學博文學院計算機科學與技術(shù)專業(yè)2020年的必修課。數(shù)據(jù)結(jié)構(gòu)考試參考教材:《數(shù)據(jù)結(jié)構(gòu)》(C語言版)，嚴為民吳偉民主編，清華大學出版社，2011年。具體考試大綱如下

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

(一)基礎(chǔ)理論知識

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

2.線性表的定義，線性表上經(jīng)常執(zhí)行的基本操作，以及這些操作在順序和鏈式存儲結(jié)構(gòu)下的實現(xiàn)和復雜性分析。

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

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

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

6.樹的定義、基本術(shù)語和存儲結(jié)構(gòu)，二叉樹的定義和性質(zhì)，二叉樹的存儲結(jié)構(gòu)和各種運算，哈夫曼和哈夫曼編碼。

7.圖的定義和常用術(shù)語，圖的存儲結(jié)構(gòu)及其遍歷操作，尋找最小生成樹和最短路徑的算法，拓撲排序。

8.各種搜索方法的算法、適用范圍和時間復雜度分析。

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

(2)基本技能

1.能夠閱讀用c語言編寫的算法。

2.可以分析算法實現(xiàn)的功能、運行結(jié)果和時間，以及空之間的復雜度。

3.能夠根據(jù)需要用C類語言寫一些經(jīng)典的，常用的算法。

(3)每章的學習目標、要求和主要學習內(nèi)容

靠前章導言

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

主要學習內(nèi)容:

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

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

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

4.算法描述和分析

第二章線性表

學習目的要求:掌握線性表的抽象數(shù)據(jù)類型定義，兩種存儲方式，以及對應存儲結(jié)構(gòu)上的線性表操作。

主要學習內(nèi)容:

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

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

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

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

5.應用示例

第三章堆棧和隊列

學習目標:掌握棧和隊列的結(jié)構(gòu)特點以及操作實現(xiàn)的特點。

主要學習內(nèi)容:

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

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

3.堆棧應用示例

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

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

6.隊列的應用

第四章弦

學習目標:掌握字符串的定義、基本存儲結(jié)構(gòu)、基本操作和應用。

主要學習內(nèi)容:

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

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

3.字符串模式匹配算法

4.字符串的應用

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

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

主要學習內(nèi)容:

1.數(shù)組的定義和操作

2.陣列的順序存儲和實施

3.特殊矩陣的壓縮存儲

4.廣義表的定義

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

第六章樹和二叉樹

學習目標:掌握樹特征、存儲和操作實現(xiàn)。

主要學習內(nèi)容:

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

2.二叉樹

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

4.樹木和森林

5.霍夫曼樹及其應用

6.樹形應用示例

第七章圖

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

主要學習內(nèi)容

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

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

3.圖的遍歷

4.圖的連通性

5.最短路徑

6.應用示例

第九章了解

學習目標:掌握數(shù)據(jù)搜索技術(shù)、表示和實現(xiàn)方法。

主要學習內(nèi)容:

1.順序搜索，有序表的搜索

2.索引順序搜索，二分搜索法方法

3.哈希表

4.應用示例

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

學習目標:掌握數(shù)據(jù)結(jié)構(gòu)中排序的基本概念和五種重要的排序方法。

主要學習內(nèi)容:

1.插入排序

2.交換排序

3.選擇排序

4.合并和排序

5.基數(shù)排序

6.各種排序方法的比較

第11章外部排序

學習目標:了解訪問外部存儲信息的特點，掌握外部排序的方法和實現(xiàn)。

主要學習內(nèi)容

1.訪問外部存儲信息

2.外部分類方法

二、考試形式和時間

1.答題方法是閉卷筆試

2.答題時間120分鐘，滿分200分

第三，測試類型

1.選擇題(40分)

2.填寫空題(40分)

3.真假問題(20分)

4.申請題(100分)

部分內(nèi)容來源于網(wǎng)絡轉(zhuǎn)載、學生投稿，如有侵權(quán)或?qū)Ρ菊居腥魏我庖?、建議或者投訴，請聯(lián)系郵箱（1296178999@qq.com）反饋。 未經(jīng)本站授權(quán)，不得轉(zhuǎn)載、摘編、復制或者建立鏡像， 如有違反，本站將追究法律責任！