招生學院招生專業(yè)代碼招生專業(yè)名稱考試科目代碼及名稱

    計算機學院083500

    085400軟件工程

    電子信息881數(shù)據(jù)結(jié)構(gòu)

    一、考試內(nèi)容

    1、數(shù)據(jù)結(jié)構(gòu)基本概念及簡單的算法分析

    1)數(shù)據(jù)結(jié)構(gòu)、抽象數(shù)據(jù)類型、數(shù)據(jù)類型、算法的基本概念

    2)算法性能分析與度量：算法的性能標準；算法的空間復雜度與時間復雜度概念與分析方法；時間復雜度的漸進表示法；

    2、線性表

    1)順序表：順序表的定義和特點；順序表的類定義；順序表的查找、插入和刪除；順序表的優(yōu)缺點

    2)單鏈表：單鏈表的結(jié)構(gòu)；單鏈表的類定義；單鏈表中的插入與刪除；帶表頭結(jié)點的單鏈表；靜態(tài)鏈表；鏈表的優(yōu)缺點

    3)循環(huán)鏈表：循環(huán)鏈表的類定義；用循環(huán)鏈表解約瑟夫問題；

    4)雙向鏈表的基本操作

    3、棧和隊列

    1)棧：棧的抽象數(shù)據(jù)類型；棧的順序存儲表示；棧的鏈接存儲表示

    2)隊列：隊列的抽象數(shù)據(jù)類型；隊列的順序存儲表示；隊列的鏈接存儲表示；

    3)棧和隊列的應(yīng)用

    4、樹與森林

    1)樹和森林的概念：樹的定義；樹的術(shù)語；樹的抽象數(shù)據(jù)類型

    2)二叉樹：二叉樹的定義；二叉樹的性質(zhì)；二叉樹的抽象數(shù)據(jù)類型

    3)二叉樹的表示：順序表表示；鏈表存儲表示

    4)二叉樹遍歷：中序遍歷；前序遍歷；后序遍歷；不用棧的二叉樹中序遍歷算法

    5)線索化二叉樹：線索；中序線索化二叉樹；前序與后序的線索化

    6)樹與森林：樹的存儲表示；森林與二叉樹的轉(zhuǎn)換；樹的遍歷；森林的遍歷；

    7)霍夫曼樹：帶權(quán)路徑長度；霍夫曼樹；霍夫曼編碼

    5、圖

    1)圖的基本概念：圖的基本概念；圖的抽象數(shù)據(jù)類型

    2)圖的存儲表示：鄰接矩陣；鄰接表；鄰接多重表

    3)圖的遍歷與連通性：深度優(yōu)先搜索；廣度優(yōu)先搜索；連通分量；

    4)圖的基本算法：最小生成樹：克魯斯卡爾算法；普里姆算法；最短路徑；關(guān)鍵路徑

    6、查找

    1)查找、查找表及平均查找長度的基本概念

    2）順序查找；基于有序順序表的二分查找算法及分析

    3)二叉排序樹：定義；二叉排序上的查找、插入與刪除；

    4)AVI樹：AVI樹的定義；平衡化旋轉(zhuǎn)；

    5)散列：散列表與散列方法；散列函數(shù)；處理溢出的閉散列方法；處理溢出的開散列方法；散列表分析

    7、排序

    1）排序的基本術(shù)語與概念

    2)插入排序：直接插入排序；對分插入排序；鏈表插入排序；希爾排序　3)交換排序：起泡排序；快速排序

    4)選擇排序：直接選擇排序；堆排序

    5)歸并排序：歸并；迭代的歸并排序算法；遞歸的表歸并排序

    6)基數(shù)排序：多關(guān)鍵碼排序；鏈式基數(shù)排序

    7)外排序的基本概念

    二、考試形式與試卷結(jié)構(gòu)

    （一）試卷成績及考試時間

    本試卷滿分為150分，考試時間為180分鐘。

    （二）答題方式

    答題方式為閉卷、筆試。

    （三）試卷內(nèi)容結(jié)構(gòu)

    數(shù)據(jù)結(jié)構(gòu)基本概念:20%順序與鏈式線性表:15%棧與隊列:15%

    樹與二叉樹:20%圖:15%查找與排序:15%

    （四）試卷題型結(jié)構(gòu)

    簡答題（約40分）；應(yīng)用題（約50分）；算法分析（約30分）算法設(shè)計（約30分）。

添加南華大學學姐微信，或微信搜索公眾號“考研派小站”，關(guān)注[考研派小站]微信公眾號，在考研派小站微信號輸入[南華大學考研分數(shù)線、南華大學報錄比、南華大學考研群、南華大學學姐微信、南華大學考研真題、南華大學專業(yè)目錄、南華大學排名、南華大學保研、南華大學公眾號、南華大學研究生招生）]即可在手機上查看相對應(yīng)南華大學考研信息或資源。