第一部分 數據結構

一、考試要求

數據結構是計算機相關專業的專業基礎課。本門課程要求考生能夠比較系統地理解數據結構的基本概念、基本原理和方法，掌握數據的邏輯結構、存儲結構以及各種基本操作的實現;要求考生能夠運用所學的基本原理和基本方法分析、判斷和解決相關的理論問題和實際問題;要求考生能夠對算法進行設計與分析并選擇適當的數據結構和方法進行問題求解。

二、考試內容范圍

1. 數據結構中的基本定義

(1) 數據結構的基本概念，數據的邏輯結構、存儲結構。

(2) 抽象數據類型的定義、表示和實現。

(3) 算法定義及算法的基本特性，算法分析的基本概念。

2. 線性結構

(1) 線性表的定義，線性表的基本操作，線性表的順序存儲結構和基本運算的實現，線性表的鏈式存儲結構 ( 包括單鏈表、循環鏈表和雙向鏈表 ) 和基本運算的實現，從時間和空間復雜度的角度綜合比較線性表兩種存儲結構的特點及其適用場合。

(2) 串的定義、存儲表示和基本操作，在定長順序存儲結構上實現串的基本操作算法。

(3) 數組的定義、順序存儲表示和基本運算的實現。

3. 樹與二叉樹

(1) 樹與二叉樹的基本概念，包括基本特征、基本操作。

(2) 二叉樹的基本性質、二叉樹的二叉鏈表存儲結構、二叉樹的三種基本遍歷算法 ( 前序、中序和后序 ) ;由二叉樹的遍歷序列恢復二叉樹;二叉樹遍歷的應用。

4. 圖

(1) 圖的定義，基本概念，圖的分類。

(2) 圖的鄰接矩陣存儲方法、鄰接表存儲方法。

(3) 圖的深度優先和廣度優先遍歷算法。

(4) 最小生成樹 (Prim 算法和 Kruskal 算法 ) ，最短路徑， AOV 網與拓撲排序。

5. 查找

(1) 順序表和有序表的查找方法。

(2) 二叉排序樹的基本概念、建立和查找。

(3) 平衡二叉樹的維護平衡的方法 。

(4) 哈希查找和哈希表。

6. 內排序

(1) 排序的基本概念，排序方法的分類。

(2) 插入排序 ( 含折半插入排序 ) 、希爾排序、選擇排序、歸并排序、快速排序、堆排序。

(3) 各種排序方法排序的特點及比較，各種排序算法的時空復雜度簡單分析。

第二部分 面向對象程序設計(JAVA語言)

一、考試要求

面向對象程序設計指采用JAVA語言，要求考生掌握Java程序設計基本步驟與過程;熟悉Java各種基本數據類型及其操作，學會根據實際問題要求來選擇數據類型;掌握Java語言基本程序設計技術;掌握Java面向對象程序設計的抽象性、封裝性、繼承性和多態性;熟悉如何使用面向對象程序設計方法進行程序設計。

二、考試內容范圍

1. JAVA語言基礎

(1) 使用標識符命名變量、常量、方法和類。

(2) Java的基本數值類型。

2. 選擇結構

(1) 使用單分支if語句實現選擇控制。

(2) 使用雙分支if-else語句實現選擇控制。

(3) 使用嵌套的if語句和多分支if語句實現選擇控制。

(4) 使用switch語句實現選擇控制。

3. 數學函數、字符和字符串

(1) 使用Math類中的方法解決數學問題。

(2) 使用char類型表示字符。

(3) 使用string對象表示字符串。

(4) 使用length()方法來返回字符串長度。

(5) 使用charAt(i)方法來返回字符串中的字符。

(6) 使用indexOf方法定位一個字符串中的字符或子字符串。

4. 循環結構

(1) 使用while循環編寫重復執行語句的程序。

(2) 使用do-while語句編寫循環。

(3) 使用for語句編寫循環。

(4) 使用break和continue來實現程序的控制。

5. 方法

(1) 使用形參定義方法。

(2) 使用實參調用方法。

(3) 定義帶返回值的方法。

(4) 定義無返回值的方法。

6. 一維數組與多維數組

(1) 聲明數組引用變量以及創建數組。

(2) 使用下標訪問數組元素。

(3) 使用線性查找算法和二分查找算法查找數組中的元素。

(4) 使用選擇排序法對數組排序。

7. 對象和類

(1) 描述對象和類，并使用類來建模對象。

(2) 使用UML圖形符號來描述類和對象。

(3) 使用構造方法創建對象。

(4) 通過對象引用變量訪問對象。

(5) 使用引用類型定義引用變量。

(6) 使用對象成員訪問操作符來訪問對象的數據和方法。

(7) 封裝數據域使得類易于維護。

7. 繼承與多態

(1) 通過繼承由父類定義子類。

(2) 使用關鍵字super調用父類的構造方法和方法。

(3) 在子類中重寫實例方法。

(4) 區分重寫和重載的不同。

8. 抽象類和接口

(1) 設計和使用抽象類。

(2) 使用接口指定對象共同的行為。

(3) 定義接口以及實現接口的類。

考試總分：150分 考試時間：3小時 考試方式：閉卷，筆試

考試題型： 選擇題、填空題、簡答題、程序分析題及綜合應用題

參考書目：

[1] 嚴蔚敏等. 數據結構(C語言版).清華大學出版社, 2014

[2] 沈澤剛等.Java語言程序設計，清華大學出版社,2018