1、算法設計基礎(Introduction to Algorithm Design)課程代碼：06410027學分：5學時：96 (其中：講課學時：64實驗學時：0上機學時：32課外學時:0 )先修課程：離散數學、程序設計基礎適用專業：物聯網工程教材：數據結構(C+)，王紅梅，清華大學出版社，2011年6月第2版教材名稱、主編、出 版社、版次一、課程性質與課程目標(-)課程性質算法設計基礎是高等工科院校計算機通信類的一門專業基礎課，算法是程序設計的靈魂和 思想，在任何應用領域，精心設計的算法都是解決各種問題最有效的方法。它不僅是計算機應用程 序和系統程序設計的基礎，也是單片機及嵌入式系統程序開發的

2、重要基礎。通過算法設計基礎 課程的學習，使學生能針對實際應用問題，分析設計出合理的算法，編寫出優質程序。(二)課程目標.知識方面課程目標1.1:理解用算法描述計算問題的過程和方法，掌握算法分析的事前估計法及算法分析 相關的兩個基本概念：時間復雜度和空間復雜度，學會用兩種復雜度來表示算法的基本性能。課程目標1.2：理解算法設計中所處理的數據對象及數據對象間的關系，即數據結構的概念，深 刻理解各種數據結構的邏輯特性，理解并熟練掌握各種數據結構的物理存儲表示，以數據結構為基 礎，理解各種不同數據結構上基本算法的設計與實現，同時對算法能作時間和空間性能的分析。課程目標1.3：著重理解算法中查找和排序兩

3、種基本的算法，掌握不同結構上的查找、排序方法 及對應的算法描述、性能分析。.能力和素養方面課程目標2.1：具備依據工程實際問題的需求抽象數據和數據關系，并將此在計算機中合理表(3)熟練掌握圖的兩種搜索路徑的遍歷方法。.實驗要求本實驗要求實現以下功能：(1)以鄰接矩陣或鄰接表作為存儲結構建立一個無向圖。(2)深度(或廣度)優先搜索該無向圖，輸出遍歷序列。(3)若圖是一個非連通圖，求圖的連通分量個數。實驗7：二叉排序樹的查找性能.實驗目的(1)理解二叉排序樹的基本特征。(2)掌握二叉排序樹上的查找、插入等基本算法的操作過程。.實驗要求本實驗要求實現以下功能：(1)對給定的同一個查找集合，按升序和隨

4、機順序建立兩課二叉排序樹。(2)比較同一個待查值在不同二叉排序樹上進行查找的比較次數。(3)對隨機順序建立的二叉排序樹，輸出查找最好、最壞和平均情況。實驗8：內部排序方法的驗證.實驗目的熟悉各種內部排序算法的基本思想。.實驗要求本實驗要求實現以下功能：對從鍵盤輸入的順序任意的8個正整數，通過各種排序(至少2個排序方法)使之成為有 序的序列。輸出每一趟排序的結果。四、學時分配及教學方法章(按序填寫)教學形式及學時分配主要教學方 法支撐的課程目 標課堂 教學實驗上機課程 實踐小 計第一章緒論426講授1.1第二章線性表6410講授+演示1.2, 2.1, 2.2,2.3第三章棧和隊列6410講授+

5、案例+1.2, 2.1, 2.2,演示2.3第四章字符串和多維數組8412講授+演示1.2, 2.1, 2.2,2.3第五章樹和二叉樹12416講授+演示+ 案例+互動1.2, 2.1, 2.2,2.3第六章圖12618講授+演示+ 案例+自學1.2, 2.1, 2.2,2.3第七章查找技術8412講授+案例+演示+對比+自學1.2, 2.1, 2.2,2.3第八章排序技術8412講授+演本+ 對比1.2, 2.1, 2.2,2.3合計643276五、課程考核考核形式考核要求考核權重備注平時作業主要考核學生對課堂講授的知識點的 復習、理解和掌握程度，考核作業是否 提交或按時提交、考核所完成作業

6、的質 量和正確程度。總分數平均計算（取5 次作業）10%課堂和上機考勤主要考核學生課堂聽講出勤情況、上機 實驗出勤情況。缺勤一次扣1分10%上機完成8個上機實驗，主要考核對算法的 理解，編程能力。10%評分細則見附錄1期末考試閉卷70%六、參考書目及學習資料1.算法基礎：打開算法之門，托馬斯H.科爾曼著王宏志譯，機械工業出版社，2015年第1版.數據結構（C語言版），嚴蔚敏，清華大學出版社，1997年第1版.數據結構（用面向對象方法與C+語言描述），殷人昆，清華大學出版社,2007年第2版。七、大綱說明（內容可包括課程基本要求、習題要求及其它一些必要的說明）1、本課程的課程設計見算法設計課程設

7、計教學大綱。2、課程以講授為主，輔以課堂討論、課程成績根據學生課堂參與情況、平時作業和期末考試 成績綜合評定。3、采用多媒體和黑板相結合的教學手段，注重學生的課堂氛圍和對知識掌握程度的及時反饋。2017年 8月27日附錄1:實驗評價內容與評分比重以及評分細則考核內容成績考核要求考核權重指標點預習準備情 況優秀（90-100）明確實驗要求、已準備好所有程序代 碼。20%2-2良(80-89)明確實驗要求、已準備了大部分程序 代碼。中(70-79)對實驗要求較明確、已準備了部分程 序代碼。及格(60-69)對實驗要求理解得不夠透徹、只有少 量程序代碼或只有一些簡單的思路。不及格（60分以下）對實驗

8、要求理解不明確，有極少或沒 有程序代碼和思路。編程實現能 力與運行結 果優秀（90-100）程序正確，運行結果正確且提示較為 清晰和友好。60%1-3良(80-89)程序正確，運行結果正確但提示不夠 清晰友好。中(70-79)程序能運行，但運行結果有少量錯 誤。及格(60-69)程序能運行，但運行結果不正確或程 序錯誤較多無法運行或沒有程序。不及格（60分以下）只有個別程序能運行或程序錯誤較 多無法運行或沒有程序。報告清晰， 按時提交優秀(90-100)報告清楚，按時提交。20%2-2良(80-89)報告較清楚，按時提交中(70-79)報告清楚或較清楚，但未按時提交。及格(60-69)報告不清

9、楚但按時提交。不及格（60分以下）報告不清楚也未按時提交。示的能力。課程目標2.2：具備依托工程實際問題中數據對象的關系設計有效算法，并對算法性能進行時 空分析的能力。課程目標2.3：具備將算法轉化為解決工程實際問題的可運行程序的能力。（三）課程目標與專業畢業要求指標點的對應關系本課程支撐專業培養計劃中畢業要求1中的指標點1-1,畢業要求2中的指標點2-1. 2-2. 2-3,畢業要求4中的指標點4-3.畢業要求1-3:具備將工程基礎知識用于描述、求解物聯網領域復雜工程問題的能力。.畢業要求2-1：具備對物聯網領域復雜工程問題進行識別和有效分解的能力。.畢業要求2-2：能夠針對物聯網復雜工程問

10、題中的模塊或過程進行恰當表述，并建立合 適的數學模型。.畢業要求2-3：能夠利用恰當條件，對物聯網領域復雜工程問題進行分析和探討，能意識到問題的關鍵環節。5.畢業要求4-3：理解離散結構、計算模型在物聯網基礎問題求解中的意義與基本運用。課程目標 畢業要求孤課程目標1.1課程目標1.2課程目標1.3課程目標2.3課程目標2.2課程目標2.3畢業要求1-3VVV畢業要求2-1VVVV畢業要求2-2VVVV畢業要求2-3VVV畢業要求4-3VVV二、課程內容與教學要求第一章緒論（一）課程內容.算法起源和算法的基本概念。.數據結構的基本概念，以及算法和數據結構之間的關系。.算法的時間復雜度和空間復雜度

11、分析。（二）教學要求. 了解課程的性質、任務和目的。.掌握與數據結構有關的幾個重要概念。. 了解算法設計的重要性。.對算法分析有初步了解。（三）重點與難點.重點與數據結構有關的幾個重要概念：數據、數據元素、數據項；數據的邏輯結構和存儲結構在 概念上的聯系與區別；評價算法優劣的標準及方法。.難點算法與程序的區別；邏輯結構、存儲結構的聯系與區別；算法的時間復雜度分析方法。第二章線性表（-）課程內容. 了解線性表的邏輯結構。.掌握線性表在兩種不同存儲結構上各種操作的算法實現。.線性表的應用算法舉例。（二）教學要求.掌握線性表的基本概念和特點。.熟練掌握對順序表和單鏈表的常用操作方法及其算法實現。.掌

12、握線性表的簡單應用一一一元多項式的表示及相加運算（三）重點與難點.重點順序表和鏈式表的基本操作。.難點鏈式表的基本操作以及一元多項式的相加運算。第三章棧和隊列（一）課程內容.棧的定義和邏輯結構特征；理解在棧的順序存儲和鏈式存儲上實現各種棧操作的算法。.隊列的定義和邏輯結構特征；隊列的順序存儲（循環隊列）和鏈接存儲表示及各種操作的實現算法；.棧的應用算法一一表達式求值。（二）教學要求.掌握棧和隊列的定義。.熟練掌握兩種結構在順序和鏈接存儲結構上各種操作的算法實現。.掌握表達式求值方法并了解其算法實現過程。（三）重點與難點.重點棧和隊列的順序存儲表示、鏈式存儲表示及基本操作的實現。.難點順序棧的溢

13、出判斷條件；循環隊列的隊空、隊滿判斷條件。第四章字符串和多維數組（一）課程內容.字符串的定義和存儲，理解字符串模式匹配算法。.多維數組的定義和存儲。.特殊矩陣的壓縮存儲和尋址方法。.字符串應用算法一一凱撒密碼；數組應用算法一一幻方。（二）教學要求.熟悉串的定義、存儲結構和操作。.掌握數組的定義及順序存儲結構。.掌握特殊矩陣和稀疏矩陣的定義以及各種存儲結構。.掌握稀疏矩陣的轉置方法并了解其算法。. 了解凱撒加密和幻方算法。（三）重點與難點.重點掌握數組的定義和數組的存儲結構、特殊矩陣和稀疏矩陣的壓縮存儲。.難點稀疏矩陣的壓縮存儲表示下的矩陣運算的算法實現。第五章樹和二叉樹（-）課程內容.樹的基本

14、概念。.二叉樹的邏輯結構、基本性質和遍歷操作的定義。.二叉樹的順序、鏈式存儲，以及鏈式存儲上的遍歷算法實現。.二叉樹的非遞歸遍歷算法。.樹的存儲結構，樹、二叉樹及森林之間的相互轉換。.二叉樹應用算法一一哈夫曼編碼。（二）教學要求.掌握樹的定義、存儲結構以及樹和森林的遍歷算法。.熟練掌握二叉樹的定義、性質、存儲結構、各種遍歷方法及其實現。.掌握樹、二叉樹及森林間的轉換方法。.熟練掌握二叉樹的應用一一哈夫曼樹的構造算法，掌握哈夫曼樹的應用。（三）重點與難點.重點二叉樹的概念、遍歷及基本操作，樹的存儲結構表示以及樹、森林與二叉樹的轉換方法、樹的 遍歷方法，哈夫曼樹及其應用。.難點利用二叉樹的基本遍歷

15、操作實現其他復雜的運算。第六章圖（一）課程內容.圖的邏輯結構。.圖的存儲結構及實現；圖的深度優先和廣度優先遍歷算法。.最小生成樹算法。.最短路徑算法。.拓撲排序算法。（二）教學要求.掌握圖的定義和術語。.熟練掌握圖的存儲結構及深度和廣度優先搜索方法及其實現。.掌握圖的生成樹的概念，熟練掌握求圖的最小生成樹的普里姆和克魯斯卡爾方法，了解 其實現算法，并具有利用普里姆法和克魯斯卡爾法構造圖的最小生成樹的能力。.掌握圖的最短路徑迪杰斯拉特方法，了解其實現算法，并具有構造單源點最短路徑及其 長度的能力。.掌握拓撲排序的方法并了解其實現算法。（三）重點與難點.重點圖的存儲結構、深度和廣度優先搜索方法及其

16、實現、圖的最小生成樹的構造方法、圖的最短路 徑及其長度的求解方法、有向無環圖的拓撲有序序列的構造方法。.難點最小生成樹、最短路徑的算法思想及其算法實現、拓撲排序的算法實現。第七章查找技術（-）課程內容.查找的基本概念。.線性表的查找：順序表的查找、有序表的折半查找。.樹表的查找：二叉排序樹的定義，二叉排序樹表上的查找、插入、刪除算法的設計和實 現。4,散列查找：散列表、散列函數的基本概念，散列表的構造方法及散列查找算法。（二）教學要求. 了解查找的基本思想及查找成功和不成功的概念。.掌握在順序表、有序表上的查找方法和算法，并能利用平均查找長度分析算法的性能。.熟練掌握二叉排序樹的插入、查找方法

17、及其算法實現，并具有對二叉排序樹進行查找分 析的能力，了解二叉排序樹的刪除操作及其算法實現。. 了解平衡二叉樹的基本概念。.熟練掌握散列表的構造方法，并具有對散列表進行查找和分析的能力。（三）重點與難點.重點順序表的查找、二叉排序樹的查找和插入以及查找性能的分析、散列表的構造方法以及查找性 能的分析。.難點二叉排序樹刪除操作的算法實現。第八章排序技術（一）課程內容.排序的基本概念。.以插入、交換、選擇、歸并和分配思想為基礎的各種排序算法實現及分析。.上述各種排序算法的比較。（二）教學要求.理解排序的基本思想和基本概念。.理解并掌握插入排序、冒泡排序、快速排序、直接選擇排序、堆排序、歸并排序和基

18、數 排序的基本思想、步驟、算法及時空效率分析。. 了解各種典型的內部排序算法的特點和適用范圍。.理解穩定性的概念。（三）重點與難點.重點各種排序方法及時空效率分析。.難點快速排序、堆排序及其算法實現。三、本課程開設的實驗項目編號實驗項目名稱學時類型要求支撐的課程目標1冒泡排序算法的改良2驗證+設計型必做1.1, 1.2, 2.1, 2.22單鏈表的合并4設計型必做1.1, 1.2, 2.1, 2.2,3棧和隊列的應用4設計型必做1.2, 2.1, 2.2, 2.34統計文本中單詞個數4設計型必做1.2, 2.1, 2.2, 2.35二叉樹的遍歷算法4驗證型必做1.1, 1.2, 2.1, 2.

19、26圖的遍歷算法及應用6驗證+設計型必做1.1, 1.2, 2.1, 2.27二叉排序樹的查找性能4驗證+設計型必做1.1, 1.2, 1.3, 2.1,2.28排序算法4驗證型必做1.1, 1.2, 1.3, 2.1,2.2實驗1：冒泡排序算法的改良.實驗目的(1)熟悉用Visual C+進行程序設計的方法。(2)掌握用時間復雜度分析算法性能的方法。.實驗要求本實驗要求實現以下功能：(1)實現經典的冒泡排序算法。(2)從提前結束排序過程的角度出發，考慮對冒泡排序算法進行簡單的改進。(3)對改進后的算法分析最好、最壞和一般情況下的時間復雜度。實驗2：單鏈表的創建、合并和輸出.實驗目的(1)熟悉

20、線性表的基本操作。(2)掌握單鏈表的創建、查找、插入和合并等運算。.實驗要求本實驗要求實現以下功能：(1)從鍵盤輸入順序任意的5個整數，按有序插入的要求生成第一個有序單鏈表，將該鏈表 輸出顯示。(2)再從鍵盤輸入順序任意的5個整數，按有序插入的要求生成第二個有序單鏈表，將該鏈 表輸出顯示。(3)將這兩個有序單鏈表合并成一個有序單鏈表，要求使用兩個單鏈表的原有空間進行合 并，將生成的有序單鏈表輸出顯示。實驗3：棧和隊列的應用.實驗目的(1)理解棧和隊列的結構特征和運算特征。(2)學會在實際問題背景下靈活運用棧和隊列的特征。.實驗要求本實驗要求實現以下功能：(1)從鍵盤輸入任意括號序列，編程判斷括號是否