2021遼寧石油化工大學(xué)數(shù)據(jù)結(jié)構(gòu)專業(yè)研究生考試大綱 正文

一、 考試要求

1、理解數(shù)據(jù)結(jié)構(gòu)的基本概念；把握數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)及其差異，以及各種基本操作的實(shí)現(xiàn)；

2、把握基本的數(shù)據(jù)處理原理和方法的基礎(chǔ)上，能夠?qū)λ惴ㄟM(jìn)行設(shè)計(jì)與分析；

3、能夠選擇合適的數(shù)據(jù)結(jié)構(gòu)和方法進(jìn)行問(wèn)題求解。

二、 考試內(nèi)容

1、線性表

（1）線性表的定義和基本操作。

（2）線性表的實(shí)現(xiàn)：①順序存儲(chǔ)結(jié)構(gòu)；②鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；③線性表的應(yīng)用。

2、棧、隊(duì)列和數(shù)組

（1）棧和隊(duì)列的基本概念。

（2）棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)。

（3）棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。

（4）棧和隊(duì)列的應(yīng)用。

（5）非凡矩陣的壓縮存儲(chǔ)。

3、樹(shù)與二叉樹(shù)

（1）樹(shù)的概念。

（2）二叉樹(shù)：①二叉樹(shù)的定義及其主要特征；②二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；③二叉樹(shù)的遍歷；④線索二叉樹(shù)的基本概念和構(gòu)造；⑤二叉排序樹(shù)；⑥平衡二叉樹(shù)。

（3）樹(shù)、森林：①樹(shù)的存儲(chǔ)結(jié)構(gòu)；②森林與二叉樹(shù)的轉(zhuǎn)換；③樹(shù)和森林的遍歷。

（4）樹(shù)的應(yīng)用：①等價(jià)類問(wèn)題；②哈夫曼（Huffman）樹(shù)和哈夫曼編碼。

4、圖

（1）圖的概念。

（2）圖的存儲(chǔ)及基本操作：①鄰接矩陣法；②鄰接表法；

（3）圖的遍歷：①深度優(yōu)先搜索；②廣度優(yōu)先搜索。

（4）圖的基本應(yīng)用及其復(fù)雜度分析：①最小（代價(jià)）生成樹(shù)；②最短路徑；③拓?fù)渑判?；③關(guān)鍵路徑。

5、查找

（1）查找的基本概念。

（2）順序查找法。

（3）折半查找法。

（4）B-樹(shù)。

（5）散列（Hash）表及其查找。

（6）查找算法的分析及應(yīng)用。

5、內(nèi)部排序

（1）排序的基本概念。

（2）插入排序：①直接插入排序；②折半插入排序；

（3）氣泡排序。

（4）簡(jiǎn)單選擇排序。

（5）希爾排序（shell sort）。

（6）快速排序。

（7）堆排序。

（8）二路歸并排序（merge sort）。

（9）基數(shù)排序。

（10）各種內(nèi)部排序算法的比較。

（11）內(nèi)部排序算法的應(yīng)用。

遼寧石油化工大學(xué)

本文來(lái)源：http://zhangjiajieline.cn/liaoningshiyouhuagongdaxue/cankaoshumu_387219.html