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

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

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

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

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

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