（科目名稱：數(shù)據(jù)結(jié)構(gòu),科目代碼：910）

一、考查目標

數(shù)據(jù)結(jié)構(gòu)是佛山科學技術(shù)學院控制工程碩士學位研究生入學考試科目之一。該科目主要考查考生是否具備與計算機科學與技術(shù)有關(guān)的學科基礎(chǔ)知識以及綜合分析設計能力，以判別考生是否具備開展控制工程學科相關(guān)學術(shù)領(lǐng)域高水平、創(chuàng)新性科學研究的潛力。從而為國家培養(yǎng)具有較強分析問題和解決實際問題能力，并具有一定創(chuàng)新意識和創(chuàng)新能力的高層次專門技術(shù)人才。

該課程具體考查要求有：

1.理解數(shù)據(jù)結(jié)構(gòu)的基本概念、原理和方法。

2.掌握各種抽象數(shù)據(jù)類型定義、數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)、以及基本操作的實現(xiàn)，能夠?qū)λ惴ㄟM行基本的時間復雜度與空間復雜度的分析。

3.能夠運用數(shù)據(jù)結(jié)構(gòu)的基本原理和方法進行問題的分析與求解，具備采用C/C++或Java語言設計與實現(xiàn)算法的能力。

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

（一）試卷成績及考試時間

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

（二）答題方式

答題方式為閉卷、筆試。

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

各部分內(nèi)容所占分值為：

1.算法時間復雜度分析(5～10分)；

2.數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)(10～28分)；

3.線性表(20～28分)；

4.二叉樹(20～28分)；

5.樹與森林(5～10分)；

6.圖(15～20分)；

7.查找(20～25分)；

8.排序(20～25分)；

9.文件(5～10分)。

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

1.填空題：5小題，共25分；

2.判斷題：5小題，共15分；

3.簡答題：5小題，共20分；

4.應用題：3小題，共30分。

5.算法設計與分析題：3小題，共60分。

（五）主要參考書目

嚴蔚敏．《數(shù)據(jù)結(jié)構(gòu)(C語言)》．北京：清華大學出版社，2008年。

三、考查范圍

1.基礎(chǔ)知識

（1）基本概念和術(shù)語。

（2）抽象數(shù)據(jù)類型。

（3）算法性能分析與復雜性度量。

2.線性表

（1）線性表的定義與抽象。

（2）線性表的順序表示與實現(xiàn)。

（3）線性表的鏈式表示與實現(xiàn)鏈表。

3.棧與隊列

（1）隊列、棧的定義及抽象操作。

（2）隊列、棧的順序存儲結(jié)構(gòu)及相關(guān)算法。

（3）隊列、棧的鏈式存儲結(jié)構(gòu)及相關(guān)算法。

（4）棧、隊列的應用、棧與遞歸過程的關(guān)系。

4.數(shù)組、廣義表

（1）數(shù)組的定義及操作。

（2）數(shù)組的順序存儲及規(guī)律。

（3）矩陣的壓縮存儲。

（4）廣義表的定義與存儲方式。

5.串

（1）串的基本概念和抽象操作。

（2）串的存儲方式、串操作的實現(xiàn)。

（3）串的模式匹配算法。

6.樹和二叉樹

（1）樹的定義及抽象操作。

（2）二叉樹的性質(zhì)及存儲方式（順序、鏈式）。

（3）二叉樹的遍歷及各類相關(guān)算法。

（4）樹的存儲結(jié)構(gòu)及算法。

（5）Huffman樹及其應用。

7.圖

（1）圖的定義及基本操作。

（2）圖的存儲結(jié)構(gòu)：（鄰接矩陳，鄰接表存儲方法，十字鏈表法）。

（3）圖的遍歷及相關(guān)算法：深度優(yōu)先搜索與廣度優(yōu)先搜索算法等。

（4）連通分量，生成樹，最小生成樹。

（5）拓撲排序，關(guān)鍵路徑。

8.內(nèi)部排序

（1）排序基本知識。

（2）插入排序：直接插入排序，希爾排序等。

（3）選擇排序：直接選擇排序，堆排序等。

（4）交換排序：冒泡排序，快速排序等。

（5）歸并排序：

（6）排序各種方法比較。

9.查找

（1）靜態(tài)查找表

（2）動態(tài)查找樹表

（3）哈希表

10.文件

（1）文件的基本概念

（2）文件的組織結(jié)構(gòu)

更多信息請查看學歷考試網(wǎng)