《資料結構》課程教學大綱--2012版
一、課程基本資訊
課程名稱：資料結構
英文名稱：data structure
課程編碼: 11107c/11207c
課程類別：專業主幹課
總學時: 64學時（含實驗16學時）
總學分: 4
適用專業：電腦科學與技術/網路工程方向
先修課程：高階語言程式設計，離散數學，概率論與數理統計
開課系部: 電腦科學與技術系
二、 課程的性質和任務
《資料結構》是電腦科學與技術專業的一門專業必修課程。它系統地介紹線性表、棧、佇列、字串、陣列、廣義表、樹、二叉樹、圖、查詢表等常用資料結構的基本概念、操作及其典型應用例子。在知識方面，要求學生掌握常用資料結構的基本概念及其不同的實現方法，使學生了解資料物件的特性，資料組織的基本方法；在技能方面，通過系統學習能夠在不同儲存結構上實現不同的運算，並對演算法設計的方式和技巧有所體會。
通過學習，初步具備分析問題、解決問題的能力，養成良好的程式設計風格，積聚和提高基本的分析設計能力，為後續課程的學習打下堅實的基礎。
三、課程教學基本要求
（一）理論教學內容和基本要求
第一章緒論?
資料結構的基本概念；演算法設計；時間和空間複雜度?
本章知識點：理解相關的基本概念；掌握演算法五大要素；掌握計算語句頻度和估算演算法時間複雜度的方法。?
重點：基本概念
難點：演算法的時間和空間複雜度，資料結構的概念
第二章線性表?
線性表的邏輯結構；線性表的儲存結構及操作的實現；一元多項式的表示；習題討論課
本章知識點：掌握線性表的邏輯結構、線性表的儲存結構、線性表在順序結構和鏈式結構上實現基本操作的方法；理解從時間和空間複雜度的角度比較線性表兩種儲存結構的不同特點及其適用場合。重點：
線性表的概念
難點：線性表的表示及實現
第三章棧和佇列?
棧的定義，表示及實現； 表示式求值； 棧與遞迴過程； 佇列的定義，表示及實現；
本章知識點：了解棧和佇列的特點；掌握在兩種儲存結構上棧的基本操作的實現；掌握迴圈佇列和鏈佇列的基本運算；掌握遞迴演算法執行過程中棧狀態的變化過程。?
重點：棧和佇列的表示和實現
難點：迴圈佇列
第四章串?
串的邏輯結構，儲存結構；串的應用；
本章知識點：理解串的基本運算的定義，掌握利用這些基本運算來實現串的其它各種運算的方法；掌握在順序儲存結構上實現串的各種操作的方法；重點掌握串上實現的模式匹配演算法。
重點：串的各種運算方法
難點：串的模式匹配演算法
第五章陣列和廣義表?
陣列的儲存結構；稀疏矩陣的表示及操作的實現；廣義表的定義和儲存結構；廣義表的遞迴演算法；
本章知識點：掌握陣列在以行為主的儲存結構中的位址計算方法；掌握矩陣實現壓縮儲存時的下標變換；理解稀疏矩陣的兩種儲存方式的特點和適用範圍，領會以三元組表示稀疏矩陣時進行運算採用的處理方法；掌握廣義表的定義及其儲存結構，學會廣義表的表頭，表尾分析方法。
重點:稀疏矩陣儲存，矩陣元素位址的計算
難點：矩陣的三元組儲存時演算法
第六章樹和二叉樹?
樹的基本概念；二叉樹的性質和儲存結構；遍歷二叉樹和線索二叉樹；樹的儲存結構和遍歷；樹和森林；哈夫曼樹及其應用；習題討論課?
本章知識點：理解二叉樹的結構特點；掌握二叉樹的各種儲存結構的特點及適用範圍；深入掌握按各種次序遍歷二叉樹的遞迴和非遞迴演算法；掌握二叉樹的線索化，在中序線索樹上找給定結點的前驅和後繼的方法；掌握樹的各種儲存結構及其特點；掌握建立最優二叉樹和哈夫曼編碼的方法。?
重點：二叉樹概念，性質，遍歷演算法
難點：二叉樹線索化，二叉樹的非遞迴演算法
第七章圖?
圖的基本概念；圖的儲存結構；圖的遍歷及應用：最小生成樹、最短路徑等、拓撲排序。
本章知識點：熟悉圖的各種儲存結構，了解實際問題與採用何種儲存結構和演算法有密切聯絡；掌握遍歷圖的遞迴和非遞迴演算法；掌握應用圖的遍歷演算法求各種簡單路徑問題，比如，最小生成樹、最短路徑、拓撲排序等。?
重點：圖的相關概念，圖的遍歷演算法
難點：最小生成樹，最短路徑，拓撲排序
第九章查詢?
靜態查詢表(順序表,有序表,索引順序表)； 動態查詢表(二叉排序樹,平衡二叉樹,b-樹和b+樹)的建立和查詢；雜湊表的建立，查詢及分析；習題討論課。?
本章知識點：理解順序查詢，折半查詢和索引查詢的方法，並能靈活應用；掌握二叉排序樹的構造方法及演算法；掌握二叉平衡樹的建立方法；了解b-樹，b+樹的特點以及它們的建立過程；掌握雜湊表的構造方法；按定義計算各種查詢方法在等概率情況下查詢成功時和失敗時的平均查詢長度，理解雜湊表在查詢不成功時的平均查詢長度的計算方法。
重點：折半查詢，二叉排序樹，雜湊表
難點：二叉平衡樹的建立方法，b-樹，b+樹
第十章內部排序?
概念；插入排序；交換排序(起泡,排序)；選擇排序(簡單選擇,堆)；歸併排序；基數排序。
本章知識點：理解各種排序方法的特點並能靈活應用；掌握各種方法的排序過程和各種排序方法的時間複雜度分析。重點掌握快速排序、堆排序、歸併排序和基數排序的基本思想及排序過程，難點是這四個排序演算法的實現。??
重點：插入排序，交換排序，快速排序，堆排序
難點：快速排序，堆排序，歸併排序
（二）實驗教學內容和基本要求
實驗教學內容及要求見《資料結構》實驗教學大綱
四、課程教學要求及形式
1、課程概念多、抽象、涉及面廣，因此課程教學採用課堂講授+cai輔助教學講授方式、課堂討論、習題課、課程**教學資源等多種形式進行課程教學，積極引導學生，激發學生的思維，讓學生參與到教學中。
2、每章布置3-6道習題以鞏固教學；另外安排6個上機實驗使理論與實際相結合（參考實驗大綱），訓練學生的實際動手能力。
3、考試採用閉卷、平時成績相結合的形式。閉卷部分的考試題包括基本概念、理解掌握、分析問題等，題型可採用選擇題、填空題、簡答題、分析應用題等多種形式。
考核形式：平時成績：20%，期末成績：80%
五、學時分配
六、建議教材及參考書
建議教材：《資料結構》嚴蔚敏主編，清華大學出版社
[1]《資料結構與程式設計》(c語言第二版)，(美)robert l.kuse等著，敖富江譯，清華大學出版社.
[2] 《實用資料結構》,譚浩強主編，中國鐵道出版社.
[3]《資料結構習題與解析》(c語言版)，李春葆等，清華大學出版社.
[4]《資料結構習題集》(c語言版)，嚴蔚敏等，清華大學出版社.
《資料結構》課程教學大綱
保持青春的秘訣，是有一顆不安分的心。data structure a 課程 課程性質 專業基礎理論課 必修 適用專業 資訊計算 資訊保安 開課學期 5 總學時數 72 總學分數 4.5 編寫年月 2003年7月 修訂年月 2007年7月 執筆 高學軍 劉科峰 李小英 一 課程的性質和目的 資料結構是...
資料結構課程教學大綱
一 課程基本概況 課程名稱 資料結構 課程名稱 英文 data structures 課程編號 b09042 課程總學時 60 其中，講課48，實驗12 課程學分 3 課程分類 專業選修課 開設學期 4 適用專業 計算機網路工程本科 先修課程 集合論，圖論，高階語言 結構或記錄，指標 後續課程 資料...
《資料結構》教學大綱
五 課程的教學內容 一 課堂講授的教學內容 1 資料結構的概念 資料結構的概念，抽象資料型別，演算法和演算法分析。2 線性表 線性表邏輯結構，線性表的順序儲存及運算實現，線性表的鏈式儲存和實現，一元多項式的表示與相加。3棧和佇列 棧基本概念及棧的應用，佇列基本概念及佇列的應用。4 串串及其基本運算，...