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

10101 數據結構
參考書目：嚴蔚敏、吳偉民等《數據結構》（C 版）、清華大學出版社
1.概述
（1）數據結構的基本概念（理解）
（2）算法的五個特性（理解）
（3）計算語句頻度和估算算法時間復雜度和空間復雜度的方法 （掌握）
（4）抽象數據類型（理解）
2.線性表
（1）線性表的邏輯結構（理解）
（2）線性表的順序存儲結構和鏈式存儲結構（掌握）
（3）線性表在順序結構上實現基本操作的方法（掌握）
（4）線性表在鏈式結構上實現基本操作的方法 （掌握）
（5）從時間、空間復雜度的角度比較線性表兩種存儲結構的不同特點及其適用  場合（理解）
3.棧和隊列
（1）棧的特點（理解）
（2）在順序存儲結構上棧的基本操作的實現（掌握）
（3）在鏈式存儲結構上棧的基本操作的實現（掌握）
（4）遞歸算法中棧的作用（理解）
（5）棧的典型應用實例（掌握）
（6）隊列的特點（理解）
（7）在順序存儲結構上循環(huán)隊列基本操作的實現（掌握）
（8）在鏈式存儲結構上鏈隊列的基本操作的實現（掌握）
（9）隊列的典型應用實例（掌握）
4.數組和廣義表
（1）數組的存儲結構（理解）
（2）數組在行序為主序的存儲結構中的地址計算方法（掌握）
（3）特殊矩陣的壓縮存儲方法（掌握）
（4）稀疏矩陣的三元組表示以及運算處理方法（理解）
（5）廣義表的概念（理解）
5.樹與二叉樹
（1）二叉樹的概念（理解）
（2）二叉樹的各種存儲結構（掌握）
（3）二叉樹的性質（掌握）
（4）按各種次序遍歷二叉樹的遞歸算法（掌握）
（5）按各種次序遍歷二叉樹的非遞歸算法（掌握）
（6）建立二叉樹的各種算法（掌握）
（7）建立最優(yōu)二叉樹和哈夫曼編碼的方法（掌握）
（8）樹的各種存儲結構及其特點（理解）
（9）樹與二叉樹、森林與二叉樹的相互轉換（理解）
（10）樹與等價類劃分問題（理解）
6.圖
（1）圖的基本概念（理解）
（2）圖的存儲結構（鄰接矩陣和鄰接表）（掌握）
（3）圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷（掌握）
（4）最小生成樹（PRIM 算法和 Kruscal 算法）（掌握）
（5）某一點到其他各點之間的最短路徑（迪杰斯特拉算法）（掌握）
（6）拓撲排序（掌握）
（7）關鍵路徑和關鍵活動（掌握）
7.查找算法
（1）順序查找算法及特點（掌握）
（2）折半查找算法及特點（掌握）
（3）索引查找的過程和特點（理解）
（4）二叉排序樹的構造方法和查找過程（掌握）
（5）二叉平衡樹的旋轉平衡方法（掌握）
（6）B-樹的特點及其建立過程和查找過程（理解）
（7）哈希表的構造方法和查找方法（掌握）
（8）各種查找算法在等概率情況下查找成功和查找失敗時的平均查找長度的  計算方法（掌握）
8.排序算法
（1）插入排序（直接插入排序、折半插入排序）方法的排序過程和特點（掌握）
（2）SHELL 插入排序方法的排序過程（理解）
（3）交換排序(起泡排序,快速排序)方法的排序過程和特點（掌握）
（4）選擇排序(簡單選擇排序,堆排序)的排序過程和特點（掌握）
（5）歸并排序方法的排序過程和特點（掌握）
（6）基數排序方法的排序過程和特點（理解）
（7）各種排序方法的算法實現以及時間復雜度和空間復雜度分析（理解）

北京交通大學

本文來源：http://m.zgxindalu.cn/beijingjiaotongdaxue/cankaoshu_470122.html