I 考試的內(nèi)容

一、考試基本要求

1、基本理論知識(shí)

(l)、數(shù)據(jù)結(jié)構(gòu)的基本概念和基本術(shù)語(yǔ)，算法的描述方法和算法分析的基本概念。

(2)、線(xiàn)性表的基本概念、線(xiàn)性表的基本操作以及這些操作分別在順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下的實(shí)現(xiàn)及復(fù)雜度分析。

(3)、棧和隊(duì)列的定義、存儲(chǔ)結(jié)構(gòu)、實(shí)現(xiàn)和典型應(yīng)用。

(4)、串的定義及其基本操作。

(5)、數(shù)組的定義、運(yùn)算和存儲(chǔ)。

(6)、樹(shù)的定義、基本術(shù)語(yǔ)和存儲(chǔ)結(jié)構(gòu)，二叉樹(shù)的定義和性質(zhì)、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及其各種操作，哈夫曼樹(shù)的概念和應(yīng)用。

(7)、圖的定義和術(shù)語(yǔ)、圖的存儲(chǔ)結(jié)構(gòu)及其基本操作。

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

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

2、基本技能

(1)、能用基本數(shù)據(jù)結(jié)構(gòu)及其算法描述、解決實(shí)際的較為簡(jiǎn)單的問(wèn)題。

(2)、能閱讀“類(lèi)C”語(yǔ)言編寫(xiě)的算法，能根據(jù)要求用“類(lèi)C”語(yǔ)言編寫(xiě)算法。

(3)、能分析算法所完成的功能、運(yùn)行結(jié)果和時(shí)間復(fù)雜度。

二、考核知識(shí)點(diǎn)及考核要求

第一章 緒論

一、考核知識(shí)點(diǎn)

1.數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、元素、結(jié)點(diǎn)等基本概念。抽象數(shù)據(jù)類(lèi)型的定義、表示和實(shí)現(xiàn)方法。

2.算法、算法的特性、如何用類(lèi)C語(yǔ)言來(lái)描述算法。

3.算法設(shè)計(jì)的基本要求以及計(jì)算語(yǔ)句頻度和估算算法時(shí)間復(fù)雜度的方法。

二、考核要求

1.識(shí)記：有關(guān)數(shù)據(jù)結(jié)構(gòu)的基本概念，四種基本數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)。

2.理解：四種基本數(shù)據(jù)結(jié)構(gòu)的基本運(yùn)算，算法復(fù)雜度度量的基本概念。

3.應(yīng)用：用類(lèi)C語(yǔ)言描述算法

第二章 線(xiàn)性表

一、 考核知識(shí)點(diǎn)

1.線(xiàn)性表的定義和基本操作。

2.線(xiàn)性表順序存儲(chǔ)結(jié)構(gòu)的表示和基本運(yùn)算。

3.線(xiàn)性表鏈?zhǔn)酱鎯?chǔ)，帶有附加表頭結(jié)點(diǎn)和不帶附加表頭結(jié)點(diǎn)的單鏈表、循環(huán)鏈表和雙向鏈表的表示和查找、插入、刪除等基本操作。

二、考核要求

1.識(shí)記：線(xiàn)性表基本概念、基本運(yùn)算，各種鏈表的表示。

2.理解：順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)的比較，各種鏈表的基本操作算法

第三章 棧和隊(duì)列

一、考核知識(shí)點(diǎn)

1.棧的定義、操作特點(diǎn)，棧的順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)以及入棧、出棧、判空(滿(mǎn))、取棧頂元素等基本操作。

2.隊(duì)列的定義、操作特點(diǎn)，循環(huán)隊(duì)列的存儲(chǔ)、入列、出列、判空(滿(mǎn))、取隊(duì)首元素等操作。

3.棧的應(yīng)用舉例，如：數(shù)制轉(zhuǎn)換、表達(dá)式求值等。

二、考核要求

1.識(shí)記：棧和隊(duì)列的概念、功能、操作特點(diǎn)、主要運(yùn)算。

2.理解：棧和隊(duì)列與一般線(xiàn)性表對(duì)比的特殊性，棧和隊(duì)列的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，循環(huán)隊(duì)列。

3.應(yīng)用：棧和隊(duì)列的常見(jiàn)的使用場(chǎng)合。

第四章 串

一、考核知識(shí)點(diǎn)

1.串的定義、空串的概念。

2.串的基本操作。

3.串的順序存儲(chǔ)結(jié)構(gòu)及在順序存儲(chǔ)結(jié)構(gòu)下基本操作的實(shí)現(xiàn)。

4.串的基本模式匹配算法。

二、考核要求

1.識(shí)記：串的有關(guān)概念。

2.理解：串的基本操作，串的順序存儲(chǔ)結(jié)構(gòu)及其基本操作。

3.應(yīng)用：串的基本操作函數(shù)的使用。

第五章 數(shù)組和廣義表

一、考核知識(shí)點(diǎn)

1.數(shù)組的順序存儲(chǔ)結(jié)構(gòu)。

2.二維數(shù)組的按行存儲(chǔ)及按列存儲(chǔ)和計(jì)算數(shù)組元素的地址計(jì)算公式。

3.三元組表的概念和基本操作。

4.廣義表的定義。

二、考核要求

1.識(shí)記：數(shù)組的順序存儲(chǔ)結(jié)構(gòu)，廣義表的定義。

2.理解：二維數(shù)組的地址計(jì)算，三元組表的表示。

3.應(yīng)用：用三元組表解決稀疏矩陣的存儲(chǔ)問(wèn)題。

第六章 樹(shù)和二叉樹(shù)

一、考核知識(shí)點(diǎn)

1.樹(shù)的定義和術(shù)語(yǔ)。

2.二叉樹(shù)(完全二叉樹(shù)、滿(mǎn)二叉樹(shù))的定義和性質(zhì)、二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)(順序表示法和二叉鏈表表示法)。

3.二叉樹(shù)遍歷算法(先序、中序、后序、層次)。

4.樹(shù)和森林轉(zhuǎn)換為二叉樹(shù)的方法(孩子兄弟表示法)。

5.樹(shù)的路徑長(zhǎng)度、樹(shù)的帶權(quán)路徑長(zhǎng)度、Huffman樹(shù)的構(gòu)造方法。

二、考核要求

1.識(shí)記：樹(shù)的基本概念

2.理解：二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)、遍歷算法，孩子兄弟表示法，樹(shù)的路徑長(zhǎng)度，哈夫曼樹(shù)的構(gòu)造方法

3.應(yīng)用：利用哈夫曼樹(shù)解決一些最優(yōu)化問(wèn)題

第七章 圖

一、考核知識(shí)點(diǎn)

1.圖的定義。

2.圖的基本術(shù)語(yǔ)。

(1)圖及無(wú)向圖、有向圖、網(wǎng)、子圖、連通圖、強(qiáng)連通圖。

(2)頂點(diǎn)的度、入度、出度。

(3)頂點(diǎn)間路徑、路徑長(zhǎng)度、環(huán)。

3.圖的存儲(chǔ)結(jié)構(gòu)

(l)鄰接矩陣 (2)鄰接表(含逆鄰接表)

4.遍歷圖

(l)深度優(yōu)先搜索遍歷圖的算法及其時(shí)間復(fù)雜度。

(2)廣度優(yōu)先搜索遍歷圖的思想及其時(shí)間復(fù)雜度。

5.生成樹(shù)、最小生成樹(shù)的概念。

6.拓?fù)渑判虻姆椒?/p>

7.求最短路徑的算法。

二、考核要求

1.識(shí)記：圖的基本概念和術(shù)語(yǔ)，最小生成樹(shù)、拓?fù)渑判?、最短路徑的概念和算法思想?/p>

2.理解：圖的存儲(chǔ)方式和基于該存儲(chǔ)方式的基本操作(求入度、出度、下一條邊等)

3.應(yīng)用：拓?fù)湫蛄械膽?yīng)用，最短路徑的應(yīng)用。

第八章 動(dòng)態(tài)存儲(chǔ)管理(不要求)

第九章 查找

一、考核知識(shí)點(diǎn)

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

2.靜態(tài)查找表的查找算法及其效率(最壞和平均查找長(zhǎng)度)。

(l)順序查找 (2)折半查找 (3)分塊查找

3.動(dòng)態(tài)查找表

二叉排序樹(shù)定義、構(gòu)造過(guò)程及其查找算法和效率。

4.哈希表

(l)哈希表的特點(diǎn)。(2)構(gòu)造哈希函數(shù)的方法(除留余數(shù)法等)。(3)處理沖突的方法。

二、考核要求

1.識(shí)記：查找的基本概念，靜態(tài)查找表和動(dòng)態(tài)查找表的概念，哈希表的概念

2.理解：各種靜態(tài)查找算法的比較次數(shù)分析;二叉排序樹(shù)的生成過(guò)程和查找算法;哈希函數(shù)的選擇，沖突處理的方法，散列查找的過(guò)程。

3.應(yīng)用：分析各種查找算法的比較次數(shù)。

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

一、考核知識(shí)點(diǎn)

1.排序的目的、分類(lèi)和排序方法的穩(wěn)定性的定義。

2.直接插入排序的思想

3. 快速排序

(1)冒泡排序的算法。 (2)快速排序的思想。

4.選擇排序

(1)簡(jiǎn)單的選擇排序的算法。

(2)堆的定義、堆排序的思想。

5.二路歸并排序的思想。

二、考核要求

1.識(shí)記：直接插入排序、冒泡排序、簡(jiǎn)單選擇排序的思想

2.理解：快速排序、堆排序、二路歸并排序的思想，各種排序方法的穩(wěn)定性、平均比較次數(shù)、平均移動(dòng)次數(shù)的分析。

3.應(yīng)用：用類(lèi)C或者C語(yǔ)言編寫(xiě)直接插入排序、冒泡排序、簡(jiǎn)單選擇排序等排序算法。

第十一章 外部排序(不要求)

第十二章 文件(不要求)

II 考試的形式及試卷結(jié)構(gòu)

1、 考試的形式：采用閉卷筆試的形式?？荚嚂r(shí)間120分鐘，全卷100分。

2、 試卷中各章所占的比例：第一章約占8%，第二、三、四、五章共約占40%，第六章約占20%，第七章約占15%，第九章約占12，第十章約占5%。

3、 試題對(duì)不同能力層次要求的分?jǐn)?shù)比例：識(shí)記約占30%，理解約占40%，應(yīng)用約占30%。

4、 試題難易占分比例：易約占30%，中約占50%，難約占20%。

5、考卷的結(jié)構(gòu)：試題分為客觀(guān)題和主觀(guān)題?？陀^(guān)題一般有填空題、選擇題、名詞解釋、程序填空題等類(lèi)型;主觀(guān)題一般有簡(jiǎn)答題、算法設(shè)計(jì)題等類(lèi)型。

III 參考書(shū)目

主要參考書(shū)：《數(shù)據(jù)結(jié)構(gòu)》(C語(yǔ)言版) 嚴(yán)蔚敏 吳偉民 編著，清華大學(xué)出版社。