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

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

本文來(lái)源：http://m.btfokj.cn/zhongguonongyedaxue/cankaoshu_390502.html