2021山東工商學院807數(shù)據結構研究生考試大綱 正文

807數(shù)據結構考試大綱
一、考試總體要求
《數(shù)據結構》是一門專業(yè)基礎課，要求考生理解數(shù)據結構的基本概念，掌握數(shù)據的邏輯結構、存儲結構及其差異，以及各種基本操作的實現(xiàn)；在掌握基本的數(shù)據處理原理和方法的基礎上，能夠對算法進行時間復雜度和空間復雜度分析；能夠選擇合適的數(shù)據結構和方法進行問題求解。具備采用C、C++設計與實現(xiàn)算法的能力。
二、考試內容
本課程主要考試主要包括的內容：基本概念和算法分析、線性表、棧和隊列、串、數(shù)組和廣義表、樹和二叉樹、圖、查找、排序。
1.基本概念和算法分析
本部分主要介紹數(shù)據結構的基本概念和常用術語，算法和算法分析方法。重點要求理解數(shù)據結構的基本概念、理解抽象數(shù)據結構的定義、算法的基本要素和算法分析方法，掌握算法的時間復雜度和空間復雜度分析方法。
2.線性表
本部分主要介紹線性表的邏輯結構和各種存儲表示方法，以及運算的實現(xiàn)。重點要求掌握線性表的定義、特點和基本操作，熟練掌握線性表的存儲表示，包括順序存儲和鏈式存儲，以及在這兩種存儲結構上的插入、刪除、查找等運算的實現(xiàn)，理解其異同點和優(yōu)缺點。掌握特殊鏈表的定義和基本運算的實現(xiàn)，包括循環(huán)鏈表和雙向鏈表，掌握線性表的應用，包括一元多項式的組織和操作以及其它應用等。
3.棧和隊列
本部分主要介紹棧和隊列的邏輯結構定義，以及在兩種存儲結構上基本運算的實現(xiàn)。重點要求熟練掌握棧和隊列的基本概念，以及棧和隊列的兩種實現(xiàn)方法（順序存儲結構實現(xiàn)和鏈式存儲結構實現(xiàn)）及其操作的實現(xiàn)。能夠掌握棧和隊列的基本應用。
4.串
本部分主要介紹串的基本概念、存儲結構和運算。重點要求掌握串的基本概念，掌握串模式匹配KMP及改進算法。
5.數(shù)組和廣義表
本部分主要介紹數(shù)組和廣義表的定義、存儲及運算。重點要求掌握數(shù)組的特點及存儲表示方法。掌握特殊矩陣的存儲表示方法，包括對稱矩陣、對角線矩陣、稀疏矩陣。掌握廣義表的定義、存儲表示方法以及對廣義表的分解操作。
6.樹和二叉樹
本部分主要介紹二叉樹的定義、性質、存儲結構、遍歷、線索化；樹的定義、存儲結構、遍歷、樹和森林的轉換，赫夫曼樹及其赫夫曼編碼等內容。要求掌握樹與二叉樹的定義、性質，掌握二叉樹的存儲表示，包括順序存儲和鏈式存儲。掌握二叉樹的遍歷及其應用，包括先序、中序、后序和層次序遍歷。理解線索二叉樹的定義、存儲表示和尋找前驅、后繼。掌握樹和森林的存儲表示、樹、森林與二叉樹的轉換、樹和森林的遍歷。掌握赫夫曼樹和赫夫曼編碼及其應用。
7.圖
本部分主要介紹介紹圖的基本概念、兩種常用的存儲結構、兩種遍歷方法以及圖的應用算法。重點要求掌握圖的基本概念，基本性質。掌握圖的存儲方法，重點掌握鄰接矩陣法和鄰接表法。掌握圖的兩種遍歷方法：深度優(yōu)先遍歷和廣度優(yōu)先遍歷算法及實現(xiàn)，掌握拓撲排序算法及算法實現(xiàn)。理解基于圖的最小(代價)生成樹算法、最短路徑算法、關鍵路徑算法。
8.查找
本部分主要介紹線性表、樹和哈希表的查找方法、算法實現(xiàn)以及各種查找方法的時間性能（平均查找長度）分析。重點要求掌握順序查找、折半查找、二叉排序樹和哈希表查找的基本思想和算法實現(xiàn)。掌握平衡二叉樹的基本操作，理解B-樹和B+樹的基本概念。能夠理解各種不同查找算法的特點及其適用情況，分析不同查找算法的性能。
9.內部排序
本部分主要介紹幾種內部排序方法的基本思想、排序過程、算法實現(xiàn)、時間和空間性能的分析；并且對各種排序方法進行比較。重點要求掌握直接插入排序、折半插入排序、起泡排序、快速排序、直接選擇排序、堆排序、歸并排序、基數(shù)排序的基本思想和排序過程。掌握各類排序方法的時間/空間復雜度，以及穩(wěn)定性。
 

山東工商學院

本文來源：http://www.zgxindalu.cn/sdgsxy/cksm_380614.html