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

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

北京交通大學(xué)

本文來源：http://www.zhongzhouzhikong.com/beijingjiaotongdaxue/cankaoshu_470184.html