華僑大學

華僑大學碩士研究生招生考試初試自命題科目考試大綱

招生學院：計算機科學與技術學院 招生專業：軟件工程/電子信息

科目名稱：數據結構

一、考試形式與試卷結構

(一)試卷滿分值及考試時間

本試卷滿分為150分，考試時間為180分鐘。

(二)答題方式

答題方式為閉卷、筆試。試卷由試題和答題紙組成;答案必須寫在答題紙(由考點提供)相應的位置上。

(三)試卷內容結構

考試內容為數據結構(100%)。

(四)試卷題型結構

1. 問答題(單一技術解決單一問題)(50分)，共3-6道;

2. 綜合應用題(多種技術解決某一問題)(50分)，共2-5道;

3. 算法設計題(50分)，共3道。

二、考查目標

數據結構課程考試的目的在于測試考生對于數據結構的基本概念、基本理論、基礎知識的掌握情況，以及分析研究計算機加工的對象特性、選擇適當的數據結構和存儲結構、設計與之相適應的算法、運用算法的時間和空間分析方法的能力。

三、考查范圍或考試內容概要

1. 數據結構基礎知識

數據結構、算法等的基本概念;抽象數據類型;算法的描述和算法分析等。

2. 線性表

線性表的邏輯結構;線性表的順序存儲結構;線性表的鏈式存儲結構和線性鏈表;循環鏈表和雙向鏈表等。

3. 棧和隊列

棧的抽象數據類型;棧的表示與實現;棧的應用;隊列的抽象數據類型;鏈式隊列;循環隊列等。

4. 串

串類型的定義;串的表示和實現;串的模式匹配;串操作應用等。

5. 數組和廣義表

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

6. 樹和二叉樹

樹和二叉樹的定義和基本操作;二叉樹的性質;二叉樹的存儲結構;二叉樹遍歷算法和應用;線索二叉樹;樹和森林;哈夫曼樹及其應用等。

7. 圖

圖的定義和術語;圖的存儲結構;圖的遍歷;圖的連通性;有向無環圖及其應用;最短路徑等。

8. 查找

靜態查找表;動態查找表;哈希表等。

9. 內部排序

排序的定義，排序方法的穩定性，內部排序與外部排序，排序方法的分類;插入排序;快速排序;選擇排序;歸并排序;基數排序;各種內部排序方法的比較分析等。

四、參考教材或主要參考書：

1. 嚴蔚敏、吳偉民，《數據結構(C語言版)》，清華大學出版社，2011年。

2. 嚴蔚敏、吳偉民、米寧，《數據結構習題集(C語言版)》，清華大學出版社，2011年。