2022年北京交通大學(xué)898數(shù)據(jù)結(jié)構(gòu)碩士研究生考研大綱及參考書(shū)目 正文

898 數(shù)據(jù)結(jié)構(gòu)
1.緒論
（1）數(shù)據(jù)結(jié)構(gòu)基本概念和術(shù)語(yǔ)
（2）算法的特性和設(shè)計(jì)要求
（3）算法時(shí)間復(fù)雜度和空間復(fù)雜度分析
2.線(xiàn)性表
（1）線(xiàn)性表的特點(diǎn)
（2）在順序存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)線(xiàn)性表的各種基本操作
（3）在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)線(xiàn)性表的基本操作（單鏈表，單向循環(huán)鏈表）
（4）線(xiàn)性表的簡(jiǎn)單應(yīng)用3.棧和隊(duì)列
（1）棧和隊(duì)列的操作特點(diǎn)
（2）在順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上實(shí)現(xiàn)棧（順序棧、鏈棧）和隊(duì)列
（循環(huán)隊(duì)列、鏈隊(duì)列）的各種基本操作
（3）棧和隊(duì)列的簡(jiǎn)單應(yīng)用
（4）遞歸程序設(shè)計(jì)的基本方法（分治法、減治法） 4.串
（1）串的基本運(yùn)算的定義
（2）采用定長(zhǎng)數(shù)組和變長(zhǎng)數(shù)組（動(dòng)態(tài)分配）實(shí)現(xiàn)串的各種基本操作5.樹(shù)和二叉樹(shù)
（1）二叉樹(shù)的結(jié)構(gòu)特點(diǎn)和性質(zhì)
（2）二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)（數(shù)組表示法、二叉鏈表、三叉鏈表）
（3）二叉樹(shù)的深度優(yōu)先遍歷（先序、中序和后序）（遞歸算法）
（4）二叉樹(shù)的層次次序遍歷
（5）利用二叉樹(shù)的遍歷求解問(wèn)題
（6）樹(shù)的存儲(chǔ)結(jié)構(gòu)（雙親表示法、孩子表示法、孩子兄弟表示法）
（7）樹(shù)與二叉樹(shù)的相互轉(zhuǎn)換
（8）樹(shù)和森林的遍歷方法
（9）最優(yōu)二叉樹(shù)和哈夫曼編碼6.圖
（1）圖的基本概念
（2）圖的存儲(chǔ)結(jié)構(gòu)（數(shù)組表示法、鄰接表表示法）
（3）圖的深度優(yōu)先搜索和廣度優(yōu)先搜索算法及簡(jiǎn)單應(yīng)用
（4）圖遍歷的應(yīng)用：最小生成樹(shù)﹑最短路徑﹑拓?fù)渑判颟p關(guān)鍵路徑等7.查找
（1）基本概念（靜態(tài)查找，動(dòng)態(tài)查找，關(guān)鍵字，平均查找長(zhǎng)度等）
（2）靜態(tài)查找算法（順序查找、折半查找、索引順序表查找）
（3）二叉排序樹(shù)的建立、插入和刪除過(guò)程
（4）哈希表（概念、構(gòu)造方法和處理沖突的方法） 8.排序
（1）排序的基本概念
（2）插入排序（簡(jiǎn)單插入，折半插入，希爾排序）
（3）交換排序（冒泡排序，快速排序）
（4）選擇排序（簡(jiǎn)單選擇排序，堆排序）
（5）歸并排序（二路歸并）
（6）基數(shù)排序
（7）各種排序方法的比較分析（穩(wěn)定性、時(shí)間和空間性能等）
參考書(shū)目：《數(shù)據(jù)結(jié)構(gòu)(C 語(yǔ)言版)(第 2 版)》，嚴(yán)蔚敏，李冬梅，人民郵電出版社。

北京交通大學(xué)

本文來(lái)源：http://m.zgxindalu.cn/beijingjiaotongdaxue/cankaoshu_470184.html