《數據結構》考試大綱

一、考試內容概述

(一)基本理論知識

1．數據結構的基本概念和基本術語，算法的描述，算法的時間復雜度和空間復雜度分析。

2．線性表的定義，在線性表上常進行的基本操作，這些操作在順序和鏈式存儲結構下的實現及復雜度分析。

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

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

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

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

7．圖的定義和常用術語、圖的存儲結構及其遍歷操作，求最小生成樹、最短路徑的算法，拓撲排序。

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

9．各種內排序算法的基本思想和算法的時間復雜度分析，不同排序方法的比較。

(二)基本技能

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

2．能分析算法所實現的功能、運行結果和時間、空間復雜度。

3．能根據要求用類C語言編寫一些經典、常用算法。

二、考試形式

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

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

考試時間：120分鐘。

三、試題難易程度分布

較易試題 約占50％

中等試題 約占30％

較難試題 約占20％

四、題型及題型分值分布

單選題 約占20％

多選題 約占10％

填空題 約占15％

算法閱讀題 約占10％

綜合題 約占30％

程序設計題 約占15％

五、內容比例

第一章 緒論 約占5％

第二章線性表 約占10％

第三章 棧和隊列 約占15％

第四章 串 約占5％

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

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

4．了解二叉樹線索化的實質及線索化的過程。

5．了解樹的存儲結構，理解樹和森林轉換為二叉樹的方法。

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

第七章 圖

1．了解圖的定義。

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

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

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

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

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

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

第八章 查 找

1．了解查找、關鍵字、平均查找長度等概念。

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

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

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

第九章 內部排序

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

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

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

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

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

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