《數(shù)據(jù)結構與算法分析》考試大綱

1、數(shù)據(jù)結構與算法分析考試大綱一考試的內(nèi)容和要求總體要求1. 理解數(shù)據(jù)結構的基本概念； 掌握數(shù)據(jù)的邏輯結構、 存儲結構及其差異，以及各種基本操作的實現(xiàn)。2. 掌握基本數(shù)據(jù)處理原理和方法的基礎上， 能夠?qū)λ惴ㄟM行基本的時間復雜度與空間復雜度設計與分析。3. 能夠選擇合適的數(shù)據(jù)結構和方法進行問題求解， 具備采用 C+語言設計與實現(xiàn)算法的能力。（一）數(shù)據(jù)結構和算法的基本概念1、考試內(nèi)容數(shù)據(jù)結構的基本概念； 算法的基本概念和五個基本性質(zhì)；算法復雜度的基本概念及計算；抽象數(shù)據(jù)類型的定義。2、考試要求（ 1）了解數(shù)據(jù)結構的基本概念，包括邏輯結構、存儲結構的基本概念、兩者之間的區(qū)別與聯(lián)系。（ 2）掌握算法的定義

2、和五個基本性質(zhì)。（ 3）了解算法復雜度的基本概念，掌握時間復雜度的計算。（ 4）掌握抽象數(shù)據(jù)類型的定義。（二）線性表1、考試內(nèi)容順序表、單鏈表2、考試要求（ 1）了解線性表的定義、邏輯結構及基本操作。（ 2）掌握線性表的順序存儲結構的定義及實現(xiàn)。（ 3）掌握線性表的鏈式結構的定義及實現(xiàn)。（ 4）掌握順序表及鏈表各自的優(yōu)缺點。（ 5）能應用線性表求解相關問題，并設計出算法。（三）棧與隊列1、考試內(nèi)容棧的定義、邏輯結構、基本操作；隊列的定義、 邏輯結構、基本操作；遞歸的定義、遞歸的兩個基本要素、遞歸算法的設計。2、考試要求（ 1）掌握棧的定義及操作特性。（ 2）掌握隊列的定義及操作特性。（ 3）掌

3、握棧和隊列的區(qū)別。（ 4）掌握遞歸的定義、遞歸的兩個基本要素、遞歸算法的設計。（ 5）掌握棧和隊列的應用，能夠運用棧和隊列設計算法解決問題。（四）字符串1、考試內(nèi)容字符串的定義、字符串的操作特性、字符串的應用。2、考試要求（ 1）掌握字符串的定義及相關術語。（ 2）掌握字符串的基本操作。（ 3）掌握字符串的應用，能夠運用字符串設計算法求解問題。（五）樹和二叉樹1、考試內(nèi)容樹形結構相關術語；樹的定義、樹的邏輯結構、樹的基本操作；二叉樹的定義、二叉樹的邏輯結構、二叉樹的基本操作。2、考試要求（ 1）了解樹形結構的相關術語。（ 2）掌握樹的定義、樹的邏輯結構及基本操作。（ 3）掌握二叉樹的定義、二叉

4、樹的邏輯結構、二叉樹的基本操作。（ 4）掌握二叉樹的五種基本形態(tài)及五個基本性質(zhì)。（ 5）掌握二叉樹的前序遍歷、 中序遍歷、后序遍歷和層次遍歷規(guī)則，能寫出二叉樹的遍歷序列。（ 6）掌握二叉樹的算法設計。（六）圖1、考試內(nèi)容圖的定義及相關術語、 圖的邏輯結構及基本操作、 圖的存儲結構及實現(xiàn)、圖的遍歷、圖的最小生成樹。2、考試要求（ 1）了解圖的定義及相關術語。（ 2）掌握圖的邏輯結構及基本操作。（ 3）掌握圖的鄰接矩陣、鄰接表的存儲方式及實現(xiàn)。（ 4）掌握圖的深度優(yōu)先和廣度優(yōu)先遍歷算法。（ 5）掌握圖的兩種最小生成樹算法，能構造圖的最小生成樹并計算代價。（七）查找1、考試內(nèi)容查找的概念、查找的結構

5、及查找算法2、考試要求（ 1）掌握查找的概念及相關術語。（ 2）掌握順序查找算法和折半查找算法的基本思想和算法實現(xiàn)。（ 2）掌握散列表查找，散列函數(shù)的設計。（ 3）掌握二叉排序樹的概念，創(chuàng)建二叉排序樹及在二叉排序樹上進行查找。（八）排序1、考試內(nèi)容排序的定義及相關術語、常用的內(nèi)排序算法2、考試要求（ 1）掌握簡單選擇排序、直接插入排序、交換排序的算法思想和實現(xiàn)，能夠?qū)懗雠判蜻^程。（ 2）了解各種排序方法的特點，能夠針對特定問題背景選擇適當?shù)呐判蚍椒?。二考試形式及試卷結構（一）考試形式閉卷、筆試，滿分100 分，考試時間為120 分鐘。（二）考試內(nèi)容結構與比例1、數(shù)據(jù)結構和算法的基本概念約占 10%2、線性表約占 15%3、棧與隊列約占 15%4、字符串約占 5%5、樹與二叉樹約占 20%6、圖約占 15%7、查找約占 10%8、內(nèi)排序約占 10%（三）試卷題型結構與比例1、選擇題約占 20%2、填空題約占 10%3、判斷題約占10%4、名