2021山東工商學(xué)院807數(shù)據(jù)結(jié)構(gòu)研究生考試大綱 正文

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

山東工商學(xué)院

本文來源：http://www.lyhuahuisp.com/sdgsxy/cksm_380614.html