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

考試科目代碼：[ 865]               考試科目名稱：數據結構

一、考試內容及要點

（一）緒論：

１．熟悉各名詞、術語的含義，掌握基本概念，特別是數據的邏輯結構和存儲結構之間的關系；

２．了解抽象數據類型的定義、表示和實現方法；

３．熟悉類C語言的書寫規范，特別要注意值調用和引用調用的區別，輸入、輸出的方式以及錯誤處理方式；

４．理解算法五個要素的確切含義；

５．掌握計算語句頻度和估算算法時間復雜度的方法。

（二）線性表：

１．線性表的邏輯結構定義、抽象數據類型定義和各種存儲結構的描述方法；

２．在線性表的兩類存儲結構（順序存 儲和鏈式存儲）上實現基本操作；

３．一元多項式的抽象數據類型定義、表示及加法的實現。

（三）棧和隊列：

１．棧和隊列的結構特性；

２．在兩種存儲結構上如何實現棧和隊列的基本操作和棧和隊列在程序設計中的應用以及如何利用堆棧去模擬遞歸程序的運行。

（四）串：

１．串的數據類型定義；

２．串的三種存儲表示：定長順序存儲結構、塊鏈存儲結構和堆分配存儲結構；

３．串的各種基本操作的實現及應用；串的模式匹配算法。

（五）數組和廣義表：

１．數組的類型定義和表示方法；

２．特殊矩陣和稀疏矩陣的壓縮存儲方法及運算的實現；

３．廣義表的邏輯結構和存儲結構、m元多項式的廣義表表示以及廣義表的操作的遞歸算法舉例 。

（六）樹和二叉樹：

１．二叉樹的定義、性質和存儲結構；

２．二叉樹的遍歷和線索化以及遍歷算法的各種描述形式；

３．樹和森林的定義、存儲結構、樹和森林與二叉樹的轉換、遍歷；

４．樹的多種應用；

５．平衡二叉樹、平衡二叉排序樹的 定義、性質極其應用。

６．本章是該課程的重點內容之一。

（七）圖：

１．圖的定義和術語；

２．圖的四種存儲結構：數組表示法、鄰接表、十字鏈表和鄰接多重表；

３．圖的兩種遍歷策略：深度優先搜索和廣度優先搜索；

４．圖的連通性：連通分量和最小生成樹；

５．拓撲排序和關鍵路徑；兩類求最短路徑問題的解法。

（八）查找：

１．討論查找表（包括靜態查找表和動態查找表）的各種實現方法：順序表、有序表、樹表和哈希表；

２．關于衡量查找表的主要操作——查找的查找效率的平均查找長度的討論。

（九）內部排序：

１．討論比較各種內部排序方法，插入排序、交換排序、選擇排序、歸并排序和基數排序的基本思想、算法特點、排序過程以及它們的時間復雜度分析。

２．在每類排序方法中，從簡單方法入手，重點討論性能先進的高效方法（如，插入排序類中的希爾排序、交換排序類中的快速排序、選擇排序類中的堆排序等）。

二、參考書目

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