《2014年湖南大學(xué)085212軟件工程考研大綱.doc》由會(huì)員分享，可在線(xiàn)閱讀，更多相關(guān)《2014年湖南大學(xué)085212軟件工程考研大綱.doc（5頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

2014年湖南大學(xué)085212軟件工程考研大綱 852《數(shù)據(jù)結(jié)構(gòu)》考試大綱 　　一、考試要求 　　《數(shù)據(jù)結(jié)構(gòu)》是一門(mén)專(zhuān)業(yè)基礎(chǔ)課，要求考生能夠理解數(shù)據(jù)結(jié)構(gòu)的基本概念;掌握數(shù)據(jù)結(jié)構(gòu)中邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)的基本概念和差異，以及各種基本操作的實(shí)現(xiàn)；在掌握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM(jìn)行設(shè)計(jì)與分析；能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進(jìn)行問(wèn)題求解；能夠針對(duì)具體問(wèn)題設(shè)計(jì)正確的數(shù)據(jù)結(jié)構(gòu)加以應(yīng)用；具備采用類(lèi)c或c++語(yǔ)言設(shè)計(jì)與實(shí)現(xiàn)算法的能力。 　　本課程包括：算法的基本概念、分析和設(shè)計(jì)方法；軟件開(kāi)發(fā)中常用的各類(lèi)結(jié)構(gòu)，包括線(xiàn)性結(jié)構(gòu)、樹(shù)結(jié)構(gòu)、圖結(jié)構(gòu)；查找、排序等各類(lèi)常用算法。主要考察學(xué)生對(duì)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識(shí)的理解、是否具備對(duì)現(xiàn)有常用結(jié)構(gòu)和算法的應(yīng)用能力、是否具備針對(duì)具體應(yīng)用設(shè)計(jì)合適數(shù)據(jù)結(jié)構(gòu)的能力。 　　二、主要參考書(shū)目 　　《數(shù)據(jù)結(jié)構(gòu)與算法分析》（C++版）CliffordA.Shaffer第二版電子工業(yè)出版社 　　《數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版)》，嚴(yán)蔚敏，吳偉民，清華大學(xué)出版社； 　　三、考查范圍 　　1、數(shù)據(jù)結(jié)構(gòu)基本概念及簡(jiǎn)單的算法分析 　　1)什么是數(shù)據(jù)結(jié)構(gòu) 　　2)抽象數(shù)據(jù)類(lèi)型及面向?qū)ο蟾拍睿簲?shù)據(jù)類(lèi)型；數(shù)據(jù)抽象與抽象數(shù)據(jù)類(lèi)型；面向?qū)ο蟮母拍?；用于描述?shù)據(jù)結(jié)構(gòu)的語(yǔ)言 　　3)數(shù)據(jù)結(jié)構(gòu)的抽象層次 　　4)算法定義 　　5)性能分析與度量：算法的性能標(biāo)準(zhǔn)；算法的后期測(cè)試；算法的事前估計(jì)；空間復(fù)雜度度量；時(shí)間復(fù)雜度度量；時(shí)間復(fù)雜度的漸進(jìn)表示法；漸進(jìn)的空間復(fù)雜. 　　2、數(shù)組 　　1)作為抽象數(shù)據(jù)類(lèi)型的數(shù)組：數(shù)組的定義和初始化；作為抽象數(shù)據(jù)類(lèi)型的數(shù)組；數(shù)組的順序存儲(chǔ)方式； 　　2)順序表：順序表的定義和特點(diǎn)；順序表的類(lèi)定義；順序表的查找、插入和刪除；使用順序表的事例； 　　3)字符串：字符串的抽象數(shù)據(jù)類(lèi)型；字符串操作的實(shí)現(xiàn)；字符串的模式匹配。 　　3、鏈表 　　1)單鏈表：?jiǎn)捂湵淼慕Y(jié)構(gòu)；單鏈表的類(lèi)定義；單鏈表中的插入與刪除；帶表頭結(jié)點(diǎn)的單鏈表； 　　2)循環(huán)鏈表：循環(huán)鏈表的類(lèi)定義；用循環(huán)鏈表解約瑟夫問(wèn)題；多項(xiàng)式及其相加：多項(xiàng)式的類(lèi)定義；多項(xiàng)式的加法 　　3)雙向鏈表 　　4、棧和隊(duì)列 　　1)棧：棧的抽象數(shù)據(jù)類(lèi)型；棧的順序存儲(chǔ)表示；棧的鏈接存儲(chǔ)表示 　　2)隊(duì)列：隊(duì)列的抽象數(shù)據(jù)類(lèi)型；隊(duì)列的順序存儲(chǔ)表示；隊(duì)列的鏈接存儲(chǔ)表示； 　　3)隊(duì)列的應(yīng)用舉例 　　4)優(yōu)先級(jí)隊(duì)列：優(yōu)先級(jí)隊(duì)列的定義；優(yōu)先級(jí)隊(duì)列的存儲(chǔ)表示 　　5、遞歸 　　1)遞歸的概念 　　2)迷宮問(wèn)題 　　3)遞歸過(guò)程與遞歸工作棧 　　4)利用棧實(shí)現(xiàn)的迷宮問(wèn)題非遞歸解法 　　5)廣義表：廣義表的概念；廣義表的表示及操作；廣義表存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)； 　　6)廣義表的訪(fǎng)問(wèn)算法； 　　6、樹(shù)與森林 　　1)樹(shù)和森林的概念：樹(shù)的定義；樹(shù)的術(shù)語(yǔ)；樹(shù)的抽象數(shù)據(jù)類(lèi)型 　　2)二叉樹(shù)：二叉樹(shù)的定義；二叉樹(shù)的性質(zhì)；二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型 　　3)二叉樹(shù)的表示：數(shù)組表示；鏈表存儲(chǔ)表示 　　4)二叉樹(shù)遍歷：中序遍歷；前序遍歷；后序遍歷；應(yīng)用二叉樹(shù)遍歷的事例；二叉樹(shù)遍歷的游標(biāo)類(lèi)；不用棧的二叉樹(shù)中序遍歷算法 　　5)線(xiàn)索化二叉樹(shù)：線(xiàn)索；中序線(xiàn)索化二叉樹(shù)；前序與后序的線(xiàn)索化 　　6)堆：堆的定義；堆的建立；堆的插入與刪除 　　7)樹(shù)與森林：樹(shù)的存儲(chǔ)表示；森林與二叉樹(shù)的轉(zhuǎn)換；樹(shù)的遍歷；森林的遍歷；二叉樹(shù)的計(jì)數(shù) 　　8)霍夫曼樹(shù)：路徑長(zhǎng)度；霍夫曼樹(shù)；霍夫曼編碼 　　7、集合與搜索 　　1)集合及其表示：集合基本概念；以集合為基礎(chǔ)的抽象數(shù)據(jù)類(lèi)型；用位向量實(shí)現(xiàn)集合抽象據(jù)類(lèi)型；用有序鏈表實(shí)現(xiàn)集合的抽象數(shù)據(jù)類(lèi)型 　　2)等價(jià)類(lèi)：等價(jià)關(guān)系與等價(jià)類(lèi)；確定等價(jià)類(lèi)的鏈表方法； 　　3)簡(jiǎn)單的搜索結(jié)構(gòu)：搜索的概念；靜態(tài)搜索結(jié)構(gòu)；順序搜索；基于有序順序表的對(duì)分搜索 　　4)二叉搜索樹(shù)：定義；二叉搜索樹(shù)上的搜索；二叉搜索樹(shù)的插入；二叉搜索樹(shù)的刪除； 　　5)AVL樹(shù)：AVL樹(shù)的定義；平衡化旋轉(zhuǎn)；AVL樹(shù)的插入和刪除；AVL樹(shù)的高度 　　8、圖 　　1)圖的基本概念：圖的基本概念；圖的抽象數(shù)據(jù)類(lèi)型 　　2)圖的存儲(chǔ)表示：鄰接矩陣；鄰接表；鄰接多重表 　　3)圖的遍歷與連通性：深度優(yōu)先搜索；廣度優(yōu)先搜索；連通分量；重連通分量 　　4)最小生成樹(shù)：克魯斯卡爾算法；普里姆算法 　　5)最短路徑；拓?fù)渑判?；關(guān)鍵路徑 　　9、排序 　　1)插入排序：直接插入排序；希爾排序 　　2)交換排序：起泡排序；快速排序 　　3)選擇排序：直接選擇排序；錦標(biāo)賽排序；堆排序 　　4)歸并排序：歸并；迭代的歸并排序算法；遞歸的表歸并排序 　　5)基數(shù)排序：多關(guān)鍵碼排序；鏈?zhǔn)交鶖?shù)排序 　　6)外排序：外排序的基本過(guò)程；k路平衡歸并； 　　10、索引與散列結(jié)構(gòu) 　　1)索引技術(shù)：2-3_樹(shù)；b_樹(shù) 　　2)散列：散列表與散列方法；散列函數(shù)；處理溢出的閉散列方法；處理溢出的開(kāi)散列方法；散列表分析