|
友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。 下載流程： 考研真題 點擊“考研試卷””下載; 考博真題 點擊“考博試卷庫” 下載
《數據結構》(自主命題)課程考試大綱
一、考試內容
要求掌握基本數據結構（線性表、棧與隊列、數組、二叉樹、圖
等）的特點及其不同實現，掌握常用的算法，同時對算法的時間復雜
度有一定的分析能力，并考察學生能否運用數據結構解決實際問題的
能力。具體知識點和考核要求如下：
1.緒論
(1)掌握數據、數據元素、數據項、數據類型等基本概念和術語的含
義；
(2)掌握數據結構的四種邏輯結構和兩種存儲結構表示方法，特
別是邏輯結構和存儲結構之間的關系；
(3)理解算法五個要素的確切含義；
(4)掌握算法設計的基本要求以及計算語句頻度和算法時間復雜
度的方法。
2、線性表
(1)深刻理解線性結構的特點以及線性表的概念；
(2)熟練掌握順序表和單鏈表的組織方法；
(3)熟練掌握線性表在順序存儲結構和鏈式存儲結構上的查找、
插入和刪除等算法；
1)了解順序表與鏈表的優缺點；
2)了解循環鏈表及雙鏈表的組織方法和特點。
3、棧和隊列
(1)理解棧和隊列的定義、特點及與線性表的異同；
(2)掌握順序棧的組織方法及進棧、退棧等基本算法，弄清棧滿
和?？盏臈l件及利用棧解決簡單的實際問題，如：數制轉換、表達式
求值等；
(3)掌握鏈棧的組織方法及進棧、退棧等基本算法；
(4)掌握鏈隊列上實現的入隊、出隊等基本算法；
(5)掌握循環隊列上實現的入隊、出隊等基本算法，及隊滿、隊
空的條件，弄清順序隊列的“假溢出”現象及其原因。
4、串
(1)掌握串的有關概念和術語、串的邏輯結構和特點；
(2)掌握串的存儲結構；
(3)掌握模式匹配的定義及 KMP 算法。
5、數組和廣義表
(1)掌握多維數組存在一維數組中的兩種存儲表示方法并綜合運
用數組在以行為主的存儲結構中的地址計算方法；
(2)掌握對特殊矩陣(對稱矩陣,下三角矩陣等) 進行壓縮存儲時
的下標變換公式；
(3)了解稀疏矩陣的三元組壓縮存儲表示方法及有關算法；
(4)理解并掌握廣義表的定義、存儲結構。
6、樹和二叉樹
(1)理解樹的概念并熟悉有關術語的含義（如孩子、兄弟、深度、
度等概念）；
(2)深刻領會二叉樹的定義和結構特性，了解相應的證明方法；
(3)理解常見的二叉樹（如滿二叉樹、完全二叉樹）的概念；
(4)深刻領會二叉樹的順序存儲和鏈式存儲結構；
(5)熟悉二叉樹的遍歷次序并熟練掌握遍歷算法；
(6)掌握二叉樹線索化的實質及線索化的過程；
(7)了解樹和森林的定義、樹的存儲結構并掌握樹、森林與二叉
樹之間的相互轉換方法；
(8)掌握赫夫曼（Huffman）樹的概念及其構造赫夫曼樹的方法。
7、圖
(1)理解圖的概念并熟悉有關術語（如：頂點、邊、有向圖、無
向圖、入度、出度、連通性與生成樹等）；
(2)熟練掌握鄰接矩陣表示法和鄰接表表示法；
(3)掌握連通圖遍歷的基本思想和算法（深度優先和廣度優先），
能夠給出兩種遍歷的頂點訪問序列；
(4)掌握非連通圖的遍歷方法及圖的連通分量的求法；
(5)理解最小生成樹的概念及普里姆（Prim）算法和克魯斯卡爾
算法（Kruskal）,并能根據算法用圖示法表示出給定網的一棵最小生
成樹的過程；
(6)了解 AOE 有向無環網的關鍵路徑, 關鍵活動的計算思路；
(7)掌握拓撲排序的基本思想，對給定的有向圖（若拓撲序列存
在）能夠寫出所有拓撲序列；
(8)掌握求單源點最短距離的迪杰斯特拉（Dijkstra）算法。
8、查找
(1)熟練掌握順序查找算法、折半查找算法；
(2)掌握查找效率的計算方法—平均查找長度；
(3)理解二叉排序樹的構造和查找算法；
(4)掌握哈希表、哈希函數的構造方法、以及處理沖突的方法。
9、內部排序
理解內部排序的定義和各種排序算法的基本思想及其特點；
了解各種內部排序（插入，希爾，選擇，冒泡，快速，堆，歸并
等排序）的排序過程及其依據的原則；
一般了解排序方法“穩定”的含義；
了解各種內部排序算法的優缺點、各種排序算法的時間花費。
二、考試形式及試卷結構
考試形式為閉卷、筆試，試卷滿分 150 分，考試時間為 180 分鐘。
試卷主要題型：單項選擇題、填空題、判斷對錯題、應用題、程
序閱讀題、算法設計題。
免責聲明：本文系轉載自網絡，如有侵犯，請聯系我們立即刪除，另：本文僅代表作者個人觀點，與本網站無關。其原創性以及文中陳述文字和內容未經本站證實，對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾，請讀者僅作參考，并請自行核實相關內容。
|
文章搜索
您現在的位置： 
