Ⅰ考試形式

一、試卷滿分及考試時間

本試卷滿分為150分，考試時間為180分鐘

二、答題方式

答題方式為閉卷、筆試

Ⅱ考查目標

1.理解數據結構的基本概念；掌握數據結構的邏輯結構、存儲結構及

其差異，以及各種基本操作的實現。mcm財布

2.掌握基本的數據處理原理和方法的基礎上，能夠對算法進行設計與

分析。

3.能夠選擇合適的數據結構和方法進行問題求解。

一、基本概念和術語

（一）數據元素、數據結構、抽象數據類型等概念

（二）算法設計的基本要求

（三）語句的頻度和估算時間復雜度

二、線性表

（一）線性表的定義和基本操作

2

（二）線性表的實現

1．順序存儲結構

2．鏈式存儲結構

3．線性表的應用

三、棧、隊列和數組

（一）棧和隊列的基本概念

（二）棧和隊列的順序存儲結構

（三）棧和隊列的鏈式存儲結構

（四）棧和隊列的應用

（五）特殊矩陣的壓縮存儲

四、樹與二叉樹棧

（一）樹的概念

（二）二叉樹

1．二叉樹的定義及其主要特征

2．二叉樹的順序存儲結構和鏈式存儲結構

3．二叉樹的遍歷

4．線索二叉樹的基本概念和構造

5．二叉排序樹

6．平衡二叉樹

（三）樹、森林

1．樹的存儲結構

2．森林與二叉樹的轉換

3．樹和森林的遍歷

（四）樹的應用

3

1．特價類問題

2．哈夫曼(Huffman)樹和哈夫曼編碼

五、圖

（一）圖的概念

（二）圖的存儲結構及基本操作

1.鄰接矩陣

2.鄰接表

（三）圖的遍歷

1．深度優先搜索

2．廣度優先搜索

（四）圖的基本應用

1．最小（代價）生成樹

2．拓撲排序

3．關鍵路徑

4．最短路徑

六、查找

（一）查找的基本概念

（二）順序查找法

（三）折半查找法

（四）B-樹

（五）散列(Hash)表及其查找

（六）查找算法的分析及應用

七、內部排序

（一）排序的基本概念

4

（二）插入排序

1．直接插入排序

2．折半插入排序

（三）氣泡排序（bubblesort）

（四）簡單選擇排序

（五）希爾排序（shellsort）

（六）快速排序

（七）堆排序

（八）二路歸并排序(mergesort)

（九）基數排序

（十）各種內部排序算法的比較

（十一）內部排序算法的應用

Ⅲ特別推薦

1．嚴蔚敏、吳偉民,數據結構（C語言版）,清華大學出版社出版

2．嚴蔚敏,吳偉民,《數據結構習題解析》,清華大學出版社出版