湖南師范大學碩士研究生入學考試自命題科目考試大綱

考試科目代碼：885               考試科目名稱：數據結構

一、考試內容及要點

1．了解數據的邏輯結構和存儲結構之間的關系，熟悉抽象數據類型的定義、表示和實現方法，掌握類C語言的書寫規范和輸入、輸出的方式。

2.掌握線性表的邏輯結構定義、抽象數據類型定義和各種存儲結構的描述方法，掌握在線性表的順序存儲結構上實現基本操作。

3.了解棧和隊列的基本概念和結構特性，掌握棧和隊列的順序實現及基本操作。

4.了解串的數據類型定義，掌握串的定長順序存儲結構，掌握串的各種基本操作的實現及應用，了解串的樸素模式匹配算法。

5.理解數組的類型定義和表示方法，掌握特殊矩陣和稀疏矩陣的壓縮存儲方法及運算的實現，理解廣義表的邏輯結構和存儲結構。

6.熟悉二叉樹的定義、性質和存儲結構，理解二叉樹的遍歷和線索化以及遍歷算法的各種描述形式，熟悉樹和森林的定義、存儲結構、樹和森林與二叉樹的轉換、遍歷。

7.熟悉圖的定義和術語，掌握圖的存儲結構（數組表示法、鄰接表），熟悉圖的兩種遍歷策略，了解圖的連通性、拓撲排序和關鍵路徑，掌握兩類求最短路徑問題的解法。

8.了解查找表的各種實現方法（順序表、有序表、樹表和哈希表），理解平均查找長度。

9.掌握各種內部排序方法（插入、交換、選擇）的基本思想、算法特點、排序過程。

二、參考書目

嚴蔚敏、吳偉民 編著，數據結構（C語言版），清華大學出版社，2007年