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

一、考查目標(biāo)

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

該課程具體考查要求有：

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

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

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

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

（一）試卷成績(jī)及考試時(shí)間

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

（二）答題方式

答題方式為閉卷、筆試。

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

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

1.算法時(shí)間復(fù)雜度分析(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.簡(jiǎn)答題：5小題，共20分；

4.應(yīng)用題：3小題，共30分。

5.算法設(shè)計(jì)與分析題：3小題，共60分。

（五）主要參考書目

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

三、考查范圍

1.基礎(chǔ)知識(shí)

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

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

（3）算法性能分析與復(fù)雜性度量。

2.線性表

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

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

（3）線性表的鏈?zhǔn)奖硎九c實(shí)現(xiàn)鏈表。

3.棧與隊(duì)列

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

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

（3）隊(duì)列、棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及相關(guān)算法。

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

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

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

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

（3）矩陣的壓縮存儲(chǔ)。

（4）廣義表的定義與存儲(chǔ)方式。

5.串

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

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

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

6.樹和二叉樹

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

（2）二叉樹的性質(zhì)及存儲(chǔ)方式（順序、鏈?zhǔn)剑?/P>

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

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

（5）Huffman樹及其應(yīng)用。

7.圖

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

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

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

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

（5）拓?fù)渑判?，關(guān)鍵路徑。

8.內(nèi)部排序

（1）排序基本知識(shí)。

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

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

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

（5）歸并排序：

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

9.查找

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

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

（3）哈希表

10.文件

（1）文件的基本概念

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

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