中国在职研究生招生信息网

 　　北京交通大學軟件工程專業(yè)隸屬于軟件學院，該學院是教育部37所國家示范性軟件學院之一，而北京交通大學軟件工程專業(yè)的本科教育就已經獲首批國家級一流專業(yè)建設點。近幾年，北京交通大學開設軟件工程專業(yè)在職研究生教育，考生報考需要參加考試。其復試科目之一為《數(shù)據(jù)結構》。下面介紹2022年北京交通大學在職研究生考試大綱之復試《數(shù)據(jù)結構》。

　　參加北京交通大學在職研究生的考生，可以將嚴蔚敏、吳偉民編著的《數(shù)據(jù)結構》(C 版)作為參考書目，并掌握以下八個知識點。

　　第一，考生應理解數(shù)據(jù)結構的基本概念、算法的五個特性、抽象數(shù)據(jù)類型，掌握計算語句頻度和估算算法時間復雜度和空間復雜度的方法。

　　第二，考生應理解線性表的邏輯結構、 從時間、空間復雜度的角度比較線性表兩種存儲結構的不同特點及 其適用場合，掌握線性表的順序存儲結構和鏈式存儲結構、線性表在順序結構上實現(xiàn)基本操作的方法以及線性表在鏈式結構上實現(xiàn)基本操作的方法。

　　第三，考生應理解棧的特點、遞歸算法中棧的作用、隊列的特點、掌握在順序存儲結構上棧的基本操作的實現(xiàn)、在鏈式存儲結構上棧的基本操作的實現(xiàn)、棧的典型應用實例、在順序存儲結構上循環(huán)隊列基本操作的實現(xiàn)、在鏈式存儲結構上鏈隊列的基本操作的實現(xiàn)、隊列的典型應用實例。

　　第四，考生應理解數(shù)組的存儲結構、稀疏矩陣的三元組表示以及運算處理方法、廣義表的概念，掌握數(shù)組在行序為主序的存儲結構中的地址計算方法以及特殊矩陣的壓縮存儲方法。

　　第五，考生應理解二叉樹的概念、樹的各種存儲結構及其特點、樹與二叉樹、森林與二叉樹的相互轉換以及樹與等價類劃分問題，掌握二叉樹的各種存儲結構、二叉樹的性質、按各種次序遍歷二叉樹的遞歸算法、按各種次序遍歷二叉樹的非遞歸算法、建立二叉樹的各種算法以及建立最優(yōu)二叉樹和哈夫曼編碼的方法。

　　第六，考生應理解圖的基本概念，掌握圖的存儲結構、圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷、最小生成樹、某一點到其他各點之間的最短路徑、拓撲排序以及關鍵路徑和關鍵活動。

　　第七，考生應理解索引查找的過程和特點、B-樹的特點及其建立過程和查找過程，掌握順序查找算法及特點、折半查找算法及特點、二叉排序樹的構造方法和查找過程、二叉平衡樹的旋轉平衡方法、哈希表的構造方法和查找方法、各種查找算法在等概率情況下查找成功和查找失敗時的平均查找長度的計算方法。

　　第八，考生應理解SHELL 插入排序方法的排序過程、 基數(shù)排序方法的排序過程和特點、各種排序方法的算法實現(xiàn)以及時間復雜度和空間復雜度分析，掌握方法的排序過程和特點、交換排序方法的排序過程和特點、選擇排序的排序過程和特點以及歸并排序方法的排序過程和特點。

　　以上是有關2022年北京交通大學在職研究生考試大綱之復試《數(shù)據(jù)結構》的詳細介紹。如果還有其他疑問需要解答，可登錄本網(wǎng)站咨詢本站老師。