PAGE5《數據結構》課程教學大綱課程代碼：B03203課程名稱：數據結構英文名稱：DataStructures課程總學時：60（其中理論課46學時，實驗14學時）學分：2.5課程類別：必修課程性質：專業基礎課先修課程：計算機導論、Java語言程序設計面向專業：軟件技術、計算機網絡技術開課單位：軟件工程系一、課程的性質、地位和任務本課程是計算機程序設計的重要理論技術基礎，是計算機學科的核心課程，是專業技術基礎課。本課程的目的是使學生掌握數據組織、存儲和運算的基本原理和方法，培養學生進行數據結構的算法設計及分析問題的能力，能夠編寫出正確、清晰、質量較高的程序，并且為學習后續課程打下良好的基礎，在畢業后從事專業工作時能正確選擇與使用數據結構；本課程的任務是從抽象數據類型的角度討論各種基本類型的數據結構及其應用，另外還討論了查找和排序的各種實現方法，使學生具備基本理論分析和編程能力。二、課程的教學目標（一）理論、知識方面1．掌握數據結構的基本概念，進行初步算法分析。2．掌握線性表的邏輯結構、物理結構以及常用操作的算法。3．掌握棧和隊列的邏輯結構、物理結構，理解棧和隊列的應用。4．了解串類型的定義、表示和實現。5．理解數組的定義、基本運算和存儲結構，理解廣義表的定義、術語、存儲結構、基本運算，了解遞歸算法設計。6．掌握樹的基本概念，二叉樹的定義、性質和存儲結構，遍歷二叉樹，了解線索二叉樹的概念、應用，掌握赫夫曼樹及應用7．掌握靜態查找表的查找方法、理解動態查找表的查找方法，掌握哈希表的基本概念8．掌握常用內部排序算法（二）能力、技能方面1．培養學生的數據抽象能力。2．具備基本理論分析和編程能力。三、課程教學內容與要求第一章緒論（2學時）1.教學內容及基本要求了解數據結構的發展及所處的地位（1學時）；深刻理解數據結構的基本概念和術語；掌握算法描述及算法的評價標準（1學時）。2.重點、難點重點：數據結構的概念和術語。難點：時間復雜度的分析。第二章線性表（6學時）1.教學內容及基本要求理解線性表的概念、存儲結構；深刻理解線性表的順序存儲結構的特點、類型描述，熟練掌握插入、刪除、查找操作的算法實現（2學時）；熟練掌握線性表的鏈式存儲結構的特點、類型描述，插入、刪除、查找操作的算法實現（2學時）；掌握循環鏈表、雙向鏈表及其基本操作的算法（2學時）。2.重點、難點重點：線性表的順序存儲和鏈式存儲結構。難點：線性表的鏈式存儲。第三章棧和隊列（4學時）1.教學內容及基本要求理解堆棧的概念、存儲結構（1學時）；熟練掌握順序存儲和鏈式存儲兩種結構下的進棧、出棧的算法（1學時）。理解隊列的概念、存儲結構（1學時）；熟練掌握順序存儲和鏈式存儲兩種結構下的入隊、出隊的算法（1學時）。2.重點、難點重點：堆棧及其操作，隊列及其操作。難點：遞歸方法的應用，循環隊列的使用。第四章串（2學時）1.教學內容及基本要求理解字符串的概念，掌握字符串的存儲結構；了解字符串操作的應用。2.重點、難點重點：字符串的存儲結構。難點：字符串操作的實現。第五章數組和廣義表（2學時）1.教學內容及基本要求理解數組的定義、基本運算和存儲結構，特殊矩陣的壓縮存儲（1學時）；理解廣義表的定義、術語、存儲結構、基本運算，遞歸算法設計（1學時）。2.重點、難點重點：特殊矩陣的壓縮存儲；廣義表的定義、術語、存儲結構、運算。難點：特殊矩陣的壓縮存儲。第六章樹和二叉樹（8學時）1.教學內容及基本要求理解樹及二叉樹的基本概念；深刻理解二叉樹的定義、性質、存儲結構（2學時）；熟練掌握遍歷和線索二叉樹的方法（2學時）；掌握哈夫曼樹與哈夫曼編碼（2學時）；掌握樹及森林與二叉樹之間的轉換（2學時）。2.重點、難點重點：二叉樹的遍歷、線索及應用。難點：哈夫曼樹的構造。第七章圖（8學時）1.教學內容及基本要求理解圖的概念及基本術語；掌握圖的鄰接矩陣和鄰接表的存儲結構（2學時）；熟練掌握圖的深度優先遍歷和廣度優先遍歷的方法（2學時）；了解圖的遍歷在實際中的應用（2學時）；了解最小生成樹和最短路徑（2學時）。2.重點、難點重點：圖的存儲結構。難點：圖的遍歷。第八章查找（6學時）1.教學內容及基本要求掌握順序查找、二分查找、分塊查找的方法和過程（2學時）；熟練掌握二叉排序樹的定義，結點插入和刪除的操作方法及二叉排序樹的查找過程（2學時）；熟練掌握哈希表定義、哈希函數構造和沖突的處理方法（2學時）。2.重點、難點重點：順序查找、二分查找、分塊查找的方法。難點：二叉排序樹結點的刪除，哈希函數的構造。第九章排序（6學時）1.教學內容及基本要求理解排序的概念；了解各種不同排序方法的適用場合（1學時）；熟練掌握插入排序、快速排序、選擇排序的算法，了解各算法的時間復雜度（3學時）；熟練掌握堆排序、歸并排序、基數排序的算法，了解各算法的時間復雜度（2學時）。2.重點、難點重點：各種排序的算法思想。難點：堆排序。四、學時分配序號教學內容講課習題課實驗合計1緒論222線性表6283棧和隊列4244串245數組和廣義表226樹和二叉樹822127圖82108查找6289排序62210總計=SUM(ABOVE)4441260五、大綱說明1．本課程理論總學時為46學時，為保證基本的教學質量，應當嚴格要求學生做好一定數量的習題，建議講課占90％左右，習題課等占10％左右。2．在教學過程中，逐步推行多媒體教學；不斷進行教學方式方法的探索，重視培養學生的自學能力。3．考核方式和成績評定：本課程的總成績由理論考試成績、平時作業與實驗課成績3部分組成，按百分制計。其中：理論考試成績占70%（理論考試成績通過期末閉卷考試方式評定），平時作業成績占10%（按每次作業完成情況評定），實驗課成績占20%(依實驗課表現與實驗報告情況評定)。理論考試為閉卷筆試，120分鐘，滿分100分，統考，流水作業評分。4．對外語的要求：在講授過程中，給出各章節主要專業名詞的英語單詞，通過本門課程的學習，學生可接觸到100個左右專業名詞的英語單詞。、推薦教材