2019年南華大學考研881數(shù)據(jù)結構 初試考試大綱

1、附件附件5南華大學南華大學2019年碩士研究生入學考試大綱年碩士研究生入學考試大綱招生學院招生學院招生專業(yè)代碼招生專業(yè)代碼招生專業(yè)名稱招生專業(yè)名稱考試科目代碼及名稱考試科目代碼及名稱計算機學院0835085211軟件工程計算機技術數(shù)據(jù)結構一、考試內(nèi)容一、考試內(nèi)容1、數(shù)據(jù)結構基本概念及簡單的算法分析數(shù)據(jù)結構基本概念及簡單的算法分析1)數(shù)據(jù)結構、抽象數(shù)據(jù)類型、數(shù)據(jù)類型、算法的基本概念2)算法性能分析與度量：算法的性能標準；算法的空間復雜度與

2、時間復雜度概念與分析方法；時間復雜度的漸進表示法；2、線性表、線性表1)順序表：順序表的定義和特點；順序表的類定義；順序表的查找、插入和刪除；順序表的優(yōu)缺點2)單鏈表：單鏈表的結構；單鏈表的類定義；單鏈表中的插入與刪除；帶表頭結點的單鏈表；靜態(tài)鏈表；鏈表的優(yōu)缺點3)循環(huán)鏈表：循環(huán)鏈表的類定義；用循環(huán)鏈表解約瑟夫問題；4)雙向鏈表的基本操作3、棧和隊列、棧和隊列1)棧：棧的抽象數(shù)據(jù)類型；棧的順序存儲表示；棧的鏈接存儲表示2)隊列：隊列的抽

3、象數(shù)據(jù)類型；隊列的順序存儲表示；隊列的鏈接存儲表示；3)棧和隊列的應用4、樹與森林、樹與森林1)樹和森林的概念：樹的定義；樹的術語；樹的抽象數(shù)據(jù)類型2)二叉樹：二叉樹的定義；二叉樹的性質(zhì)；二叉樹的抽象數(shù)據(jù)類型3)二叉樹的表示：順序表表示；鏈表存儲表示4)二叉樹遍歷：中序遍歷；前序遍歷；后序遍歷；不用棧的二叉樹中序遍歷算法5)線索化二叉樹：線索；中序線索化二叉樹；前序與后序的線索化6)樹與森林：樹的存儲表示；森林與二叉樹的轉換；樹的遍歷；

4、森林的遍歷；7)霍夫曼樹：帶權路徑長度；霍夫曼樹；霍夫曼編碼5、圖1)圖的基本概念：圖的基本概念；圖的抽象數(shù)據(jù)類型2)圖的存儲表示：鄰接矩陣；鄰接表；鄰接多重表3)圖的遍歷與連通性：深度優(yōu)先搜索；廣度優(yōu)先搜索；連通分量；4)圖的基本算法：最小生成樹：克魯斯卡爾算法；普里姆算法；最短路徑；關鍵路徑6、查找、查找1)查找、查找表及平均查找長度的基本概念2）順序查找；基于有序順序表的二分查找算法及分析3)二叉排序樹：定義；二叉排序上的查找、插

5、入與刪除；4)AVI樹：AVI樹的定義；平衡化旋轉；5)散列：散列表與散列方法；散列函數(shù)；處理溢出的閉散列方法；處理溢出的開散列方法；散列表分析7、排序、排序1）排序的基本術語與概念2)插入排序：直接插入排序；對分插入排序；鏈表插入排序；希爾排序3)交換排序：起泡排序；快速排序4)選擇排序：直接選擇排序；堆排序5)歸并排序：歸并；迭代的歸并排序算法；遞歸的表歸并排序6)基數(shù)排序：多關鍵碼排序；鏈式基數(shù)排序7)外排序的基本概念二、考試形式

6、考試形式與試卷結構與試卷結構（一）試卷成績及考試時間（一）試卷成績及考試時間本試卷滿分為150分，考試時間為180分鐘。（二）答題方式（二）答題方式答題方式為閉卷、筆試。（三）試卷內(nèi)容結構（三）試卷內(nèi)容結構數(shù)據(jù)結構基本概念:20%順序與鏈式線性表:15%棧與隊列:15%樹與二叉樹:20%圖:15%查找與排序:15%（四）試卷題型結構（四）試卷題型結構簡答題（約40分）；應用題（約50分）；算法分析（約30分）算法設計（約30分）。學位點