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

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

二、考試形式 閉卷 筆試

三、考試內容

1. 數據結構概述

1.1 掌握數據結構的基本概念和術(shù)語(yǔ)，包括數據、數據元 素、數據項、數據對象、數據結構、數據的邏輯結構、數據的 存儲結構、數據類(lèi)型、抽象數據類(lèi)型。

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

2.線(xiàn)性表

2.1 理解線(xiàn)性表的基本概念

2.2 掌握線(xiàn)性表的順序存儲結構及其算法實(shí)現

2.3 掌握線(xiàn)性表的鏈式存儲結構及其算法實(shí)現，包括單鏈 表、雙向鏈表、循環(huán)鏈表

3.棧和隊列

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

3.2 棧的應用，理解函數調用、遞歸的實(shí)現過(guò)程、能夠利 用棧解決表達式求值、括號匹配等問(wèn)題;

3.2 隊列，掌握隊列及其特性，理解隊列的抽象數據類(lèi)型， 掌握循環(huán)隊列及其基本運算實(shí)現、鏈隊列及其基本運算實(shí)現

3.2.5 隊列的應用，能夠利用隊列解決銀行排隊、二叉樹(shù) 層序遍歷、圖的廣度優(yōu)先遍歷等問(wèn)題;

4.串、數組和廣義表

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

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

4.3 廣義表的基本概念 5.樹(shù)和二叉樹(shù)

5.1 樹(shù)的定義及基本術(shù)語(yǔ)

5.2 二叉樹(shù)，掌握二叉樹(shù)的定義、二叉樹(shù)的性質(zhì)以及二叉 樹(shù)的存儲結構

5.3 遍歷二叉樹(shù)，包括二叉樹(shù)的遞歸遍歷、二叉樹(shù)的非遞 歸遍歷

5.4 二叉樹(shù)遍歷算法的應用

5.5 線(xiàn)索二叉樹(shù)，掌握線(xiàn)索二叉樹(shù)的定義和存儲結構、二

叉樹(shù)的線(xiàn)索化、線(xiàn)索二叉樹(shù)中結點(diǎn)的前驅和后繼查找方法

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

5.7 哈夫曼樹(shù)及其應用 6.圖

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

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

6.3 圖的遍歷，掌握圖的深度優(yōu)先和圖的廣度優(yōu)先搜索

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

7.排序

7.1 理解排序的基本概念

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

8. 查找

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

8.2 靜態(tài)查找表，掌握順序表的查找、有序表的折半查找

8.3 動(dòng)態(tài)查找表，掌握二叉排序樹(shù)(包括二次排序樹(shù)的定

義和特點(diǎn)、二叉排序樹(shù)的創(chuàng )建、插入、刪除結點(diǎn))，掌握平衡二 叉樹(shù)的定義

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

1.周桂紅等編，《數據結構》，天津：南開(kāi)大學(xué)出版社，2016 年