一、考試内容概述

　　(一)基本理(lǐ)論知識

　　1．數據結構的基本概念和基本術語，算法的描述，算法的時間複雜度和空間複雜度分(fēn)析。

　　2．線(xiàn)性表的定義，在線(xiàn)性表上常進行的基本操作(zuò)，這些操作(zuò)在順序和鏈式存儲結構下的實現及複雜度分(fēn)析。

　　3．棧和隊列的定義、特點、表示方法和實現。

　　4．串的定義及其基本操作(zuò)。

　　5．數組的定義、運算和存儲、稀疏矩陣的壓縮存儲、廣義表的定義和基本操作(zuò)。

　　6．樹的定義、基本術語和存儲結構，二叉樹的定義和性質(zhì)、二叉樹的存儲結構及其各種操作(zuò)，Huffman和Huffman編碼。

　　7．圖的定義和常用(yòng)術語、圖的存儲結構及其遍曆操作(zuò)，求最小(xiǎo)生成樹、最短路徑的算法，拓撲排序。

　　8．各種查找方法的算法、适用(yòng)範圍及時間複雜度的分(fēn)析。

　　9．各種内排序算法的基本思想和算法的時間複雜度分(fēn)析，不同排序方法的比較。

　　(二)基本技(jì )能(néng)

　　1．能(néng)閱讀用(yòng)類C語言編寫的算法。

　　2．能(néng)分(fēn)析算法所實現的功能(néng)、運行結果和時間、空間複雜度。

　　3．能(néng)根據要求用(yòng)類C語言編寫一些經典、常用(yòng)算法。

　　二、考試形式

　　考試采用(yòng)閉卷、筆(bǐ)答(dá)的考試方式。

　　滿分(fēn)：150分(fēn)(單科(kē)成績)。

　　考試時間：120分(fēn)鍾。

　　三、試題難易程度分(fēn)布

　　較易試題    約占50％

　　中(zhōng)等試題    約占30％

　　較難試題    約占20％

　　四、題型及題型分(fēn)值分(fēn)布

　　單選題    約占20％

　　多(duō)選題    約占10％

　　填空題    約占15％

　　算法閱讀題    約占10％

　　綜合題    約占30％

　　程序設計題    約占15％

　　五、内容比例

　　第一章  緒論    約占5％

　　第二章線(xiàn)性表    約占10％

　　第三章  棧和隊列    約占15％

　　第四章  串    約占5％

　　第五章  數組和廣義表    約占5％

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

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

　　5．了解樹的存儲結構，理(lǐ)解樹和森林轉換為(wèi)二叉樹的方法。

　　6．掌握樹的路徑長(cháng)度和樹的帶權路徑長(cháng)度的計算方法， Huffman樹的構造方法和Huffman編碼。

　　第七章  圖

　　1．了解圖的定義。

　　2.了解圖的基本術語：圖及無向圖、有(yǒu)向圖、網、子圖、連通圖、強連通圖、頂點的度、入度、出度、頂點問路徑、路徑長(cháng)度、環。

　　3．理(lǐ)解圖的兩種存儲結構：鄰接矩陣和鄰接表(含逆鄰接表)。

　　4．掌握遍曆圖的兩種方法：深度優先搜索和廣度優先搜索遍曆圖的算法及其時間複雜度。

　　5．理(lǐ)解生成樹、最小(xiǎo)生成樹的概念，掌握最小(xiǎo)生成樹的構造過程(Prim算法和Kmskal算法)及其時間複雜度。

　　6．掌握拓撲排序的方法及最短路徑的計算。

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

　　第八章  查找

　　1．了解查找、關鍵字、平均查找長(cháng)度等概念。

　　2．靜态查找表：掌握順序查找(設哨兵)、折半查找算法及其效率(最壞和平均查找長(cháng)度)分(fēn)析，了解分(fēn)塊查找算法及其效率分(fēn)析。

　　3．動态查找表：掌握二叉排序樹的定義、構造過程及其查找算法和效率分(fēn)析，掌握平衡二叉樹的定義和其構造過程。

　　4．了解哈希表的特點，掌握構造哈希函數的方法(除留餘數法等)，掌握處理(lǐ)沖突的方法及效率分(fēn)析。

　　第九章  内部排序

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

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

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

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

　　5．理(lǐ)解歸并排序的思想、基數排序的思想及特點。

　　6．了解各種内部排序方法的比較。