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

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

北京交通大學

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