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

    計(jì)算機(jī)學(xué)院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)算法性能分析與度量：算法的性能標(biāo)準(zhǔn)；算法的空間復(fù)雜度與時(shí)間復(fù)雜度概念與分析方法；時(shí)間復(fù)雜度的漸進(jìn)表示法；

    2、線性表

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

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

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

    4)雙向鏈表的基本操作

    3、棧和隊(duì)列

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

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

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

    4、樹與森林

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

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

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

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

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

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

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

    5、圖

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

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

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

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

    6、查找

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

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

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

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

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

    7、排序

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

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

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

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

    6)基數(shù)排序：多關(guān)鍵碼排序；鏈?zhǔn)交鶖?shù)排序

    7)外排序的基本概念

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

    （一）試卷成績及考試時(shí)間

    本試卷滿分為150分，考試時(shí)間為180分鐘。

    （二）答題方式

    答題方式為閉卷、筆試。

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

    數(shù)據(jù)結(jié)構(gòu)基本概念:20%順序與鏈?zhǔn)骄€性表:15%棧與隊(duì)列:15%

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

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

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

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