碩士研究生招生考試《數(shù)據(jù)結(jié)構(gòu)》考試大綱

碩士研究生招生考試《數(shù)據(jù)結(jié)構(gòu)》考試大綱I.考試性質(zhì)《數(shù)據(jù)結(jié)構(gòu)》是一門專業(yè)基礎(chǔ)課，要求考生能夠理解數(shù)據(jù)結(jié)構(gòu)的基本概念;掌握數(shù)據(jù)結(jié)構(gòu)中邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)的基本概念和差異，以及各種基本操作的實(shí)現(xiàn)；在掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM(jìn)行設(shè)計(jì)與分析；能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進(jìn)行問題求解；能夠針對具體問題設(shè)計(jì)正確的數(shù)據(jù)結(jié)構(gòu)加以應(yīng)用；具備采用類c或c++或JAVA語言設(shè)計(jì)與實(shí)現(xiàn)算法的能力。本課程包括：算法的基本概念、分析和設(shè)計(jì)方法；軟件開發(fā)中常用的各類結(jié)構(gòu)，包括線性結(jié)構(gòu)、樹結(jié)構(gòu)、圖結(jié)構(gòu)；查找、排序等各類常用算法。主要考察學(xué)生對數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識的理解、是否具備對現(xiàn)有常用結(jié)構(gòu)和算法的應(yīng)用能力、是否具備針對具體應(yīng)用設(shè)計(jì)合適數(shù)據(jù)結(jié)構(gòu)的能力。II.考查目標(biāo)考試目標(biāo)是了解常見數(shù)據(jù)結(jié)構(gòu)的概念，掌握數(shù)據(jù)結(jié)構(gòu)的構(gòu)造方法以及相應(yīng)的算法思想，會對重點(diǎn)數(shù)據(jù)結(jié)構(gòu)的操作方法和算法進(jìn)行簡單的偽代碼編寫。III.考試形式和試卷結(jié)構(gòu)一、試卷總分及考試時間試卷總分為150分，考試時間180分鐘。二、答題方式答題方式為閉卷、筆試。三、試卷內(nèi)容結(jié)構(gòu)基本概念理解70%算法的應(yīng)用50%算法設(shè)計(jì)30%四、試卷題型結(jié)構(gòu)⑴選擇:40分；(2)填空題20分⑶簡答題:30分；⑷算法應(yīng)用題:30分；⑸算法設(shè)計(jì)題:30分。Ⅳ．考查內(nèi)容線性表線性表的邏輯結(jié)構(gòu)線性表的順序存儲結(jié)構(gòu)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)單鏈表循環(huán)鏈表雙向鏈表?xiàng)Ｅc隊(duì)列棧棧的基本概念順序棧1.3鏈?zhǔn)綏ｊ?duì)列隊(duì)列的基本概念鏈隊(duì)列循環(huán)隊(duì)列——隊(duì)列的順序存儲結(jié)構(gòu)串串類型的定義字符串的實(shí)現(xiàn)字符串模式匹配算法簡單字符串模式匹配算法首尾字符串模式匹配算法KMP模式匹配算法數(shù)組和廣義表數(shù)組數(shù)組的基本概念數(shù)組的順序存儲方式矩陣矩陣的定義和操作特殊矩陣稀疏矩陣廣義表基本概念廣義表的存儲結(jié)構(gòu)第五章、樹和二叉樹樹的基本概念樹的定義基本術(shù)語二叉樹二叉樹的定義二叉樹的性質(zhì)二叉樹的存儲結(jié)構(gòu)二叉樹的遍歷遍歷的定義遍歷算法樹和森林樹的存儲表示森林的存儲表示樹和森林的遍歷樹和森林與二叉樹的轉(zhuǎn)換哈夫曼樹與哈夫曼編碼哈夫曼樹的基本概念哈夫曼樹構(gòu)造算法哈夫曼樹編碼第六章、圖圖的定義和術(shù)語圖的存儲表示鄰接矩陣鄰接表圖的遍歷深度優(yōu)先搜索廣度優(yōu)先搜索圖的最小代價生成樹Prim算法Kruskal算法有向無環(huán)圖的應(yīng)用拓?fù)渑判蜿P(guān)鍵路徑最短路徑問題單源點(diǎn)最短路徑所有頂點(diǎn)之間的最短路徑第七章、查找1.查找的基本概念2.靜態(tài)表的查找2.1順序查找2.2有序表的查找3.動態(tài)查找表3.1二叉排序樹4.散列表4.1散列表的概念4.2構(gòu)造散列函數(shù)的方法4.3處理沖突的方法第八章、排序排序概述插入排序直接插入排序Shell排序交換排序冒泡排序快速排序選擇排序普通選擇排序堆排序歸并排序Ⅴ主要參考書籍[1]李春葆、尹為民、蔣晶玨、喻丹丹、蔣