第一部分 數據結構

一、考試要求

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

二、考試內容范圍

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

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

(2) 抽象數據類(lèi)型的定義、表示和實(shí)現。

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

2. 線(xiàn)性結構

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

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

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

3. 樹(shù)與二叉樹(shù)

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

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

4. 圖

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

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

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

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

5. 查找

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

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

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

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

6. 內排序

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

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

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

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

一、考試要求

面向對象程序設計指采用JAVA語(yǔ)言，要求考生掌握Java程序設計基本步驟與過(guò)程;熟悉Java各種基本數據類(lèi)型及其操作，學(xué)會(huì )根據實(shí)際問(wèn)題要求來(lái)選擇數據類(lèi)型;掌握Java語(yǔ)言基本程序設計技術(shù);掌握Java面向對象程序設計的抽象性、封裝性、繼承性和多態(tài)性;熟悉如何使用面向對象程序設計方法進(jìn)行程序設計。

二、考試內容范圍

1. JAVA語(yǔ)言基礎

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

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

2. 選擇結構

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

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

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

(4) 使用switch語(yǔ)句實(shí)現選擇控制。

3. 數學(xué)函數、字符和字符串

(1) 使用Math類(lèi)中的方法解決數學(xué)問(wèn)題。

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

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

(4) 使用length()方法來(lái)返回字符串長(cháng)度。

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

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

4. 循環(huán)結構

(1) 使用while循環(huán)編寫(xiě)重復執行語(yǔ)句的程序。

(2) 使用do-while語(yǔ)句編寫(xiě)循環(huán)。

(3) 使用for語(yǔ)句編寫(xiě)循環(huán)。

(4) 使用break和continue來(lái)實(shí)現程序的控制。

5. 方法

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

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

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

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

6. 一維數組與多維數組

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

(2) 使用下標訪(fǎng)問(wèn)數組元素。

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

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

7. 對象和類(lèi)

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

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

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

(4) 通過(guò)對象引用變量訪(fǎng)問(wèn)對象。

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

(6) 使用對象成員訪(fǎng)問(wèn)操作符來(lái)訪(fǎng)問(wèn)對象的數據和方法。

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

7. 繼承與多態(tài)

(1) 通過(guò)繼承由父類(lèi)定義子類(lèi)。

(2) 使用關(guān)鍵字super調用父類(lèi)的構造方法和方法。

(3) 在子類(lèi)中重寫(xiě)實(shí)例方法。

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

8. 抽象類(lèi)和接口

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

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

(3) 定義接口以及實(shí)現接口的類(lèi)。

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

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

參考書(shū)目：

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

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