2014年數(shù)學(xué)考研大綱(數(shù)學(xué)一)

大連海事大學(xué)碩士研究生入學(xué)考試大綱考試科目：數(shù)據(jù)結(jié)構(gòu)試卷滿分及考試時間：試卷滿分為100分，考試時間為180分鐘。一、數(shù)據(jù)結(jié)構(gòu)基本概念考試內(nèi)容(1)數(shù)據(jù)結(jié)構(gòu)的基本概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)、物理結(jié)構(gòu)、算法等。(2)抽象數(shù)據(jù)類型的表示和實現(xiàn)。(3)算法時間復(fù)雜度和空間復(fù)雜度的分析?？荚囈笳莆蘸屠斫鈹?shù)據(jù)結(jié)構(gòu)的概念；掌握數(shù)據(jù)結(jié)構(gòu)的相關(guān)術(shù)語與基本概念；掌握算法的時間復(fù)雜度及判斷算法好壞的方法。二、線性表考試內(nèi)容(1)線性表的類型定義。(2)線性表的順序存儲方法和實現(xiàn)，相關(guān)查找、插入和刪除算法算法實現(xiàn)，應(yīng)用舉例；(3)線性表的鏈?zhǔn)酱鎯Ψ椒ê蛯崿F(xiàn)，相關(guān)查找、插入和刪除算法算法實現(xiàn)，應(yīng)用舉例?？荚囈笳莆站€性表的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的各自特點；熟練掌握順序表和鏈?zhǔn)奖淼牟迦搿h除和查找等基本操作；能夠編制和實現(xiàn)順序表和鏈?zhǔn)奖砘静僮鞯某绦?；三、棧和隊列考試?nèi)容(1)棧的定義及特點，棧的順序存儲和鏈接存儲的表示和實現(xiàn)，進(jìn)棧出棧算法。(2)棧的應(yīng)用舉例，如表達(dá)式求值、數(shù)制轉(zhuǎn)換等。(3)隊列的定義及特點，隊列的表示和實現(xiàn)，循環(huán)隊列和鏈隊列的進(jìn)隊出隊算法。考試要求掌握棧和隊列兩種特殊的線性表的特點熟練掌握棧的基本操作即進(jìn)棧、出棧、?？铡M、取棧頂元素等操作；熟練掌握隊列的基本操作即入隊列、出隊列、判斷隊列空、隊列滿等；四、串考試內(nèi)容串類型的定義。(2)串的表示和實現(xiàn)，定長順序存儲表示。(3)串的匹配算法?？荚囈笳莆沾亩x與特點；掌握串的抽象數(shù)據(jù)類型的定義、定長順序存儲表示、基本操作；熟練掌握串的模式匹配算法中的樸素算法、首尾匹配算法；會計算KMP算法的next[j]。五、數(shù)組和廣義表考試內(nèi)容(1)數(shù)組的邏輯結(jié)構(gòu)定義和存儲方法。(2)特殊矩陣和稀疏矩陣的壓縮存儲方法及其適用范圍。(3)廣義表的結(jié)構(gòu)特點及其存儲方法。考試要求掌握數(shù)組的定義；掌握二維數(shù)組的存儲結(jié)構(gòu)及尋址方法；掌握矩陣壓縮存儲的基本思想特殊矩陣和稀疏矩陣的壓縮存儲方法及尋址方法；掌握三元組順序表的轉(zhuǎn)置運算；掌握廣義表的定義、其基本概念及存儲方法；六、樹和二叉樹考試內(nèi)容(1)二叉樹的定義、性質(zhì)和存儲結(jié)構(gòu)。(2)二叉樹的遍歷及有關(guān)算法，利用遍歷算法實現(xiàn)二叉樹的其他操作，如計算二叉樹結(jié)點個數(shù)、葉子結(jié)點個數(shù)、二叉樹的高度等。(3)樹和森林的定義、存儲結(jié)構(gòu)與二叉樹的轉(zhuǎn)換。(4)樹的應(yīng)用，哈夫曼樹及哈夫曼編碼、帶權(quán)路徑長度的計算?？荚囈笫炀氄莆斩鏄涞慕Y(jié)構(gòu)特性，了解相應(yīng)的證明方法；熟練掌握二叉樹的二叉鏈表存儲；掌握二叉樹各種遍歷的遞歸算法，靈活運用遍歷算法實現(xiàn)二叉樹的其它操作；熟悉樹的各種存儲結(jié)構(gòu)及其特點，掌握樹和森林與二叉樹的轉(zhuǎn)換方法；掌握哈夫曼樹的特性及建立哈夫曼樹和哈夫曼編碼的方法。七、圖考試內(nèi)容(1)圖的定義及相關(guān)術(shù)語和性質(zhì)。(2)圖的存儲結(jié)構(gòu)：鄰接矩陣表示法、鄰接表。(3)圖的兩種遍歷策略：深度優(yōu)先搜索和廣度優(yōu)先搜索，以及相關(guān)算法。(4)圖的最小生成樹，構(gòu)造最小生成樹的兩種算法：普里姆算法和克魯斯卡爾算法。(5)拓?fù)渑判蚝完P(guān)鍵路徑。(6)兩類求最短路徑問題的算法，迪杰斯特拉算法和弗洛伊德算法?？荚囈笳莆绽斫鈭D的抽象數(shù)據(jù)類型定義及其基本術(shù)語；掌握圖的鄰接矩陣和鄰接表的存儲方法；掌握圖的遍歷方法及其在鄰接矩陣和鄰接表存儲結(jié)構(gòu)上的實現(xiàn)；掌握構(gòu)造最小生成樹的Prim算法和Kruskal算法的基本思想和求解過程；掌握求解最短路徑的Dijkstra算法和Floyd算法的基本思想及過程；掌握拓?fù)湫蛄械亩x及拓?fù)渑判蛩惴?；掌握關(guān)鍵路徑的定義及求解過程；八、查找考試內(nèi)容(1)靜態(tài)查找：順序查找、折半查找的查找方法及其實現(xiàn)方法。(2)動態(tài)查找：二叉排序樹、平衡二叉樹。二叉排序樹的插入和查找算法及其實現(xiàn)。(3)哈希表：哈希函數(shù)的構(gòu)造方法、處理沖突的方法、哈希表的查找與分析?？荚囈笳莆侦o態(tài)查找（順序查找、折半查找）及其分析方法，并能靈活地運用；掌握二叉排序樹的構(gòu)造方法、查找過程及其查找分析；掌握平衡二叉樹的構(gòu)造、調(diào)整方法及平衡樹查找分析；掌握哈希表的建表方法和處理沖突的方法，理解哈希表與其他查找表的本質(zhì)區(qū)別；掌握各種查找方法的平均查找長度；九、排序考試內(nèi)容(1)排序的基本概念。(2)插入排序：直接插入排序、其他插入排序和希爾排序。(3)交換排序：冒泡排序和快速排序。(4)選擇排序：簡單選擇排序、堆排序。(5)歸并排序：2-路歸并排序。(6)各種排序方法的算法實現(xiàn)。能從“關(guān)鍵字間的比較次數(shù)”分析算法的平均情況和最壞情況的時間性能。排序方法“穩(wěn)定”或“不穩(wěn)定”的含義?？荚囈罄斫馀判虻幕?/p>