考試科目代碼:[822]

考試科目名稱(chēng):數據結構

一、考試目標

(一)考查考生對基本數據結構相關(guān)知識的理解，包括邏輯結構、存儲結構和運算三者的關(guān)系;考查考生對不同算法開(kāi)銷(xiāo)的分析能力。

(二)考查考生掌握線(xiàn)性結構、樹(shù)、圖和查找、排序算法的掌握程度，要求考生在指定的數據結構和算法中完成特定問(wèn)題的求解。

(三)考查考生分析問(wèn)題及設計簡(jiǎn)單解決方案的能力，要求考生能針對實(shí)際問(wèn)題，選擇合適的數據結構和算法，設計問(wèn)題求解方案。

二、試卷結構

(一)考試時(shí)間：180分鐘，滿(mǎn)分：150分。

(二)題型結構

1、選擇題：30分 ;

2、程序填空題：20分;

3、綜合應用題：40分

4、算法設計題：共60分。

三、 答題方式

閉卷筆試

四、考試內容

1. 緒論

考試內容：數據結構、算法等的基本概念;抽象數據類(lèi)型;算法的描述和算法分析等。

考試要求：

[1] 掌握數據邏輯結構的4種基本結構，掌握數據結構中的物理存儲結構與邏輯結構。

[2] 熟練掌握時(shí)間復雜度與空間復雜度、語(yǔ)句頻度等概念及計算，了解語(yǔ)句頻度與時(shí)間復雜度的不同，掌握大O表示法來(lái)表示時(shí)間復雜度。

2. 線(xiàn)性表

考試內容：線(xiàn)性表的邏輯結構;線(xiàn)性表的順序存儲結構;線(xiàn)性表的鏈式存儲結構，包括單鏈表、循環(huán)鏈表和雙向鏈表等。

考試要求：

[1] 掌握線(xiàn)性表的順序存儲結構和鏈式存儲結構的表示和基本運算的實(shí)現。

[2] 熟練掌握線(xiàn)性表的基本操作：查找、插入、刪除，尤其是鏈式存儲結構上的編程實(shí)現，如指針在鏈表中的操作。理解隨機訪(fǎng)問(wèn)的含義。

3. 棧和隊列

考試內容：棧的抽象數據類(lèi)型;棧的表示與實(shí)現;棧的應用;隊列的抽象數據類(lèi)型;鏈式隊列;循環(huán)隊列等。

考試要求：

[1]掌握棧的操作特性及其應用，掌握順序棧和鏈棧的四要素，掌握棧的常見(jiàn)應用示例。

[2]掌握隊列的操作特性及其應用，掌握順序隊列、循環(huán)隊列和鏈隊列的表示，掌握隊列的常見(jiàn)應用示例。

4. 串

考試內容：串類(lèi)型的定義;串的表示和實(shí)現;串的模式匹配;串操作應用等。

考試要求：

[1]掌握順序串和鏈串的主要特點(diǎn)及其應用場(chǎng)合。

[2]掌握KMP算法的原理和代碼實(shí)現。

5. 遞歸

考試內容：遞歸的相關(guān)概念、遞歸調用的實(shí)現、遞歸算法的設計方法。

考試要求：

[1]掌握遞歸算法設計的步驟。

6. 數組和廣義表

考試內容：數組的定義和運算;數組的順序存儲結構;矩陣的壓縮存儲;廣義表的表示等。

考試要求:

[1]掌握稀疏矩陣的三元組表示及基本運算的實(shí)現。

[2]掌握廣義表的定義和特點(diǎn)。

7. 樹(shù)和二叉樹(shù)

考試內容：樹(shù)和二叉樹(shù)的定義和基本操作;二叉樹(shù)的性質(zhì);二叉樹(shù)的存儲結構;二叉樹(shù)遍歷算法和應用;線(xiàn)索二叉樹(shù);樹(shù)和森林;哈夫曼樹(shù)及其應用等。

考試要求：

[1]掌握樹(shù)二叉樹(shù)定義和性質(zhì)。

[2]掌握二叉樹(shù)的各種存儲結構，重點(diǎn)掌握二叉鏈表的表示。

[3]重點(diǎn)掌握二叉樹(shù)的遍歷和應用。

[4]掌握哈夫曼樹(shù)的構造算法。

8. 圖

考試內容：圖的定義和術(shù)語(yǔ);圖的存儲結構;圖的遍歷;圖的連通性;有向無(wú)環(huán)圖及其應用;最短路徑等。

考試要求:

[1] 掌握圖的相關(guān)概念和性質(zhì)。

[2] 掌握圖的存儲結構和圖的兩種遍歷算法。

[3] 熟練掌握兩種求解最小生成樹(shù)的算法(Prim算法和Kruskal 算法)

[4] 熟練掌握最短路徑算法——Dijkstra算法。

9. 查找

考試內容：靜態(tài)查找表;動(dòng)態(tài)查找表;哈希表等。

考試要求:

[1]掌握查找的相關(guān)概念、掌握順序查找、二分查找、分塊查找的算法及性能分析。

[2]掌握折半查找的算法描述。

[3]掌握二叉排序樹(shù)的構造、插入算法，掌握二叉排序樹(shù)的查找長(cháng)度計算。

[4]掌握哈希表的構造，掌握常見(jiàn)的沖突處理方法，掌握查找成功與不成功時(shí)的平均查找長(cháng)度的計算。

10. 內排序

考試內容：排序的定義，排序方法的穩定性，內部排序與外部排序，排序方法的分類(lèi);插入排序;交換排序;選擇排序;歸并排序;基數排序;各種內部排序方法的比較分析等。

[1]掌握排序的相關(guān)概念，理解排序的穩定性。

[2]掌握快速排序，正確描述算法并分析算法的開(kāi)銷(xiāo)。

[3]掌握堆排序，深入理解排序算法，并能用代碼描述。

[4]掌握各種排序算法的性能比較。

五、主要參考書(shū)目

(一)《數據結構教程》(第5版)，李春葆，清華大學(xué)出版社，2017年

(二)《數據結構》(C語(yǔ)言版)，嚴蔚敏、吳偉民編著(zhù)，清華大學(xué)出版社，2007年