教案課程名稱數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計課程代碼總學(xué)時64課程負責人任課教師

單元教案授課日期年月日—月日授課地點授課班級班級人數(shù)教學(xué)單元單元1緒論教學(xué)時數(shù)4教學(xué)目標AOB1:掌握計算機程序設(shè)計中的線性表、棧、隊列、樹和圖的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)。了解遞歸的數(shù)據(jù)邏輯組織結(jié)構(gòu)；AOB3:掌握對算法的科學(xué)分析方法。BOB1:能根據(jù)實際問題中的數(shù)據(jù)特性選擇適當?shù)臄?shù)據(jù)結(jié)構(gòu)；教學(xué)方式混合式教學(xué)評價方式課堂考勤（20%），課堂活動參與程度（30%）線上單元測試（50%）教學(xué)資源1.算法與數(shù)據(jù)結(jié)構(gòu)（Java語言描述），陳媛，清華大學(xué)大學(xué)出版社2.電腦50臺（含eclips）;3.網(wǎng)絡(luò)學(xué)習(xí)資源：/forums/ST_Arithmetic：課程平臺網(wǎng)址：/teacher/mainCourse/courseHome.html?courseOpenId=u3bwaoaqhzdgvlcf34d8ea單元教學(xué)設(shè)計第一次課（2學(xué)時）教學(xué)內(nèi)容課程介紹課程性質(zhì)：專業(yè)知識課程課程學(xué)習(xí)目標：掌握線性表、棧、隊列、樹和圖的數(shù)據(jù)邏輯組織結(jié)構(gòu)和數(shù)據(jù)存儲結(jié)構(gòu)，了解遞歸的數(shù)據(jù)邏輯組織結(jié)構(gòu)。掌握計算機程序設(shè)計中的線性表、棧、隊列、樹、圖的數(shù)據(jù)增、刪、改、查操作運算。了解遞歸的處理算法，掌握選擇與排序的處理算法。著力提高理論素養(yǎng)與解決實際問題的能力；基于所學(xué)理論知識，學(xué)會觀察問題、分析問題和解決問題，將理論知識熟練的運用于編程之中；增強思維能力和創(chuàng)新能力。企業(yè)崗位能力需求：能夠識別、分析、解決軟件編碼、軟件測試、軟件實施與維護等活動中的常見技術(shù)問題。具備終身學(xué)習(xí)意識和自主學(xué)習(xí)能力。1.1學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義計算機的作用數(shù)值計算問題：線性方程，微分方程，線性代數(shù)……非數(shù)值計算問題：電話號碼查詢，計算機對弈，城市間鋪設(shè)光纜，數(shù)據(jù)結(jié)構(gòu)的研究對象：非數(shù)值計算領(lǐng)域的程序設(shè)計問題問題的操作對象：操作對象之間的關(guān)系，在操作對象上面施加的操作算法＋數(shù)據(jù)結(jié)構(gòu)＝程序1.2數(shù)據(jù)結(jié)構(gòu)的基本概念數(shù)據(jù)(data)：信息的載體，是對客觀事物的符號表示，能夠被計算機識別、存儲和加工處理。圖像、聲音、視頻等都可通過編碼由計算機處理，因此也屬于數(shù)據(jù)的范疇數(shù)據(jù)元素(dataelement)：數(shù)據(jù)的基本單位,也稱為元素、結(jié)點或記錄。數(shù)據(jù)元素可由若干個數(shù)據(jù)項（字段、域）構(gòu)成，數(shù)據(jù)項是數(shù)據(jù)不可分割的最小單位數(shù)據(jù)對象：數(shù)據(jù)的子集，具有相同性質(zhì)的數(shù)據(jù)元素的集合數(shù)據(jù)的結(jié)構(gòu)：數(shù)據(jù)元素的集合中，元素相互之間的關(guān)系邏輯結(jié)構(gòu)：集合,線性結(jié)構(gòu),樹型結(jié)構(gòu),圖狀結(jié)構(gòu)物理結(jié)構(gòu)：順序，鏈接，索引，散列數(shù)據(jù)結(jié)構(gòu)的形式：Data_Structures=(D,S)D是數(shù)據(jù)元素的有限集，S是D上關(guān)系的有限集關(guān)系用序偶表示:<ai,aj>或(ai,aj)ai稱為前驅(qū)或弧尾，aj稱為后續(xù)或弧頭例：某公司有1名經(jīng)理(M)，2個部門經(jīng)理(D)，每個部門各有3名職員(E)。人員之間的關(guān)系是：經(jīng)理指導(dǎo)部門經(jīng)理的工作，部門經(jīng)理指導(dǎo)職員的工作。GROUP=(P，R)P={M，D1，D2，E11，E12，E13，E21，E22，E23}R={<M,D1>,<M,D2>,<D1,E11>,<D1,E12>…<D２,E23>}例：某公司有1名經(jīng)理，2個部門經(jīng)理，每個部門各有3名職員。人員之間的關(guān)系是：按人員年齡從大到小排列。GROUP=(P，R)P={M，D1，D2，E11，E12，E13，E21，E22，E23}R={<D1,M>,<M,E11>,<E11,E21>,<E21,E12>…<E22,E23>}例：某公司有1名經(jīng)理，2個部門經(jīng)理，每個部門各有3名職員。人員之間的關(guān)系是：人員之間的友好關(guān)系。GROUP=(P，R)P={M，D1，D2，E11，E12，E13，E21，E22，E23}R={(M,D1),(M,D2),(D1,D2),(D2,E12)…(D２,E22)}數(shù)據(jù)的存儲結(jié)構(gòu)：邏輯結(jié)構(gòu)在存儲器中的映象數(shù)據(jù)元素的存儲：用二進制位(bit)的位串表示數(shù)據(jù)元素關(guān)系的存儲順序存儲結(jié)構(gòu)：用元素之間存儲的相對位置表示關(guān)系鏈式存儲結(jié)構(gòu)：用存儲元素的引用（指針）表示關(guān)系教學(xué)重點數(shù)據(jù)結(jié)構(gòu)的基本概念教學(xué)難點數(shù)據(jù)結(jié)構(gòu)的基本概念教學(xué)流程教學(xué)環(huán)節(jié)教師活動學(xué)生活動講評和考勤（5分鐘）1平臺發(fā)布任務(wù)2考勤1考勤課程引入（10分鐘）課程介紹認真思考、記錄關(guān)鍵內(nèi)容講授和課堂練習(xí)（70分鐘）1.學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的意義（10分鐘）2.非數(shù)值結(jié)算舉例（15分鐘）3.數(shù)據(jù)結(jié)構(gòu)的基本概念（20分鐘）4．數(shù)據(jù)結(jié)構(gòu)的形式定義舉例。（15分鐘）5.數(shù)據(jù)的存儲結(jié)構(gòu)。（10分鐘）1.積極回答教師提問2.認真思考、記錄關(guān)鍵內(nèi)容3.積極參與課堂的討論和互動總結(jié)與發(fā)布課后任務(wù)（5分鐘）1.總結(jié)課堂內(nèi)容以及在練習(xí)過程中出現(xiàn)的，問題。2.布置課后任務(wù)1.思考教師總結(jié)2.記錄課后任務(wù)第二次課（2學(xué)時）教學(xué)內(nèi)容1.3算法算法(Algorithm)：對特定問題求解步驟的一種描述，是指令的有限序列算法的特性：可執(zhí)行性、有窮性、確定性、輸入、輸出算法的描述方法：自然語言、程序設(shè)計語言、類程序設(shè)計語言、流程圖算法的設(shè)計原則算法應(yīng)當滿足具體問題的需求正確性，四個層次：1.不含語法錯誤。2.對于幾組輸入數(shù)據(jù)能夠得出滿足要求的結(jié)果3.對于精心選擇的、典型、苛刻、帶有刁難性的幾組輸入數(shù)據(jù)，能夠得出滿足要求的結(jié)果。4.對于一切合法的輸入數(shù)據(jù)都能得出滿足要求的結(jié)果健壯性：當輸入數(shù)據(jù)非法時，算法能適當?shù)刈龀龇磻?yīng)，不會產(chǎn)生出錯的結(jié)果或信息，不會導(dǎo)致程序執(zhí)行終斷可讀性：算法要方便閱讀和交流評價算法的指標：執(zhí)行需要占用多少機器資源時間資源;算法運行時花費的時間代價空間資源:程序中使用的數(shù)據(jù)結(jié)構(gòu)占用的空間代價算法執(zhí)行時間相關(guān)的因素事后統(tǒng)計法事前估算法:算法的策略、問題的規(guī)模、書寫程序的語言、編譯程序產(chǎn)生的機器代碼的質(zhì)量、機器執(zhí)行指令的速度算法的時間復(fù)雜性分析算法耗費的時間：1.算法中所有語句執(zhí)行時間之和。2.語句的執(zhí)行時間：該語句的頻度(語句重復(fù)執(zhí)行的次數(shù))，與該語句執(zhí)行一次所需時間的乘積。算法時間取決于控制結(jié)構(gòu)和原操作的綜合效果f(n)是算法中頻度最大的語句頻度，通常是最深層循環(huán)內(nèi)的原操作執(zhí)行的次數(shù)。隨著n的增長，算法執(zhí)行時間的增長率和f(n)的增長率相同。算法時間復(fù)雜度記作：T(n)=O(f(n))舉例：課堂練習(xí)：常見函數(shù)比較：通常有如下的函數(shù)關(guān)系：c<log2n<n<nlog2n<n2<n3<2n指數(shù)時間的關(guān)系為：O(2n)<O(n!)<O(nn)算法的時間復(fù)雜度不僅是問題規(guī)模n的函數(shù)，還與所處理的數(shù)據(jù)集有關(guān)。全面分析算法，需考慮它在最壞情況下的代價、最好情況下的代價和平均情況下的代價。算法的空間復(fù)雜度：S(n)=O(g(n))隨著問題規(guī)模n的增大，算法運行所需存儲量的增長率與g(n)的增長率相同算法所需的存儲量：輸入數(shù)據(jù)所占空間，程序本身所占空間，輔助變量所占空間教學(xué)重點算法教學(xué)難點時間復(fù)雜度分析教學(xué)流程教學(xué)環(huán)節(jié)教師活動學(xué)生活動考勤（5分鐘）1.考勤1.考勤講授和課堂練習(xí)（80分鐘）1.算法的概念（10分鐘）2.算法的設(shè)計原則（10分鐘）3.評價算法的指標（10分鐘）4.算法的時間復(fù)雜性分析（20分鐘）5.算法的時間復(fù)雜性分析課堂練習(xí)（20分鐘）6.算法的空間復(fù)雜度（10分鐘）1.積極回答教師提問2.認真思考、記錄關(guān)鍵內(nèi)容3.積極參與課堂的討論和互動4.積極完成課堂練習(xí)總結(jié)與發(fā)布課后任務(wù)（5分鐘）1.總結(jié)本次課程內(nèi)容；2.布置課后任務(wù)1.思考教師總結(jié)，2.記錄教師的任務(wù)要求并在課后完成。教學(xué)效果與反思根據(jù)單元測驗結(jié)果，90%的學(xué)生教好掌握了教學(xué)內(nèi)容，達成了單