科目代碼、名稱: 843數(shù)據(jù)結(jié)構(gòu)

專業(yè)類別：√學(xué)術(shù)型 □專業(yè)學(xué)位

適用專業(yè): 081200計算機科學(xué)與技術(shù),083500軟件工程

一、 基本內(nèi)容

1. 數(shù)據(jù)類型和數(shù)據(jù)結(jié)構(gòu)的基本概念

邏輯結(jié)構(gòu)和物理存儲結(jié)構(gòu);數(shù)據(jù)結(jié)構(gòu)的抽象數(shù)據(jù)類型表示;數(shù)據(jù)結(jié)構(gòu)的應(yīng)用

2.線性表存儲結(jié)構(gòu)及實現(xiàn)

動態(tài)數(shù)組的空間申請和空間管理;動態(tài)數(shù)組的聲明和實現(xiàn);

鏈表的基本結(jié)構(gòu)和創(chuàng)建方式;鏈表的遍歷;鏈表的插入和刪除;鏈表的歸并和拆分;鏈表應(yīng)用;

3.棧和隊列

棧的基本結(jié)構(gòu)和創(chuàng)建方式;棧的基本屬性和基本操作;棧的應(yīng)用;中綴轉(zhuǎn)后綴算法;后綴表達式計算

隊列的基本結(jié)構(gòu)和創(chuàng)建方式;隊列的基本屬性和基本操作;隊列的應(yīng)用;

4.雙向鏈表

雙向鏈表的基本結(jié)構(gòu)和創(chuàng)建方式;雙向鏈表的遍歷、插入和刪除方法;雙向鏈表的應(yīng)用

5. 遞歸算法

遞歸算法的基本概念和實現(xiàn)方法;數(shù)制轉(zhuǎn)換、漢諾塔

6.二叉樹

二叉樹的基本概念和表示方法;二叉樹的創(chuàng)建、遞歸遍歷方法;二叉樹的非遞歸遍歷方法;二叉搜索樹的創(chuàng)建、插入、刪除方法;二叉平衡樹及平衡的調(diào)整方法

7.堆

完全二叉樹結(jié)構(gòu);堆的創(chuàng)建方法、堆調(diào)整;堆的插入、刪除方法;優(yōu)先隊列概念;堆的應(yīng)用-優(yōu)先隊列

8.霍夫曼樹

編碼壓縮方法;霍夫曼編碼;霍夫曼樹創(chuàng)建方法

9.復(fù)雜樹結(jié)構(gòu)

2-3-4樹創(chuàng)建方法;B樹創(chuàng)建、插入和刪除方法

10.查找算法

順序查找算法及時間復(fù)雜度;折半查找算法及時間復(fù)雜度;哈希表構(gòu)造方法(開散列、閉散列);哈希查找算法及沖突解決方法

11.排序算法

簡單排序算法及時間復(fù)雜度(選擇排序、交換排序、冒泡排序、插入排序);高級排序算法及時間復(fù)雜度(快速排序、堆排序、歸并排序、基數(shù)排序);理解算法的最好排序時間、最壞排序時間及平均排序時間

12.圖

圖的基本結(jié)構(gòu)(無向圖和有向圖);圖的基本表示方法;圖的基本遍歷算法(深度、廣度遍歷)、插入和刪除算法;最短路徑算法;最小生成樹算法

二、考試要求(包括考試時間、總分、考試方式、題型、分數(shù)比例等)

考試時間：180分鐘

總分：150分

考試方式：閉卷筆試

題型、分數(shù)比例：簡答或選擇(約20%)程序閱讀(約20%)、綜合和程序設(shè)計題(約60%)

三、主要參考書目

數(shù)據(jù)結(jié)構(gòu)與算法分析-C++語言描述(第2版)，Larry Nyhoff著，黃達明等譯，清華大學(xué)出版社出版, 2006年