科目代碼、名稱: 843數據結構

專業(yè)類別：√學術型 □專業(yè)學位

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

一、 基本內容

1. 數據類型和數據結構的基本概念

邏輯結構和物理存儲結構;數據結構的抽象數據類型表示;數據結構的應用

2.線性表存儲結構及實現

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

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

3.棧和隊列

棧的基本結構和創(chuàng)建方式;棧的基本屬性和基本操作;棧的應用;中綴轉后綴算法;后綴表達式計算

隊列的基本結構和創(chuàng)建方式;隊列的基本屬性和基本操作;隊列的應用;

4.雙向鏈表

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

5. 遞歸算法

遞歸算法的基本概念和實現方法;數制轉換、漢諾塔

6.二叉樹

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

7.堆

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

8.霍夫曼樹

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

9.復雜樹結構

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

10.查找算法

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

11.排序算法

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

12.圖

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

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

考試時間：180分鐘

總分：150分

考試方式：閉卷筆試

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

三、主要參考書目

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