湖南工程學(xué)院

    2021年專業(yè)碩士研究生入學(xué)考試復(fù)習(xí)大綱

    科目名稱數(shù)據(jù)結(jié)構(gòu)編

    號(hào)851

    一、考試范圍及要點(diǎn)

    (一)數(shù)據(jù)結(jié)構(gòu)和算法

    1數(shù)據(jù)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)的概念；2數(shù)據(jù)類型與抽象數(shù)據(jù)類型；3算法的概念，用C∕C++描述算法和程序設(shè)計(jì)，算法分析初步。

    (二)線性表

    1線性表的定義和基本操作；2線性表的順序存儲(chǔ)結(jié)構(gòu)；3線性表的鏈?zhǔn)酱鎯?chǔ)

    結(jié)構(gòu)（線性鏈表，循環(huán)鏈表，雙向鏈表）；4一元多項(xiàng)式的抽象數(shù)據(jù)類型定義、表示及加法的實(shí)現(xiàn)。

    (三)棧和隊(duì)列1棧的定義和基本操作；2棧的抽象數(shù)據(jù)類型；3順序棧，鏈?zhǔn)綏＃?棧和遞歸算法，算術(shù)表達(dá)式求值；5隊(duì)列的定義和基本操作；6隊(duì)列的抽象數(shù)據(jù)類型；7順序隊(duì)列，鏈?zhǔn)疥?duì)列；8雙端隊(duì)列的定義和基本操作。

    (四)串1串類型的定義；串的三種存儲(chǔ)表示：定長順序存儲(chǔ)結(jié)構(gòu)、塊鏈存儲(chǔ)結(jié)構(gòu)和堆分配存儲(chǔ)結(jié)構(gòu)；2串的各種基本操作的實(shí)現(xiàn)及應(yīng)用；3串的模式匹配算法。

    (五)數(shù)組和廣義表

    1數(shù)組的定義和基本操作；2數(shù)組的順序存儲(chǔ)結(jié)構(gòu)；3特殊矩陣和稀疏矩陣的

    壓縮存儲(chǔ)；4廣義表的存儲(chǔ)結(jié)構(gòu)；5廣義表的遞歸算法。

    (六)樹和二叉樹

    1樹的基本概念和基本操作，樹的抽象數(shù)據(jù)類型；2二叉樹的概念和性質(zhì)，

    特殊二叉樹，二叉樹的存儲(chǔ)結(jié)構(gòu)；3遍歷二叉樹：前序遍歷，中序遍歷，后序

    遍歷，層次遍歷。4線索二叉樹的概念和存儲(chǔ)結(jié)構(gòu)，二叉樹的線索化，線索二

    叉樹的遍歷；5樹的存儲(chǔ)結(jié)構(gòu)，樹與二叉樹之間的轉(zhuǎn)換，森林與二叉樹之間的

    轉(zhuǎn)換，樹和森林的遍歷；6赫夫曼樹（Huffman）及其應(yīng)用。

    (七)圖

    1圖的基本概念和基本操作；2圖的存儲(chǔ)結(jié)構(gòu)：數(shù)組表示法(鄰接矩陣)，鄰

    接表，逆鄰接表，十字鏈表，鄰接多重表；3圖的遍歷：深度優(yōu)先搜索法，廣

    度優(yōu)先搜索法，求圖的連通分量；4從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑，每

    對(duì)頂點(diǎn)之間的最短路徑；5拓?fù)渑判蚝完P(guān)鍵路徑。

    (八)動(dòng)態(tài)存儲(chǔ)管理1可利用空間表及分配方法；2邊界標(biāo)示法和伙伴系統(tǒng)；3無用單元收集和存儲(chǔ)緊縮。(九)查找1靜態(tài)查找表；2動(dòng)態(tài)查找表；3哈希(Hash)表：哈希表的概念，哈希函數(shù)構(gòu)造方法，哈希表的建立和查找，沖突處理方法。(十)內(nèi)部排序

    比較各種內(nèi)部排序方法：插入排序、快速排序、選擇排序、歸并排序和基數(shù)排序的基本思想、算法特點(diǎn)、排序過程以及它們的時(shí)間復(fù)雜度分析。(十一)外部排序

    1外存信息的存??；2實(shí)現(xiàn)外部排序的基本方法；為減少平衡歸并排序中所需進(jìn)行的外存讀/寫次數(shù)可采取的措施：利用敗者樹實(shí)現(xiàn)多路歸并，通過置換-選擇排序產(chǎn)生初始?xì)w并段，并對(duì)所得長度不等的歸并段構(gòu)造最佳歸并樹。

    (十二)文件

    1文件的基本概念，文件的基本操作；2文件的物理結(jié)構(gòu)：順序文件，索引順序存取方法和虛擬存儲(chǔ)存取方法，直接存取文件，多關(guān)鍵字文件。

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

    1、考試形式

    閉卷，筆試。答題時(shí)間:180分鐘。

    2、試卷結(jié)構(gòu)

    試卷滿分150分。

    （1）單項(xiàng)選擇題（40分）

    （2）填空題（20分）

    （3）問答題（60分）

    （4）編程題（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é)院考研信息或資源。