一、考試要求：
本課程要求掌握數據結構的基本理論知識，常用數據結構及 對應的基本算法， 以及數據結構的程序實現技能。內容包括線性 表、棧、隊列、樹、圖等常見結構的邏輯結構、存儲結構和對應 的常用基本算法， 以及查找和排序的基本概念和常用算法。會做 簡單的算法分析， 包括算法的時間代價和空間代價。會分析研究 計算機加工的數據結構的特性， 以便為應用涉及的數據選擇適當 的邏輯結構、存儲結構及相應的算法。
課程考試中既測試對基本知識、基本理論的掌握程度，又測 試對基本知識與基本理論的靈活運用能力。
二、考試要點：
1.緒論
(1) 數據結構基本概念和術語;
(2) 算法描述的方法;
(3)邏輯結構、存儲結構及數據運算三方面的要領及相互 關系;
(4) 算法復雜度的分析方法。
2.線性表
(1) 線性表的邏輯特性;
(2) 兩類不同的存儲結構(順序和鏈式存儲結構) 的異同;
(3) 單鏈表、循環鏈表、雙向鏈表的特點;
(4) 線性表在順序存儲結構中實現基本運算(查找、插入、 刪除、合并等)的算法及分析;
(5) 線性表在鏈式存儲結構中實現基本運算(查找、插入、 刪除、合并等)的算法及分析;
(6)用時間和空間復雜度分析線性表的特點。
3.棧和隊列
(1) 棧和隊列的基本概念;
(2) 棧和隊列在存儲結構上的基本運算的實現;
(3) 循環隊列中對邊界條件的處理;
(4) 棧的典型應用并能編程實現。
4.串
(1) 串的邏輯結構定義;
(2) 串的基本運算及其實現;
(3) 串的堆分配存儲結構;
(4) 串的模式匹配算法。
5.數組和廣義表
(1) 數組的邏輯結構和存儲結構;
(2) 數組在以行為主的存儲結構中地址的計算方法;
(3) 特殊矩陣的壓縮存儲方式及下標變換公式;
(4) 稀疏矩陣壓縮存儲方法的特點和適用范圍，三元組表 示的稀疏矩陣進行矩陣運算時采用的處理方法。
6.樹和二叉樹
(1) 樹的定義和基本術語;
(2) 二叉樹的定義;
(3) 二叉樹的結構特性及相應的證明方法;
(4) 二叉樹的各種存儲結構特點及使用范圍;
(5) 二叉樹的各種遍歷算法;
(6) 線索二叉樹的定義;
(7) 樹的存儲結構;
(8) 樹和二叉樹的轉換方法;
(9) 最優二叉樹的特性;
(10) 建立最優二叉樹和實現 Huffman 編碼的方法。
7.圖
(1) 圖的基本概念;
(2) 圖的兩種常用的存儲結構特點及實現;
(3) 圖的兩類遍歷算法： 深度優先、廣度優先;
(4) 圖的應用：最小生成樹、最短路徑的算法實現。
8.查找
(1) 靜態查找表和動態查找表的定義;
(2)順序查找、二分查找以及塊查找的基本思想和算法實 現;
(3) 二叉排序樹的概念及查找過程;
(4)哈希查找的基本思想、哈希函數的構造方法、處理沖 突的方法;
(5) 各種算法的時間性能(平均查找長度)分析。
9.排序
(1) 排序的基本概念、排序算法的穩定性;
(2)冒泡排序、插入排序、選擇排序、快速排序、希爾排
序和堆排序的基本思想、排序過程、算法實現、時間和空間性能 的比較分析結論;
(3) 歸并排序和基數排序的基本思想。
三、參考書目
《數據結構(C 語言版) (第2 版) 》， 嚴蔚敏、李冬梅、 吳偉民，人民郵電出版社，2016 年， ISBN：9787115379504
