1
2
3
4
考試科目名稱：數據結構 考試科目代碼：[843]
一、考試要求
數據結構講授數據邏輯結構、存儲結構以及操作算法等基本知識的專業核心課程。要求學生理解數據結構、算法的基本概念，掌握三大數據結構(線性表、樹和圖)的邏輯結構、存儲結構以及基本運算算法;掌握常用的查找和排序算法及其性能分析;學會分析數據對象的特征，能夠針對具體應用問題選擇適當的數據結構及相應算法，并掌握算法時間空間分析的技巧和復雜程序設計基本技能。
二、考試內容
1.緒論
2 數據結構的基礎概念(數據、數據元素、數據對象、數據結構、數據類型、抽象數據類型)
2 數據結構的內容(邏輯結構、存儲結構、運算集合)
2 算法及算法的性能評價(語句頻度、時間復雜度、空間復雜度)
2 數據結構與C語言表示
2.線性表
2 線性表的概念及其抽象數據類型定義
2 線性表的順序存儲結構及順序表的基本運算
2 線性表的鏈式存儲
1) 單鏈表及單鏈表的基本運算
2) 循環鏈表
3) 雙向鏈表
4) 靜態鏈表
2 線性表的應用——一元多項式的表示及相加
2 順序表與鏈表的綜合比較
3.限定性線性表——棧和隊列
2 棧的定義
2 棧的表示及實現(順序棧、雙向棧、鏈式棧)
2 棧的應用
2 棧與遞歸的實現
2 隊列的定義
2 隊列的表示及實現(順序隊列、循環隊列、鏈式隊列)
2 隊列的應用
4.串
2 串的基本概念
2 串的存儲實現(定長順序串、堆串、塊鏈串)
2 串的簡單模式匹配算法Brute-Force(布魯特-福斯)算法
2 串的應用
5.數組與廣義表
2 數組的定義
2 數組的順序存儲與實現
2 特殊矩陣的壓縮存儲(三角矩陣、帶狀矩陣、稀疏矩陣)
2 廣義表的概念
2 廣義表的存儲結構
2 廣義表的操作實現
6.樹與二叉樹
2 樹的定義及基本術語
2 二叉樹的定義與基本操作
2 二叉樹的性質
2 二叉樹的存儲結構(二叉鏈表)
2 二叉樹的遍歷及線索化
1) 二叉樹的遍歷
2) 遍歷算法的應用
3) 基于棧的遞歸消除
4) 線索二叉樹
5) 由遍歷序列確定二叉樹
2 樹的存儲結構
2 樹、森林與二叉樹的相互轉換
2 樹和森林的遍歷
2 哈夫曼樹及其應用
1) 哈夫曼的概念和建立算法
2) 哈夫曼編碼的算法
7.圖
2 圖的定義與基本術語
2 圖存儲結構
1) 鄰接矩陣
2) 鄰接表
3) 十字鏈表
4) 鄰接多重表
2 圖的遍歷
1) 深度優先搜索
2) 廣度優先搜索
2 圖的應用
1) 圖的連通性問題(無向圖的連通分量、圖中兩個頂點之間的簡單路徑、圖的生成樹與最小生成樹、普里姆算法、克魯斯卡爾算法)
2) 有向無環圖的應用(拓撲排序、關鍵路徑)
3) 最短路徑(迪杰斯特拉算法、佛羅伊德算法)
8.查找
2 查找的基本概念
2 基于線性表的查找方法
1) 順序查找法
2) 折半查找法
3) 分塊查找法
2 基于樹的查找方法
1) 二叉排序樹
2) 平衡二叉排序樹
3) B樹
2 計算式查找法——哈希法
1) 哈希函數的構造方法
2) 處理沖突的方法
3) 哈希表的查找
4) 哈希法性能分析
9.內部排序
2 排序的基本概念
2 插入類排序
1) 直接插入排序
2) 折半插入排序
3) 希爾排序
2 交換類排序
1) 冒泡排序
2) 快速排序
2 選擇類排序
1) 簡單選擇排序
2) 樹形選擇排序
3) 堆排序
2 歸并排序
2 分配類排序
1) 多關鍵字排序
2) 鏈式基數排序
3) 基數排序的順序表實現
2 各種排序方法綜合比較
10.算法設計與分析
2 遞歸與分治(遞歸方法設計、分治法)
2 回溯法
2 分支限界法
2 貪心算法
2 動態規劃法
參考書目：
《數據結構-C語言描述》，耿國華，高等教育出版社，2015年。
《數據結構與算法》，趙仲孟，高等教育出版社，2016年。
原標題：2025年西安工程大學碩士研究生入學考試大綱
文章來源：https://dxxy.xpu.edu.cn/info/1381/6644.htm
