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