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

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

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

1．?dāng)?shù)據(jù)結(jié)構(gòu)的基本概念和基本術(shù)語，算法的描述，算法的時(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ù)語和存儲(chǔ)結(jié)構(gòu)，二叉樹的定義和性質(zhì)、二叉樹的存儲(chǔ)結(jié)構(gòu)及其各種操作，Huffman和Huffman編碼。

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

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

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

(二)基本技能

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

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

3．能根據(jù)要求用類C語言編寫一些經(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％

第六章 樹和二叉樹 約占15％

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

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

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

第七章 圖

1．了解圖的定義。

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

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

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

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

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

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

第八章 查 找

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

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

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

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

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

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

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

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

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

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

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