622       《數據結構》考試大綱

一、考試的總體要求

考試內容涉及數據結構的邏輯結構和物理結構的基本概念

以及各種結構的基本概念、算法分析計算等方面，要求考生對相

關概念及結構有較深入的了解，熟練掌握各種數據結構的基本原

理和應用，并具有綜合運用所學知識分析問題和解決問題的能力。

二、考試的內容

1.  緒論

27

1)   數據、數據元素、數據結構、數據類型、抽象數據類型的概念；

2)   什么是數據結構；

3)   算法、算法描述與算法分析的概念；

2.  線性表

1)   順序表的邏輯結構定義及基本操作；

2)   順序表在順序存儲結構和鏈式存儲結構中基本操作的實

現；

3)   鏈表的邏輯結構定義、基本操作；

4)   鏈表在順序存儲結構和鏈式存儲結構中基本操作的實現；

5)   線性表的一元多項式及實現稀疏多項式的運算；

3.  棧和隊列

1)   棧的結構特性、基本操作及在順序存儲結構和鏈式存儲結構上基本操作的實現；

2)   隊列的結構特性、基本操作及在順序存儲結構和鏈式存儲結構上基本操作的實現；

3)   棧和隊列的基本應用；

4)   棧和隊列遞歸算法的設計；

4.  串（考查）

掌握串的邏輯結構定義、串的基本運算及其實現;串的匹配算法。

5.  數組和廣義表（考查）

掌握數組的邏輯結構定義和存儲方法；掌握特殊矩陣和稀疏

矩陣的壓縮存儲方法；掌握廣義表的邏輯結構和存儲結構以及廣

義表運算的遞歸算法。

6.  樹和二叉樹

28

1)   樹的基本概念；二叉樹的定義、性質、存儲表示；

2)   二叉樹的遍歷；線索二叉樹；森林和二叉樹的相互轉換；

3)   樹的應用，哈夫曼樹及哈夫曼編碼。

7.  圖

1)  圖的基本概念、存儲表示（鄰接矩陣、鄰接表、十字鏈表，鄰接多重表）；

2)   圖的遍歷；

3)   圖的連通性問題；

4)   圖的應用，最小生成樹、拓撲排序、關鍵路徑、最短路

徑；

8.  動態存儲管理（考查）

了解內存的“分配”和“回收”策略；可利用空間表及分配方法；邊界標識法和伙伴系統。

9.  查找

1)   什么是靜態查找表、動態查找表、哈希表；

2)   線性表的查找、二叉排序樹、哈希表的查找；

10.  內部排序

1)   排序的概念及各種排序的基本思想和算法分析；

2)   插入排序、快速排序（交換排序）、選擇排序、歸并排序、基數排序、內排序的比較 。

三、考試題型及比例

單項選擇題：20%左右

填空題：15%左右

判斷對錯題：15%左右

綜合應用題 25%左右

算法設計題 25%左右

29

四、考試形式及時間

考試形式為閉卷筆試，試卷總分值為 150 分，考試時間為三

小時。

五、主要參考教材

1)《數據結構》（C 語言版）（第 2 版） (  嚴蔚敏、吳偉民

編著,      清華大學出版社 2015.2)

2)《數據結構精講與習題詳解》（C 語言版）（第 2 版）殷

人昆      清華大學出版社，2018.01.01