1、福州理工學院1課程名稱數據結構與算法設計系教（部）信息工程系研室計算機授課教 師黃取治福州理工學院2職稱講師3附件 2:教 案（首頁）課程名稱數據結構與算法設計學 分總計:學時講授：學時上機：學時實驗/訓：學時 其它：學時類另U（請打V）公共課口公共選修課專業基礎課專業必修課專業方向選修 課實驗實訓課（僅限本科）公共課口公共選修課口專業基礎課專業必修課 口專業選修課口 實驗實訓課（僅限高職）授課對象（請打V）本科高職其他使用教材 參考資料（注明書名、主編、出版社、出版時間）教學方法教學手段考核方式學生創新 精神與實 踐能力的 培養方法4數據結構與算法設計課程教案(續頁)5授課時間第1周授課方式

2、(請打V)講授上機實驗/訓其它課時 安排授課題目(章節或單位課時)： 第一章緒論教學目的與要求(分了解、熟悉、掌握三個層次)：1了解數據結構課程的重要性和課程的基本要求，以及本課程涵蓋的內容；2.掌握數據結構的基本概念；3.理解算法描述和簡單的算法分析。教學重點與難點：1.重點是數據結構的基本概念2.難點是時間復雜度分析教 學內容備注數據結構與算法設計課程教案(續頁)61.從后序課(數據庫、操作系統、編譯原理、人工智能)的需要和考研兩方面 介紹數據結構課程的重要性。2.通過三個例子講解數據結構研究的內容。3.介紹基本概念：數據的三個層次，數據結構的三個要素，數據結構的分類， 四種存儲結構，抽象

3、數據類型，算法，算法的五個特性，對算法設計的要求，算法 描述和算法分析，時間復雜度和空間復雜度。4.從百錢買百雞”(一百兀錢買一百支筆”)的算法例子說明選擇算法的重要性： 萬案1:for( i = 0; i =100; i+) for( j = 0; j =100;j+) for( k= 0; k =100; k+)if( (i+j+k=100 &3*i+2*j+0.5*k=100) printf(“i=%cj=%d,k=%d ,i,j,k)萬案2:for( i = 0; i =20; i+) for( j = 0; j =34-i; j+)if(3*i+2*j+(100-i-j) *

4、0.5=100)printf(“i=%d,j=%d,k=%d”，jj)1；00方案1內層循環超過100萬次，在某機器上運行了50分鐘；方案2的if語句執行525次，運行了2秒鐘，相差1500倍。5.算法分析舉例(1)常量階：時間復雜度為0(1)+X；s=0;語句頻度為1,時間復雜度為O(1)。7for(j=1;jv=10000;+j)+x; s+=x;語句頻度為10000,時間復雜度為0(1)。(2) 對數階：時間復雜度為O(logn)s=0;for(j=1; jv=n; j*=2)s+;語句頻度為logn,所以時間復雜度為O(logn)。(3) 線性階：時間復雜度為O(logn)S=0;fo

5、r (j=1;j=n ;+j)s+;語句頻度為n,所以時間復雜度為0(n)。(4)時間復雜度為O(nlogn)s=0;for(j=1;jv=n;j*=2) for(k=1;kv=n;+k) s+;時間復雜度為O(nlogn)(5) 平方階：時間復雜度為O(logn)s=0;for (j=1;j=n ;+j)for (k=1;k=n;+k)s+;語句頻度為n2,所以時間復雜度為O(n2)。s=0;for (j=1; j=n; j+)for (k=1;k=j;+k)s+;語句頻度為n(n+1)/2，所以時間復雜度仍為O(n2)。(6) 立方階：時間復雜度為O( n3)例：矩陣乘法：n x nfor

6、( i = 0; i n; i+)(n+1)for( j = 0; j n; j+)n(n+1) cij = 0；n22for( k= 0; k n; j+)/ n(n+1)cij = cij+aik* bkj; II n38說明：各語句行后的數字是該語句重復執行的次數；本算法時間復雜度為0 （n3）6.空間復雜度算法原地（就地）工作：若所用額外存儲空間相對于輸入數據量來說是常數，則稱此算法為原地（就地）工作。數據結構與算法設計課程教案（續頁）9復習思考題:推薦閱讀書目:教案（末頁）10授課時間第周授課方式（請打V）講授上機實驗/訓其它課時 安排授課題目（章節或單位課時）：教學目的與要求（分了

7、解、熟悉、掌握三個層次）：教學重點與難點：教 學內容備注數據結構與算法設計課程教案（續頁）11教案（末頁）12復習思考題:推薦閱讀書目:數據結構與算法設計課程教案（續頁）13授課時間第周授課方式（請打V）講授上機實驗/訓其它課時 安排授課題目（章節或單位課時）：教學目的與要求（分了解、熟悉、掌握三個層次）：教學重點與難點：教 學內容備注教案（末頁）14數據結構與算法設計課程教案（續頁）15復習思考題:推薦閱讀書目:教案（末頁）16授課時間第周授課方式（請打V）講授上機實驗/訓其它課時 安排授課題目（章節或單位課時）：教學目的與要求（分了解、熟悉、掌握三個層次）：教學重點與難點：教 學內容備注數

8、據結構與算法設計課程教案（續頁）17教案（末頁）18復習思考題:推薦閱讀書目:數據結構與算法設計課程教案（續頁）19授課時間第周授課方式（請打V）講授上機實驗/訓其它課時 安排授課題目（章節或單位課時）：教學目的與要求（分了解、熟悉、掌握三個層次）：教學重點與難點：教 學內容備注教案（末頁）20數據結構與算法設計課程教案（續頁）21復習思考題:推薦閱讀書目:教案（末頁）22授課時間第周授課方式（請打V）講授上機實驗/訓其它課時 安排授課題目（章節或單位課時）：教學目的與要求（分了解、熟悉、掌握三個層次）：教學重點與難點：教 學內容備注數據結構與算法設計課程教案（續頁）23教案（末頁）24復習思

9、考題:推薦閱讀書目:數據結構與算法設計課程教案（續頁）25授課時間第周授課方式（請打V）講授上機實驗/訓其它課時 安排授課題目（章節或單位課時）：教學目的與要求（分了解、熟悉、掌握三個層次）：教學重點與難點：教 學內容備注教案（末頁）26數據結構與算法設計課程教案（續頁）27復習思考題:推薦閱讀書目:教案（末頁）28授課時間第周授課方式（請打V）講授上機實驗/訓其它課時 安排授課題目（章節或單位課時）：教學目的與要求（分了解、熟悉、掌握三個層次）：教學重點與難點：教 學內容備注數據結構與算法設計課程教案（續頁）29教案（末頁）30復習思考題:推薦閱讀書目:數據結構與算法設計課程教案（續頁）31

10、授課時間第周授課方式（請打V）講授上機實驗/訓其它課時 安排授課題目（章節或單位課時）：教學目的與要求（分了解、熟悉、掌握三個層次）：教學重點與難點：教 學內容備注教案（末頁）32數據結構與算法設計課程教案（續頁）33復習思考題:推薦閱讀書目:教案（末頁）34授課時間第周授課方式（請打V）講授上機實驗/訓其它課時 安排授課題目（章節或單位課時）：教學目的與要求（分了解、熟悉、掌握三個層次）：教學重點與難點：教 學內容備注數據結構與算法設計課程教案（續頁）35教案（末頁）36復習思考題:推薦閱讀書目:數據結構與算法設計課程教案（續頁）37授課時間第周授課方式（請打V）講授上機實驗/訓其它課時 安排授課題目（章節或單位課時）：教學目的與要求（分了解、熟悉、掌握三個層次）：教學重點與難點：教 學內容備注教案（末頁）38數據結