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

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

北京交通大學

本文來源：http://m.btfokj.cn/beijingjiaotongdaxue/cankaoshu_470184.html