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

一、 考試要求

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

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

3、能夠選擇合適的數(shù)據(jù)結構和方法進行問題求解。

二、 考試內(nèi)容

1、線性表

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

（2）線性表的實現(xiàn)：①順序存儲結構；②鏈式存儲結構；③線性表的應用。

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

（1）棧和隊列的基本概念。

（2）棧和隊列的順序存儲結構。

（3）棧和隊列的鏈式存儲結構。

（4）棧和隊列的應用。

（5）非凡矩陣的壓縮存儲。

3、樹與二叉樹

（1）樹的概念。

（2）二叉樹：①二叉樹的定義及其主要特征；②二叉樹的順序存儲結構和鏈式存儲結構；③二叉樹的遍歷；④線索二叉樹的基本概念和構造；⑤二叉排序樹；⑥平衡二叉樹。

（3）樹、森林：①樹的存儲結構；②森林與二叉樹的轉換；③樹和森林的遍歷。

（4）樹的應用：①等價類問題；②哈夫曼（Huffman）樹和哈夫曼編碼。

4、圖

（1）圖的概念。

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

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

（4）圖的基本應用及其復雜度分析：①最小（代價）生成樹；②最短路徑；③拓撲排序；③關鍵路徑。

5、查找

（1）查找的基本概念。

（2）順序查找法。

（3）折半查找法。

（4）B-樹。

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

（6）查找算法的分析及應用。

5、內(nèi)部排序

（1）排序的基本概念。

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

（3）氣泡排序。

（4）簡單選擇排序。

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

（6）快速排序。

（7）堆排序。

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

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

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

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

遼寧石油化工大學

本文來源：http://zgxindalu.cn/liaoningshiyouhuagongdaxue/cankaoshumu_387219.html