華僑大學(xué)

2020年華僑大學(xué)碩士研究生招生考試初試自命題科目考試大綱

招生學(xué)院：計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院

招生專(zhuān)業(yè)：軟件工程/電子信息

科目名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)

一、考試形式與試卷結(jié)構(gòu)

(一)試卷滿(mǎn)分值及考試時(shí)間

本試卷滿(mǎn)分為150分，考試時(shí)間為180分鐘。

(二)答題方式

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

(三)試卷內(nèi)容結(jié)構(gòu)

考試內(nèi)容為數(shù)據(jù)結(jié)構(gòu)(100%)。

(四)試卷題型結(jié)構(gòu)

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

2. 綜合應(yīng)用題(多種技術(shù)解決某一問(wèn)題)(50分)，共2-5道;

3. 算法設(shè)計(jì)題(50分)，共3道。

二、考查目標(biāo)

數(shù)據(jù)結(jié)構(gòu)課程考試的目的在于測(cè)試考生對(duì)于數(shù)據(jù)結(jié)構(gòu)的基本概念、基本理論、基礎(chǔ)知識(shí)的掌握情況，以及分析研究計(jì)算機(jī)加工的對(duì)象特性、選擇適當(dāng)?shù)臄?shù)據(jù)結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)、設(shè)計(jì)與之相適應(yīng)的算法、運(yùn)用算法的時(shí)間和空間分析方法的能力。

三、考查范圍或考試內(nèi)容概要

1. 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識(shí)

數(shù)據(jù)結(jié)構(gòu)、算法等的基本概念;抽象數(shù)據(jù)類(lèi)型;算法的描述和算法分析等。

2. 線(xiàn)性表

線(xiàn)性表的邏輯結(jié)構(gòu);線(xiàn)性表的順序存儲(chǔ)結(jié)構(gòu);線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和線(xiàn)性鏈表;循環(huán)鏈表和雙向鏈表等。

3. 棧和隊(duì)列

棧的抽象數(shù)據(jù)類(lèi)型;棧的表示與實(shí)現(xiàn);棧的應(yīng)用;隊(duì)列的抽象數(shù)據(jù)類(lèi)型;鏈?zhǔn)疥?duì)列;循環(huán)隊(duì)列等。

4. 串

串類(lèi)型的定義;串的表示和實(shí)現(xiàn);串的模式匹配;串操作應(yīng)用等。

5. 數(shù)組和廣義表

數(shù)組的定義和運(yùn)算;數(shù)組的順序存儲(chǔ)結(jié)構(gòu);矩陣的壓縮存儲(chǔ);廣義表的表示等。

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

樹(shù)和二叉樹(shù)的定義和基本操作;二叉樹(shù)的性質(zhì);二叉樹(shù)的存儲(chǔ)結(jié)構(gòu);二叉樹(shù)遍歷算法和應(yīng)用;線(xiàn)索二叉樹(shù);樹(shù)和森林;哈夫曼樹(shù)及其應(yīng)用等。

7. 圖

圖的定義和術(shù)語(yǔ);圖的存儲(chǔ)結(jié)構(gòu);圖的遍歷;圖的連通性;有向無(wú)環(huán)圖及其應(yīng)用;最短路徑等。

8. 查找

靜態(tài)查找表;動(dòng)態(tài)查找表;哈希表等。

9. 內(nèi)部排序

排序的定義，排序方法的穩(wěn)定性，內(nèi)部排序與外部排序，排序方法的分類(lèi);插入排序;快速排序;選擇排序;歸并排序;基數(shù)排序;各種內(nèi)部排序方法的比較分析等。

四、參考教材或主要參考書(shū)：

1. 嚴(yán)蔚敏、吳偉民，《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)》，清華大學(xué)出版社，2011年。

2. 嚴(yán)蔚敏、吳偉民、米寧，《數(shù)據(jù)結(jié)構(gòu)習(xí)題集(C語(yǔ)言版)》，清華大學(xué)出版社，2011年。