《數(shù)據(jù)結(jié)構(gòu)》考試大綱

數(shù)據(jù)結(jié)構(gòu)

一考科：數(shù)據(jù)結(jié)構(gòu)二適專：計算機科學與技術(shù)專業(yè)計算機技術(shù)，軟件工程三參書：《數(shù)據(jù)結(jié)構(gòu)C語版）》，嚴敏，清華大學出版社2007四考試容求1、了解數(shù)據(jù)結(jié)構(gòu)及其分類、數(shù)結(jié)構(gòu)與算法的密切關(guān)系。2、熟悉各種基本數(shù)據(jù)結(jié)構(gòu)及其操作，學會根據(jù)實際問題要求來選擇數(shù)據(jù)結(jié)構(gòu)。3、掌握設(shè)計算法的步驟和算法分析方法。4、掌握數(shù)據(jù)結(jié)構(gòu)在排序和查找等常用算法中的應用。5、初步掌握文件組織方法和索技術(shù)。五考內(nèi)：、數(shù)據(jù)構(gòu)本念簡的法析1)什么是數(shù)據(jù)結(jié)構(gòu)2)抽象據(jù)類型及面向?qū)ο蟾牛簲?shù)據(jù)類型；數(shù)據(jù)抽象與抽象數(shù)據(jù)類型；面向?qū)ο蟮母拍?；用于描述?shù)據(jù)結(jié)構(gòu)的語言3)數(shù)據(jù)構(gòu)的抽象層次4)算法義5)性能析與度量：算法的性標準；算法的后期測試；算法的事前估計；空間復雜度度量；時間復雜度度量；時間復雜度的漸進表示法；漸進的空間復.、數(shù)組1)作為抽象數(shù)據(jù)類型的數(shù)組數(shù)的定義和初始化作為抽象數(shù)據(jù)類型的數(shù)組數(shù)組的順序存儲方式2)順序表：順序表的定義和特點；順序表的類定義；順序表的查找、插入和刪除；使用順序表的事例3)字符：字符串的抽象數(shù)據(jù)型；字符串操作的實現(xiàn)；字符串的模式匹配、鏈1)單鏈：單鏈表的結(jié)構(gòu)；單表的類定義；單鏈表中的插入與刪除；帶表頭結(jié)點的單鏈表；用模板定義的單鏈表類；單鏈表的游標類；靜態(tài)鏈表2)循環(huán)表：循環(huán)鏈表的類定；用循環(huán)鏈表解約瑟夫問題；多項式及其相加：多項式的類定義；多項式的加法3)雙向表、棧隊

1)棧：的抽象數(shù)據(jù)類型；棧順序存儲表示；棧的鏈接存儲表示2)隊列：隊列的抽象數(shù)據(jù)類型；隊列的順序存儲表示；隊列的鏈接存儲表示3)隊列的應用舉例4)優(yōu)先隊列：優(yōu)先級隊列的義；優(yōu)先級隊列的存儲表示、遞1)遞歸概念2)迷宮題3)遞歸程與遞歸工作棧4)利用實現(xiàn)的迷宮問題非遞解法5)廣義：廣義表的概念；廣表的表示及操作；廣義表存儲結(jié)構(gòu)的實現(xiàn)；廣6)義表的訪問算法；廣義表的遞歸算法、樹森1)樹和林的概念：樹的定義樹的術(shù)語；樹的抽象數(shù)據(jù)類型2)二叉：二叉樹的定義；二樹的性質(zhì)；二叉樹的抽象數(shù)據(jù)類型3)二叉的表示：數(shù)組表示；表存儲表示4)二叉遍歷：中序遍歷；前遍歷；后序遍歷；應用二叉樹遍歷的事例；叉樹遍歷的游標類；不用棧的二叉樹中序遍歷算法5)線索二叉樹：線索；中序索化二叉樹；前序與后序的線索化6)堆：的定義；堆的建立；的插入與刪除7)樹與林：樹的存儲表示；林與二叉樹的轉(zhuǎn)換；樹的遍歷；森林的遍歷二叉樹的計數(shù)8)霍夫樹：路徑長度；霍夫樹；霍夫曼編碼、集與索1)集合其表示：集合基本概；以集合為基礎(chǔ)的抽象數(shù)據(jù)類型；用位向量實現(xiàn)集合抽象據(jù)類型；用有序鏈表實現(xiàn)集合的抽象數(shù)據(jù)類型2)等價：等價關(guān)系與等價類確定等價類的鏈表方法；并查集3)簡單搜索結(jié)構(gòu)：搜索的概；靜態(tài)搜索結(jié)構(gòu)；順序搜索；基于有序順序表的對分搜索4)二叉索樹定；二叉搜索樹上的搜索叉索樹的插入二搜索樹的刪除；與二叉搜索樹相關(guān)的中序游標類5)AVI樹：樹定義；平衡旋轉(zhuǎn)AVI樹插入和刪除AVI樹高度、圖1)2)3)4)

圖的基本概念：圖的基本概念；圖的抽象數(shù)據(jù)類型圖的存儲表示：鄰接矩陣；鄰接表；鄰接多重表圖的遍歷與連通性：深度優(yōu)先搜索；廣度優(yōu)先搜索；連通分量；重連通分量最小生成樹：克魯斯卡爾算法；普里姆算法

5)活動絡：用頂點表示活動網(wǎng)絡；用邊表示活動的網(wǎng)絡、排1)2)3)4)5)6)

插入排序：直接插入排序；對分插入排序；鏈表插入排序；希爾排序交換排序：起泡排序；快速排序選擇排序：直接選擇排序；錦標賽排序；堆排序歸并排序：歸并；迭代的歸并排序算法；遞歸的表歸并排序基數(shù)排序：多關(guān)鍵碼排序；鏈式基數(shù)排序外排序：外排序的基本過程k路衡歸并；初始歸并段的生成；最佳歸并樹10、引散結(jié)：1)靜態(tài)引結(jié)構(gòu)：線性索引；排表m路態(tài)查找樹2)動態(tài)引結(jié)