|
友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。 下載流程： 考研真題 點擊“考研試卷””下載; 考博真題 點擊“考博試卷庫” 下載
西南石油大學數據結構2020年碩士研究生招生專業課考試大綱
考試科目名稱：數據結構
一、考試性質
數據結構是碩士研究生入學考試科目之一，是碩士研究生招生院校自行命題的選拔性考試。本考試大綱的制定力求反映招生類型的特點，科學、公平、準確、規范地測評考生的相關基礎知識掌握水平，考生分析問題和解決問題及綜合知識運用能力。應考人員應根據本大綱的內容和要求自行組織學習內容和掌握有關知識。
本大綱主要包括三大常用數據結構的邏輯、物理表示與基本操作算法實現部分的知識，各種結構的經典應用和具體問題求解?？忌鷳莆崭鞣N數據結構及其操作，具備一定的算法設計與分析能力，能夠根據實際問題選擇合適的數據結構并設計算法實現。
二、考試主要內容
（一）緒論
1、基本概念和術語
1）基本要求
了解課程的研究內容，理解數據結構的相關概念。
2）考試范圍
掌握數據結構的研究內容、基本概念和相關術語；理解抽象數據類型的表示與實現。
2、算法和算法分析
1）基本要求
理解算法的含義，熟悉算法描述語言，掌握算法的性能評價指標及評價方法,并能分析常用算法的時間復雜度。
2）考試范圍
算法的概念與特征；算法效率的度量指標；時間復雜度與空間復雜度的計算方法；常見時間復雜度類型與性能優劣比較。
（二）線性表
1、線性表的類型定義
1）基本要求
掌握線性表的邏輯結構及相關概念；理解線性表的抽象數據類型。
2）考試范圍
線性表的概念及文件、數據項及記錄的相關概念；線性表的抽象數據類型；用線性表表示集合合并的算法；合并有序線性表的算法。
2、線性表的表示和實現
1）基本要求
掌握線性表的順序與鏈式兩種存儲結構及其各種基本運算的的實現過程；掌握兩種存儲方式之間的差異及各自優缺點；能夠靈活運用順序表和鏈表解決實際問題。
2）考試范圍
順序存儲結構的概念及計算第i個元素存儲地址的公式；用類C描述線性表的順序存儲結構；順序表的初始化、插入、刪除、定位和有序表合并算法；線性鏈表及相關概念；用C語言描述線性表的鏈式存儲結構；鏈表的訪問、插入、刪除和有序合并算法；線性表的靜態鏈表表示基本定義；循環鏈表的定義以及與單鏈表的區別；雙向鏈表的定義和存儲表示；雙向鏈表的插入與刪除算法；一元多項式的表示及相加算法實現。
（三）棧和隊列
1、棧
1）基本要求
理解棧的定義、特性和運算；掌握棧的順序存儲實現及其性能分析；理解和掌握用棧實現表達式求解的過程；了解棧的鏈式存儲結構的實現。
2）考試范圍
棧的抽象數據類型定義；棧的先進后出特性；棧的存儲表示與基本操作實現；棧的應用。
2、隊列
1）基本要求
理解隊列的定義、特性和運算；理解隊列的順序存儲實現及其性能分析；理解循環隊列的背景和實現方法；理解隊列的鏈式存儲結構的實現及其性能分析。
2）考試范圍
隊列的抽象數據類型定義；隊列的先進先出特性；隊列的存儲表示與基本操作實現。
（四）串
1）基本要求
掌握串的相關概念、串的存儲結構（順序串和鏈式串）及基本運算的實現；掌握KMP算法的基本思想及模式匹配過程；能靈活運用串的特點解決復雜的應用問題。
2）考試范圍：
串類型的定義；串的定長順序存儲、堆分配存儲、塊鏈存儲表示和實現；串的模式匹配算法；串的應用。
（五）數組和廣義表
1）基本要求
理解數組結構及其存儲，理解矩陣的壓縮存儲方式及其映射關系；理解廣義表以及子表、原子和長度等概念；理解廣義表的基本運算及其存儲。
2）考試范圍：
數組的定義；二維數組的兩種存儲方式（以行序為主、以列序為主）及其數組元素存儲位置計算公式；特殊矩陣與稀疏矩陣的壓縮存儲方式；廣義表的定義和存儲結構。
（六）樹和二叉樹
1）基本要求
理解樹和二叉樹的定義及相關術語；理解二叉樹的五個性質及相關概念；理解二叉樹的兩種存儲結構的形式、描述及特點，理解二叉樹的遍歷運算，并能綜合應用；理解線索二叉樹及其存儲結構，線索化方法和算法，以及在指定線索二叉樹中求解指定次序的前趨和后繼的算法；理解樹和森林的存儲結構及其描述，樹（森林）與二叉樹的相互轉換，樹（森林）的遍歷算法；理解樹模型在軟件設計中的作用；理解赫夫曼樹的有關概念、應用及構造。
2）考試范圍：
樹的定義和基本術語；二叉樹的定義；二叉樹的性質；二叉樹的存儲結構；遍歷二叉樹；線索二叉樹；樹的存儲結構；森林與二叉樹的轉換；樹和森林的遍歷；最優二叉樹（赫夫曼樹）；赫夫曼編碼。
（七）圖
1）基本要求
理解圖的相關概念、圖的存儲結構；熟練掌握圖的兩種遍歷算法（深度優先搜索遍歷和廣度優先搜索遍歷），并能靈活應用；熟練掌握求解最小生成樹的算法；熟練掌握拓撲排序算法和關鍵路徑算法，并能靈活應用；熟練掌握最短路徑算法并能靈活應用。
2）考試范圍：
圖的定義和術語；圖的數組表示法與鄰接表存儲結構；圖的深度優先搜索與廣度優先搜索；最小生成樹；拓撲排序；關鍵路徑；最短路徑。
（八）查找
1）基本要求
理解查找的相關概念，理解簡單順序查找、折半查找算法及性能分析；理解二叉排序樹的定義、特性和查找算法，二叉排序樹的構造、插入結點的算法和刪除結點的實現方法；理解平衡二叉樹的定義及構造平衡二叉樹的方法；理解Ｂ-樹的定義、特性和查找方法，理解在Ｂ-樹中插入和刪除關鍵字的運算實現；理解散列表結構的相關概念和構造散列函數的基本方法；理解沖突及其處理的基本方法；理解哈希查找過程；掌握上述各種查找算法的時間性能分析。
2）考試范圍：
順序表的查找；有序表的查找；索引順序表的查找；二叉排序樹和平衡二叉樹；B-樹和B+樹；什么是哈希表；哈希函數的構造方法；處理沖突的方法；哈希表的查找及分析。
（九）內部排序
1）基本要求
理解排序的相關概念；理解直接插入排序、Shell排序、冒泡排序、快速排序、簡單選擇排序、堆排序和歸并排序等算法的基本思想、算法實現、時間復雜度和空間占用情況，并能根據具體問題選擇合適的算法。
2）考試范圍：
排序概述；插入排序；交換排序；選擇排序；歸并排序；各種內部排序方法的分析比較。
三、考試形式和試卷結構
1、考試時間和分值
如：考試時間為180分鐘，試卷滿分為150分。
2、考試題型結構
（1）單項選擇題：每個問題都只有一個選擇，根據題目內容選擇正確答案。
（2）填空題：根據題目要求，填充對應位置的內容。
（3）判斷題：根據題目內容判斷其描述問題的正確性。
（4）應用題：根據題目內容完成相應問題的求解，要求給出具體求解過程。
（5）算法設計題：根據題目要求，采用類C語言或C語言完成算法的編寫，解決實際問題。
四、參考書目
《數據結構》（C語言版），嚴蔚敏，吳偉民主編，清華大學出版社，2018
免責聲明：本文系轉載自網絡，如有侵犯，請聯系我們立即刪除，另：本文僅代表作者個人觀點，與本網站無關。其原創性以及文中陳述文字和內容未經本站證實，對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾，請讀者僅作參考，并請自行核實相關內容。
|
文章搜索
您現在的位置： 
