東北林業大學

考試內容范圍:

一、數據結構和算法

1.要求考生理解數據結構、邏輯結構、存儲結構和抽象數據類型的基本概念。

2.要求考生理解算法的五個特點。

3.要求考生掌握算法時間和空間復雜度的大O表示法。

二、線性表

1. 要求考生理解線性表的概念、邏輯結構。

2. 要求考生掌握線性表的順序存儲結構及其基本操作和特征。

3. 要求考生熟練掌握單鏈表、循環鏈表、雙向鏈表的存儲結構及其各種基本操作。

4. 要求考生熟練掌握在順序和鏈表存儲結構上的典型算法實現，并能夠盡量提高算法性能。

三、棧和隊列

1. 要求考生掌握棧的特征、順序棧和鏈棧的設置和操作實現。

2. 要求考生掌握隊列的特征、順序(循環隊列)和鏈隊列的設置和操作實現。

3. 要求考生了深入理解棧和隊列的結構特性和典型操作。

四、樹和二叉樹

1. 要求考生理解樹的基本概念和特征。

2. 要求考生熟練掌握二叉樹的概念和性質、二叉樹的順序存儲結構和鏈式存儲結構、二叉樹的遍歷和應用。熟練掌握二叉樹的相關(遞歸、非遞歸)算法的實現。

3. 要求考生掌握樹的存儲結構、樹和森林與二叉樹間的轉換，掌握樹和森林的遍歷。

4. 要求考生掌握哈夫曼樹的概念、哈夫曼樹的構造過程及哈夫曼編碼。

五、圖

1. 要求考生理解無向圖、有向圖的相關概念、術語，掌握圖的鄰接矩陣和鄰接表的存儲結構。

2. 要求考生熟練掌握圖的深度優先和廣度優先遍歷算法及其應用。

3. 要求考生理解圖的連通性的概念。

4. 要求考生掌握求最小生成樹(Prim算法和Kruskal算法)的求解過程。

5. 要求考生理解有向無環圖的概念，掌握拓撲排序和關鍵路徑的求解過程。

6. 要求考生了解帶權最短路徑的概念，掌握求最短路徑的求解過程。

六、查找

1. 要求考生理解查找的概念及其效率的評價方法。

2. 要求考生理解靜態查找表的概念，熟練掌握順序、折半查找算法。

3. 要求考生理解動態查找表和二叉排序樹的概念和查找與操作。

4. 要求考生了解平衡二叉樹的概念與操作。

5. 要求考生理解哈希表的概念，熟練掌握哈希函數的構造和處理沖突的基本方法。

七、內部排序

1.要求考生掌握插入類排序的排序算法、排序特點和排序過程：直接插入排序、希爾排序。

2.要求考生掌握交換類排序的排序算法、排序特點和排序過程：冒泡排序、快速排序。

3.要求考生掌握選擇類排序的的排序算法、排序特點和排序過程：簡單選擇排序、堆排序。

4.掌握以上各種排序算法是否穩定，對各種排序方法時間和空間方面進行簡單分析。

八、高級語言程序設計

1. 要求考生掌握C語言程序設計基本知識.

2. 要求考生熟練應用C語言解決應用問題.

考試總分：150分 考試時間：3小時 考試方式：筆試

考試題型： 選擇填空(40分)

判斷題(20分)

閱讀程序寫結果題(20分)

程序填空題(20分)

編寫程序(30分)

算法設計(20分)

參考書：

《數據結構(C語言版)》 嚴蔚敏，李冬梅、吳偉民 人民郵電出版社 2014

《c程序設計》 譚浩強，清華大學出版社出版 2010