網(wǎng)站介紹 關(guān)于我們 聯(lián)系方式 友情鏈接 廣告業(yè)務(wù) 幫助信息
1998-2022 ChinaKaoyan.com Network Studio. All Rights Reserved. 滬ICP備12018245號
初試《數(shù)據(jù)結(jié)構(gòu)》科目考試大綱
一、考查目標(biāo)
考查學(xué)生對數(shù)據(jù)結(jié)構(gòu)及算法分析相關(guān)基礎(chǔ)知識及技能的掌握水平,并對學(xué)生利用有關(guān)基礎(chǔ)知識和技能分析研究計算機加工的數(shù)據(jù)結(jié)構(gòu)特性,進(jìn)一步為實際應(yīng)用涉及的數(shù)據(jù)選擇及設(shè)計適當(dāng)?shù)倪壿嫿Y(jié)構(gòu)、存儲結(jié)構(gòu)及其相應(yīng)的算法能力進(jìn)行考核。
二、考試形式與試卷結(jié)構(gòu)
(一)試卷滿分及考試時間
滿分為150分,考試時間為3小時。
(二)答題方式
答題方式為閉卷、筆試。
(三)試卷內(nèi)容結(jié)構(gòu)
內(nèi)容結(jié)構(gòu)為各部分知識點在試卷中所占的比例。
(四)試卷題型結(jié)構(gòu)
選擇題10分、簡答題20分、解答題80分、算法設(shè)計題40分,合計150分。
三、考查內(nèi)容及要求
(一)數(shù)據(jù)結(jié)構(gòu)概述
1、基本概念及術(shù)語
數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、抽象數(shù)據(jù)類型的概念;數(shù)據(jù)結(jié)構(gòu)的分類、兩種物理結(jié)構(gòu)的特點。
2、ADT的表示與實現(xiàn)
ADT的定義、作用及類C語言實現(xiàn)方法。
3、算法和算法分析
算法的概念、特性和評判標(biāo)準(zhǔn)、算法時間復(fù)雜度的概念、簡單的算法時間復(fù)雜度分析。
(二)線性表
1、線性表的類型定義
線性表的抽象數(shù)據(jù)類型定義、線性結(jié)構(gòu)的特點。
2、線性表的順序表示和實現(xiàn)
順序表的含義、特點和相關(guān)算法。
3、線性表的鏈?zhǔn)奖硎竞蛯崿F(xiàn)
鏈表的含義、特點和相關(guān)算法。
4、一元多項式表示與相加
一元多項式表示與相加的方法、順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)的區(qū)別和選擇。
(三)棧與隊列
1、棧
棧結(jié)構(gòu)的抽象數(shù)據(jù)類型定義、特點、存儲結(jié)構(gòu)和相關(guān)算法。
2、棧的應(yīng)用舉例
棧的應(yīng)用及相關(guān)算法。
3、隊列
隊列結(jié)構(gòu)的抽象數(shù)據(jù)類型定義、特點、存儲結(jié)構(gòu)和相關(guān)算法。
(四)串
1、串類型的定義、表示和實現(xiàn)
串的定義、串的三種主要表示和實現(xiàn)方式。
2、串的模式匹配
串的常見模式匹配算法。
(五)數(shù)組與廣義表
1、數(shù)組的定義
數(shù)組概念、特點。
2、數(shù)組的順序表示和實現(xiàn)
數(shù)組順序存儲結(jié)構(gòu)表示和實現(xiàn)。
3、數(shù)組的壓縮存儲
特殊矩陣的壓縮存儲、稀疏矩陣的壓縮存儲的實現(xiàn)方法。
4、廣義表的定義和實現(xiàn)
廣義表的定義及運算、廣義表的存儲結(jié)構(gòu)。
(六)樹和二叉樹
1、樹的定義和基本術(shù)語
樹的定義、常用術(shù)語。
2、二叉樹
二叉樹的定義、二叉樹的性質(zhì)、存儲結(jié)構(gòu)。
3、數(shù)組的壓縮存儲
特殊矩陣的壓縮存儲、稀疏矩陣的壓縮存儲的實現(xiàn)方法。
4、遍歷二叉樹和線索二叉樹
二叉樹遍歷及線索化的概念、方法和算法。
5、樹和森林
樹的存儲結(jié)構(gòu),樹、森林、二叉樹間相互轉(zhuǎn)換方法、樹和森林遍歷方法。
6、赫夫曼樹及其應(yīng)用
赫夫曼樹和赫夫曼編碼構(gòu)造方法。
(七)圖
1、圖的定義和術(shù)語
圖的定義和術(shù)語。
2、圖的存儲結(jié)構(gòu)
圖的鄰接矩陣表示法、鄰接表表示法、十字鏈表表示法。
3、圖的遍歷
圖的深度優(yōu)先及廣度優(yōu)先遍歷方法和算法。
4、圖的連通性問題
連通子圖、生成樹、最小生成樹的定義和構(gòu)造方法。
5、拓?fù)渑判?br />
拓?fù)渑判蚍椒、算法及?yīng)用。
6、最短路徑
最短路徑問題求解方法、算法及應(yīng)用。
7、關(guān)鍵路徑
關(guān)鍵路徑問題求解方法、算法及應(yīng)用。
(八)查找
1、靜態(tài)查找表
查找的概念、順序查找和折半查找的方法和算法。
2、動態(tài)查找表
二叉查找樹和二叉平衡概念及作用、二叉查找樹和二叉平衡樹相關(guān)算法。
3、哈希表
哈希表的概念、沖突的概念、常見哈希函數(shù)構(gòu)造方法、哈希表的處理沖突的常用方法。
(九)排序
1、排序的概念
排序的有關(guān)概念、排序的類型。
2、排序方法及算法
掌握插入排序、快速排序、選擇排序、歸并排序、基數(shù)排序的方法、算法及相關(guān)算法時間、空間復(fù)雜度分析過程。
四、考試用具說明
考試使用黑色筆作答,考試時需要攜帶計算器、直尺、筆。
來源未注明“中國考研網(wǎng)”的資訊、文章等均為轉(zhuǎn)載,本網(wǎng)站轉(zhuǎn)載出于傳遞更多信息之目的,并不意味著贊同其觀點或證實其內(nèi)容的真實性,如涉及版權(quán)問題,請聯(lián)系本站管理員予以更改或刪除。如其他媒體、網(wǎng)站或個人從本網(wǎng)站下載使用,必須保留本網(wǎng)站注明的"稿件來源",并自負(fù)版權(quán)等法律責(zé)任。
來源注明“中國考研網(wǎng)”的文章,若需轉(zhuǎn)載請聯(lián)系管理員獲得相應(yīng)許可。
聯(lián)系方式:chinakaoyankefu@163.com
掃碼關(guān)注
了解考研最新消息
網(wǎng)站介紹 關(guān)于我們 聯(lián)系方式 友情鏈接 廣告業(yè)務(wù) 幫助信息
1998-2022 ChinaKaoyan.com Network Studio. All Rights Reserved. 滬ICP備12018245號