題號：315

　　《數據結構》考試大綱

　　一、考試內容：

　　1.了解數據、數據結構、抽象數據類型以及算法等概念的確切含義，熟悉數據結構的邏輯結構和物理結構，能夠以完整的理論模型定義各種數據結構：

　　2.熟練掌握線性數據結構（包括普通線性表、棧、隊列）的邏輯結構描述方法和物理結構存儲方法（順序映像和隨機映像）的描述方法，熟練掌握及這些線性數據結構上的基本運算操作及其實現方法。并能夠解決應用問題，了解串、數組、和廣義表的邏輯結構和存儲方式，能夠綜合分析線性數據結構各自的特點，并使用線性數據結構解決實際應用問題；

　　3.熟悉樹、二叉樹的定義、性質及存儲方式，重點掌握二叉樹的遍歷和線索化過程，并能靈活運用于實際問題的求解中，掌握樹與二叉樹之間的轉換關系和轉換算法，二叉樹的其它應用問題。掌握二叉排序樹的概念，并能用于解決實際問題。

　　4.熟悉圖的定義和存儲方式，掌握圖的廣度優先和深度優先遍歷算法及其應用，掌握無向圖的連通性、連通分量、生成樹及最小生成樹的算法，掌握有向圖的拓撲排序算法和關鍵路徑以及最短路徑的求解算法。

　　5.掌握靜態查找表、動態查找表的各種查找方法，掌握哈希表的基本概念，以及哈希表的建立和查找方法，以及相關的沖突問題及其解決方法。能夠分析各種查找算法的效率（空間復雜度和時間復雜度）；

　　6.熟練掌握各種內部排序算法（包括簡單選擇排序、插入排序、快速排序、歸并排序、基數排序）的基本思想，能夠分析這些排序算法的時間復雜度和空間復雜度，并能綜合應用這些算法解決實際應用問題并分析各種算法的優、缺點

　　7.結合基本數據結構，了解動態存儲管理的基本思想和方法，能夠使用邊界標識法實現分配和回收策略；

　　8.了解文件的基本概念，掌握幾種類型的文件結構以及文件和管理的基本方法。

　　二、參考書目

　　1.《數據結構》（C語言版）嚴蔚敏等編，清華大學出版社，1992年。

　　2.《數據結構》高宏賓、倪鈴編，西北工業大學出版社，1994年。

　　3.《數據結構與算法基礎》王曉冬編，電子工業出版社，2000年。