2021年山東大學考研大綱    

909-數據結構

一、考試基本要求

要求考生系統地理解數據結構的基本概念，掌握各種數據結構的定義和實現算法。要求考生具有抽象思維能力，邏輯推理能力，和綜合運用所學的知識分析問題和解決問題的能力。

二、考試范圍和主要內容

1．預備知識

了解C++和Java基本語法結構；掌握遞歸思想。

2．程序性能

了解復雜性的表示和計算方法。

掌握插入排序、選擇排序、冒泡排序、名詞排序基本思想。

3．數據描述

掌握線性表的公式化描述、鏈表描述、間接尋址等存儲方法，了解遍歷器的作用和實現方法，掌握插入、刪除、合并等運算方法。

掌握箱子排序、基數排序

4．數組和矩陣

掌握對角矩陣、三對角矩陣、三角矩陣、對稱矩陣等特殊矩陣的特征，掌握存儲方法和基本運算實現。

了解稀疏矩陣的存儲方法和基本運算實現。

5．堆棧

掌握堆棧的基本概念、基本操作和實現方法。

掌握括號匹配、離線等價類的實現思想。

6．隊列

掌握隊列的基本概念、基本操作和實現方法。

7．跳表和散列

了解跳表的基本概念、基本操作和實現方法。

掌握散列的基本概念、基本操作和實現方法。

8．二叉樹

掌握二叉樹的基本概念、存儲方法、常用操作和特征；掌握二叉樹的前序、中序、后序、按層遍歷方法。

掌握基于樹存儲的在線等價類實現。

了解樹的存儲方法。

9．優先隊列

掌握堆的基本概念和插入、刪除和初始化方法。

掌握堆排序思想。

掌握霍夫曼樹、霍夫曼編碼實現方法。

了解左高樹基本概念和插入、刪除、合并、初始化的實現方法。

10．搜索樹

掌握二叉搜索樹(排序樹)基本概念和插入、刪除、搜索的實現方法。

掌握二叉平衡樹（AVL樹）基本概念和插入、刪除、搜索的實現方法。

掌握m叉搜索樹和B樹基本概念以及插入、刪除、搜索的實現方法。

11．圖

掌握圖基本概念。

掌握圖的鄰接矩陣和臨界鏈表存儲方法；掌握圖的深度優先和廣度優先遍歷算法。

掌握圖的尋找路徑和尋找連通構件方法。

掌握生成樹的尋找方法。

12．貪婪算法

了解貪婪算法基本理念。

掌握AOV網的拓撲排序算法。

掌握單源最短路徑Dijkstra算法。

掌握最小耗費生成樹的概念、Prim算法和Kruskal算法。

了解AOE網的關鍵路徑算法。

13．分而治之算法

了解分而治之思想；掌握歸并排序、快速排序實現方法。

了解選擇問題基本思想。

14．動態規劃

掌握所有頂點對時間的最短路徑算法。