《數(shù)據(jù)結(jié)構(gòu)》考試大綱

一、考試內(nèi)容概述

(一)基本理論知識(shí)

1．?dāng)?shù)據(jù)結(jié)構(gòu)的基本概念和基本術(shù)語(yǔ)，算法的描述，算法的時(shí)間復(fù)雜度和空間復(fù)雜度分析。

2．線性表的定義，在線性表上常進(jìn)行的基本操作，這些操作在順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的實(shí)現(xiàn)及復(fù)雜度分析。

3．棧和隊(duì)列的定義、特點(diǎn)、表示方法和實(shí)現(xiàn)。

4．串的定義及其基本操作。

5．?dāng)?shù)組的定義、運(yùn)算和存儲(chǔ)、稀疏矩陣的壓縮存儲(chǔ)、廣義表的定義和基本操作。

6．樹(shù)的定義、基本術(shù)語(yǔ)和存儲(chǔ)結(jié)構(gòu)，二叉樹(shù)的定義和性質(zhì)、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及其各種操作，Huffman和Huffman編碼。

7．圖的定義和常用術(shù)語(yǔ)、圖的存儲(chǔ)結(jié)構(gòu)及其遍歷操作，求最小生成樹(shù)、最短路徑的算法，拓?fù)渑判颉?/p>

8．各種查找方法的算法、適用范圍及時(shí)間復(fù)雜度的分析。

9．各種內(nèi)排序算法的基本思想和算法的時(shí)間復(fù)雜度分析，不同排序方法的比較。

(二)基本技能

1．能閱讀用類C語(yǔ)言編寫的算法。

2．能分析算法所實(shí)現(xiàn)的功能、運(yùn)行結(jié)果和時(shí)間、空間復(fù)雜度。

3．能根據(jù)要求用類C語(yǔ)言編寫一些經(jīng)典、常用算法。

二、考試形式

考試采用閉卷、筆答的考試方式。

滿分：150分(單科成績(jī))。

考試時(shí)間：120分鐘。

三、試題難易程度分布

較易試題 約占50％

中等試題 約占30％

較難試題 約占20％

四、題型及題型分值分布

單選題 約占20％

多選題 約占10％

填空題 約占15％

算法閱讀題 約占10％

綜合題 約占30％

程序設(shè)計(jì)題 約占15％

五、內(nèi)容比例

第一章 緒論 約占5％

第二章線性表 約占10％

第三章 棧和隊(duì)列 約占15％

第四章 串 約占5％

第五章 數(shù)組和廣義表 約占5％

第六章 樹(shù)和二叉樹(shù) 約占15％

4．了解二叉樹(shù)線索化的實(shí)質(zhì)及線索化的過(guò)程。

5．了解樹(shù)的存儲(chǔ)結(jié)構(gòu)，理解樹(shù)和森林轉(zhuǎn)換為二叉樹(shù)的方法。

6．掌握樹(shù)的路徑長(zhǎng)度和樹(shù)的帶權(quán)路徑長(zhǎng)度的計(jì)算方法， Huffman樹(shù)的構(gòu)造方法和Huffman編碼。

第七章 圖

1．了解圖的定義。

2.了解圖的基本術(shù)語(yǔ)：圖及無(wú)向圖、有向圖、網(wǎng)、子圖、連通圖、強(qiáng)連通圖、頂點(diǎn)的度、入度、出度、頂點(diǎn)問(wèn)路徑、路徑長(zhǎng)度、環(huán)。

3．理解圖的兩種存儲(chǔ)結(jié)構(gòu)：鄰接矩陣和鄰接表(含逆鄰接表)。

4．掌握遍歷圖的兩種方法：深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷圖的算法及其時(shí)間復(fù)雜度。

5．理解生成樹(shù)、最小生成樹(shù)的概念，掌握最小生成樹(shù)的構(gòu)造過(guò)程(Prim算法和Kmskal算法)及其時(shí)間復(fù)雜度。

6．掌握拓?fù)渑判虻姆椒白疃搪窂降挠?jì)算。

7．掌握求最短路徑問(wèn)題的Dijkstra算法，了解Floyd算法。

第八章 查 找

1．了解查找、關(guān)鍵字、平均查找長(zhǎng)度等概念。

2．靜態(tài)查找表：掌握順序查找(設(shè)哨兵)、折半查找算法及其效率(最壞和平均查找長(zhǎng)度)分析，了解分塊查找算法及其效率分析。

3．動(dòng)態(tài)查找表：掌握二叉排序樹(shù)的定義、構(gòu)造過(guò)程及其查找算法和效率分析，掌握平衡二叉樹(shù)的定義和其構(gòu)造過(guò)程。

4．了解哈希表的特點(diǎn)，掌握構(gòu)造哈希函數(shù)的方法(除留余數(shù)法等)，掌握處理沖突的方法及效率分析。

第九章 內(nèi)部排序

1．了解排序的目的、分類和排序方法的穩(wěn)定性的定義。

2．插人排序：掌握直接插入、折半插入排序算法和希爾排序的思想。

3．快速排序：掌握起泡排序的算法和快速排序的思想。

4．選擇排序：掌握簡(jiǎn)單的選擇排序的算法和堆的定義、堆排序的思想。

5．理解歸并排序的思想、基數(shù)排序的思想及特點(diǎn)。

6．了解各種內(nèi)部排序方法的比較。