|
友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。 下載流程： 考研真題 點擊“考研試卷””下載; 考博真題 點擊“考博試卷庫” 下載
2020年西安理工大學計算機科學與工程學院
碩士研究生入學考試課程《數據結構》考試大綱
科目代碼：863
科目名稱：數據結構
第一部分 考試說明
一、考試性質
數據結構是計算機各專業的專業基礎課。考核目標是測試計算機科學與技術及相近各專業的本科畢業生對于該課程的知識掌握程度,以保證被錄取者具有本學科基本的專業理論基礎及程序設計能力,以利于計算機科學與技術及軟件工程學科的導師擇優選拔碩士研究生。
考試對象為參加全國碩士研究生入學考試的本科畢業生和具有同等學力的在職人員。
二、考試范圍
各種基本類型的數據結構的概念、特征、操作、存儲表示和基本應用；各種基本查找表的概念、特征及其查找方法；基本的內排序方法及其應用；用C語言(或C++)進行算法描述,并對算法進行分析。
三、評價目標
考查基本概念、基本知識、基本方法的基礎上，注重考查學生運用基本知識來分析和解決實際問題的能力,注重考查算法和程序設計的能力。
具體要求見本考試大綱第二部分的“考查要點”。
四、考試形式與試卷結構
1.答卷方式:閉卷,筆試。
2.答題時間:180 分鐘。
3.考查內容及其考查比例
基本概念、基本知識、基本方法約占50%～60%；綜合應用、算法和程序設計與算法分析約占50%～40%。
4.試卷結構與考試題型
試卷共150分,基本的考試題型有：
(1)單項選擇題和多項選擇題(基本概念)；
(2)填空題(基本知識、基本方法)；
(3)簡答題（概念理解）；
(4)應用題(基本方法的應用)；
(5)算法和程序設計題；
五、教材和參考書
教材: 《數據結構》(C語言版)，嚴蔚敏、吳偉民編著,清華大學出版社,2009.6
第二部分 考查要點
1.數據結構基本概念和術語
1） 了解數據元素、數據結構、抽象數據類型、存儲結構等概念；了解算法概念及算法設計的基本要求 ；
2） 掌握算法分析方法、語句的頻度和估算時間復雜度、空間復雜度分析方法。
2.線性表
1） 理解線性表的定義和基本操作；線性表的抽象數據類型定義；
2） 掌握線性表的順序存儲結構及應用方法；
3） 掌握線性表的鏈式存儲結構(單鏈表,雙鏈表,循環鏈表)。
具體要求：
要求掌握線性表的順序存儲方式下的元素插入、元素刪除及線性表遍歷算法；要求掌握線性表的鏈式存儲方式下，元素的插入、元素的刪除及線性表遍歷算法（帶頭結點及不帶頭結點的單鏈表）
3.棧和隊列
1） 理解棧的定義和基本操作及棧的抽象數據類型定義；
2） 掌握順序棧及鏈式棧的操作方法；
3） 掌握棧在遞歸算法、 算術表達式求值及其它應用。
4） 理解隊列的定義和基本操作及隊列的抽象數據類型；
5） 掌握順序隊列的操作方法，了解鏈式隊列的操作方法；
具體要求：
要求掌握棧的順序存儲和鏈式存儲兩種方式下入棧、出棧的算法；循環隊列的順序存儲方式下，入隊和出隊算法。
4.字符串
1） 了解字符串的定義和基本操作及字符串的存儲結構；
2） 了解字符串的基本操作；
3） 了解字符串模式匹配應用。
5.數組
1） 理解數組的定義和基本操作；
2） 掌握數組的順序存儲結構及應用；
3） 掌握特殊矩陣和稀疏矩陣的壓縮存儲。
具體要求：掌握三角矩陣的壓縮存儲方法和稀疏矩陣三元組法的壓縮存儲方法。
6.樹和二叉樹
1） 理解樹的基本概念和基本操作,樹的抽象數據類型。
2） 理解二叉樹的概念和性質,特殊二叉樹及二叉樹的存儲結構；
3） 掌握遍歷二叉樹：前序遍歷,中序遍歷,后序遍歷,層次遍歷。
4） 掌握線索二叉樹的概念和存儲結構,二叉樹的線索化的方法,線索二叉樹的遍歷方法。
5） 理解樹的存儲結構；
6） 掌握樹與二叉樹之間的轉換,森林與二叉樹之間的轉換,森林的遍歷方法。
7） 掌握樹的路徑長度和帶權路徑長度的計算方法；
8） 理解赫夫曼樹(Huffman)的概念,并掌握哈夫曼算法, 哈夫曼編碼樹的構造方法。
具體要求：
掌握上述2）-8）基本概念相關的所有數據演示過程及相關計算，例如給定節點權值構造赫夫曼樹、計算帶權路徑長度并給出赫夫曼樹編碼，給定二叉樹構造出某種線索二叉樹等等；
掌握二叉樹的二叉鏈表存儲方式下的先序、中序、后序遍歷的算法、二叉樹的葉子結點計數算法、節點計數的算法等。
7.圖
1） 理解圖的基本概念和基本操作，圖的抽象數據類型、有向圖、無向圖等概念。
2） 掌握圖的存儲結構：數組表示法(鄰接矩陣)；鄰接表，逆鄰接表，十字鏈表；
3） 掌握圖的遍歷：深度優先搜索法, 寬度優先搜索法, 求圖的連通分量。
4） 理解生成樹、最小生成樹的概念，并掌握克魯斯卡爾(Kruskal)算法,普里姆(Prim)算法構造最小生成樹的方法。
5） 掌握從一個頂點到其余各頂點的最短路徑。
具體要求：
掌握上面2）-5）相關的各算法的數據演示方法；
掌握圖的深度優先搜索算法和圖的廣度優先搜索算法。
9.查找
1） 理解查找的概念,關鍵字比較次數,平均查找長度。
2） 掌握順序表的查找:順序查找,折半查找。
3） 掌握樹表的查找:二叉排序樹,二叉排序樹的的概念和基本操作,二叉排序樹的建立,二叉排序樹其它操作實現；掌握平衡二叉樹的概念。
4） 掌握哈希(Hash)表的查找:哈希表的概念,哈希函數構造方法,哈希表的建立和查找方法,開放地址法及鏈地址法沖突處理方法及平均查找長度的計算方法。
具體要求：
掌握上述2）-4）相關的數據演示過程及平均查找長度的計算方法；
掌握在順序存儲的線性表上實施順序查找和有序順序表上實施折半查找的算法；掌握在二叉排序樹中遞歸查找指定關鍵字的算法。
10.排序
1） 理解排序的穩定性、比較關鍵字次數、移動記錄次數等排序概念。
2） 交換排序:冒泡排序,快速排序。
3） 插入排序:直接插入排序,希爾排序。
4） 選擇排序:直接選擇排序,堆排序。
5） 歸并排序。
6） 掌握各種排序算法的特征評價，了解其應用。
具體要求：
掌握2）-5）各種排序方法的數據演示過程和特點、時間復雜度及空間復雜度；
掌握冒泡排序、直接插入排序、直接選擇排序、快速排序的算法。
免責聲明：本文系轉載自網絡，如有侵犯，請聯系我們立即刪除，另：本文僅代表作者個人觀點，與本網站無關。其原創性以及文中陳述文字和內容未經本站證實，對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾，請讀者僅作參考，并請自行核實相關內容。
|
文章搜索
您現在的位置： 
