2021中國農(nóng)業(yè)大學(xué)821數(shù)據(jù)結(jié)構(gòu)研究生考試大綱 正文

821數(shù)據(jù)結(jié)構(gòu)考試大綱
一、考查目標(biāo)
1．理解數(shù)據(jù)結(jié)構(gòu)的基本概念；掌握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)及其差異，以及各種基本操作的實現(xiàn)。
2．掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM(jìn)行設(shè)計與分析。
3．能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進(jìn)行問題求解。
 
二、考試形式和試卷結(jié)構(gòu)
1．試卷滿分及考試時間
試卷滿分150分，考試時間180分鐘。
2．答題方式
答題方式為筆試、閉卷。
3．試卷內(nèi)容與題型結(jié)構(gòu)
單選題 10題 每小題 2分 共20分
填空題 10題 每小題 2分 共20分
簡答題  5題 每小題 5分 共25分
綜合題  3題 每小題15分 共45 分
算法題  4題 每小題10分 共40 分
 
三、考查內(nèi)容
1．概念
（1）基本概念和術(shù)語
l 數(shù)據(jù)
l 數(shù)據(jù)結(jié)構(gòu)
l 抽象數(shù)據(jù)類型
（2）算法的描述和分析
l 算法、算法的時間復(fù)雜度和空間復(fù)雜度概念
l 算法描述和算法分析的方法，對于一般算法能分析出時間復(fù)雜度
2．線性表
（1）線性表的概念
l 線性表的邏輯結(jié)構(gòu)
l 線性表的存儲結(jié)構(gòu)：順序表，單鏈表，雙鏈表，循環(huán)鏈表，靜態(tài)鏈表
（2）線性表的實現(xiàn)
l 順序存儲結(jié)構(gòu)：查找、插入、刪除等基本操作及其平均時間性能分析
l 鏈?zhǔn)酱鎯Y(jié)構(gòu)：查找、插入、刪除等基本操作及其平均時間性能分析
3．棧、隊列
（1）棧和隊列的概念
l 棧和隊列的邏輯結(jié)構(gòu)
l 棧和隊列的存儲結(jié)構(gòu)：順序棧，循環(huán)隊列，鏈?zhǔn)綏＃準(zhǔn)疥犃?br /> （2）棧和隊列的實現(xiàn)
l 順序存儲結(jié)構(gòu)：入棧、出棧、入隊、出隊等基本操作及其平均時間性能分析
l 鏈?zhǔn)酱鎯Y(jié)構(gòu)：入棧、出棧、入隊、出隊等基本操作及其平均時間性能分析
4．?dāng)?shù)組和廣義表
（1）數(shù)組和廣義表的概念
l 數(shù)組和廣義表的邏輯結(jié)構(gòu)
l 數(shù)組的存儲結(jié)構(gòu)：特殊矩陣壓縮存儲、稀疏矩陣壓縮存儲（三元組表）
l 廣義表的存儲結(jié)構(gòu)：鏈?zhǔn)酱鎯?br /> （2）數(shù)組和廣義表的實現(xiàn)
l 數(shù)組順序存儲結(jié)構(gòu)：一般數(shù)組順序存儲的地址計算方法
l 廣義表鏈?zhǔn)酱鎯Y(jié)構(gòu)：非空廣義表的求表頭和表尾等基本操作
5．樹和二叉樹
（1）樹和二叉樹的概念
l 樹和二叉樹的邏輯結(jié)構(gòu)
l 樹和二叉樹的存儲結(jié)構(gòu)：樹的孩子兄弟表示法、二叉樹的二叉鏈表
l 樹和二叉樹的遍歷：樹的三種遍歷方法、二叉樹的三種遍歷方法
l 樹和二叉樹的轉(zhuǎn)換方法
（2）樹和二叉樹的實現(xiàn)
l 二叉樹的遞歸遍歷
l Huffman樹
l Huffman編碼
6．圖
（1）圖的概念
l 圖的邏輯結(jié)構(gòu)
l 圖的存儲結(jié)構(gòu)：鄰接矩陣、鄰接表
l 圖的遍歷：深度優(yōu)先搜索方法、廣度優(yōu)先搜索方法
（2）圖的實現(xiàn)
l 最小（代價）生成樹：Prim和Kruskal方法
l 最短路徑：Dijkstra方法
l 拓?fù)渑判?br /> l 關(guān)鍵路徑
7．查找
（1）查找的概念
l 查找表、查找分類、查找結(jié)構(gòu)
l 查找算法效率的評判標(biāo)準(zhǔn)：平均查找長度
（2）靜態(tài)表及其查找
l 順序查找
l 折半查找
（3）動態(tài)表及其查找
l 二叉排序樹
l 平衡二叉樹
（4）Hash表及其查找
l Hash函數(shù)
l 處理沖突方法
l Hash查找
（5）各種查找算法的分析
8．排序
（1）排序的概念
l 排序方法穩(wěn)定性、排序分類
l 排序算法效率的評判標(biāo)準(zhǔn)
（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的二叉樹至多有        個結(jié)點。
3．簡答題
請比較順序表和單鏈表在存儲空間和數(shù)據(jù)訪問方面的特點。
4．綜合題
已知一棵二叉樹的先序遍歷的結(jié)果是ABDECF，中序遍歷的結(jié)果是DEBAFC，請畫出這棵二叉樹，并寫出該二叉樹的后序遍歷結(jié)果。
5．算法題
分析下面算法功能，以及時間復(fù)雜度。
#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) 用循環(huán)單鏈表實現(xiàn)隊列，要求該隊列只使用一個指向隊尾指針。請寫出結(jié)點和隊列的類型定義，并分別編寫隊列初始化、入隊、出隊算法。
 
五、參考教材
(1) 數(shù)據(jù)結(jié)構(gòu)-基于C語言的描述，彭波主編，清華大學(xué)出版社
(2) 數(shù)據(jù)結(jié)構(gòu)，嚴(yán)蔚敏編著，清華大學(xué)出版社
 
 
 

中國農(nóng)業(yè)大學(xué)

本文來源：http://www.zhongzhouzhikong.com/zhongguonongyedaxue/cankaoshu_390502.html