2021年中國農業大學碩士研究生招生考試大綱

821數據結構考試大綱

一、考查目標

1．理解數據結構的基本概念；掌握數據的邏輯結構、存儲結構及其差異，以及各種基本操作的實現。

2．掌握基本的數據處理原理和方法的基礎上，能夠對算法進行設計與分析。

3．能夠選擇合適的數據結構和方法進行問題求解。

二、考試形式和試卷結構

1．試卷滿分及考試時間

試卷滿分150分，考試時間180分鐘。

2．答題方式

答題方式為筆試、閉卷。

3．試卷內容與題型結構

單選題           10題      每小題 2分          共20分

填空題           10題      每小題 2分          共20分

簡答題           5題      每小題 5分          共25分

綜合題           3題      每小題15分         共45 分

算法題           4題      每小題10分         共40 分

三、考查內容

1．概念

（1）基本概念和術語

l  數據

l  數據結構

l  抽象數據類型

（2）算法的描述和分析

l  算法、算法的時間復雜度和空間復雜度概念

l  算法描述和算法分析的方法，對于一般算法能分析出時間復雜度

2．線性表

（1）線性表的概念

l  線性表的邏輯結構

l  線性表的存儲結構：順序表，單鏈表，雙鏈表，循環鏈表，靜態鏈表

（2）線性表的實現

l  順序存儲結構：查找、插入、刪除等基本操作及其平均時間性能分析

l  鏈式存儲結構：查找、插入、刪除等基本操作及其平均時間性能分析

3．棧、隊列

（1）棧和隊列的概念

l  棧和隊列的邏輯結構

l  棧和隊列的存儲結構：順序棧，循環隊列，鏈式棧，鏈式隊列

（2）棧和隊列的實現

l  順序存儲結構：入棧、出棧、入隊、出隊等基本操作及其平均時間性能分析

l  鏈式存儲結構：入棧、出棧、入隊、出隊等基本操作及其平均時間性能分析

4．數組和廣義表

（1）數組和廣義表的概念

l  數組和廣義表的邏輯結構

l  數組的存儲結構：特殊矩陣壓縮存儲、稀疏矩陣壓縮存儲（三元組表）

l  廣義表的存儲結構：鏈式存儲

（2）數組和廣義表的實現

l  數組順序存儲結構：一般數組順序存儲的地址計算方法

l  廣義表鏈式存儲結構：非空廣義表的求表頭和表尾等基本操作

5．樹和二叉樹

（1）樹和二叉樹的概念

l  樹和二叉樹的邏輯結構

l  樹和二叉樹的存儲結構：樹的孩子兄弟表示法、二叉樹的二叉鏈表

l  樹和二叉樹的遍歷：樹的三種遍歷方法、二叉樹的三種遍歷方法

l  樹和二叉樹的轉換方法

（2）樹和二叉樹的實現

l  二叉樹的遞歸遍歷

l  Huffman樹

l  Huffman編碼

6．圖

（1）圖的概念

l  圖的邏輯結構

l  圖的存儲結構：鄰接矩陣、鄰接表

l  圖的遍歷：深度優先搜索方法、廣度優先搜索方法

（2）圖的實現

l  最小（代價）生成樹：Prim和Kruskal方法

l  最短路徑：Dijkstra方法

l  拓撲排序

l  關鍵路徑

7．查找

（1）查找的概念

l  查找表、查找分類、查找結構

l  查找算法效率的評判標準：平均查找長度

（2）靜態表及其查找

l  順序查找

l  折半查找

（3）動態表及其查找

l  二叉排序樹

l  平衡二叉樹

（4）Hash表及其查找

l  Hash函數

l  處理沖突方法

l  Hash查找

（5）各種查找算法的分析

8．排序

（1）排序的概念

l  排序方法穩定性、排序分類

l  排序算法效率的評判標準

（2）插入排序

l  簡單插入排序

l  希爾排序

（3）交換排序

l  冒泡排序

l  快速排序

（4）選擇排序

l  簡單選擇排序

l  堆排序

（5）歸并排序

l  二路歸并排序

l  分治歸并排序

（6）各種排序算法的比較

四、題型舉例

1．選擇題

在單鏈表中成功查找一個元素的等概率下的平均搜索長度是        。

A. n                            B. n/2                         C. (n+1)/2                         D. n+1

2．填空題

深度為5的二叉樹至多有        個結點。

3．簡答題

請比較順序表和單鏈表在存儲空間和數據訪問方面的特點。

4．綜合題

已知一棵二叉樹的先序遍歷的結果是ABDECF，中序遍歷的結果是DEBAFC，請畫出這棵二叉樹，并寫出該二叉樹的后序遍歷結果。

5．算法題

分析下面算法功能，以及時間復雜度。

#define List_Size 100

typedef struct  {

ElemType elem[List_Size];

int              length;

} SqList;

void ex(SqList la, SqList lb, SqList &lc)  {

         i=0;  j=0;  k=0;

while(i<la.length && j<lb.length)  {

if(la.elem[i]<=lb.elem[j])  lc.elem[k++]=la.elem[i++];

                            else  lc.elem[k++]=lb.elem[j++];

           }

           while(i<la.length)  lc.elem[k++]=la.elem[i++];

while(j<lb.length)  lc.elem[k++]=lb.elem[j++];

} // ex

(2) 用循環單鏈表實現隊列，要求該隊列只使用一個指向隊尾指針。請寫出結點和隊列的類型定義，并分別編寫隊列初始化、入隊、出隊算法。

五、參考教材

       (1) 數據結構-基于C語言的描述，彭波主編，清華大學出版社

       (2) 數據結構，嚴蔚敏編著，清華大學出版社