山東大學2019年碩士研究生招生考試自命題科目909數(shù)據(jù)結(jié)構(gòu)考試大綱

1、1909數(shù)據(jù)結(jié)構(gòu)一、考試基本要求要求考生系統(tǒng)地理解數(shù)據(jù)結(jié)構(gòu)的基本概念，掌握各種數(shù)據(jù)結(jié)構(gòu)的定義和實現(xiàn)算法。要求考生具有抽象思維能力，邏輯推理能力，和綜合運用所學的知識分析問題和解決問題的能力。二、考試范圍和主要內(nèi)容1預備知識預備知識了解C和Java基本語法結(jié)構(gòu)；掌握遞歸思想。2程序性能程序性能了解復雜性的表示和計算方法。掌握插入排序、選擇排序、冒泡排序、名詞排序基本思想。3數(shù)據(jù)描述數(shù)據(jù)描述掌握線性表的公式化描述、鏈表描述、間接尋址等存儲方

2、法，了解遍歷器的作用和實現(xiàn)方法，掌握插入、刪除、合并等運算方法。掌握箱子排序、基數(shù)排序4數(shù)組和矩陣數(shù)組和矩陣掌握對角矩陣、三對角矩陣、三角矩陣、對稱矩陣等特殊矩陣的特征，掌握存儲方法和基本運算實現(xiàn)。了解稀疏矩陣的存儲方法和基本運算實現(xiàn)。5堆棧堆棧掌握堆棧的基本概念、基本操作和實現(xiàn)方法。掌握括號匹配、離線等價類的實現(xiàn)思想。6隊列隊列掌握隊列的基本概念、基本操作和實現(xiàn)方法。7跳表和散列跳表和散列了解跳表的基本概念、基本操作和實現(xiàn)方法。掌握散

3、列的基本概念、基本操作和實現(xiàn)方法。8二叉樹二叉樹掌握二叉樹的基本概念、存儲方法、常用操作和特征；掌握二叉樹的前序、中序、后序、按層遍歷方法。掌握基于樹存儲的在線等價類實現(xiàn)。了解樹的存儲方法。29優(yōu)先隊列優(yōu)先隊列掌握堆的基本概念和插入、刪除和初始化方法。掌握堆排序思想。掌握霍夫曼樹、霍夫曼編碼實現(xiàn)方法。了解左高樹基本概念和插入、刪除、合并、初始化的實現(xiàn)方法。10搜索樹搜索樹掌握二叉搜索樹(排序樹)基本概念和插入、刪除、搜索的實現(xiàn)方法。掌握

4、二叉平衡樹（AVL樹）基本概念和插入、刪除、搜索的實現(xiàn)方法。掌握m叉搜索樹和B樹基本概念以及插入、刪除、搜索的實現(xiàn)方法。11圖掌握圖基本概念。掌握圖的鄰接矩陣和臨界鏈表存儲方法；掌握圖的深度優(yōu)先和廣度優(yōu)先遍歷算法。掌握圖的尋找路徑和尋找連通構(gòu)件方法。掌握生成樹的尋找方法。12貪婪算法貪婪算法了解貪婪算法基本理念。掌握AOV網(wǎng)的拓撲排序算法。掌握單源最短路徑Dijkstra算法。掌握最小耗費生成樹的概念、Prim算法和Kruskal算法。