華北電力大學(xué)（北京）

華北電力大學(xué)2021年碩士生入學(xué)考試初試科目考試大綱

考試科目編號：844

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

一、考試的總體要求

掌握常用數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和基本操作，靈活運(yùn)用所學(xué)的數(shù)據(jù)結(jié)構(gòu)解決實(shí)際問題。

二、考試的內(nèi)容

(一)基本概念和術(shù)語

(二)常用數(shù)據(jù)結(jié)構(gòu)及算法

1、線性表

①線性表的特點(diǎn);

②順序表數(shù)據(jù)類型描述和基本操作的實(shí)現(xiàn);

③單向鏈表的數(shù)據(jù)類型描述和基本操作的實(shí)現(xiàn);

④單向循環(huán)鏈表、雙向循環(huán)鏈表的數(shù)據(jù)類型描述和基本操作的實(shí)現(xiàn);

⑤線性表的應(yīng)用：兩個(gè)線性表的合并、一元多項(xiàng)式的求和與求積。

2、棧與隊(duì)列

①棧與隊(duì)列的特點(diǎn);

②順序棧、鏈棧的數(shù)據(jù)類型描述和基本操作的實(shí)現(xiàn);

③循環(huán)隊(duì)列、鏈隊(duì)列的數(shù)據(jù)類型描述和基本操作的實(shí)現(xiàn);

④表達(dá)式求值的兩種方法。

3、二叉樹與樹

①二叉樹的特點(diǎn)和性質(zhì);

②二叉樹的順序存儲與二叉鏈表的數(shù)據(jù)類型描述和基本操作的實(shí)現(xiàn)(創(chuàng)建、查找、遞歸遍歷、非遞歸遍歷、層次遍歷)和遍歷的應(yīng)用;

③二叉樹與樹、森林的轉(zhuǎn)換以及遍歷的對應(yīng)關(guān)系;

④樹的存儲結(jié)構(gòu)：雙親表示、孩子鏈表、雙親孩子鏈表和孩子兄弟鏈表的數(shù)據(jù)類型描述;

⑤樹的算法：創(chuàng)建、查找、插入、刪除、遍歷以及遍歷的應(yīng)用;

⑥表達(dá)式二叉樹的創(chuàng)建與求值;

⑥哈夫曼樹及哈夫曼編碼。

4、圖

①圖的特點(diǎn);

②鄰接矩陣、鄰接表的數(shù)據(jù)類型描述;

③圖的創(chuàng)建、圖的遍歷、最小生成樹、最短路徑、AOV網(wǎng)及拓?fù)渑判颉�AOE網(wǎng)及關(guān)鍵路徑;

④圖的遍歷算法的應(yīng)用。

(三)數(shù)據(jù)處理技術(shù)

1、查找

①靜態(tài)查找：順序查找(帶崗哨)、折半查找;

②動態(tài)查找：二叉排序樹和二叉平衡樹的查找、插入和刪除;

③哈希表：哈希函數(shù)、處理沖突的方法;

④查找性能分析(ASL)。

2、內(nèi)排序

①插入類排序(直接插入排序、折半插入排序、希爾排序)

②交換類排序(冒泡排序、快速排序)

③選擇類排序(簡單選擇排序、堆排序)

④歸并類排序(二路歸并排序)

⑤排序算法的復(fù)雜度分析

三、考試的題型

單選題、填空題(概念及算法)、算法應(yīng)用題、算法設(shè)計(jì)題。

四、參考書目

1.林碧英主編，新編數(shù)據(jù)結(jié)構(gòu)及算法教程，清華大學(xué)出版社.