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

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

北京交通大學(xué)

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