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