中國地質大學（北京）2021碩士研究生《數據結構與C語言》考試大綱

　　科目名稱：數據結構

　　代 碼：858

一、考試性質

本課程在計算機科學中是程序設計(特別是非數值計算的程序設計)的基礎，而且是設計和實現大型應用程序的重要基礎。本課程需要掌握基本的數據結構、基本算法分析技術、排序、檢索和索引技術。對常用的基本數據結構，掌握相應的存儲實現技術和經典算法，并通過算法時間空間的效率分析，理解時空權衡的原則。對常用的各種經典排序算法深入討論其時間和空間開銷。了解文件管理和外排序技術，以及常見的檢索和索引技術。掌握數據結構和算法的設計分析技術，提高程序設計的質量;根據所求解問題的性質選擇合理的數據結構并對時間空間復雜性進行要的控制。

二、考試形式與試卷結構

1、答卷方式：閉卷、筆試

2、答卷時間：180分鐘

3、題型比例：滿分75分/150分，概念題5題(占總分20%-40%)，其余題型全為操作題和計算題。

三、考查要點

1、基本概念

數據結構定義(邏輯結構、存儲結構、運算)，抽象數據類型 ，算法及其算法度量和評價。

2、線性表

線性表的順序存儲結構、線性表的鏈式存儲結構，掌握;循環鏈表、多項式及其相加、雙向鏈表。

3、棧和隊列

棧的存儲結構及其基本操作、隊列存儲結構及其基本操作，掌握;棧與遞歸的實現。

4、串

字符串抽象數據類型，存儲表示和類定義 ，掌握;字符串的運算 ，了解;#字符串的模式匹配。

5、數組和廣義表

數組的定義、基本運算和存儲結構，特殊矩陣的壓縮存儲，了解;#廣義表的定義、術語、存儲結構、運算，*遞歸算法設計。

6、樹

二叉樹的概念及性質，二叉樹的抽象數據類型，二叉樹的遍歷，二叉樹的存儲實現，Huffman編碼樹 ，樹和二叉樹的轉換掌握;線索二叉樹(了解);*非遞歸深度優先周游二叉樹和穿線二叉樹。

7、圖

圖的基本概念，圖的抽象數據類型，圖的存儲結構，圖的周游，最小支撐樹,拓撲排序，掌握 ;最短路徑問題，關鍵路徑算法。

8、動態存儲管理

基本概念和算法

9、查找

靜態查找表及查找算法：順序查找、折半查找，動態查找表及查找算法，二叉排序樹，哈希表及查找算法，掌握;B_和B+樹、鍵樹。

10、內排序

排序問題的基本概念，三種簡單排序算法(插入排序、冒泡排序、選擇排序);

Shell排序，快速排序，歸并排序，堆排序，了解;#基數排序;#各種排序算法的理論和實驗時間代價的討論以及排序問題的下限的研究。

11、外排序

外排序的特點 掌握;二路外排序，置換選擇排序 ，了解。

12、文件管理

文件的基本概念，常用的文件操作，文件的組織結構，文件的不同組織方式的特點。

四、參考資料

嚴蔚敏、吳偉民，《數據結構》C語言版，清華大學出版社，第1版 (2009年3月1日)