2021遼寧石油化工大學數據結構專業研究生考試大綱 正文

一、 考試要求

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

2、把握基本的數據處理原理和方法的基礎上，能夠對算法進行設計與分析；

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

二、 考試內容

1、線性表

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

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

2、棧、隊列和數組

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

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

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

（4）棧和隊列的應用。

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

3、樹與二叉樹

（1）樹的概念。

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

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

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

4、圖

（1）圖的概念。

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

（3）圖的遍歷：①深度優先搜索；②廣度優先搜索。

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

5、查找

（1）查找的基本概念。

（2）順序查找法。

（3）折半查找法。

（4）B-樹。

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

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

5、內部排序

（1）排序的基本概念。

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

（3）氣泡排序。

（4）簡單選擇排序。

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

（6）快速排序。

（7）堆排序。

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

（9）基數排序。

（10）各種內部排序算法的比較。

（11）內部排序算法的應用。

遼寧石油化工大學

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