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