2016北京林業大學數據結構考研大綱

• 2025考研復試伴學班
• 2025考研復試標準班
• 2026考研英語全程班
• 26考研全科上岸規劃營「擇校▪規劃▪備考」
• 北京林業大學2025考研專業課復習資料「真題▪筆記▪講義▪題庫」

《數據結構》考試大綱

一、考試大綱的性質

數據結構是報考我校軟件工程、計算機技術專業學位碩士的考試科目。為幫助考生明確考試復習范圍和有關要求，特制定本考試大綱。

二、考試范圍和內容

1.數據結構基本概念

(1)數據結構的基本概念：數據、數據元素、數據結構、數據的邏輯結構、物理結構、算法等。

(2)算法時間復雜度和空間復雜度的分析方法。

2.線性表

(1)線性表的定義。

(2)線性表的順序存儲結構和主要算法實現，如查找、插入和刪除算法。

(3)線性表的鏈式存儲結構和主要算法實現，如查找、插入和刪除算法。

(4)循環鏈表、雙向鏈表的特點。

(5)從時間和空間復雜度的角度比較兩種存儲結構的不同特點及其適用場合。

(6)線性表的應用，如線性表的合并算法。

3.棧和隊列

(1)棧的定義及特點，棧的順序存儲和鏈接存儲結構，進棧出棧算法，順序棧棧滿和棧空的條件。

(2)棧的應用，如表達式求值算法，借助棧深入理解遞歸算法。

(3)隊列的定義及特點，隊列的順序存儲(循環隊)和鏈接存儲結構，進隊出隊算法，循環隊列中隊滿及隊空的條件。

4.串和數組

(1)串的定義。

(2)串的古典模式匹配算法。

(3)數組地址的計算方法。

(4)特殊矩陣的壓縮存儲方法。

5.樹和二叉樹

(1)二叉樹的定義和性質。

(2)二叉樹的兩種存儲結構：順序存儲和鏈式存儲。

(3)二叉樹的創建和三種不同遍歷算法，利用遍歷算法實現二叉樹的其他操作，如計算二叉樹結點個數、葉子結點個數、二叉樹的高度等算法。

(4)線索二叉樹的特性及構造方法。

(5)樹和森林的定義、存儲結構與二叉樹的轉換方法。

(6)樹的應用，哈夫曼樹及哈夫曼編碼的構造算法、帶權路徑長度的計算。

6.圖

(1)圖的定義和性質。

(2)圖的兩種存儲結構：鄰接矩陣和鄰接表。

(3)圖的兩種遍歷策略：深度優先搜索算法和廣度優先搜索算法。

(4)圖的基本應用，包括拓撲排序算法、求解最短路徑的迪杰斯特拉算法、構造最小生成樹的兩種算法（普里姆算法和克魯斯卡爾算法）。

7.查找

(1)線性表的查找：順序查找和折半查找算法。

(2)樹表的查找：二叉排序樹的定義，二叉排序樹的創建、插入、刪除和查找算法。

(3)散列表的查找：兩種處理沖突的方法包括開放地址法（線性探測法、二次探測法）和鏈地址法。

(4)上述三種不同查找算法的分析，平均查找長度ASL的計算方法及時間復雜度分析，不同查找算法的適用場合。

8.排序

(1)排序的基本概念。

(2)插入排序：直接插入排序、折半插入排序和希爾排序。

(3)交換排序：冒泡排序和快速排序。

(4)選擇排序：簡單選擇排序和堆排序。

(5)歸并排序：2-路歸并排序。

(6)上述各種排序方法的特點和排序過程，時間和空間復雜度的分析，排序方法“穩定”或“不穩定”的含義。排序算法的實現及適用場合。

三、考試方式和時間

考試方式：閉卷筆試。

考試時間：180分鐘。

試卷滿分：150分。

考試主要題型：選擇題、判斷題、填空題、應用題、算法設計題（算法實現用C/C++語言）。

四、主要參考書

嚴蔚敏，李冬梅，吳偉民.數據結構（C語言版）.北京：人民郵電出版社.