|
友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。 下載流程： 考研真題 點擊“考研試卷””下載; 考博真題 點擊“考博試卷庫” 下載
《數據結構》課程教學大綱
學時：68 學分：4
理論學時：34 實驗學時：34
適用專業：計算機科學與技術
大綱執筆人：陳鳳祥 大綱審定人：齊學梅
一、課程的教學目的：
《數據結構》 是計算機教育專業的一門必修的基礎課，教學中將介紹數據、數據結
構和抽象數據類型等基本概念及基本類型的數據結構及其應用。本課程將突出抽象數據
類型的概念，對每一種數據結構，將給出抽象數據類型規范說明和實現方法，培養學生
的數據抽象能力，提高軟件設計和編程水平。本課程不僅為后繼軟件課程提供必要的知
識基礎，也為計算機及其應用的專業人員提供必要的技能訓練。
二、課程的基本要求：
1. 學會分析研究計算機加工的數據結構的特性；
2. 為應用涉及的數據選擇適當的邏輯結構、存儲結構及其相應的算法；
3. 初步掌握算法的時間分析和空間分析的技術。
三、講授內容：
第一章 緒論 （2 學時）
1.1 數據結構有關概念及術語
1.2 抽象數據類型的表示與實現
1.3 算法描述與分析
了解：數據結構基本概念，數據結構的抽象層次，抽象數據類型。
掌握：算法的性能分析與度量方法。
第二章 線性表 （5 學時）
2.1 線性表的定義及其運算
2.2 線性表的順序存儲結構
2.3 線性表的鏈表存儲結構
2.4 線性表的實現舉例
熟練掌握：單鏈表、循環鏈表及雙向鏈表的定義及實現
第三章 棧和隊列（5 學時）
3.1 棧
3.2 棧的應用舉例
3.3 棧與遞歸的實現
3.4 列隊
熟練掌握：棧的定義及實現
熟練掌握：隊列的定義及實現
第四章 串（4 學時）
4.1 串的類型定義
4.2 串的表示和實現
4.3 串的模式匹配算法
4.4 串操作應用舉例
熟練掌握：串的定義和實現
了解： 模式匹配算法
第五章 數組和廣義表（4 學時）
5．1 數組的定義、順序表示和實現
5．2 矩陣的壓縮存儲
5．3 廣義表的定義、存儲結構
了解：稀疏距陣的定義及其數組實現
掌握：廣義表的定義及其實現方法
第六章 樹 （10 學時）
6．1 樹的基本概念和術語
6．2 遍歷二叉樹和線索二叉樹
6．3 樹和森林
6．4 樹的應用
6．5 回溯法與樹的遍歷、樹的計數
了解：樹和森林的概念
掌握：二叉樹的概念、性質及二叉樹的表示
掌握：線索化二叉樹及尋找某結點的前驅和后繼的方法
掌握：樹與森林的實現和遍歷方法
掌握：霍夫曼樹的實現方法
熟練掌握：二叉樹的遍歷方法
第七章 圖（8 學時）
7.1 圖的基本概念和術語
7.2 圖的存儲結構
7.3 圖的遍歷
7.4 圖的連通性問題
7.5 有向無環圖及應用
7.6 最短路徑
掌握：圖的基本概念和圖的存儲表示
掌握：構造最小生成樹的 Prim 和 Kruskal 方法
掌握：求解關鍵路徑的方法
熟練掌握：活動網絡的拓撲排序方法
熟練掌握：圖的兩種遍歷方法與求解連通性問題的方法
第八章 動態存儲管理（可放入操作系統課程中講解）
第九章 查找（8 學時）
9.1 靜態查找表
9.2 動態查找表
9.3 哈希表及其查找
熟練掌握：靜態搜索表的順序查找
熟練掌握：二叉搜索樹的表示、查找、插入、刪除算法及其性能分析方法
熟練掌握：Ｂ—樹、Ｂ＋樹的查找和構造方法
第十章 排序 （8 學時）
10.1 排序的基本概念
10.2 插入排序
10.3 交換排序
10.4 選擇排序
10.5 歸并排序
10.6 基數排序
10.7 內部排序方法的比較討論
掌握：排序的基本概念和性能分析方法
掌握：插入排序、交換排序、選擇排序、歸并排序等內部排序的方法及其性能分析
方法
了解：基數排序方法及其性能分析方法
第十一章 外部排序（2 學時）
11．1 外存信息的存取
11．２ 外部排序的方法、基本思想
11．３ 多路平衡歸并的實現
11．４ 轉換一選擇排序
11．５ 最佳歸并樹
了解：外部排序的基本概念和基本方法
掌握：最佳歸并樹的建立方法
第十二章 文件（2 學時）
12．１ 文件的概念和術語
12．２ 順序文件
12．３ 索引文件
12．４ 散列文件
掌握：文件的基本概念；順序文件，索引文件和散列文件的組織方法和操作方法。
機動： 2 學時
四．實驗開設內容、要求、時間安排：
一、時間安排
序 號 實驗名稱 課 時 必（選）做
實驗一 線性表及其應用 2 必做
實驗二 樹及其應用 4 必做
實驗三 圖及其應用 自定 選做
實驗四 查找技術 4 必做
二、實驗內容
實驗一 線性表及其應用
實驗目的：１．深入了解線性表的各種存儲結構。
２．熟練掌握在各種存儲結構上進行插入、刪除等操作的算法。
３．通過線性表結構解決現實中的一些問題。
實驗內容：１．線性表的各種存儲結構。
２．各種存儲結構上進行插入、刪除等操作的算法。
３．通過線性表結構解決現實中的一些問題。
實驗二 樹及其應用
實驗目的：１．熟悉樹的各種存儲結構的特性。
２．應用樹的結構解決具體問題。
實驗內容：１．樹的各種存儲結構。
２．應用樹的結構解決具體問題。
實驗三 圖及其應用
實驗目的：１．熟悉圖的各種存儲結構的特性。
２．應用圖的結構解決具體問題
實驗內容：１．圖的各種存儲結構。
２．應用圖的結構解決具體問題
實驗四 查找技術
實驗目的：１．熟練掌握常用的一些查找算法。
２．深入理解各種查找算法的結構特點及各算法之間的區別。
３．能通過所學的查找算法解決一些實際問題。
實驗內容：１．常用的一些查找算法。
２．各種查找算法的結構特點及各算法之間的區別。
３．能通過所學的查找算法解決一些實際問題。
五．教學參考書目
1．嚴蔚敏 吳偉民 數據結構 清華大學出版社 1997 年 4 月。
2.嚴蔚敏、吳偉民編著，數據結構題集，清華大學出版社，1999.2，第一版。
3．張曉莉等編著，數據結構與算法，機械工業出版社，2002.9，第一版。
4．李春葆編著，數據結構（C 語言篇）習題與解析，清華大學出版社，2002.4。，
5．李春葆編著，數據結構考研指導，清華大學出版社，2003.1，第一版。
免責聲明：本文系轉載自網絡，如有侵犯，請聯系我們立即刪除，另：本文僅代表作者個人觀點，與本網站無關。其原創性以及文中陳述文字和內容未經本站證實，對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾，請讀者僅作參考，并請自行核實相關內容。
|
文章搜索
您現在的位置： 
