中國農(nóng)業(yè)科學(xué)院2022年碩士研究生招生考試自命題科目考試大綱
科目代碼：808 考試科目：數(shù)據(jù)結(jié)構(gòu)
考查目標(biāo)
要求考生比較系統(tǒng)地理解數(shù)據(jù)結(jié)構(gòu)的基本概念和基本理論，掌握數(shù)據(jù)結(jié)構(gòu)的基本方法，具備一定的運算能力、邏輯思維能力、編程能力和綜合運用所學(xué)知識分析問題和解決實際問題的能力。
考試形式和試卷結(jié)構(gòu)
1.試卷滿分及考試時間
本試卷滿分為 150 分，考試時間為 180 分鐘。
2.答題方式
閉卷、筆試。
3.試卷內(nèi)容結(jié)構(gòu)
考試內(nèi)容包括數(shù)據(jù)的方法、存儲數(shù)據(jù)結(jié)構(gòu)的方法以及在各種結(jié)構(gòu)上執(zhí)行操作的算法。題型包括選擇、填空、簡答和寫算法題等。
考試大綱
1、數(shù)據(jù)結(jié)構(gòu)概論
1) 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、抽象數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)等概念;
2) 算法的定義、特性、算法的時間復(fù)雜度、算法的空間復(fù)雜度、遞歸算法等概念。
2、線性表
1) 掌握線性表的基本概念及其存儲結(jié)構(gòu);
2)掌握順序表的各種操作(插入、刪除等)實現(xiàn)及算法復(fù)雜度;
3) 掌握單鏈表的各種操作(插入、刪除等)實現(xiàn)及算法復(fù)雜度;
4) 了解順序表和鏈表的特點，對比他們的優(yōu)缺點。
3、桟和隊列
1) 了解棧、隊列的基本概念;
2) 棧的順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)，及在兩種結(jié)構(gòu)下實現(xiàn)棧的操作;
3) 掌握棧的入桟、出棧操作，并能利用棧解決實際問題;
4) 掌握隊列的入隊、出隊操作，并能利用隊列解決實際問題。
4、數(shù)組和廣義表
1) 理解多維數(shù)組的行主序、列主序存儲;
2) 了解特殊矩陣(對稱矩陣、三角矩陣、稀疏矩陣)的壓縮存儲;
3) 了解廣義表的定義、表示、存儲方法和遞歸算法。
5 、樹和二叉樹
1) 了解樹和二叉樹的基本概念、術(shù)語和性質(zhì);
2) 掌握二叉樹的兩種存儲結(jié)構(gòu)(順序存儲、二叉鏈表存儲);
3) 掌握二叉樹的先根、中根、后根遍歷算法;
4) 掌握常見的構(gòu)造二叉樹的方法;
5) 掌握二叉樹的層次遍歷算法，能夠用順序循環(huán)隊列演示遍歷過程;
6) 掌握建立哈夫曼樹和哈夫曼編碼的方法及帶權(quán)外路徑長度(WPL)的計算;
7) 了解樹和二叉樹的相互轉(zhuǎn)換，了解樹的存儲、遍歷。
6、圖
1) 了解圖的基本概念;
2) 掌握圖的存儲結(jié)構(gòu)(鄰接矩陣表示法、鄰接表表示法);
3) 掌握圖的兩種遍歷算法(深度優(yōu)先搜索遍歷、廣度優(yōu)先搜索遍歷);
4) 掌握圖的最小生成樹算法思想(Prim、Kruskal);
5) 掌握圖的最短路徑算法思想(Dijkstra、Floyd)。
7、查找
1) 了解查找的基本概念(查找表、查找、平均查找長度 ASL);
2) 了解靜態(tài)查找表(順序表、有序表、靜態(tài)表、索引順序表)和動態(tài)查找表(二叉排樹、平衡二叉樹、B-樹、B+樹);
3) 掌握線性表的查找算法(順序查找、折半查找、分塊查找)。會計算查找過程中的比較次數(shù)，會分析它們的算法時間復(fù)雜度，了解它們的優(yōu)點和缺點，能夠根據(jù)實際情況選擇適當(dāng)?shù)牟檎宜惴?
4) 掌握二叉排序樹的定義以及查找、插入等操作。了解平衡二叉樹;
5) 掌握散列技術(shù)：會利用除余法構(gòu)造散列函數(shù)，掌握處理沖突的兩種方法(開放定址法、鏈地址法)，會計算平均查找長度。
8、排序
1) 掌握排序的基本概念(排序算法的穩(wěn)定性、排序算法性能評價);
2) 掌握各種內(nèi)排序算法(直接插入排序、折半插入排序、、希爾排序、冒泡排序、快速排序、直接選擇排序、堆排序、歸并排序);
3) 掌握上述排序算法的時間復(fù)雜度和空間復(fù)雜度，能夠根據(jù)實際情況選擇適當(dāng)?shù)嘏判蛩惴ā?/p>
