一、考試基本要求及適用范圍概述

要求考生掌握數據結構的基本概念和術語;掌握包括線性表、 棧和隊列、 串、數組和特殊矩陣、樹和二叉樹以及圖在內的各種數 據結構的基本概念、邏輯結構與存儲結構， 以及在這些結構的基礎 上的相關算法實現;能夠針對具體問題選擇合適的數據結構抽象建 模，設計合適的存儲結構，并采用 C/C++、Java、Python 或類 C 語 言描述等程序設計語言基本運算的算法實現;掌握各種查找、排序 算法;能夠對基本算法進行復雜度分析。適用于人工智能專業。

二、考試形式 閉卷 筆試

三、考試內容

1. 數據結構概述

1.1 掌握數據結構的基本概念和術語，包括數據、數據元 素、數據項、數據對象、數據結構、數據的邏輯結構、數據的 存儲結構、數據類型、抽象數據類型。

1.2 算法和算法分析，掌握算法特性、算法的時間復雜度 分析、算法的空間復雜度分析

2.線性表

2.1 理解線性表的基本概念

2.2 掌握線性表的順序存儲結構及其算法實現

2.3 掌握線性表的鏈式存儲結構及其算法實現，包括單鏈 表、雙向鏈表、循環鏈表

3.棧和隊列

3.1 棧，掌握棧及其特性，理解棧的抽象數據類型，掌握 順序棧及其基本算法實現、鏈棧及其基本算法實現

3.2 棧的應用，理解函數調用、遞歸的實現過程、能夠利 用棧解決表達式求值、括號匹配等問題;

3.2 隊列，掌握隊列及其特性，理解隊列的抽象數據類型， 掌握循環隊列及其基本運算實現、鏈隊列及其基本運算實現

3.2.5 隊列的應用，能夠利用隊列解決銀行排隊、二叉樹 層序遍歷、圖的廣度優先遍歷等問題;

4.串、數組和廣義表

4.1 串，掌握串的基本概念及操作、 串的定長順序存儲及 基本運算

4.2 數組，掌握數組的定義及操作、數組的順序存儲、特 殊矩陣的壓縮存儲、隨機稀疏矩陣的壓縮存儲

4.3 廣義表的基本概念 5.樹和二叉樹

5.1 樹的定義及基本術語

5.2 二叉樹，掌握二叉樹的定義、二叉樹的性質以及二叉 樹的存儲結構

5.3 遍歷二叉樹，包括二叉樹的遞歸遍歷、二叉樹的非遞 歸遍歷

5.4 二叉樹遍歷算法的應用

5.5 線索二叉樹，掌握線索二叉樹的定義和存儲結構、二

叉樹的線索化、線索二叉樹中結點的前驅和后繼查找方法

5.6 樹和森林，掌握樹的存儲、森林的存儲結構、樹和森 林的遍歷、樹、森林和二叉樹的相互轉換

5.7 哈夫曼樹及其應用 6.圖

6.1 掌握圖的基本概念，包括圖、無向圖、有向圖、完全 圖、圖的連通性等

6.2 圖的存儲結構，掌握圖的鄰接矩陣和鄰接表表示

6.3 圖的遍歷，掌握圖的深度優先和圖的廣度優先搜索

6.4 圖的基本算法，掌握最小生成樹算法(Kruskal 算法 和 Prim 算法)、求某個頂點(單源點)到其余各頂點的最短路 徑(Dijkstra 算法)、拓撲排序、關鍵路徑

7.排序

7.1 理解排序的基本概念

7.2 排序算法，掌握插入排序(包括直接插入排序、希爾 排序)、交換排序(包冒泡排序、快速排序)、選擇排序(包括 簡單選擇排序、堆排序)、歸并排序、基數排序等基本排序算法 及其復雜度分析

8. 查找

8.1 理解查找的基本概念、查找成功和查找失敗的平均查 找長度

8.2 靜態查找表，掌握順序表的查找、有序表的折半查找

8.3 動態查找表，掌握二叉排序樹(包括二次排序樹的定

義和特點、二叉排序樹的創建、插入、刪除結點)，掌握平衡二 叉樹的定義

8.4 哈希表，掌握哈希函數的確定方法、處理沖突的方法 四、主要參考教材

1.周桂紅等編，《數據結構》，天津：南開大學出版社，2016 年