2016安徽農業大學數據結構考研大綱

考研專業課大綱來源：中國考研網 2015-09-23　相關院校：安徽農業大學

2016安徽農業大學數據結構考研大綱

科目名稱	數據結構			科目代碼		829
參考書目名稱		編者	出版單位		版次		年份
《數據結構》（c語言版）		嚴蔚敏等	清華大學出版社
考試范圍及要點
一、數據結構基本概念及簡單的算法分析考試內容 (1)數據結構的基本概念，數據的邏輯結構、存儲結構。 (2)算法的定義、算法的基本特性以及算法分析的基本概念、算法的性能標準；算法的后期測試；算法的事前估計；空間復雜度度量；時間復雜度度量；時間復雜度的漸進表示法；漸進的空間復雜。考試要求建立有關數據結構最基本的概念，包括數據的邏輯結構、存儲結構和算法，算法分析的基本概念與基本方法。二、線性表考試內容 (1)線性關系、線性表的定義，線性表的基本操作。 (2)線性表的順序存儲結構與鏈式存儲結構(包括單鏈表、循環鏈表和雙向鏈表)的構造原理。在以上兩種存儲結構上對線性表實施的最主要的操作(包括三種鏈表的建立、插入和刪除、檢索等)的算法設計。考試要求掌握線性表的基本概念以及兩種存儲結構的構造原理，掌握在各種存儲結構下對線性表進行的基本操作的算法設計。三、棧和隊列考試內容 (1)堆棧與隊列的基本概念、基本操作。 (2)堆棧與隊列的順序存儲結構與鏈式存儲結構的構造原理。 (3)在不同存儲結構的基礎上對堆棧與隊列實施插入與刪除等基本操作對應的算法設計。考試要求掌握堆棧和隊列的基本概念與特征，掌握在兩種存儲結構下如何對堆棧和隊列進行插入和刪除等操作，以及利用堆棧與隊列解決實際問題的基本方法。四、串考試內容 (1)串的基本概念、串的基本操作和存儲結構。 (2)串的模式匹配算法和改進的KMP算法。考試要求充分了解串的基本概念、掌握串的存儲結構和相關的操作算法。五、數組和廣義表考試內容 (1)數組的概念、多維數組的實現。 (2)對稱矩陣和稀疏矩陣的壓縮存儲。 (3)廣義表的基本概念。考試要求掌握數組、廣義表和稀疏矩陣的基本概念，物理結構和基本操作的實現。六、樹和二叉樹考試內容 (1)樹的基本概念和基本操作,樹的抽象數據類型。 (2)二叉樹的概念和性質,特殊二叉樹；二叉樹的存儲結構。 (3)二叉樹的生成與建立。 (4)遍歷二叉樹：前序遍歷,中序遍歷,后序遍歷,層次遍歷。 (5)二叉樹其它操作實現舉例。 (6)線索二叉樹的概念和存儲結構,二叉樹的線索化,線索二叉樹的遍歷。 (7)樹的存儲結構,樹與二叉樹之間的轉換,森林與二叉樹之間的轉換,樹和森林的遍歷。 (8)樹的路徑長度和帶權路徑長度,哈夫曼樹(Huffman)的概念,哈夫曼算法, 哈夫曼編碼樹。 (9)二叉排序樹的的概念和基本操作,二叉排序樹的建立,二叉排序樹其它操作實現舉例。考試要求充分了解樹型結構的邏輯特征，掌握各種存儲結構的構造原理，能夠熟練利用常用的三種遍歷方法，掌握利用二叉樹的遍歷操作解決實際問題的方法，掌握二叉排序樹的建立以及在二叉排序樹中查找一個結點存在與否的過程。七、圖考試內容 (1)圖的定義，基本概念，圖的分類，常用名詞術語。 (2)圖的鄰接矩陣存儲方法、鄰接表存儲方法的構造原理。 (3)圖的遍歷操作。 (4)最小生成樹，最短路徑，AOV網與拓撲排序。考試要求充分了解圖的邏輯結構的特點，掌握常用的兩種存儲方法，掌握最小生成樹(Prim算法和Kruskal算法)、最短路徑、拓撲排序的具體求解過程。八、查找考試內容 (1)查找的概念,關鍵字比較次數,平均查找長度。 (2)順序表的查找:順序查找,折半查找,分塊查找。 (3)樹表的查找:二叉排序樹,平衡二叉樹。 (4)哈希(Hash)表的查找:哈希表的概念,哈希函數構造方法,哈希表的建立和查找,沖突處理方法。考試要求充分了解各種順序文件的結構與相應的查找方法；了解各種查找算法之間時空效率的差異；從結構與操作上了解散列文件的建立、散列函數的選擇(構造)原則、處理散列沖突的方法以及在散列文件中查找一個記錄存在與否的過程。九、排序考試內容 (1)排序的概念；排序的穩定性；比較關鍵字次數，移動記錄次數；順序表的排序，鏈接表(單鏈表)的排序。 (2)內排序方法與算法 (a)交換排序：冒泡排序，快速排序。 (b)插入排序：直接插入排序，2-路插入排序，折半插入排序，希爾排序。 (c)選擇排序：直接選擇排序，錦標賽排序，堆排序。 (d)歸并排序。 (e)基數排序。 (3)各種排序算法的評價和應用。考試要求充分了解各種排序方法的排序特點和排序過程，對于任意給出的數據元素序列，能夠熟練地采用指定排序方法進行排序，并且能夠對每一種排序方法排序過程中所進行的元素之間的比較次數、相應排序算法的時間、空間、排序的穩定性等性能進行簡單分析。
試題結構：
一、試卷滿分及考試時間本試卷滿分為150分，考試時間為180分鐘二、答題方式答題方式為閉卷、筆試三、試卷內容結構數據結構基本概念及簡單的算法分析：5％線性表：10％－15％棧和隊列：10％串：5％數組和廣義表：5－10％樹和二叉樹：15％－20％圖：15－20％查找和排序：15％－20％四、試卷題型結構填空題：10分，占7％選擇題：10分，占7％簡答題：30分，占20％應用題：60分，占40％算法分析與設計題：40分，占27％