【文章內(nèi)容簡介】 時)實驗7 圖的建立與遍歷(2學時)實驗8 查找與排序(2學時)注：教師可根據(jù)教學實際情況（如：學生情況及學時情況等），適當調(diào)整實踐教學內(nèi)容及學時分配。五、課程考核本課程考核形式為：平時成績占40%，期末考試成績占60%。其中平時成績的結(jié)構(gòu)分包括：課堂表現(xiàn)10%、平時作業(yè)10%和實驗20%，期末考試為閉卷筆試考試：120分鐘，卷面分滿分100分。期末考試成績低于50分者，本課程成績按不及格論處。課堂表現(xiàn)10%：包括課堂考勤和課堂提問，如果缺課課時達到本課程教學時數(shù)的1/3，則取消考試資格。平時作業(yè)10%：根據(jù)上交次數(shù)及完成情況進行評定。實驗20%：根據(jù)各次實驗完成情況及實驗報告成績進行評定。期末考試60%：本課程的期末考試考核內(nèi)容主要包括線性表、棧與隊列、串、數(shù)組與廣義表、樹與二叉樹、圖、查找和內(nèi)部排序。其中，線性表、二叉樹、圖、查找和內(nèi)部排序內(nèi)容為考核的重點。六、本課程與其它課程的先行后續(xù)關(guān)系先行課程：《高級程序設(shè)計語言》、《離散數(shù)學》后續(xù)課程：《操作系統(tǒng)》、《編譯原理》、《數(shù)據(jù)庫理論》、《算法分析與設(shè)計》等七、建議教材及教學參考書：嚴蔚敏，吳偉民編著，《數(shù)據(jù)結(jié)構(gòu)（C語言版）》，清華大學出版， 嚴蔚敏，吳偉民編著，《數(shù)據(jù)結(jié)構(gòu)題集（C語言版）》，清華大學出版， ：[1] 許卓群，張乃孝，楊冬青，唐世渭，《數(shù)據(jù)結(jié)構(gòu)》，高等教育出版社，2004.[2] 徐孝凱，《數(shù)據(jù)結(jié)構(gòu)簡明教程》，清華大學出版社，1995 [3] 陳文博，朱青，《數(shù)據(jù)結(jié)構(gòu)與算法》，機械工業(yè)出版社，1996 [4] 李云清，楊慶紅，揭安全編著，《數(shù)據(jù)結(jié)構(gòu)》（C語言版），人民郵電出版社，2007.[5] 楊秀金主編，《數(shù)據(jù)結(jié)構(gòu)》，西安電子科技大學出版社，2002.[6] 李廉治，姜文清，郭福順，《數(shù)據(jù)結(jié)構(gòu)》，大連理工大學出版社，1989[7] Aho A V, Hopcroft J E, Ullman J Structures and Publishing Company,Inc.,1983[8] Baron R J, Shapiro L Structures and their Nostrand Reinhold Company, 1980[9] Esakov J, Weiss Structures: An Advanced Approach Using , Inc.,1989[10] [美]S巴斯《計算機算法：設(shè)計和分析引論》朱洪等譯，復旦大學出版社，1985第三篇：《數(shù)據(jù)結(jié)構(gòu) A》課程教學大綱《數(shù)據(jù)結(jié)構(gòu) A》課程教學大綱Data Structure A課程代碼：適用專業(yè)：信息計算、信息安全 總學時數(shù)：72編寫年月：2003年7月執(zhí)筆：高學軍、劉科峰、李小英一、課程的性質(zhì)和目的數(shù)據(jù)結(jié)構(gòu)是信息與計算科學專業(yè)的一門重要專業(yè)基礎(chǔ)課程。當用計算機來解決實際問題時，就要涉及到數(shù)據(jù)的表示及數(shù)據(jù)的處理，而數(shù)據(jù)表示及數(shù)據(jù)處理正是數(shù)據(jù)結(jié)構(gòu)課程的主要研究對象，通過這兩方面內(nèi)容的學習，為后續(xù)課程，特別是軟件方面的課程打下了厚實的知識基礎(chǔ)，同時也提供了必要的技能訓練。因此，數(shù)據(jù)結(jié)構(gòu)課程在信息與計算科學專業(yè)中具有舉足輕重的作用。課程性質(zhì)：專業(yè)基礎(chǔ)理論課/必修 開課學期：5 總學分數(shù)： 修訂年月：2007年7月二、課程教學內(nèi)容及學時分配第1章 緒論（4學時）理解數(shù)據(jù)、數(shù)據(jù)元素和數(shù)據(jù)項的概念及其相互間的關(guān)系。理解數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)的聯(lián)系與區(qū)別，以及在數(shù)據(jù)結(jié)構(gòu)上施加的運算及其實現(xiàn)。掌握簡單的算法分析方法。本章知識點為：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結(jié)構(gòu)、存儲結(jié)構(gòu)和數(shù)據(jù)類型等概念術(shù)語的確定含義；抽象數(shù)據(jù)類型的定義、表示和實現(xiàn)方法；描述算法的類C語言；算法設(shè)計的基本要求以及從時間和空間角度分析算法的方法。第2章 線性表（10學時，2個學時實驗上機）理解線性表的定義及其運算。理解順序表和鏈表的定義、組織形式、結(jié)構(gòu)特征和類型說明，掌握在這兩種表上實現(xiàn)的插入、刪除和按值查找的算法。了解循環(huán)鏈表、雙向(循環(huán))鏈表的結(jié)構(gòu)特點和在其上施加的插入、刪除等操作。掌握稀疏多項式在線性表的兩種存儲結(jié)構(gòu)上的實現(xiàn)方法。本章知識點為：線性表的邏輯結(jié)構(gòu)定義、抽象數(shù)據(jù)類型定義和各種存儲結(jié)構(gòu)的描述方法；在線性表的兩類存儲結(jié)構(gòu)(順序的和鏈式的)上實現(xiàn)基本操作；稀疏多項式的抽象數(shù)據(jù)類型定義、表示和加法的實現(xiàn)。第3章 棧和隊列（6學時，2個學時實驗上機）理解棧和隊列的定義、特征及在其上所定義的基本運算。掌握在兩種存儲結(jié)構(gòu)上對棧和隊列所施加的基本運算的實現(xiàn)。熟練掌握循環(huán)隊列和鏈隊列的基本操作實現(xiàn)算法，尤其是隊滿和隊空的描述方法。本章知識點為：抽象數(shù)據(jù)類型棧的定義；棧的表示和實現(xiàn)；棧的應(yīng)用；抽象數(shù)據(jù)類型隊列的定義；鏈隊列；循環(huán)隊列。第4章 串（4學時，2個學時實驗上機）熟悉串的七種基本操作的定義，并能利用這些基本操作來實現(xiàn)串的其它各種操作的方法。熟練掌握在串的定長順序存儲結(jié)構(gòu)上實現(xiàn)串的各種操作的方法。掌握串的堆存儲結(jié)構(gòu)以及在其上實現(xiàn)串操作的基本方法。本章知識點為：串的數(shù)據(jù)類型定義；串的三種存儲表示：定長順序存儲結(jié)構(gòu)、塊鏈存儲結(jié)構(gòu)和堆分配存儲結(jié)構(gòu)；串的各種基本操作的實現(xiàn)及其應(yīng)用；第5章 數(shù)組和廣義表（6學時，2個學時實驗上機）了解數(shù)組的兩種存儲表示方法，并掌握數(shù)組在以行為主的存儲結(jié)構(gòu)中的地址計算方法。掌握對特殊矩陣進行壓縮存儲時的下標變換公式。了解稀疏矩陣的兩種壓縮存儲方法的特點和適用范圍，領(lǐng)會以三元組表示稀疏矩陣時進行矩陣運算采用的處理方法。掌握廣義表的結(jié)構(gòu)特點及其存儲表示方法。本章知識點為：數(shù)組的類型定義和表示方式；特殊矩陣和稀疏矩陣的壓縮存儲方法及運算的實現(xiàn)；廣義表的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)和廣義表的操作。第6章 樹和二叉樹（12學時，2個學時實驗上機）深刻理解樹的定義、性質(zhì)及其存儲方法，熟練掌握二叉樹的二叉鏈表存儲方式、結(jié)點結(jié)構(gòu)和類型定義，并能畫出給定二叉樹的二叉鏈表的結(jié)構(gòu)示意圖；理解并掌握二叉樹的三種遍歷方法，并能寫出該三種遍歷的算法；會完成樹、森林與二叉樹間的相互轉(zhuǎn)換；理解哈夫曼樹的構(gòu)造方法，并能對給定的數(shù)據(jù)集合構(gòu)造出哈夫曼樹。本章知識點為：二叉樹的定義、性質(zhì)和存儲結(jié)構(gòu)；二叉樹的遍歷和線索化以及遍歷算法的各種描述形式；樹和森林的定義、存儲結(jié)構(gòu)、與二叉樹的轉(zhuǎn)換、遍歷；樹的多種應(yīng)用。第7章 圖（12學時，2個學時實驗上機）理解圖的基本概念及術(shù)語，掌握圖的兩種存儲結(jié)構(gòu)(鄰接矩陣和鄰接表)的表示方法；熟練掌握圖的兩種遍歷(深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷)的算法思想、步驟，并能列出在兩種存儲結(jié)構(gòu)上按上述兩種遍歷算法得到的序列；理解最小生成樹的概念，能按Prim算法構(gòu)造最小生成樹；了解并掌握拓撲排序、關(guān)鍵路徑、最短路徑的算法思想。本章知識點為：圖的定義和術(shù)語；圖的四種存儲結(jié)構(gòu)：數(shù)組表示法、鄰接表、十字鏈表和鄰接多重表；圖的兩種遍歷策略：深度優(yōu)先搜索和廣度優(yōu)先搜索；圖的連通性：連通分量和最小生成樹；拓撲排序和關(guān)鍵路徑；兩類求最短路徑問題的解法。第8章 查找（10學時，2個學時實驗上機）了解查找的基本思想及查找成功和不成功的概念，掌握在順序表、有序表、索引表、散列表等上的查找方法和算法，并能求出相應(yīng)的平均查找長度。本章知識點為：討論查找表(包括靜態(tài)查找表和動態(tài)查找表)的各種實現(xiàn)方法：順序表、有序表、樹表和哈希表；平均查找長度的討論。第9章 內(nèi)部排序（8學時，2個學時實驗上機）了解排序的基本思想和基本概念，理解和掌握插入排序、冒泡排序、快速排序、直接選擇排序、堆排序、歸并排序和基數(shù)排序的基本思想、步驟及算法。本章知識點為：討論比較各種內(nèi)部排序方法，插入排序、交換排序、選擇排序、歸并排序和基數(shù)排序的基本思想、算法特點、排序過程以及它們的時間復雜度分析。在每類排序方法中，又從簡單方法入手，重點討論性能先進的高效方法。三、課程教學的基本要求本課程是信息與計算科學專業(yè)的重要專業(yè)基礎(chǔ)課，計算機科學各領(lǐng)域及有關(guān)的系統(tǒng)和應(yīng)用軟件都要用到各種數(shù)據(jù)結(jié)構(gòu)。在教學方法上采用課堂講授，課后自學，課堂討論等教學形式。(一)課堂講授本課程屬于基礎(chǔ)理論課程。在傳授知識原理的前提下，配合實際應(yīng)用例子，由淺入深善于誘導，使學生從被動吸收知識的狀態(tài)下，轉(zhuǎn)化到主動索取知識的狀態(tài)中來，并采用多媒體輔助教學，加大課堂授課的知識含量。注重培養(yǎng)學生的學習興趣，提高學生的基本素質(zhì)。（二）課后自學為了培養(yǎng)學生整理歸納，綜合分析和處理問題的能力，每章都安排一部分內(nèi)容，課上教師只給出自學提綱，不作詳