1、福州理工學(xué)院1課程名稱(chēng)數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)系教（部）信息工程系研室計(jì)算機(jī)授課教 師黃取治福州理工學(xué)院2職稱(chēng)講師3附件 2:教 案（首頁(yè)）課程名稱(chēng)數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)學(xué) 分總計(jì):學(xué)時(shí)講授：學(xué)時(shí)上機(jī)：學(xué)時(shí)實(shí)驗(yàn)/訓(xùn)：學(xué)時(shí) 其它：學(xué)時(shí)類(lèi)另U（請(qǐng)打V）公共課口公共選修課專(zhuān)業(yè)基礎(chǔ)課專(zhuān)業(yè)必修課專(zhuān)業(yè)方向選修 課實(shí)驗(yàn)實(shí)訓(xùn)課（僅限本科）公共課口公共選修課口專(zhuān)業(yè)基礎(chǔ)課專(zhuān)業(yè)必修課 口專(zhuān)業(yè)選修課口 實(shí)驗(yàn)實(shí)訓(xùn)課（僅限高職）授課對(duì)象（請(qǐng)打V）本科高職其他使用教材 參考資料（注明書(shū)名、主編、出版社、出版時(shí)間）教學(xué)方法教學(xué)手段考核方式學(xué)生創(chuàng)新 精神與實(shí) 踐能力的 培養(yǎng)方法4數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)課程教案(續(xù)頁(yè))5授課時(shí)間第1周授課方式

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

3、數(shù)據(jù)類(lèi)型，算法，算法的五個(gè)特性，對(duì)算法設(shè)計(jì)的要求，算法 描述和算法分析，時(shí)間復(fù)雜度和空間復(fù)雜度。4.從百錢(qián)買(mǎi)百雞”(一百兀錢(qián)買(mǎi)一百支筆”)的算法例子說(shuō)明選擇算法的重要性： 萬(wàn)案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)萬(wàn)案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內(nèi)層循環(huán)超過(guò)100萬(wàn)次，在某機(jī)器上運(yùn)行了50分鐘；方案2的if語(yǔ)句執(zhí)行525次，運(yùn)行了2秒鐘，相差1500倍。5.算法分析舉例(1)常量階：時(shí)間復(fù)雜度為0(1)+X；s=0;語(yǔ)句頻度為1,時(shí)間復(fù)雜度為O(1)。7for(j=1;jv=10000;+j)+x; s+=x;語(yǔ)句頻度為10000,時(shí)間復(fù)雜度為0(1)。(2) 對(duì)數(shù)階：時(shí)間復(fù)雜度為O(logn)s=0;for(j=1; jv=n; j*=2)s+;語(yǔ)句頻度為logn,所以時(shí)間復(fù)雜度為O(logn)。(3) 線(xiàn)性階：時(shí)間復(fù)雜度為O(logn)S=0;fo

5、r (j=1;j=n ;+j)s+;語(yǔ)句頻度為n,所以時(shí)間復(fù)雜度為0(n)。(4)時(shí)間復(fù)雜度為O(nlogn)s=0;for(j=1;jv=n;j*=2) for(k=1;kv=n;+k) s+;時(shí)間復(fù)雜度為O(nlogn)(5) 平方階：時(shí)間復(fù)雜度為O(logn)s=0;for (j=1;j=n ;+j)for (k=1;k=n;+k)s+;語(yǔ)句頻度為n2,所以時(shí)間復(fù)雜度為O(n2)。s=0;for (j=1; j=n; j+)for (k=1;k=j;+k)s+;語(yǔ)句頻度為n(n+1)/2，所以時(shí)間復(fù)雜度仍為O(n2)。(6) 立方階：時(shí)間復(fù)雜度為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說(shuō)明：各語(yǔ)句行后的數(shù)字是該語(yǔ)句重復(fù)執(zhí)行的次數(shù)；本算法時(shí)間復(fù)雜度為0 （n3）6.空間復(fù)雜度算法原地（就地）工作：若所用額外存儲(chǔ)空間相對(duì)于輸入數(shù)據(jù)量來(lái)說(shuō)是常數(shù)，則稱(chēng)此算法為原地（就地）工作。數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)課程教案（續(xù)頁(yè)）9復(fù)習(xí)思考題:推薦閱讀書(shū)目:教案（末頁(yè)）10授課時(shí)間第周授課方式（請(qǐng)打V）講授上機(jī)實(shí)驗(yàn)/訓(xùn)其它課時(shí) 安排授課題目（章節(jié)或單位課時(shí)）：教學(xué)目的與要求（分了

7、解、熟悉、掌握三個(gè)層次）：教學(xué)重點(diǎn)與難點(diǎn)：教 學(xué)內(nèi)容備注數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)課程教案（續(xù)頁(yè)）11教案（末頁(yè)）12復(fù)習(xí)思考題:推薦閱讀書(shū)目:數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)課程教案（續(xù)頁(yè)）13授課時(shí)間第周授課方式（請(qǐng)打V）講授上機(jī)實(shí)驗(yàn)/訓(xùn)其它課時(shí) 安排授課題目（章節(jié)或單位課時(shí)）：教學(xué)目的與要求（分了解、熟悉、掌握三個(gè)層次）：教學(xué)重點(diǎn)與難點(diǎn)：教 學(xué)內(nèi)容備注教案（末頁(yè)）14數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)課程教案（續(xù)頁(yè)）15復(fù)習(xí)思考題:推薦閱讀書(shū)目:教案（末頁(yè)）16授課時(shí)間第周授課方式（請(qǐng)打V）講授上機(jī)實(shí)驗(yàn)/訓(xùn)其它課時(shí) 安排授課題目（章節(jié)或單位課時(shí)）：教學(xué)目的與要求（分了解、熟悉、掌握三個(gè)層次）：教學(xué)重點(diǎn)與難點(diǎn)：教 學(xué)內(nèi)容備注數(shù)

8、據(jù)結(jié)構(gòu)與算法設(shè)計(jì)課程教案（續(xù)頁(yè)）17教案（末頁(yè)）18復(fù)習(xí)思考題:推薦閱讀書(shū)目:數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)課程教案（續(xù)頁(yè)）19授課時(shí)間第周授課方式（請(qǐng)打V）講授上機(jī)實(shí)驗(yàn)/訓(xùn)其它課時(shí) 安排授課題目（章節(jié)或單位課時(shí)）：教學(xué)目的與要求（分了解、熟悉、掌握三個(gè)層次）：教學(xué)重點(diǎn)與難點(diǎn)：教 學(xué)內(nèi)容備注教案（末頁(yè)）20數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)課程教案（續(xù)頁(yè)）21復(fù)習(xí)思考題:推薦閱讀書(shū)目:教案（末頁(yè)）22授課時(shí)間第周授課方式（請(qǐng)打V）講授上機(jī)實(shí)驗(yàn)/訓(xùn)其它課時(shí) 安排授課題目（章節(jié)或單位課時(shí)）：教學(xué)目的與要求（分了解、熟悉、掌握三個(gè)層次）：教學(xué)重點(diǎn)與難點(diǎn)：教 學(xué)內(nèi)容備注數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)課程教案（續(xù)頁(yè)）23教案（末頁(yè)）24復(fù)習(xí)思

9、考題:推薦閱讀書(shū)目:數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)課程教案（續(xù)頁(yè)）25授課時(shí)間第周授課方式（請(qǐng)打V）講授上機(jī)實(shí)驗(yàn)/訓(xùn)其它課時(shí) 安排授課題目（章節(jié)或單位課時(shí)）：教學(xué)目的與要求（分了解、熟悉、掌握三個(gè)層次）：教學(xué)重點(diǎn)與難點(diǎn)：教 學(xué)內(nèi)容備注教案（末頁(yè)）26數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)課程教案（續(xù)頁(yè)）27復(fù)習(xí)思考題:推薦閱讀書(shū)目:教案（末頁(yè)）28授課時(shí)間第周授課方式（請(qǐng)打V）講授上機(jī)實(shí)驗(yàn)/訓(xùn)其它課時(shí) 安排授課題目（章節(jié)或單位課時(shí)）：教學(xué)目的與要求（分了解、熟悉、掌握三個(gè)層次）：教學(xué)重點(diǎn)與難點(diǎn)：教 學(xué)內(nèi)容備注數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)課程教案（續(xù)頁(yè)）29教案（末頁(yè)）30復(fù)習(xí)思考題:推薦閱讀書(shū)目:數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)課程教案（續(xù)頁(yè)）31

10、授課時(shí)間第周授課方式（請(qǐng)打V）講授上機(jī)實(shí)驗(yàn)/訓(xùn)其它課時(shí) 安排授課題目（章節(jié)或單位課時(shí)）：教學(xué)目的與要求（分了解、熟悉、掌握三個(gè)層次）：教學(xué)重點(diǎn)與難點(diǎn)：教 學(xué)內(nèi)容備注教案（末頁(yè)）32數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)課程教案（續(xù)頁(yè)）33復(fù)習(xí)思考題:推薦閱讀書(shū)目:教案（末頁(yè)）34授課時(shí)間第周授課方式（請(qǐng)打V）講授上機(jī)實(shí)驗(yàn)/訓(xùn)其它課時(shí) 安排授課題目（章節(jié)或單位課時(shí)）：教學(xué)目的與要求（分了解、熟悉、掌握三個(gè)層次）：教學(xué)重點(diǎn)與難點(diǎn)：教 學(xué)內(nèi)容備注數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)課程教案（續(xù)頁(yè)）35教案（末頁(yè)）36復(fù)習(xí)思考題:推薦閱讀書(shū)目:數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)課程教案（續(xù)頁(yè)）37授課時(shí)間第周授課方式（請(qǐng)打V）講授上機(jī)實(shí)驗(yàn)/訓(xùn)其它課時(shí) 安排授課題目（章節(jié)或單位課時(shí)）：教學(xué)目的與要求（分了解、熟悉、掌握三個(gè)層次）：教學(xué)重點(diǎn)與難點(diǎn)：教 學(xué)內(nèi)容備注教案（末頁(yè)）38數(shù)據(jù)結(jié)