一、考試性質(zhì)

數(shù)據(jù)結(jié)構(gòu)是計算機學科的重要骨干基礎課程，所有計算機系統(tǒng)軟件和應用軟件都要用到各種類型的數(shù)據(jù)結(jié)構(gòu)以及一些典型的算法設計和分析技巧。課程教學應達到的目標是使學生掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)運算的基本理論、基本知識和基本技能，并具有利用計算機解決實際應用問題的能力。數(shù)據(jù)結(jié)構(gòu)課程既是對以往課程的深入和擴展，也是為將來更加深入地學習后續(xù)專業(yè)課程打下基礎。課程所涉及基本的樹、圖等數(shù)據(jù)結(jié)構(gòu)，是計算機科學的基本功。樹結(jié)構(gòu)、圖結(jié)構(gòu)等數(shù)據(jù)結(jié)構(gòu)，是數(shù)據(jù)庫、操作系統(tǒng)、編譯原理等后續(xù)課程的基礎。

本考試是為在計算機?？飘厴I(yè)生中招收本科生，實施的具有選拔功能的水平考試，指導思想是既有利于國家對高層次人才的選拔，又利于促進高等學校課程教學質(zhì)量的提高。

二、考試的基本要求

要求學生比較系統(tǒng)地掌握數(shù)據(jù)結(jié)構(gòu)的基本知識和基本技能，初步具有在明確所要解決的問題的基礎上，經(jīng)過對問題的深入分析和抽象，為其在計算機中建立一個模型，然后確定恰當?shù)臄?shù)據(jù)結(jié)構(gòu)表示該模型，再在此基礎上設計合適的算法，最后根據(jù)設計的數(shù)據(jù)結(jié)構(gòu)和算法進行相應的程序設計來模擬和解決實際問題，為后繼專業(yè)課程學習提供基礎。

三、考試方法和考試時間

考試方法為閉卷筆試，考試時間為90分鐘，滿分為100分。

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

第1章 數(shù)據(jù)結(jié)構(gòu)基礎

1、 考試內(nèi)容

數(shù)據(jù)結(jié)構(gòu)的基本概念和基本術語，算法的描述和算法分析。

2、基本要求

1)數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)等基本概念。

2)數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、算法的概念。

3)數(shù)據(jù)類型、抽象數(shù)據(jù)類型的概念。

4)時間復雜度、空間復雜度的概念以及簡單算法時間復雜度的計算。

5)數(shù)據(jù)結(jié)構(gòu)二元組的概念。S=(D,R)

第2章 線性表

1、考試內(nèi)容

線性表的定義、線性表的邏輯結(jié)構(gòu)、線性表的順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)，單向鏈表、循環(huán)鏈表。

2、基本要求

1)線性表的定義和線性結(jié)構(gòu)的特點。。

2)線性表的順序存儲結(jié)構(gòu)及其運算的實現(xiàn)。

3)線性表的鏈式存儲結(jié)構(gòu)及其運算的實現(xiàn)。

4)單鏈表、循環(huán)鏈表的特點。

第3章 棧和隊列

1、考試內(nèi)容

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

2、基本要求

1)棧和隊列的定義、基本運算。

2)棧和隊列的順序?qū)崿F(xiàn)及其運算的實現(xiàn)。

3)棧和隊列的鏈式實現(xiàn)及其運算的實現(xiàn)。

4)棧和隊列的應用。

5)理解遞歸的概念。

第4章 串

1、考試內(nèi)容

串的定義及其基本操作。

2、基本要求

1)串的定義。

2)串的幾種表示方法。

3)串的基本操作。

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

1、考試內(nèi)容

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

2、基本要求

1)數(shù)組的定義。

2)稀疏矩陣的存儲。

3)廣義表的概念。

第6章 樹

1、考試內(nèi)容

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

2、基本要求

1)樹的定義及其存儲結(jié)構(gòu)。

2)二叉樹的定義和性質(zhì)。

3)二叉樹的存儲結(jié)構(gòu)，包括順序和鏈式存儲。

4)二叉樹的遍歷、遞歸算法及其應用。

5)哈夫曼樹及哈夫曼編碼。

第7章 圖

1、考試內(nèi)容

圖的定義和術語、圖的存儲結(jié)構(gòu)及其各種操作。

2、基本要求

1)圖的基本概念。

2)圖的存儲結(jié)構(gòu)(鄰接矩陣、鄰接表)。

3)圖的遍歷方法(深度優(yōu)先遍歷、廣度優(yōu)先遍歷)。

4)圖的最小生成樹的算法(prim 算法、kruskal 算法)。

第8章 查找

1、考試內(nèi)容

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

2、基本要求

1)各種靜態(tài)查找技術和算法(順序查找、折半查找)。

2)動態(tài)查找的概念(二叉查找樹、AVL樹)。

3)散列表的概念。

4)散列函數(shù)構(gòu)造方法以及處理沖突的辦法

第9章 排序

1、考試內(nèi)容

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

2、基本要求

1)排序的基本概念(關鍵字、內(nèi)外排序、穩(wěn)定性等)

2)選擇排序的方法(簡單選擇排序)

3)插入排序的方法(直接插入排序)

4)交換排序的方法(冒泡排序)

5)各種排序方法的優(yōu)缺點。

五、命題要求

本課程命題范圍應涵蓋課程的所有章節(jié)，試題難易程度分為，較易占50%，中等難度占30%，較難占20%。在題型結(jié)構(gòu)上，主要包括客觀題和主觀題。

1)選擇題： 20%

2)填空題： 15%

3)判斷題： 10%

4)簡答題： 15%

5)應用題： 30%

6)編程題： 10%

六、主要參考書目

1、程海英.數(shù)據(jù)結(jié)構(gòu)(C語言版).北京：清華大學出版社，2014。

2、嚴蔚敏，李冬梅，吳偉民.數(shù)據(jù)結(jié)構(gòu)(C語言版).第2版.北京：人民郵電出版社，2016。

3、程海英，彭文藝.數(shù)據(jù)結(jié)構(gòu)案例教程(C語言版).北京：電子工業(yè)出版社，2019。