西安石油大學2020年碩士研究生招生考試

自命題科目考試大綱

科目代碼及名稱：808 數據結構與程序設計

適用專業：計算機科學與技術  計算機技術

一、考試目的及要求

“數據結構與程序設計”入學考試是為招收計算機科學與技術類碩士生而實施的選拔性考試，主要涉及數據結構、C/C++程序設計課程的內容。主要包括三大常用數據結構的邏輯、物理表示與基本操作算法實現部分的知識，各種結構的經典應用和問題求解。考生應掌握各種數據結構及其操作，具備一定的算法設計與分析能力，能夠根據實際問題選擇合適的數據結構并設計算法實現。要求考生具有較全面的數據結構表示與實現的基礎知識；具有較高的分析問題和解決問題的能力；具有較強的綜合知識運用能力。

二、考試內容

1．緒論

1.1 數據結構的基本概念；

1.2 抽象數據類型；

1.3 算法和算法的時間復雜度。

2. 線性表

2.1 線性表概述；

2.2 線性表的順序表示和實現；

2.3 線性表的鏈式表示和實現；

2.4 靜態鏈表；

2.5 線性表的基本運算。

3. 堆棧和隊列

3.1 堆棧；

3.2 堆棧應用；

3.3 隊列；

3.4 優先級隊列。

4. 串

4.1 串概述；

4.2 串的存儲結構；

4.3 串基本操作的實現算法；

4.4 串的模式匹配算法-BF和KMP算法。

5. 數組

5.1 數組概述；

5.2 動態數組；

5.3 特殊矩陣的壓縮存儲；

5.4 稀疏矩陣的壓縮存儲。

6. 遞歸算法

6.1 遞歸的概念；

6.2 遞歸算法的執行過程；

6.3 遞歸算法的設計方法；

6.4 遞歸過程和運行時棧；

6.5 遞歸算法的時間效率分析。

7. 樹和二叉樹

7.1 樹；

7.2 二叉樹；

7.3 二叉樹的設計和實現；

7.4 二叉樹遍歷；

7.5 線索二叉樹；

7.6 哈夫曼樹；

7.7 等價問題；

7.8 樹與二叉樹的轉換；

7.9 樹的遍歷。

8. 圖

8.1 圖概述；

8.2 圖的存儲結構；

8.3 圖的實現；

8.4 圖的遍歷；

8.5 最小生成樹；

8.6 最短路徑；

8.7 拓撲排序；

8.8 關鍵路徑。

9. 排序

9.1 排序的基本概念；

9.2 插入排序；

9.3 選擇排序；

9.4 交換排序；

9.5 歸并排序；

9.6 基數排序；

9.7 排序算法性能比較。

10. 查找

10.1 查找的基本概念；

10.2 靜態查找； 

10.3 動態查找；

10.4 哈希查找；

三、考試的題型及比例

單項選擇題（20%）

填空題（13%）

簡答題（20%）

算法理解與設計題（47%）

四、考試形式及時間

考試形式為閉卷筆試?？荚嚂r間為3小時。

五、主要參考書目（可以多本）

1. 嚴蔚敏，《數據結構（ C語言版）》（第二版），人民郵電出版社，2016 年

2．朱戰立，《數據結構（使用 C語言）》 (第五版 )，電子工業出版社，2014 年

3．M.A.韋斯，《數據結構與算法分析 --- C++ 語言描述》， (第四版 )，電子工業出版社，2016 年