|
友情提示：本站提供全國400多所高等院校招收碩士、博士研究生入學考試歷年考研真題、考博真題、答案，部分學校更新至2012年，2013年；均提供收費下載。 下載流程： 考研真題 點擊“考研試卷””下載; 考博真題 點擊“考博試卷庫” 下載
安徽師范大學皖江學院電子信息系 數據結構教學大綱
第 頁1
《數據結構》教學大綱
課程性質：專業基礎課程 先修課程：離散數學，C 語言
總學時：41 學分：2
理論學時：32 實驗學時：9
開課學院：皖江學院 適用專業：電子信息工程
大綱執筆人： 教學院長審定：
教研室主任審核：
一、說明
1、課程性質、地位和任務
《數據結構》在計算機科學中是一門綜合性的專業主干課，專業基礎課，主要介紹如何
合理地組織數據、有效地存儲和處理數據，正確地設計算法以及對算法的分析和評價。通過
本課程的學習，使學生深入透徹地理解數據結構的邏輯結構和物理結構的基本概念以及有關
算法，培養基本的、良好的程序設計技能，編制高效可靠的程序，為電子信息工程專業學生
今后學習操作系統、編譯原理等其它相關專業課程奠定基礎。
2、課程教學的基本要求
（1）了解數據結構及其分類、數據結構與算法的密切關系。
（2）熟悉各種基本數據結構及其操作，學會根據實際問題要求來選擇數據結構。
（3）掌握設計算法的步驟和算法分析方法。
（4）掌握線性表、棧與隊列的基本算法及應用。
（5）掌握二維數組、特殊矩陣、稀疏矩陣的表示、實現算法及應用。
（6）熟練掌握樹和二叉樹的各種性質和算法，二叉排序樹、哈夫曼樹的應用。
（7）熟練掌握圖的表示及其實現，圖的遍歷算法，拓撲排序、求取關鍵路徑和單源最
短路徑的算法。
（8）熟練掌握常用的查找、排序算法，學會分析數據表示對各種查找、排序效率的影
響。
3、本課程的重點與難點
重點：本課程的重點內容是分析各種類型數據結構的特點，數據的表示及實現的算法。
如何合理地組織數據、有效地存儲和處理數據，正確地設計編寫算法以及對算法的分析和評
價，如何應用所學知識解決實際問題。教學過程中主要采用講授方式，配合多媒體，形象的
比喻，引導、啟發學生掌握教學內容。
安徽師范大學皖江學院電子信息系 數據結構教學大綱
第 頁2
難點：本課程的難點包括線性鏈表的基本運算、帶行（列）輔助向量的稀疏矩陣的應用、
哈夫曼樹及其應用、單源最短路徑、拓撲排序、哈希表、堆排序以及如何將偽代碼編寫的算
法映射為某一高級語言的描述。
二、課堂教學時數及課后作業題型分配
章 目 教 學 內 容
教 學
時 數
教學方式
或 手 段
課 后 作 業
思 考 題 練 習 題
一 緒論 2 講授（多媒體） √
二 線性表及其順序存儲結構 4 講授（多媒體） √ √
三 線性鏈表 3 講授（多媒體） √ √
四 數組 5 講授（多媒體） √ √
五 樹與二叉樹 5 講授（多媒體） √ √
六 圖 5 講授（多媒體） √ √
七 查找技術 3 講授（多媒體） √ √
八 Hash 表技術 2 講授（多媒體） √ √
九 排序技術 3 講授（多媒體） √ √
合 計 32
三、正文
第一章 緒論
【教學目的】
通過本章教學，使學生掌握數據和數據結構的基本術語，理解算法描述與算法的評價方
法。
【重點難點】
數據結構的基本概念和術語，算法描述與算法分析。
第一節 數據結構的基本概念
一、數據結構的定義
二、數據結構的圖形表示
三、線性數據結構與非線性數據結構
第二節 算法方面的考慮
一、算法的定義
二、算法的時間復雜度和算法的空間復雜度
三、算法描述語言
第二章 線性表及其順序存儲結構
【教學目的】
安徽師范大學皖江學院電子信息系 數據結構教學大綱
第 頁3
通過本章教學，使學生掌握線性表、棧和隊列的邏輯結構和順序存儲結構的描述方法，
熟練掌握線性表、棧和隊列在順序存儲結構下的主要運算，掌握棧與隊列的主要應用，了解
字符串匹配的方法。
【重點難點】
線性表、棧和隊列的邏輯結構和順序存儲結構的描述，線性表、棧和隊列的順序存儲結
構上的插入刪除算法。
第一節 線性表的基本概念
一、線性表的定義
二、線性表的順序存儲結構
三、線性表在順序存儲下的插入運算
四、線性表在順序存儲下的刪除運算
第二節 棧及其應用
一、棧的定義
二、棧的順序存儲及其運算
三、表達式的計算
四、遞歸
第三節 隊列及其應用
一、隊列的定義
二、循環隊列及其運算
三、隊列的應用
第四節 字符串
一、字符串的基本概念
二、字符串匹配
第三章 線性鏈表
【教學目的】
通過本章教學，使學生掌握線性表的鏈式存儲結構及其運算，掌握線性鏈表在多項式運
算中的應用，深刻理解指針與指針所指結點的關系，了解頭指針、頭結點和開始結點之間的
區別。。
【重點難點】
線性表、棧和隊列鏈式存儲結構的描述，線性表、棧和隊列的鏈式存儲結構上的插入刪
除算法，多項式的表示與運算。
第一節 線性鏈表的基本概念
一、線性表順序存儲的問題
二、線性鏈表
三、帶鏈的棧
安徽師范大學皖江學院電子信息系 數據結構教學大綱
第 頁4
四、帶鏈的隊列
第二節 線性鏈表的基本運算
一、在線性鏈表中查找指定元素
二、線性鏈表的插入
三、線性鏈表的刪除
第三節 循環鏈表
第四節 多項式的表示與運算
第四章 數組
【教學目的】
通過本章教學，使學生掌握二維數組的順序存儲結構，規則矩陣（對稱矩陣、上（下）
三角矩陣、三對角矩陣）的表示與實現，掌握稀疏矩陣的帶行（列）輔助向量的三元組表示、
實現及其應用，了解十字鏈表的結構。
【重點難點】
二維數組的存儲結構，存儲地址的計算方式，規則矩陣的壓縮存儲，稀疏矩陣的三元組
表示。
第一節 數組的順序存儲結構
一、按行優先存儲
二、按列優先存儲
第二節 規則矩陣的壓縮
一、對稱矩陣的壓縮
二、三角矩陣的壓縮
三、三對角矩陣的壓縮
第三節 稀疏矩陣的表示
一、稀疏矩陣的三元組表示
二、十字鏈表
第五章 樹與二叉樹
【教學目的】
通過本章教學，使學生熟悉樹、二叉樹的基本概念，掌握二叉樹的性質、二叉樹的存儲
結構及其遍歷，掌握最優二叉樹、哈夫曼編碼的方法，了解樹和森林的相互轉換、穿線二叉
樹的概念、表達式線性化的過程等問題。
【重點難點】
二叉樹的性質，二叉樹的存儲結構，最優二叉樹，哈夫曼編碼，二叉樹的生成算法，二
叉樹的遍歷及其上的一些應用。
第一節 樹
安徽師范大學皖江學院電子信息系 數據結構教學大綱
第 頁5
一、樹的定義
二、基本術語
第二節 二叉樹及其基本性質
一、二叉樹的定義
二、二叉樹的基本性質
三、滿二叉樹與完全二叉樹
第三節 二叉樹的存儲結構
一、二叉鏈表
二、二叉鏈表的生成
三、樹和森林及其相互之間的轉換
第四節 二叉樹的遍歷
一、二叉樹的先序遍歷
二、二叉樹的中序遍歷
三、二叉樹的后序遍歷
第五節 表達式的線性化
一、有序樹的二叉樹表示
二、表達式的線性化
第六節 最優二叉樹及其應用
一、么是最優二叉樹
二、最優二叉樹的構造
三、哈夫曼編碼
第六章 圖
【教學目的】
通過本章教學，使學生理解圖的基本概念、圖的存儲方式、圖的遍歷方法，掌握圖的應
用。
【重點難點】
圖的存儲方式、圖的遍歷方法，單源最短路徑，拓撲排序，關鍵路徑。
第一節 圖的基本概念
一、圖的定義
二、圖的基本術語
第二節 圖的存儲結構
一、關聯矩陣
二、求值矩陣
三、鄰接表
安徽師范大學皖江學院電子信息系 數據結構教學大綱
第 頁6
四、鄰接多重表
第三節 圖的遍歷
一、縱向優先搜索法
二、橫向優先搜索法
第四節 圖的應用
一、單源最短路徑
二、拓撲排序
三、關鍵路徑
第七章 查找技術
【教學目的】
通過本章教學，使學生理解查找的概念，掌握常用的查找方法，熟練掌握二叉排序樹的
構造方法及平均查找長度的計算。
【重點難點】
順序查找，對分查找，分塊查找，二叉排序樹查找以及多層索引樹查找，二叉排序樹的
構造。
第一節 順序查找
一、查找的基本概念
二、順序查找算法
第二節 有序表的對分查找
一、對分查找的概念
二、對分查找的算法
第三節 分塊查找
一、分塊查找的概念
二、分塊查找的算法
第四節 二叉排序樹查找
一、二叉排序樹及其構造
二、二叉排序樹查找算法
第五節 多層索引樹查找
一、B
-
樹 二、B
+
樹
第八章 Hash 表技術
【教學目的】
通過本章教學，使學生理解 Hash 表的基本概念，掌握哈希函數的構造方法，掌握 Hash
表技術的應用。
【重點難點】
安徽師范大學皖江學院電子信息系 數據結構教學大綱
第 頁7
哈希表技術，散列函數的構造方法及沖突的處理。
第一節 Hash 表的基本概念
一、直接查找技術
二、Hash 表
三、Hash 表的構造
第二節 幾種常用的 Hash 表
一、線性 Hash 表
二、隨機 Hash 表
三、溢出 Hash 表
四、拉鏈 Hash 表
五、指標 Hash 表
第九章 排序技術
【教學目的】
通過本章教學，使學生熟練掌握五種基本內部排序方法的基本思想，掌握排序過程和實
現算法，能熟練寫出各趟結果，掌握排序算法的時間復雜度的分析。
【重點難點】
冒泡排序，快速排序，簡單插入排序，希爾排序，簡單選擇排序，堆排序，拓撲分類。
第一節 互換類排序
一、冒泡排序
二、快速排序
第二節 插入類排序
一、簡單插入排序
二、希爾排序
第三 選擇類排序
一、簡單選擇排序
二、堆排序
【課程考試】
本課程采用“閉卷”方式進行考試，考試成績以 60%的比例記入課程總評成績，課外作
業和平時測驗占 20％，實驗占 20％。重點考查學生對各種數據結構的基本概念、基本原理
的理解，測試學生對各種數據結構的表示和算法設計水平，對查找和排序的基本概念及其實
現算法的掌握情況，對知識的應用能力?？荚囶}型包括填空題、選擇題、簡答題和綜合應用
題等類型。
四、使用教材與教學參考書目
【使用教材】
安徽師范大學皖江學院電子信息系 數據結構教學大綱
第 頁8
徐士良：《實用數據結構》，清華大學出版社，2000 年 1 月
【教學參考書目】
1、嚴蔚敏，吳偉民，《數據結構》（C 語言版），清華大學出版社，1997 年 12 月
2、徐孝凱等，《數據結構》（C 語言描述），清華大學出版社，2004 年 9 月
3、[美]Yedidyah Langsam 等著，李華，瀟東譯，《數據結構 C 和 C++語言描述》（第 2
版），清華大學出版社，2004 年 3 月
免責聲明：本文系轉載自網絡，如有侵犯，請聯系我們立即刪除，另：本文僅代表作者個人觀點，與本網站無關。其原創性以及文中陳述文字和內容未經本站證實，對本文以及其中全部或者部分內容、文字的真實性、完整性、及時性本站不作任何保證或承諾，請讀者僅作參考，并請自行核實相關內容。
|
文章搜索
您現在的位置： 
