2014年湖南大學(xué)085212軟件工程考研大綱.doc
《2014年湖南大學(xué)085212軟件工程考研大綱.doc》由會(huì)員分享,可在線閱讀,更多相關(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),包括線性結(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)廣義表的訪問(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)線索化二叉樹(shù):線索;中序線索化二叉樹(shù);前序與后序的線索化 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)散列方法;散列表分析- 1.請(qǐng)仔細(xì)閱讀文檔,確保文檔完整性,對(duì)于不預(yù)覽、不比對(duì)內(nèi)容而直接下載帶來(lái)的問(wèn)題本站不予受理。
- 2.下載的文檔,不會(huì)出現(xiàn)我們的網(wǎng)址水印。
- 3、該文檔所得收入(下載+內(nèi)容+預(yù)覽)歸上傳者、原創(chuàng)作者;如果您是本文檔原作者,請(qǐng)點(diǎn)此認(rèn)領(lǐng)!既往收益都?xì)w您。
下載文檔到電腦,查找使用更方便
9.9 積分
下載 |
- 配套講稿:
如PPT文件的首頁(yè)顯示word圖標(biāo),表示該P(yáng)PT已包含配套word講稿。雙擊word圖標(biāo)可打開(kāi)word文檔。
- 特殊限制:
部分文檔作品中含有的國(guó)旗、國(guó)徽等圖片,僅作為作品整體效果示例展示,禁止商用。設(shè)計(jì)者僅對(duì)作品中獨(dú)創(chuàng)性部分享有著作權(quán)。
- 關(guān) 鍵 詞:
- 2014 湖南大學(xué) 085212 軟件工程 考研 大綱
鏈接地址:http://m.appdesigncorp.com/p-8903230.html