《數(shù)據(jù)結(jié)構(gòu)與算法》理論教案

1-教案講授章節(jié)第1講概述授課時數(shù)2教學(xué)目的：1.了解數(shù)據(jù)結(jié)構(gòu)課程的重要性和課程的基本要求，以及本課程涵蓋的內(nèi)容；2.掌握數(shù)據(jù)結(jié)構(gòu)的基本概念；3.理解算法描述和簡單的算法分析。教學(xué)內(nèi)容（講授提綱）一.課前導(dǎo)學(xué)（線上）1.閱讀：導(dǎo)學(xué)通知、課程介紹、學(xué)習(xí)方法、校內(nèi)SPOC使用方法、本章節(jié)知識點等2.觀看導(dǎo)學(xué)視頻3.論壇討論、反饋疑難點二.課堂教學(xué)1.介紹課程重要性和意義，以及學(xué)習(xí)目標(biāo)等2.什么是數(shù)據(jù)結(jié)構(gòu)2.1通過“中國軟件和信息技術(shù)服務(wù)業(yè)現(xiàn)狀”、“排隊候車”等案例介紹線性結(jié)構(gòu)。表1中國軟件和信息技術(shù)服務(wù)業(yè)現(xiàn)狀年份軟件業(yè)收入統(tǒng)計（億元）人均創(chuàng)收（億元）軟件從業(yè)人員數(shù)統(tǒng)計（萬人）20154284874.657420164823282.358620175510389.261820186190995.0645201971768106.6673圖1軍人排隊候車2.2通過“早期華為組織結(jié)構(gòu)圖”、“族譜”等案例介紹樹形結(jié)構(gòu)圖2華為早期的管理組織結(jié)構(gòu)圖圖3族譜2.3通過“高速鐵路網(wǎng)”、“哥尼斯堡七橋問題”介紹圖形結(jié)構(gòu)圖4我國“四縱四橫”高速鐵路網(wǎng)圖5哥尼斯堡七橋問題討論：歐拉回路存在的充分必要條件是：（1）圖是連通的；（2）圖中與每個頂點相連的邊數(shù)（即頂點度數(shù)）必須是偶數(shù)。3.基本概念和術(shù)語3.1介紹數(shù)據(jù)（Data）、數(shù)據(jù)元素（DataElement）、數(shù)據(jù)項（DataItem）、數(shù)據(jù)對象（DataObject）、抽象數(shù)據(jù)類型（AbstractDataType）、數(shù)據(jù)結(jié)構(gòu)三個要素。3.2課堂練習(xí)(1)在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以將之分為()?！局心洗髮W(xué)】A．動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B．緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)D．線性結(jié)構(gòu)和非線性結(jié)構(gòu)(2)己知表頭元素為c的單鏈表在內(nèi)存中的存儲狀態(tài)如下表所示?！?012全國統(tǒng)考408】地址元素鏈接地址1000Ha1010H1004Hb100CH1008Hc1000H100CHdNULL1010He1004H1014H現(xiàn)將f放于1014H處并插入到單鏈表中，若f在邏輯上位a和e之間，則a，e，f的鏈接地址”依次是()。A．1010H,1014H,1004H B．1010H,1004H,1014HC．1014H,1010H,1004H D．1014H,1004H,1010H4．算法和算法分析4.1介紹算法的定義、特性、設(shè)計要求及算法效率的衡量方法。4.2“百錢買百雞”問題討論+翻轉(zhuǎn)：我國古代數(shù)學(xué)家張丘建在《算經(jīng)》一書中曾提出過著名的百錢買百雞問題，小組討論“百錢買百雞”算法思路，開展翻轉(zhuǎn)課堂活動，最后教師總結(jié)算法的重要性。4.3引導(dǎo)學(xué)生歸納總結(jié)各種常見階數(shù)時間復(fù)雜度4.4課堂練習(xí)(1)求整數(shù)n(n>=0)階乘的算法如下，其時間復(fù)雜度是()?！?012全國統(tǒng)考408】intfact(intn){if(n<=1)return1;returnn*fact(n-1);}A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2)(2)下列程序段的時間復(fù)雜度()?！?014全國統(tǒng)考408】count=0;for(k=1;k<=n;k*=2)for(j=1;j<=n;j+=1)count++;A．O(log2n) B．O(n) C．O(nlog2n) D．O(n2)(3)下列函數(shù)的時間復(fù)雜度()。【2017全國統(tǒng)考408】intfunc(intn){inti=0,sum=0;while(sum<n)sum+=++i;returni;}A．O(log2n) B．O(n1/2) C．O(n) D．O(nlog2n)三.課后鞏固（線上）課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點測試。本章節(jié)的教學(xué)重點、難點：1.重點是數(shù)據(jù)結(jié)構(gòu)的基本概念2.難點是時間復(fù)雜度的分析教學(xué)方法、教學(xué)手段：1.介紹數(shù)據(jù)結(jié)構(gòu)與算法概念和術(shù)語（45分鐘）2.算法分析和舉例（45分鐘）3.使用教具：計算機和投影儀；4.輔助教學(xué)：雨課堂、校內(nèi)SPOC、“百科園”、學(xué)堂在線MOOC、算法演示動畫；5.課前觀看導(dǎo)學(xué)視頻；課中案例展開，應(yīng)用翻轉(zhuǎn)課堂、項目驅(qū)動以及實踐教學(xué)法；課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點在線測試。作業(yè)、討論題、思考題：說明：所有作業(yè)和實驗無紙化，提交至網(wǎng)絡(luò)教學(xué)平臺；測驗使用“百科園”考試系統(tǒng)。(1)課后作業(yè)：已知輸入x，y，z三個不相等的整數(shù)，設(shè)計一個“高效”算法，使得這三個數(shù)按從小到大輸出?！案咝А钡暮x是用最少的元素比較次數(shù)、元素移動次數(shù)和輸出次數(shù)。(2)編程求解數(shù)組中最大連續(xù)子序列之和，并分析算法的時間復(fù)雜度。提示：該問題有多種解法，應(yīng)用窮舉法時間復(fù)雜度較高為O(n3)，而時間復(fù)雜度最低能達(dá)到O(n)。(3)討論：數(shù)據(jù)的邏輯結(jié)構(gòu)與存儲結(jié)構(gòu)是一一對應(yīng)的嗎？請舉例說明。參考資料：1．馮廣慧,吳昊,文全剛.算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）[M].電子工業(yè)出版社,20192．陳守孔,胡瀟琨,李玲,馮廣慧.算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析（第四版）[M].機械工業(yè)出版社,2020

教案講授章節(jié)第2講線性表、順序表授課時數(shù)2教學(xué)目的：1.理解非空線性結(jié)構(gòu)的四個特征。2.線性表是重要的線性結(jié)構(gòu)，要掌握線性表的定義。3.掌握線性表的操作在順序表中的實現(xiàn)。教學(xué)內(nèi)容（講授提綱）一.課前導(dǎo)學(xué)（線上）1.觀看導(dǎo)學(xué)視頻2.論壇討論、反饋疑難點二.課堂教學(xué)1.通過中國軟件和信息技術(shù)服務(wù)業(yè)現(xiàn)狀統(tǒng)計表，引入線性結(jié)構(gòu)學(xué)習(xí)，總結(jié)非空線性結(jié)構(gòu)的四個特征年份軟件業(yè)收入統(tǒng)計（億元）人均創(chuàng)收（億元）軟件從業(yè)人員數(shù)統(tǒng)計（萬人）20154284874.657420164823282.358620175510389.261820186190995.0645201971768106.66732.線性表的概念3.線性表的抽象數(shù)據(jù)類型4.給定線性表的邏輯結(jié)構(gòu)設(shè)計算法（1）遍歷線性表L（2）合并線性表1:設(shè)La和Lb是元素屬于同一數(shù)據(jù)對象且非遞減有序的兩個線性表，現(xiàn)要求將兩個線性表合并成一個新的非遞減有序的線性表Lc。（3）合并線性表2:設(shè)La和Lb是元素屬于同一數(shù)據(jù)對象的兩個線性表，試將線性表Lb合并到線性表La中。要求Lb中元素和La中元素相同的不再合并。要分析為什么（2）和（3）的時間復(fù)雜度分別是O(m*n)和O(m+n)。5.線性表的順序表示及類型定義6.順序表上基本運算的實現(xiàn)（1）構(gòu)造一個空順序表；（2）拷貝構(gòu)造函數(shù)；（3）遍歷順序表；（4）查找元素；（5）求前驅(qū)和后繼；（6）插入運算；（7）刪除運算；（8）逆置運算；（9）擴大表空間；重點分析在插入和刪除操作中的時間復(fù)雜度。7.算法設(shè)計舉例（1）順序結(jié)構(gòu)線性表LA與LB的結(jié)點關(guān)鍵字為整數(shù)。LA與LB的元素按非遞減有序，線性表空間足夠大。試給出一種高效算法，將LB中元素合到LA中，使新的LA的元素仍保持非遞減有序。高效指最大限度的避免移動元素。（2）【北京航空航天大學(xué)】已知長度為n的線性表A采用順序存儲結(jié)構(gòu)，請寫一時間復(fù)雜度為0(n)、空間復(fù)雜度為0(1)的算法，該算法刪除線性表中所有值為item的數(shù)據(jù)元素。(O(1)表示算法的輔助空間為常量）。（3）【2010全國統(tǒng)考408】設(shè)將n（n>1）個整數(shù)存放到一維數(shù)組R中。試設(shè)計一個在時間和空間兩方面都盡可能高效的算法，將R中保存的序列循環(huán)左移P（0<P<n）個位置，即將R中的數(shù)據(jù)由（X0,X1,…,Xn-1）變換為（Xp,Xp+1,…,Xn-1,X0,X1,…,Xp-1）。要求：a）給出算法的基本設(shè)計思想。b）采用C或C++或JAVA語言描述算法c）說明算法的時間復(fù)雜度和空間復(fù)雜度。d）討論：若采用直接左移p位，空間復(fù)雜度仍為O(1)，但時間復(fù)雜度為O(np)。三.課后鞏固（線上）課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點測試。本章節(jié)的教學(xué)重點、難點：1.重點是順序表的定義，基本操作的實現(xiàn)。2.難點是高效算法設(shè)計，例如國家2010年碩士研究生入學(xué)考試算法題就有5種解法教學(xué)方法、教學(xué)手段：1.線性表和順序表的概念和類型定義（30分鐘）2.順序表上基本運算的實現(xiàn)（30分鐘）3.順序表算法舉例（30分鐘）4.使用教具：計算機和投影儀；5.輔助教學(xué)：雨課堂、校內(nèi)SPOC、“百科園”在線考試系統(tǒng)、學(xué)堂在線MOOC、算法演示動畫；6.課前觀看導(dǎo)學(xué)視頻；課中案例展開，應(yīng)用翻轉(zhuǎn)課堂、項目驅(qū)動以及實踐教學(xué)法；課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點在線測試。作業(yè)、討論題、思考題：1.分析在順序存儲結(jié)構(gòu)下插入和刪除結(jié)點時平均需要移動多少個結(jié)點。2.順序表la與lb非遞減有序，順序表空間足夠大。試設(shè)計一種高效算法，將lb中元素合到la中，使新的la的元素仍保持非遞減有序。高效指最大限度地避免移動元素。改為:順序表la非遞減有序，lb非遞增有序，求解該問題。參考資料：1．馮廣慧,吳昊,文全剛.算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）[M].電子工業(yè)出版社,20192．陳守孔,胡瀟琨,李玲,馮廣慧.算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析（第四版）[M].機械工業(yè)出版社,2020

教案講授章節(jié)第3講單鏈表授課時數(shù)2教學(xué)目的：1.掌握鏈表的類型定義和基本操作的實現(xiàn)。2.掌握單鏈表的建立方法，特別是頭插法和尾插法。3.了解單鏈表的應(yīng)用。教學(xué)內(nèi)容（講授提綱）一.課前導(dǎo)學(xué)（線上）1.觀看導(dǎo)學(xué)視頻2.論壇討論、反饋疑難點二.課堂教學(xué)1從順序存儲結(jié)構(gòu)的優(yōu)缺點，引出鏈表的必要性插入和刪除必須大量移動元素；必須預(yù)先確定空間；表空間不易擴充。2.鏈表的類型定義幾個概念：結(jié)點，首元結(jié)點，第一元素結(jié)點，頭結(jié)點，指針，頭指針3.線性表的操作在單鏈表中的實現(xiàn)（1）單鏈表的初始化；（2）清空單鏈表；（3）求表長；（4）遍歷鏈表；（5）查找位序為i的元素的地址；（6）查找值為value的元素的位序；（7）查找值為value的元素的前驅(qū)；（8）求某元素的后繼；（9）插入元素；（10）刪除元素。4.單鏈表的建立方法（特別是頭插法和尾插法）（1）頭插法；（2）尾插法。5.算法設(shè)計舉例（1）【2012全國統(tǒng)考408】假定采用帶頭結(jié)點的單鏈表保存單詞，當(dāng)兩個單詞有相同的后綴時，則可共享相同的后綴存儲空間。例如，“l(fā)oading”和“being”的存儲映像如下圖所示。設(shè)str1和str2分別指向兩個單詞所在單鏈表的頭結(jié)點，鏈表結(jié)點結(jié)構(gòu)為（data，next）請設(shè)計一個時間上盡可能高效的算法，找出由str1和str2所指的兩個鏈表共同后綴的起始位置（如圖中字符i所在結(jié)點的位置p）。要求：a）給出算法的基本設(shè)計思想。b）根據(jù)設(shè)計思想，采用C或C++或JAVA語音描述算法，關(guān)鍵之處給出注釋。c）說明你所設(shè)計算法的時間復(fù)雜度。（2）【2009全國統(tǒng)考408】已知一個帶有表頭結(jié)點的單鏈表，結(jié)點結(jié)構(gòu)為(data,link)，假設(shè)該鏈表只給出了頭指針list。在不改變鏈表的前提下，請設(shè)計一個盡可能高效的算法，查找鏈表中倒數(shù)第k個位置上的結(jié)點（k為正整數(shù)），若查找成功，算法輸出該結(jié)點的data域的值，并返回1；否則，只返回0，要求：a）描述算法的基本設(shè)計思想；b）描述算法的詳細(xì)實現(xiàn)步驟；c）根據(jù)設(shè)計思想和實現(xiàn)步驟，采用程序設(shè)計語言描述算法（使用C或C++或JAVA語言實現(xiàn)），關(guān)鍵之處請給出簡要注釋。三.課后鞏固（線上）課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點測試。本章節(jié)的教學(xué)重點、難點：1．動態(tài)存儲（單鏈表）的概念。2．單鏈表的算法設(shè)計。教學(xué)方法、教學(xué)手段：1．鏈表的定義和基本操作的實現(xiàn)（45分鐘）2．鏈表生成和鏈表應(yīng)用的算法設(shè)計（45分鐘）3．使用教具：計算機和投影儀；4．輔助教學(xué)：雨課堂、校內(nèi)SPOC、“百科園”在線考試系統(tǒng)、學(xué)堂在線MOOC、算法演示動畫；5．課前觀看導(dǎo)學(xué)視頻；課中案例展開，應(yīng)用翻轉(zhuǎn)課堂、項目驅(qū)動以及實踐教學(xué)法；課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點在線測試。作業(yè)、討論題、思考題：1.試述頭指針、頭結(jié)點、元素結(jié)點、首元結(jié)點的區(qū)別，說明頭指針和頭結(jié)點的作用。2.分析順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點，說明何時應(yīng)該利用何種結(jié)構(gòu)。3.為什么在單循環(huán)鏈表中常使用尾指針，若只設(shè)頭指針，插入元素的時間復(fù)雜度如何？4.在單鏈表、雙鏈表、單循環(huán)鏈表中，若知道指針p指向某結(jié)點，能否刪除該結(jié)點，時間復(fù)雜度如何？5.設(shè)ha和hb分別是兩個帶頭結(jié)點的非遞減有序單鏈表的頭指針，試設(shè)計算法，將這兩個有序鏈表合并成一個非遞增有序的單鏈表。要求使用原鏈表空間，表中無重復(fù)數(shù)據(jù)。改：設(shè)ha和hb分別是兩個帶頭結(jié)點的非遞減有序單鏈表的頭指針，試設(shè)計算法，將這兩個有序鏈表合并成一個非遞減有序的單鏈表。要求使用原鏈表空間，表中無重復(fù)數(shù)據(jù)。參考資料：1．馮廣慧,吳昊,文全剛.算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）[M].電子工業(yè)出版社,20192．陳守孔,胡瀟琨,李玲,馮廣慧.算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析（第四版）[M].機械工業(yè)出版社,20203．翁惠玉,俞勇.數(shù)據(jù)結(jié)構(gòu)：思想與實現(xiàn),高等教育出版社[M].高等教育出版社,2018

教案講授章節(jié)第4講循環(huán)鏈表、雙鏈表授課時數(shù)2教學(xué)目的：1.掌握循環(huán)鏈表引入的背景：從任一結(jié)點開始可以訪問鏈表中的全部結(jié)點。2.掌握循環(huán)鏈表（單循環(huán)鏈表，雙循環(huán)鏈表）和雙鏈表。教學(xué)內(nèi)容（講授提綱）一.課前導(dǎo)學(xué)（線上）1.觀看導(dǎo)學(xué)視頻2.論壇討論、反饋疑難點二.課堂教學(xué)1．比較順序表和單鏈表操作的優(yōu)缺點，使用范圍2．介紹單循環(huán)鏈表。指出：單循環(huán)鏈表往往只設(shè)尾指針3．講解兩個只設(shè)尾指針的單循環(huán)鏈表合并成一個單循環(huán)鏈表的例子4．雙鏈表的定義為深刻的理解雙鏈表，展開討論：p->prior->next==?;P->next->prior==?;引導(dǎo)學(xué)生理解雙鏈表的特點：p->prior->next==P->next->prior==p;注意區(qū)分雙鏈表和雙循環(huán)鏈表是兩種鏈表。5．線性表的操作在雙鏈表中的實現(xiàn)凡涉及一個方向的指針時，如求長度，取元素，元素定位等，其算法描述和單鏈表基本相同。但是在插入或刪除結(jié)點時，一個結(jié)點就要修改兩個指針域，所以要比單鏈表復(fù)雜。由于雙鏈表有兩個指針域，求前驅(qū)和后繼都很方便。s->prior=p->prior;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;p->prior->next=p->next;p->next->prior=p->prior;deletep;6.算法設(shè)計舉例（1）將單循環(huán)鏈表改為雙循環(huán)鏈表。假設(shè)一個單循環(huán)鏈表，其結(jié)點含有三個域pre、data、next。其中data為數(shù)據(jù)域；pre為指針域，它的值為空指針（null）；next為指針域，它指向后繼結(jié)點。請設(shè)計算法，將此表改成雙向循環(huán)鏈表。（2）已知一雙向循環(huán)鏈表，從第二個結(jié)點至表尾遞增有序，（設(shè)a1<x<an）。試編寫算法，將第一個結(jié)點刪除并插入表中適當(dāng)位置，使整個鏈表遞增有序。（3）【2015全國統(tǒng)考408】用單鏈表保存m個整數(shù)，節(jié)點的結(jié)構(gòu)為(data,link)，且|data|<n(n為正整數(shù))?，F(xiàn)要求設(shè)計一個時間復(fù)雜度盡可能高效地算法，對于鏈表中絕對值相等的節(jié)點，僅保留第一次出現(xiàn)的節(jié)點而刪除其余絕對值相等的節(jié)點。例如若給定的單鏈表head如下。刪除后三.課后鞏固（線上）課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點測試。本章節(jié)的教學(xué)重點、難點：1.循環(huán)鏈表和雙鏈表的概念。2.難點是循環(huán)鏈表和雙鏈表的應(yīng)用算法設(shè)計。教學(xué)方法、教學(xué)手段：1．循環(huán)鏈表和雙鏈表（45分鐘）2．算法設(shè)計（45分鐘）3．使用教具：計算機和投影儀；4．輔助教學(xué)：雨課堂、校內(nèi)SPOC、“百科園”在線考試系統(tǒng)、學(xué)堂在線MOOC、算法演示動畫；5．課前觀看導(dǎo)學(xué)視頻；課中案例展開，應(yīng)用翻轉(zhuǎn)課堂、項目驅(qū)動以及實踐教學(xué)法；課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點在線測試。作業(yè)、討論題、思考題：1.設(shè)la是一個雙向循環(huán)鏈表，其表中元素遞增有序。試寫一算法插入元素x，使表中元素依然遞增有序。改為：設(shè)la是一個雙向循環(huán)鏈表，其表中元素遞減有序。試寫一算法插入元素x，使表中元素依然遞減有序。2.設(shè)計一算法，將一個用循環(huán)鏈表表示的稀疏多項式分解成兩個多項式，使這兩個多項式各自僅有奇次冪或偶次冪項，并要求利用原鏈表中的結(jié)點空間來構(gòu)造這兩個鏈表。參考資料：1．馮廣慧,吳昊,文全剛.算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）[M].電子工業(yè)出版社,20192．陳守孔,胡瀟琨,李玲,馮廣慧.算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析（第四版）[M].機械工業(yè)出版社,20203．翁惠玉,俞勇.數(shù)據(jù)結(jié)構(gòu)：思想與實現(xiàn),高等教育出版社[M].高等教育出版社,2018

教案講授章節(jié)第5講棧授課時數(shù)2教學(xué)目的：1理解棧和隊列仍屬于線性結(jié)構(gòu)，其操作是線性表操作的子集，是操作受限的線性表。但從數(shù)據(jù)類型的角度看，它們是和線性表大不相同的重要抽象數(shù)據(jù)類型。2.掌握棧的定義及操作。棧是只準(zhǔn)在一端進行插入和刪除操作的線性表，該端稱為棧的頂端。3.掌握棧的順序和鏈?zhǔn)酱鎯Y(jié)構(gòu)，及在這兩種結(jié)構(gòu)下實現(xiàn)棧的操作。4.棧的應(yīng)用：表達(dá)式求值。教學(xué)內(nèi)容（講授提綱）一.課前導(dǎo)學(xué)（線上）1.觀看導(dǎo)學(xué)視頻2.論壇討論、反饋疑難點二.課堂教學(xué)1．棧的基本概念：棧、棧頂、棧尾，棧只在棧頂操作。2．棧的抽象數(shù)據(jù)類型定義3．順序棧及棧的操作在順序棧中的實現(xiàn)4．鏈棧及棧的操作在順序棧中的實現(xiàn)5．課堂練習(xí)（1）【2010全國統(tǒng)考408】若元素a，b，c，d，e，f依次進棧，允許進棧、退棧操作交替進行，但不允許連續(xù)三次進行退棧操作，則不可能得到的出棧序列是（）。A.d,c,e,b,f,aB.c,b,d,a,e,fC.b,c,a,e,f,dD.a,f,e,d,c,b（2）【2013全國統(tǒng)考408】一個棧的入棧序列為1,2,3,…,n，其出棧序列是p1,p2,p3…pn。若p2為3，則p3可能取值的個數(shù)是（）。A.n-3B.n-2C.n-1D.無法確定6．棧的應(yīng)用（1）過程調(diào)用（2）消除遞歸（3）使用棧進行數(shù)制轉(zhuǎn)換（4）中綴表達(dá)式的求值算術(shù)表達(dá)式中運算符(+,-,*,/等)的優(yōu)先規(guī)則設(shè)置兩個工作棧：運算符棧S1和操作數(shù)棧S2。S2存放表達(dá)式的運算結(jié)果。算法思想：1首先置操作數(shù)棧S2為空棧，置運算符棧的棧底為表達(dá)式的起始符#(優(yōu)先級最低)。2依次讀入表達(dá)式的每個字符ch,直至表達(dá)式結(jié)束：若ch是操作數(shù),則進S2棧；若ch是運算符，若其優(yōu)先級不高于棧頂運算符的優(yōu)先級時，則取出棧S2的棧頂和次棧頂?shù)膬蓚€元素以及棧S1的棧頂運算符，進行相應(yīng)的運算，并將結(jié)果放入棧S2中；如此下去，直至ch的優(yōu)先級高于棧頂運算符的優(yōu)先級，將ch入S1棧。三.課后鞏固（線上）課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點測試。本章節(jié)的教學(xué)重點、難點：1．重點是棧的概念和基礎(chǔ)知識。2．難點：中綴表達(dá)式求值。教學(xué)方法、教學(xué)手段：1．棧的基本概念和順序棧（45分鐘）2．鏈棧、中綴表達(dá)式求值（45分鐘）3．使用教具：計算機和投影儀；4．輔助教學(xué)：雨課堂、校內(nèi)SPOC、“百科園”、學(xué)堂在線MOOC、算法演示動畫；5．課前觀看導(dǎo)學(xué)視頻；課中案例展開，應(yīng)用翻轉(zhuǎn)課堂、項目驅(qū)動以及實踐教學(xué)法；課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點在線測試。作業(yè)、討論題、思考題：1.有五個數(shù)依次進棧：1、2、3、4、5。在各種出棧的序列中以3、4先出的序列有哪幾個。2.鐵路進行列車調(diào)度時，常把站臺設(shè)計成棧式結(jié)構(gòu)，若進站的六輛列車順序為：1，2，3，4，5，6，那么是否能夠得到435612，325641，154623和135426的出站序列，如果不能，說明為什么不能；如果能，說明如何得到(即寫出"進棧"或"出棧"的序列)。3.設(shè)稱正讀和反讀都相同的字符序列為“回文”，例如，“abba“和“abccba”是“回文”，“abcde”和“ababab”則不是“回文“，試寫一個算法，判別讀入的一個以@為結(jié)束符的字符序列是否是“回文”。參考資料：1．馮廣慧,吳昊,文全剛.算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）[M].電子工業(yè)出版社,20192．陳守孔,胡瀟琨,李玲,馮廣慧.算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析[M].機械工業(yè)出版社,2020教案講授章節(jié)第6講棧的應(yīng)用授課時數(shù)2教學(xué)目的：1.掌握棧的定義的本質(zhì)：LIFO。棧是只準(zhǔn)在一端進行插入和刪除操作的線性表，該端稱為棧的頂端。2.掌握棧的應(yīng)用：中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式，并求值。3.掌握遞歸過程的應(yīng)用。教學(xué)內(nèi)容（講授提綱）一.課前導(dǎo)學(xué)（線上）1.觀看導(dǎo)學(xué)視頻2.論壇討論、反饋疑難點二.課堂教學(xué)本次課繼續(xù)學(xué)習(xí)棧的應(yīng)用。1.中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式（1）算法思想及實現(xiàn)（2）舉例：中綴表達(dá)式12*(6/2-0.5)轉(zhuǎn)為后綴表達(dá)式（3）介紹中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式的簡單方法2．課堂練習(xí)（1）【2012全國統(tǒng)考408】已知操作符包括‘+’，‘-’，‘*’，‘/’，‘(’和‘)’。將中綴表達(dá)式a+b-a*((c+d)/e-f)+g轉(zhuǎn)換為等價的后綴表達(dá)式ab+acd+e/f-*-g+時，用棧來存放暫時還不能確定運算次序的操作符。若棧初始時為空，則轉(zhuǎn)換過程中同時保存在棧中的操作符的最大個數(shù)是()。A．5 B．7 C．8 D．11（2）【2014全國統(tǒng)考408】假設(shè)棧初始為空，將中綴表達(dá)式a/b+(c*d-e*f)/g轉(zhuǎn)換為等價的后綴表達(dá)式的過程中，當(dāng)掃描到f時，棧中的元素依次是()。A．+(*- B．+(-* C．/+(*-* D．/+-*3.后綴表達(dá)式求值（1）算法思想及實現(xiàn)（2）舉例：后綴表達(dá)式1262/0.5-*求值4.遞歸：若在一個函數(shù)、過程或者數(shù)據(jù)結(jié)構(gòu)定義的內(nèi)部，直接（或間接）出現(xiàn)定義本身的應(yīng)用，則稱它們是遞歸的，或者是遞歸定義的。5.遞歸過程的應(yīng)用問題的定義是遞歸的：f(n)=n*f(n-1)數(shù)據(jù)結(jié)構(gòu)是遞歸的：鏈表問題的解法是遞歸的：Hanoi塔問題6.遞歸算法的優(yōu)缺點7.遞歸的消除（1）采用迭代算法（2）尾遞歸的消除（3）利用棧消除任何遞歸三.課后鞏固（線上）課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點測試。本章節(jié)的教學(xué)重點、難點：1．中綴表達(dá)式轉(zhuǎn)成前綴、后綴表達(dá)式，并對兩種表達(dá)式求值。2．用遞歸解決的問題：問題的定義是遞歸的，數(shù)據(jù)結(jié)構(gòu)是遞歸的，以及問題的解法是遞歸的，掌握典型問題的算法。將遞歸算法轉(zhuǎn)為非遞歸算法，特別是尾遞歸的消除。教學(xué)方法、教學(xué)手段：1．復(fù)習(xí)棧的基本概念、中綴表達(dá)式轉(zhuǎn)為后綴表達(dá)式并求值（45分鐘）2．遞歸過程、消除遞歸（45分鐘）3．使用教具：計算機和投影儀；4．輔助教學(xué)：雨課堂、校內(nèi)SPOC、“百科園”在線考試系統(tǒng)、學(xué)堂在線MOOC、算法演示動畫；5．課前觀看導(dǎo)學(xué)視頻；課中案例展開，應(yīng)用翻轉(zhuǎn)課堂、項目驅(qū)動以及實踐教學(xué)法；課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點在線測試。作業(yè)、討論題、思考題：1.寫出下列中綴表達(dá)式的后綴表達(dá)式：(1)A*B*C(2)(A+B)*C-D (3)A*B+C/(D-E) (4)(A+B)*D+E/(F+A*D)+C2.選擇題：4個園盤的Hahoi塔，總的移動次數(shù)為()。A.7B.8C.15D.163.已知Ackerman函數(shù)定義如下，試寫出遞歸算法。Akm(m，n)=4.整數(shù)序列a1，a2，…，an，給出求解最大值的遞歸程序。參考資料：1．馮廣慧,吳昊,文全剛.算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）[M].電子工業(yè)出版社,20192．陳守孔,胡瀟琨,李玲,馮廣慧.算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析（第四版）[M].機械工業(yè)出版社,20203．翁惠玉,俞勇.數(shù)據(jù)結(jié)構(gòu)：思想與實現(xiàn),高等教育出版社[M].高等教育出版社,2018

教案講授章節(jié)第7講隊列授課時數(shù)2教學(xué)目的：1.隊列的基本概念和算法，其本質(zhì)是：FIFO。2.掌握鏈隊列空的條件是首尾指針相等，而循環(huán)隊列滿的條件的判定，則有犧牲一個單元和設(shè)標(biāo)記等方法。3.棧和隊列的綜合應(yīng)用教學(xué)內(nèi)容（講授提綱）一.課前導(dǎo)學(xué)（線上）1.觀看導(dǎo)學(xué)視頻2.論壇討論、反饋疑難點二.課堂教學(xué)1．隊列的基本概念和術(shù)語，其本質(zhì)是：FIFO。2．隊列的類型定義3.隊列的順序表示和實現(xiàn)，重點講解循環(huán)隊列提出問題－產(chǎn)生矛盾－解決矛盾：順序隊列的假溢出－循環(huán)隊列－隊頭隊尾相等時是滿和空的判斷。循環(huán)隊列的入隊、出隊、求隊列元素個數(shù)等操作中，都要注意取模操作。4．隊列的鏈?zhǔn)奖硎竞蛯崿F(xiàn)5．課堂練習(xí)【2014全國統(tǒng)考408】循環(huán)隊列存放在一維數(shù)組A[0..M-1]中，end1指向隊頭元素，end2指向隊尾元素的后一個位置。假設(shè)隊列兩端均可進行入隊和出隊操作，隊列中最多能容納M－1個元素，初始時為空。下列判斷隊空和隊滿的條件中，正確的是（）。A．隊空：end1==end2;隊滿end1==(end2+1)modMB．隊空：end1==end2;隊滿：end2==(end1+1)mod(M-1)C．隊空：end2==(end1+1)modM;隊滿：end1==(end2+1)modMD．隊空：end1==(end2+1)modM;隊滿：end2==(end1+1)mod(M-1)6．算法設(shè)計舉例（1）假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾結(jié)點，不設(shè)頭指針，試設(shè)計相應(yīng)的入隊列和出隊列的算法（2）要求完全利用循環(huán)隊列中的元素空間，設(shè)置一個標(biāo)志域tag，并以tag的值是0或１來區(qū)分尾指針和頭指針相同時的隊列狀態(tài)是“空”還是“不空”。請編寫與此結(jié)構(gòu)相對應(yīng)的入隊和出隊的算法。（3）請利用兩個棧S1和S2來模擬一個隊列。【上海交通大學(xué)】【廈門大學(xué)】三.課后鞏固（線上）課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點測試。本章節(jié)的教學(xué)重點、難點：1．隊列的概念，循環(huán)隊列和鏈隊列操作的實現(xiàn)。2．循環(huán)隊列中隊列空用隊頭指針等于隊尾指針來判斷，隊列滿則可用犧牲一個單元及設(shè)標(biāo)記等方法。這里特別注意入隊、出隊和求元素個數(shù)等操作中的取模運算。3．難點是棧和隊列的綜合運用教學(xué)方法、教學(xué)手段：1．隊列的基本概念、循環(huán)隊列（45分鐘）2．鏈隊列（20分鐘）3．算法設(shè)計舉例（25分鐘）4．使用教具：計算機和投影儀；5．輔助教學(xué)：雨課堂、校內(nèi)SPOC、百科園、學(xué)堂在線MOOC、算法演示動畫；6．課前觀看導(dǎo)學(xué)視頻；課中案例展開，應(yīng)用翻轉(zhuǎn)課堂、項目驅(qū)動以及實踐教學(xué)法；課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點在線測試。作業(yè)、討論題、思考題：1.若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為多少？2.設(shè)長度為n的鏈隊列用單循環(huán)鏈表表示，若只設(shè)頭指針，則入隊和出隊的時間如何？若只設(shè)尾指針呢？3.循環(huán)隊列存儲在數(shù)組A[0..m]中，則入隊時的操作為()。A.rear=rear+1B.rear=(rear+1)%(m-1)C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)4.設(shè)用變量rear和length分別指示循環(huán)隊列中隊尾元素的位置和內(nèi)含元素的個數(shù)。試給出此循環(huán)隊列的定義，并寫出相應(yīng)的入隊(QueueIn)和出隊(QueueOut)算法。5.討論：循環(huán)隊列的優(yōu)點是什么，如何判斷“空”和“滿”。參考資料：1．馮廣慧,吳昊,文全剛.算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）[M].電子工業(yè)出版社,20192．陳守孔,胡瀟琨,李玲,馮廣慧.算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析[M].機械工業(yè)出版社,2020

教案講授章節(jié)第8講串授課時數(shù)2教學(xué)目的：1.理解串的模式匹配。2.掌握樸素模式匹配算法及改進（KMP）算法、求next[]和nextval[]的算法。教學(xué)內(nèi)容（講授提綱）一.課前導(dǎo)學(xué)（線上）1.觀看導(dǎo)學(xué)視頻2.論壇討論、反饋疑難點二.課堂教學(xué)1．串的概念和術(shù)語2．串的表示和實現(xiàn)比較順序存儲、鏈?zhǔn)酱鎯Γù鎯γ芏鹊停?、塊鏈?zhǔn)酱鎯Γㄋ惴▽崿F(xiàn)復(fù)雜），字符串一般采用順序存儲結(jié)構(gòu)表示和實現(xiàn)。3．樸素模式匹配算法（1）算法思想及實現(xiàn)（2）舉例模擬匹配過程，主串S=“GoogleGooseGood”，模式串T=“Good”。4．KMP算法——KMP—Knuth,Morris,Pratt三人發(fā)明高德納（DonaldErvinKnuth，1938年），美國著名計算機科學(xué)家，斯坦福大學(xué)電腦系榮譽教授。高德納教授被譽為現(xiàn)代計算機科學(xué)的鼻祖，在計算機科學(xué)及數(shù)學(xué)領(lǐng)域發(fā)表了多部具廣泛影響的論文和著作，與EdsgerWybeDijkstra并稱為我們這個時代最偉大的計算機科學(xué)家的人。高德納還是TheArtofComputerProgramming（中譯本《計算機程序設(shè)計藝術(shù)》）的作者以及TeX和Metafont排版軟件的發(fā)明人。高德納（DonaldErvinKnuth，1938年），美國著名計算機科學(xué)家，斯坦福大學(xué)電腦系榮譽教授。高德納教授被譽為現(xiàn)代計算機科學(xué)的鼻祖，在計算機科學(xué)及數(shù)學(xué)領(lǐng)域發(fā)表了多部具廣泛影響的論文和著作，與EdsgerWybeDijkstra并稱為我們這個時代最偉大的計算機科學(xué)家的人。高德納還是TheArtofComputerProgramming（中譯本《計算機程序設(shè)計藝術(shù)》）的作者以及TeX和Metafont排版軟件的發(fā)明人。（1）算法特點，無需回溯，在O（n＋m）的時間量級上完成串的模式匹配操作（2）KMP算法思想（3）求解next數(shù)組的算法思想，舉例手工模擬過程（4）算法實現(xiàn)5．next數(shù)組的改進討論：模式串P=’aaaab’，其next函數(shù)值為01234，若主串為’aaabaaabaaaab’，當(dāng)i＝4，j＝4時si≠pj，由next[j]的指示還需進行i＝4、j＝3，i＝4、j＝2，i＝4、j＝1等三次比較。實際上，由于模式中第1、2、3個字符和第4個字符都相等，因此這種比較是不必要的，可以將模式串一次向右滑動4個字符直接進行i＝5、j＝1的比較。也就是說，若next[j]=k，當(dāng)si與pj失配且pj＝pk，則下一步不需將主串中的si與pk比較，而是直接與next[k]進行比較。由以上思想對next函數(shù)進行改進。6.樸素模式匹配算法與KMP算法的比較雖然樸素模式匹配算法的時間復(fù)雜度是O(n*m)，但在一般情況下，其實際的執(zhí)行時間近似于O(n+m)，因此至今仍被采用。KMP算法僅當(dāng)主串與模式間存在許多“部分匹配”的情況下才顯得快得多。KMP算法的最大特點是主串指針不回溯，在整個匹配過程中，對主串從頭到尾掃描一遍，對于處理存儲在外存上的大文件是非常有效的。7.課堂練習(xí)【2015全國統(tǒng)考408】已知字符串S為"abaabaabacacaabaabcc"，模式串t為"abaabc"，采用KMP算法進行匹配，第一次出現(xiàn)“失配”(s[i]!=t[i])時，i=j=5，則下次開始匹配時，i和j的值分別是（）。A．i=1，j=0B．i=5，j=0C．i=5，j=2D．i=6，j=28.算法設(shè)計舉例,寫出一個遞歸算法來實現(xiàn)字符串逆序存儲?！局锌圃貉芯可骸咳?課后鞏固（線上）觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點測試；在“百科園”完成線性結(jié)構(gòu)闖關(guān)訓(xùn)練。本章節(jié)的教學(xué)重點、難點：1．本章重點是串的模式匹配、手工描述求匹配串的next和nextval函數(shù)值。2．難點是KMP算法的推導(dǎo)過程。教學(xué)方法、教學(xué)手段：1．串的概念和術(shù)語、串的表示和實現(xiàn)（30分鐘）2．KMP算法、求解next和nextval（50分鐘）3．算法設(shè)計（10分鐘）3．使用教具：計算機和投影儀；4．輔助教學(xué)：雨課堂、校內(nèi)SPOC、“百科園”、學(xué)堂在線MOOC、算法演示動畫；5．課前觀看導(dǎo)學(xué)視頻；課中案例展開，應(yīng)用翻轉(zhuǎn)課堂、項目驅(qū)動以及實踐教學(xué)法；課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點在線測試。作業(yè)、討論題、思考題：1.設(shè)S為一個長度為n的字符串，其中的字符各不相同，則S中的互異的非平凡子串（非空且不同于S本身）的個數(shù)是多少？2.用順序結(jié)構(gòu)存儲的串S，編寫算法刪除S中第i個字符開始的j個字符。3.模式串t=“abcaabbcaabdab”，求模式串的next和nextval數(shù)組的值。4.對S=’aabcbabcaabcaaba’，T=’bca’，畫出以T為模式串，S為目標(biāo)串的匹配過程。5.函數(shù)voidinsert(char*s，char*t，intpos)表示將字符串t插入到字符串s中，插入位置為pos。請編寫實現(xiàn)該函數(shù)的算法。假設(shè)分配給字符串s的空間足夠讓字符串t插入。6.討論：kmp算法的特點是什么？BF算法已經(jīng)不適用了嗎？參考資料：1．馮廣慧,吳昊,文全剛.算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）[M].電子工業(yè)出版社,20192．陳守孔,胡瀟琨,李玲,馮廣慧.算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析[M].機械工業(yè)出版社,2020

教案講授章節(jié)第9講樹、二叉樹的概念和性質(zhì)授課時數(shù)2教學(xué)目的：1.理解樹是復(fù)雜的非線性數(shù)據(jù)結(jié)構(gòu)，樹，二叉樹的遞歸定義，基本概念，術(shù)語。2.掌握二叉樹的性質(zhì)，存儲結(jié)構(gòu)教學(xué)內(nèi)容（講授提綱）一.課前導(dǎo)學(xué)（線上）1.觀看導(dǎo)學(xué)視頻2.論壇討論、反饋疑難點二.課堂教學(xué)1.樹的基本概念合術(shù)語2.二叉樹的基本概念和特點，二叉樹的5種基本形態(tài)3.二叉樹的5個性質(zhì)（對每個性質(zhì)，都要會證明）性質(zhì)1：一個非空二叉樹的第i層上至多有2i-1個結(jié)點（i≥1）。性質(zhì)2：深度為k的二叉樹至多有2k－1個結(jié)點（k≥1）。性質(zhì)3：任何一棵二叉樹中，若葉子數(shù)為n0，度為2的結(jié)點個數(shù)為n2，則n0＝n2＋1。性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度為。性質(zhì)5：如果對一棵有n個結(jié)點的完全二叉樹按層次自上而下（每層自左而右）對結(jié)點從1到n進行編號，則對任意一個結(jié)點i（1≤i≤n）有：(1)若i＝1，則結(jié)點i為根，無雙親；若i>1，則結(jié)點i的雙親結(jié)點的編號是。(2)若2i≤n，則i的左孩子的編號是2i，否則i無左孩子。(3)若2i＋1≤n，則i的右孩子的編號是2i+1，否則i無右孩子。4.課堂練習(xí)（1）【2011全國統(tǒng)考408】若一棵完全二叉樹有768個結(jié)點，則該二叉樹中葉結(jié)點的個數(shù)是()。A．257B．258C．384D．385（2）【2009全國統(tǒng)考408】已知一棵完全二叉樹的第6層（設(shè)根是第1層）有8個葉結(jié)點，則該完全二叉樹的結(jié)點個數(shù)最多是()。A.39B.52C.111D.119三.課后鞏固（線上）課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點測試。本章節(jié)的教學(xué)重點、難點：重點和難點是二叉樹的特點和5個性質(zhì)。教學(xué)方法、教學(xué)手段：1．樹的概念和術(shù)語（30分鐘）2．二叉樹的概念和性質(zhì)（45分鐘）3．課堂練習(xí)（15分鐘）4．使用教具：計算機和投影儀；5．輔助教學(xué)：雨課堂、校內(nèi)SPOC、“百科園”在線考試系統(tǒng)、學(xué)堂在線MOOC、算法演示動畫；6．課前觀看導(dǎo)學(xué)視頻；課中案例展開，應(yīng)用翻轉(zhuǎn)課堂、項目驅(qū)動以及實踐教學(xué)法；課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點在線測試。作業(yè)、討論題、思考題：1.設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點個數(shù)分別為4，2，1，1，求葉子數(shù)。2.一棵完全二叉樹有500個結(jié)點，請問該完全二叉樹有多少個葉子結(jié)點？有多少個度為1的結(jié)點？有多少個度為2的結(jié)點？如果完全二叉樹有501個結(jié)點，結(jié)果如何？請寫出推導(dǎo)過程。3.某二叉樹有20個葉子結(jié)點，有30個結(jié)點僅有一個孩子，則該二叉樹的總結(jié)點數(shù)是多少。4.求一棵具有1025個結(jié)點的二叉樹的高度。5.一棵二叉樹高度為h，所有結(jié)點的度或為0，或為2，則這棵二叉樹最少有多少結(jié)點。6.將有關(guān)二叉樹的概念推廣到三叉樹，則一棵有244個結(jié)點的完全三叉樹的高度是多少。參考資料：1．馮廣慧,吳昊,文全剛.算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）[M].電子工業(yè)出版社,20192．陳守孔,胡瀟琨,李玲,馮廣慧.算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析（第四版）[M].機械工業(yè)出版社,20203．翁惠玉,俞勇.數(shù)據(jù)結(jié)構(gòu)：思想與實現(xiàn),高等教育出版社[M].高等教育出版社,2018

教案講授章節(jié)第10講二叉樹的存儲和遍歷運算授課時數(shù)2教學(xué)目的：1．掌握二叉樹先序、中序、后序、層次遍歷的算法。2．遞歸遍歷算法是基礎(chǔ)，由此導(dǎo)出許多實用的算法，如求二叉樹的高度、各結(jié)點的層次數(shù)、度為0、1、2的結(jié)點數(shù)，二叉樹的相似、全等、復(fù)制等。3．由二叉樹的遍歷的前序和中序序列或后序和中序序列可以唯一構(gòu)造一棵二叉樹，要會手工模擬及編寫算法。由前序和后序序列不能唯一確定一棵二叉樹。教學(xué)內(nèi)容（講授提綱）一.課前導(dǎo)學(xué)（線上）1.觀看導(dǎo)學(xué)視頻2.論壇討論、反饋疑難點二.課堂教學(xué)1.二叉樹的存儲結(jié)構(gòu)(1)二叉樹的順序存儲：按照從上到下從左到右的順序編號；對于完全二叉樹，可以從根結(jié)點開始按序號存放；對于一般二叉樹，參照完全二叉樹編號方法編號，空的結(jié)點為“虛結(jié)點”。(2)二叉樹的鏈?zhǔn)酱鎯?.二叉樹的遍歷的定義3.二叉樹的深度優(yōu)先遍歷算法思想（僅列舉左子樹先于右子樹的三種）（1）前序遍歷（根N、左子樹L、右子樹R）（2）中序遍歷（左子樹L、根N、右子樹R）（3）后序遍歷（左子樹L、右子樹R、根N）3.二叉樹的遞歸前序、中序、后序遍歷算法4.二叉樹的層次遍歷，借助隊列實現(xiàn)6.（由遍歷運算得到）二叉樹結(jié)構(gòu)的重要性質(zhì)已知二叉樹的先序序列和中序序列，可以唯一確定一棵二叉樹。已知二叉樹的后序序列和中序序列，可以唯一確定一棵二叉樹；已知二叉樹的先序序列和后序序列，不能唯一確定一棵二叉樹；已知二叉樹的層次序列和中序序列，可以唯一確定一棵二叉樹。7.課堂練習(xí)（1）【2009全國統(tǒng)考408】給定二叉樹如下圖所示。設(shè)N代表二叉樹的根，L代表根結(jié)點的左子樹，R代表根結(jié)點的右子樹。若遍歷后的結(jié)點序列為3,1,7,5,6,2,4，則其遍歷方式是()A.LRNB.NRLC.RLND.RNL（2）【2017全國統(tǒng)考408】要使一棵非空二叉樹的先序序列與中序序列相同，其所有非葉結(jié)點須滿足的條件是（）。A．只有左子樹B．只有右子樹C．結(jié)點的度均為1D．結(jié)點的度均為2（3）【2012全國統(tǒng)考408】若一棵二叉樹的前序遍歷序列為a，e，b，d，c，后序遍歷序列為b，c，d，e，a，則根結(jié)點的孩子結(jié)點（）。A.只有eB.有e、bC.有e、cD.無法確定三.課后鞏固（線上）課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點測試。本章節(jié)的教學(xué)重點、難點：1．重點是二叉樹的遞歸遍歷算法2．難點是遍歷算法的應(yīng)用教學(xué)方法、教學(xué)手段：1．二叉樹的存儲和遍歷算法（45分鐘）2．算法設(shè)計舉例（45分鐘）3．使用教具：計算機和投影儀；4．輔助教學(xué)：雨課堂、校內(nèi)SPOC、百科園、學(xué)堂在線MOOC、算法演示動畫；5．課前觀看導(dǎo)學(xué)視頻，課中案例展開，應(yīng)用翻轉(zhuǎn)課堂、項目驅(qū)動以及實踐教學(xué)法。課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點在線測試。作業(yè)、討論題、思考題：1．對二叉樹的結(jié)點從1開始進行連續(xù)編號，要求每個結(jié)點的編號大于其左、右孩子的編號，同一結(jié)點的左、右孩子中，其左孩子的編號小于其右孩子的編號，是采用何種次序的遍歷實現(xiàn)編號的。2．對任意一棵樹，設(shè)它有n個結(jié)點，這n個結(jié)點的度數(shù)之和為多少？3．編寫算法，交換以二叉鏈表存儲的二叉樹的左右子樹。4．討論：二叉樹是度為2的樹嗎？有何區(qū)別？參考資料：1．馮廣慧,吳昊,文全剛.算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）[M].電子工業(yè)出版社,20192．陳守孔,胡瀟琨,李玲,馮廣慧.算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析（第四版）[M].機械工業(yè)出版社,2020教案講授章節(jié)第11講二叉樹的算法舉例授課時數(shù)2教學(xué)目的：1．掌握二叉樹先序、中序、后序、層次遍歷的算法。2．遞歸遍歷算法是基礎(chǔ)，由此導(dǎo)出許多實用的算法，如求二叉樹的高度、各結(jié)點的層次數(shù)、度為0、1、2的結(jié)點數(shù)，二叉樹的相似、全等、復(fù)制等。3．由二叉樹的遍歷的前序和中序序列或后序和中序序列可以唯一構(gòu)造一棵二叉樹，要會手工模擬及編寫算法。由前序和后序序列不能唯一確定一棵二叉樹。教學(xué)內(nèi)容（講授提綱）一.課前導(dǎo)學(xué)（線上）1．觀看導(dǎo)學(xué)視頻2．論壇討論、反饋疑難點二.課堂教學(xué)1．算法設(shè)計舉例（1）根據(jù)帶外部結(jié)點的前序序列，建立二叉樹（2）求二叉樹高度（3）求二叉樹中葉子數(shù)（4）求二叉樹中結(jié)點總數(shù)（5）清除（刪除）二叉樹2．課堂練習(xí)自測題（1）圖（1）【2017全國統(tǒng)考408】已知一棵二叉樹的樹形如圖所示，其后序序列為e,a,c,b,d,g,f，樹中與結(jié)點a同層的結(jié)點是自測題（1）圖A．cB．dC．fD．g（2）【2011全國統(tǒng)考408】若一棵二叉樹的前序遍歷序列和后序遍歷序列分別是：1、2、3、4和4、3、2、1，則該二叉樹的中序序列不會是()。A．1,2,3,4B．2,3,4,1C．3,2,4,1D．4,3,2,1自測題（4）圖（3）【2015全國統(tǒng)考408】先序序列為a,b,c,d的不同二叉樹的個數(shù)是自測題（4）圖A．13B．14C．15D．16提示：除手工模擬求解外，建議擴展學(xué)習(xí)卡特蘭數(shù)（4）已知二叉樹的中序序列：DBFAHECG，后序序列：DFBHEGCA，請唯一確定一棵二叉樹。（5）【電子科技大學(xué)】【廈門大學(xué)】一棵二叉樹的先序、中序和后序序列如下，其中有部分未標(biāo)出，試構(gòu)造出該二叉樹。先序序列為：__CDE_GHI_K中序序列為：CB__FA_JKIG后序序列為：_EFDB_JIH_A三.課后鞏固（線上）課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點測試。本章節(jié)的教學(xué)重點、難點：1．重點是二叉樹的遞歸遍歷算法2．難點是遍歷算法的應(yīng)用教學(xué)方法、教學(xué)手段：1．算法設(shè)計舉例（60）2．課堂練習(xí)（30鐘）3．使用教具：計算機和投影儀；4．輔助教學(xué)：雨課堂、校內(nèi)SPOC、百科園、學(xué)堂在線MOOC、算法演示動畫；5．課前觀看導(dǎo)學(xué)視頻，課中案例展開，應(yīng)用翻轉(zhuǎn)課堂、項目驅(qū)動以及實踐教學(xué)法。課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點在線測試。作業(yè)、討論題、思考題：1．討論：試找出滿足下列條件的二叉樹（1）先序序列與后序序列相同（2）中序序列與后序序列相同（3）先序序列與中序序列相同（4）中序序列與層次遍歷序列相同2．設(shè)計算法，將一棵以二叉鏈表存儲的二叉樹，按結(jié)點的編號順序存儲到一維數(shù)組中。3．已知二叉樹的后序序列為DMFBHELGCA；中序序列為DBMFAHECGL，請構(gòu)造該二叉樹。4．設(shè)二叉樹中每個結(jié)點均用一個字母表示，若一個結(jié)點的左子樹或右子樹為空，用#表示，現(xiàn)前序遍歷二叉樹，訪問的結(jié)點序列為ABD##C#E##F##，寫出中序和后序遍歷二叉樹時結(jié)點的訪問序列。5．討論：設(shè)有一個表達(dá)式樹，用何種方法可以求該樹表示的表達(dá)式的值？參考資料：1．馮廣慧,吳昊,文全剛.算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）[M].電子工業(yè)出版社,20192．陳守孔,胡瀟琨,李玲,馮廣慧.算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析（第四版）[M].機械工業(yè)出版社,2020

教案講授章節(jié)第12講樹、森林與二叉樹的轉(zhuǎn)換授課時數(shù)2教學(xué)目的：1.掌握樹的存儲結(jié)構(gòu)2.掌握樹和二叉樹的相互轉(zhuǎn)換3.掌握樹和森林的遍歷及與對應(yīng)二叉樹遍歷的關(guān)系教學(xué)內(nèi)容（講授提綱）一.課前導(dǎo)學(xué)（線上）1.觀看導(dǎo)學(xué)視頻2.論壇討論、反饋疑難點二.課堂教學(xué)1.樹的存儲結(jié)構(gòu)（1）雙親表示法（2）孩子表示法（3）左孩子右兄弟表示法：本質(zhì)是二叉鏈表表示法2.算法設(shè)計舉例（1）用雙親表示法求樹的深度（2）求左孩子右兄弟表示法存儲的森林的葉子數(shù)（3）求左孩子右兄弟表示法存儲的樹的深度3.樹、森林和二叉樹的相互轉(zhuǎn)換（1）樹、森林到二叉樹的轉(zhuǎn)換（2）二叉樹到樹、森林的轉(zhuǎn)換4.樹、森林的遍歷（1）前序遍歷樹、森林的算法思想及實現(xiàn)（2）后序遍歷樹、森林的算法思想及實現(xiàn)特點：樹、森林的前序遍歷序列與其對應(yīng)的二叉樹的前序遍歷序列相同樹、森林的后序遍歷序列與其對應(yīng)的二叉樹的中序遍歷序列相同5.樹、森林的廣度優(yōu)先遍歷，借助隊列實現(xiàn)6.算法設(shè)計舉例（1）按帶外部結(jié)點的前序序列建立樹（森林）（2）求樹的高度（3）求結(jié)點總數(shù)（4）求葉子數(shù)（5）清空樹7.課堂練習(xí)（1）【2014全國統(tǒng)考408】將森林F轉(zhuǎn)換為對應(yīng)的二叉樹T，F(xiàn)中葉結(jié)點的個數(shù)等于（）A．T中葉結(jié)點的個數(shù)B．T中度為1的結(jié)點個數(shù)C．T中左孩子指針為空的結(jié)點個數(shù)D．T中右孩子指針為空的結(jié)點個數(shù)（2）【2016全國統(tǒng)考408】若森林F有15條邊、25個結(jié)點，則F包含的樹的個數(shù)是（）A．8B．9C．10D．11三.課后鞏固（線上）課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點測試。本章節(jié)的教學(xué)重點、難點：1．重點是樹的存儲結(jié)構(gòu)樹與二叉樹的轉(zhuǎn)換樹和森林的遍歷2．難點是孩子兄弟表示法的應(yīng)用算法教學(xué)方法、教學(xué)手段：1．樹的存儲結(jié)構(gòu)、樹與二叉樹的轉(zhuǎn)換（45分鐘）2．樹和森林的遍歷、算法設(shè)計舉例（45分鐘）3．使用教具：計算機和投影儀；4．輔助教學(xué)：雨課堂、校內(nèi)SPOC、百科園、學(xué)堂在線MOOC、算法演示動畫；5．課前觀看導(dǎo)學(xué)視頻，課中案例展開，應(yīng)用翻轉(zhuǎn)課堂、項目驅(qū)動以及實踐教學(xué)法。課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點在線測試。作業(yè)、討論題、思考題：1.已知一個森林的先序序列和后序序列如下，請構(gòu)造出該森林。先序序列：ABCDEFGHIJKLMNO后序序列：CDEBFHIJGAMLONK2.設(shè)計這樣的二叉樹，用它可以表示父子、夫妻和兄弟三種關(guān)系，并編寫一個查找任意父親結(jié)點的所有兒子結(jié)點的過程。3.設(shè)樹形T在后根次序下的結(jié)點排列和各結(jié)點相應(yīng)的次數(shù)如下，請畫出Ｔ的樹形結(jié)構(gòu)圖。后根次序：ＢＤＥＦＣＧＪＫＩＬＨＡ次數(shù)：００００３０００２０２４參考資料：1．馮廣慧,吳昊,文全剛.算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）[M].電子工業(yè)出版社,20192．陳守孔,胡瀟琨,李玲,馮廣慧.算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析（第四版）[M].機械工業(yè)出版社,2020

教案講授章節(jié)第13講哈夫曼樹、哈夫曼編碼授課時數(shù)2教學(xué)目的：1.理解哈夫曼樹的基本概念、術(shù)語、特點，掌握建立哈夫曼樹的方法2.掌握哈夫曼編碼的方法教學(xué)內(nèi)容（講授提綱）一.課前導(dǎo)學(xué)（線上）1.觀看導(dǎo)學(xué)視頻2.論壇討論、反饋疑難點二.課堂教學(xué)1.哈夫曼樹的概念和術(shù)語2.哈夫曼樹的性質(zhì)3.哈夫曼樹的構(gòu)造方法（1）根據(jù)給定的n個權(quán)值w1，w2，…，wn構(gòu)成含有n棵二叉樹的森林F={T1，T2，…，Tn}，其中每一棵二叉樹Ti中都只有一個權(quán)值為wi的根結(jié)點，其左右子樹為空；（2）在森林F中選出兩棵根結(jié)點權(quán)值最小的二叉樹作為一棵新二叉樹的左、右子樹，新二叉樹的根結(jié)點的權(quán)值為其左、右子樹根結(jié)點的權(quán)值之和；（3）從F中刪掉這兩棵二叉樹，同時把新二叉樹加入到F中；（4）重復(fù)（2）、（3），直到F中只含有一棵二叉樹為止，此二叉樹便為哈夫曼樹。例子：初始狀態(tài)集合中有4棵樹，權(quán)值分別為2、3、6、94.哈夫曼樹的構(gòu)造算法5.哈夫曼編碼大衛(wèi)·霍夫曼，大衛(wèi)·霍夫曼，在1952年發(fā)明哈夫曼編碼，他除了獲得計算機先驅(qū)獎以外,還在1973年獲得IEEE的McDowell獎。1998年IEEE下屬的信息論分會為紀(jì)念信息論創(chuàng)立50周年,授予他GoldenJubilee獎。哈夫曼編碼提出的背景：通訊使用電報碼；如何避免一個編碼是另一個編碼的前綴；用二叉樹可以構(gòu)造前綴碼；哈夫曼樹可以構(gòu)造最短的前綴碼（哈夫曼編碼）。在編碼中，需要從葉子結(jié)點出發(fā)，走從葉子到根的路徑；譯碼中，需要從根到葉子。6.算法設(shè)計舉例設(shè)計一個遞歸算法求一個哈夫曼樹的帶權(quán)路徑長度。提示：在對二叉樹的遍歷中，求出葉子結(jié)點的高度，就可以計算帶權(quán)路徑長度。7.課堂練習(xí)【2015全國統(tǒng)考408】下列選項給出的是從根分別到達(dá)兩個葉節(jié)點路徑上的權(quán)值序列，能屬于同一棵哈夫曼樹的是（）A．24，10，5和24，10，7B．24，10，5和24，12，7C．24，10，10和24，14，11D．24，10，5和24，14，6三.課后鞏固（線上）課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點測試。本章節(jié)的教學(xué)重點、難點：1．重點是哈夫曼樹的構(gòu)造2．難點是哈夫曼樹應(yīng)用的算法教學(xué)方法、教學(xué)手段：1．哈夫曼樹的構(gòu)造（45分鐘）2．哈夫曼樹編碼（45分鐘）3．使用教具：計算機和投影儀；4．輔助教學(xué)：雨課堂、校內(nèi)SPOC、百科園、學(xué)堂在線MOOC、算法演示動畫；5．課前觀看導(dǎo)學(xué)視頻，課中案例展開，應(yīng)用翻轉(zhuǎn)課堂、項目驅(qū)動以及實踐教學(xué)法。課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點在線測試。作業(yè)、討論題、思考題：1.某通信電文由A、B、C、D、E、F六個字符組成，它們在電文中出現(xiàn)的次數(shù)分別是16，5，7，3，8，1。試畫出其哈夫曼樹并確定其對應(yīng)的哈夫曼編碼。2.【2017全國統(tǒng)考408】已知字符集{a,b,c,d,e,f,g,h},若各字符哈夫曼編碼依次是0100,10,,0000，0101,001,011,11,0001，則編碼序列0100011001001011110101的譯碼結(jié)果是（）。A．a(chǎn)cgabfhB．a(chǎn)dbagbbC．a(chǎn)fbeagdD．a(chǎn)feefgd3.討論：介紹你知道的huffman編碼的應(yīng)用案例？參考資料：1．馮廣慧,吳昊,文全剛.算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）[M].電子工業(yè)出版社,20192．陳守孔,胡瀟琨,李玲,馮廣慧.算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析[M].機械工業(yè)出版社,2020

教案講授章節(jié)第14講堆與優(yōu)先隊列授課時數(shù)2教學(xué)目的：1.掌握二叉堆的定義、建堆、調(diào)堆的算法；2.理解優(yōu)先隊列的概念，掌握利用二叉堆實現(xiàn)優(yōu)先級隊列的方法。教學(xué)內(nèi)容（講授提綱）一.課前導(dǎo)學(xué)（線上）1.觀看導(dǎo)學(xué)視頻2.論壇討論、反饋疑難點二.課堂教學(xué)二叉堆的概念、特性、存儲優(yōu)先級隊列的簡單實現(xiàn)（1）入隊時，按照優(yōu)先級在隊列中尋找合適的位置，將新入隊的元素插入在此位置。出隊操作的實現(xiàn)保持不變。（2）入隊操作的實現(xiàn)保持不變，將新入隊的元素放在隊列尾。但出隊時，在整個隊列中查找優(yōu)先級最高的元素，讓它出隊。基于二叉堆的優(yōu)先級隊列（以小根堆為例）（1）入隊算法思想及實現(xiàn)，在如下的堆中插入元素3的過程：（2）出隊算法思想及實現(xiàn)，在如圖小根堆中最小元素3的出隊過程：（3）建立優(yōu)先級隊列（建堆）方法一：可以看成N次連續(xù)插入，其時間應(yīng)該是在O(NlogN)時間內(nèi)完成。方法二：利用堆的遞歸定義，從最后一個非終端結(jié)點開始，直到根結(jié)點，依次使用向下調(diào)整堆算法siftDown，就完成了初始堆的建立。算法舉例【中科院軟件所】已知關(guān)鍵字序列(K1,K2,K3,…,Kn-1)是大根堆。（1）試寫出一算法將(K1,K2,K3,…,Kn-1,Kn)調(diào)整為大根堆；（2）利用（1）的算法寫一個建大根堆的算法。5.課堂練習(xí)（1）【2009全國統(tǒng)考408】已知關(guān)鍵字序列5,8,12,19,28,20,15,22是小根堆（最小堆）,插入關(guān)鍵字3,調(diào)整后得到的小根堆是（）A.3,5,12,8,28,20,15,22,19B.3,5,12,19,20,15,22,8,28C.3,8,12,5,20,15,22,28,19D.3,12,5,8,28,20,15,22,19（2）【2015全國統(tǒng)考408】已知小根堆為8，15，10，21，34，16，12，刪除關(guān)鍵字8之后需重建堆，在此過程中，關(guān)鍵字之間的比較數(shù)是（）A．1B．2C．3D．4三.課后鞏固（線上）觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點測試；本章節(jié)的教學(xué)重點、難點：1．重點堆的定義和算法。2．難點是堆的算法。教學(xué)方法、教學(xué)手段：1．二叉堆的概念、特性、存儲（20分鐘）2．基于小跟堆的優(yōu)先級隊列（50分鐘）3．算法設(shè)計舉例、課堂練習(xí)（20分鐘）4．使用教具：計算機和投影儀；5．輔助教學(xué)：雨課堂、校內(nèi)SPOC、百科園、學(xué)堂在線MOOC、算法演示動畫；6．課前觀看導(dǎo)學(xué)視頻，課中案例展開，應(yīng)用翻轉(zhuǎn)課堂、項目驅(qū)動以及實踐教學(xué)法。課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點在線測試。作業(yè)、討論題、思考題：在“百科園”完成樹形結(jié)構(gòu)闖關(guān)訓(xùn)練。參考資料：1．馮廣慧,吳昊,文全剛.算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）[M].電子工業(yè)出版社,20192．陳守孔,胡瀟琨,李玲,馮廣慧.算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析[M].機械工業(yè)出版社,2020教案講授章節(jié)第15講圖的基本概念和存儲授課時數(shù)2教學(xué)目的：1.掌握圖的基本概念2.掌握圖的存儲結(jié)構(gòu)，重點是鄰接矩陣和鄰接表3.掌握圖的算法，特別是圖的生成算法4.掌握鄰接矩陣和鄰接表存儲結(jié)構(gòu)間的相互轉(zhuǎn)換教學(xué)內(nèi)容（講授提綱）一.課前導(dǎo)學(xué)（線上）1.觀看導(dǎo)學(xué)視頻2.論壇討論、反饋疑難點二.課堂教學(xué)1．圖的概念和術(shù)語介紹“我國八縱八橫高速鐵路網(wǎng)”、“地鐵線路圖”，說明數(shù)學(xué)模型的重要性圖的概念：有向圖、無向圖、完全圖、度、出度、入度、鄰接、鄰接點、連通分量、強連通分量、生成樹、第一鄰接點、下一鄰接點2．圖的類型定義3．課堂練習(xí)（1）【2009全國統(tǒng)考408】下列關(guān)于無向連通圖特性的敘述中，正確的是Ⅰ.所有頂點的度之和為偶數(shù)Ⅱ.邊數(shù)大于頂點個數(shù)減1Ⅲ.至少有一個頂點的度為1A.只有ⅠB.只有ⅡC.Ⅰ和ⅡD.Ⅰ和Ⅲ（2）【2010全國統(tǒng)考408】若無向圖G=（V.E）中含7個頂點，則保證圖G在任何情況下都是連通的，則需要的邊數(shù)最少是（）A.6B.15C.16D.21（3）【2017全國統(tǒng)考408】已知無向圖G含有16條邊，其中度為4的頂點個數(shù)為3，度為3的頂點個數(shù)為4，其他頂點的度均小于3。圖G所含的頂點個數(shù)至少是（）A、10B、11C、13D、154．圖的鄰接矩陣表示法、特點及類型定義5．圖的鄰接表存儲結(jié)構(gòu)、特點及類型定義6．圖的逆鄰接表7．圖的存儲結(jié)構(gòu)間的相互轉(zhuǎn)換三.課后鞏固（線上）課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點測試。本章節(jié)的教學(xué)重點、難點：1．重點是圖的基本概念，存儲結(jié)構(gòu)2．難點是圖的存儲結(jié)構(gòu)間相互轉(zhuǎn)換的算法教學(xué)方法、教學(xué)手段：1．圖的概念和術(shù)語（45分鐘）2．圖的存儲結(jié)構(gòu)及類型定義（45分鐘）3．使用教具：計算機和投影儀；4．輔助教學(xué)：雨課堂、校內(nèi)SPOC、百科園、學(xué)堂在線MOOC、算法演示動畫；5．課前觀看導(dǎo)學(xué)視頻，課中案例展開，應(yīng)用翻轉(zhuǎn)課堂、項目驅(qū)動以及實踐教學(xué)法。課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點在線測試。作業(yè)、討論題、思考題：1.設(shè)無向圖的頂點個數(shù)為n，則該圖最多有____條邊。2.一個有n個結(jié)點的圖，最少有____個連通分量，最多有____個連通分量。3.在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的____倍。4.要連通具有n個頂點的有向圖，至少需要____條邊。5.G是一個非連通無向圖，共有28條邊，則該圖至少有______個頂點。6.n個頂點的完全有向圖含有弧的數(shù)目是____條。7.討論：已知某有向圖的鄰接表，如何求該圖各結(jié)點的入度數(shù)。8.【2013全國統(tǒng)考408】設(shè)圖的鄰接矩陣A如下所示。各頂點的度依次是（）A.1，2，1，2B.2，2，1，1C.3，4，2，3D.4，4，2，2參考資料：1．馮廣慧,吳昊,文全剛.算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）[M].電子工業(yè)出版社,20192．陳守孔,胡瀟琨,李玲,馮廣慧.算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析（第四版）[M].機械工業(yè)出版社,2020

教案講授章節(jié)第16講圖的遍歷、生成樹授課時數(shù)2教學(xué)目的：1.掌握圖的遍歷算法：深度優(yōu)先遍歷，寬度優(yōu)先遍歷2.了解圖的連通性，掌握連通分量的求法3.理解生成樹的構(gòu)造方法教學(xué)內(nèi)容（講授提綱）一.課前導(dǎo)學(xué)（線上）1.觀看導(dǎo)學(xué)視頻2.論壇討論、反饋疑難點二.課堂教學(xué)1.圖的遍歷（1）深度優(yōu)先遍歷（DFS）a）手工模擬深度優(yōu)先遍歷過程b）深度優(yōu)先遍歷算法思想及算法實現(xiàn)（2）廣度優(yōu)先遍歷（BFS）a）手工模擬廣度優(yōu)先遍歷過程b）廣度優(yōu)先遍歷算法思想及算法實現(xiàn)2.圖的連通分量進入DFS或BFS一次可以求得一個連通分量3.深度優(yōu)先生成樹和廣度優(yōu)先生成樹采用DFS遍歷圖所得到的生成樹稱為深度優(yōu)先生成樹，采用BFS遍歷圖所得到的生成樹稱為廣度優(yōu)先生成樹4.課堂練習(xí)（1）【2015全國統(tǒng)考408】設(shè)有向圖G=(V,E)，頂點集V={V0,V1,V2,V3}，邊集E={<v0,v1>,<v0,v2>,<v0,v3>，<v1,v3>},若從頂點V0開始對圖進行深度優(yōu)先遍歷，則可能得到的不同遍歷序列個數(shù)是（）。A．2B．3C．4D．5（2）【2012全國統(tǒng)考408】對有n個頂點、e條邊且使用鄰接表存儲的有向圖進行廣度優(yōu)先遍歷，其算法時間復(fù)雜度是（）。A．O(n)B．O(e)C．O(n+e)D．O(n×e)三.課后鞏固（線上）課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點測試。本章節(jié)的教學(xué)重點、難點：1．重點：圖的遍歷算法和生成樹2．難點：圖的遍歷算法的應(yīng)用教學(xué)方法、教學(xué)手段：1．圖的遍歷（60分鐘）2．生成樹、課堂練習(xí)（30分鐘）3．使用教具：計算機和投影儀；4．輔助教學(xué)：雨課堂、校內(nèi)SPOC、百科園、學(xué)堂在線MOOC、算法演示動畫；5．課前觀看導(dǎo)學(xué)視頻，課中案例展開，應(yīng)用翻轉(zhuǎn)課堂、項目驅(qū)動以及實踐教學(xué)法。課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點在線測試。作業(yè)、討論題、思考題：1.討論：圖的BFS生成樹的樹高要小于等于同圖DFS生成樹的樹高，對嗎？2.一帶權(quán)無向圖的鄰接矩陣如下圖，試畫出它的一棵最小生成樹。作業(yè)2的圖作業(yè)3的圖3.如圖所示是一帶權(quán)有向圖的鄰接表法存儲表示。其中出邊表中的每個結(jié)點均含有三個字段，依次為邊的另一個頂點在頂點表中的序號、邊上的權(quán)值和指向下一個邊結(jié)點的指針。試求：（1）該帶權(quán)有向圖的圖形；（2）從頂點V1為起點的廣度優(yōu)先遍歷的頂點序列及對應(yīng)的生成樹；（3）以頂點V1為起點的深度優(yōu)先遍歷生成樹。4.無向圖G=(V,E)，其中：V={a,b,c,d,e,f}，E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，寫出對該圖從頂點a出發(fā)進行深度優(yōu)先遍歷可能得到的全部頂點序列。參考資料：1．馮廣慧,吳昊,文全剛.算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）[M].電子工業(yè)出版社,20192．陳守孔,胡瀟琨,李玲,馮廣慧.算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析（第四版）[M].機械工業(yè)出版社,2020

教案講授章節(jié)第17講最小生成樹授課時數(shù)2教學(xué)目的：1.掌握最小生成樹的概念。2.掌握Prime和Kruscal求最小生成樹的方法。3.理解Prime和Kruscal求最小生成樹的算法教學(xué)內(nèi)容（講授提綱）一.課前導(dǎo)學(xué)（線上）1.觀看導(dǎo)學(xué)視頻2.論壇討論、反饋疑難點二.課堂教學(xué)1.復(fù)習(xí)生成樹、深度優(yōu)先生成樹和廣度優(yōu)先生成樹采用DFS遍歷圖所得到的生成樹稱為深度優(yōu)先生成樹，采用BFS遍歷圖所得到的生成樹稱為廣度優(yōu)先生成樹2.最小生成樹n個頂點網(wǎng)絡(luò)的生成樹有n個結(jié)點，n-1條分枝。假設(shè)網(wǎng)絡(luò)中有m條邊(m≥n-1)，用MST表示許多可能的生成樹的集合，每棵樹中n-1條分枝上的權(quán)之和用WG(T)表示，則使得WG(Tmin)=Min{WG(T)|T∈MST}，的生成樹Tmin便是網(wǎng)絡(luò)的最小生成樹。應(yīng)用舉例：左圖代表6應(yīng)用舉例：左圖代表6個城市間的交通網(wǎng)，邊上的權(quán)表示公路的造價現(xiàn)在要用公路把6個城市連接起來（這至少要修5條公路），如何設(shè)計使得這5條公路的總造價最少呢？3.MST性質(zhì)假設(shè)N=（V，{E}）是一個連通無向網(wǎng)，U是頂點集V的一個非空子集。若（u，v）是一條具有最小權(quán)值的邊，其中u∈U，v∈V－U，則必存在一棵包含邊（u，v）的最小生成樹。4.Prim算法思想及實現(xiàn)5.Kruskal算法思想及實現(xiàn)6.課堂練習(xí)（1）【2012全國統(tǒng)考408】下列關(guān)于最小生成樹的敘述中，正確的是Ⅰ最小生成樹的代價唯一Ⅱ所有權(quán)值最小的邊一定會出現(xiàn)在所有的最小生成樹中Ⅲ使用普里姆（Prim）算法從不同頂點開始得到的最小生成樹一定相同Ⅳ使用普里姆算法和克魯斯卡爾（Kruskal）算法得到的最小生成樹總不相同A僅ⅠB.僅ⅡC.僅Ⅰ、ⅢD.僅Ⅱ、Ⅳ（2）【2017全國統(tǒng)考408】使用Prim(普里姆)算法求帶權(quán)連通圖的最小(代價)生成樹(MST)。請回答下列問題a）對下圖G，從頂點A開始求G的MST依次給出按算法選出的邊。b）圖G的MST是唯一的嗎?c）對任意的帶權(quán)連通圖，滿足什么條件時，其MST是唯一的?三.課后鞏固（線上）課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點測試。本章節(jié)的教學(xué)重點、難點：1．重點：生成樹、深度優(yōu)先生成樹、寬度優(yōu)先生成樹、最小生成樹的概念2．難點：求最小生成樹的算法教學(xué)方法、教學(xué)手段：1．Prime算法求最小生成樹（40分鐘）2．Kruscal算法求最小生成樹（40分鐘）3．課堂練習(xí)（10分鐘）3．使用教具：計算機和投影儀；4．輔助教學(xué)：雨課堂、校內(nèi)SPOC、百科園、學(xué)堂在線MOOC、算法演示動畫；5．課前觀看導(dǎo)學(xué)視頻，課中案例展開，應(yīng)用翻轉(zhuǎn)課堂、項目驅(qū)動以及實踐教學(xué)法。課后觀看習(xí)題視頻，并在校內(nèi)SPOC完成知識點在線測試。作業(yè)、討論題、思考題：1．利用Kruskal算法求最小生成樹作業(yè)1的圖作業(yè)2的圖作業(yè)3的圖2．已知帶權(quán)圖的鄰接矩陣，試畫出從頂點v1開始利用Prim算法得到的最小生成樹3．【2013全國統(tǒng)考408】求下面帶權(quán)圖的最?。ù鷥r）生成樹時，可能是克魯斯卡（kruskal）算法第二次選中但不是普里姆（Prim）算法（從V4開始）第2次選中的邊是（）。A．(V1,V3)B．(V1,V4)C．(V2,V3)D．(V3,V4)參考資料：1．馮廣慧,吳昊,文全剛.算法與數(shù)據(jù)結(jié)構(gòu)（C++語言版）[M].電子工業(yè)出版社,20192．陳守孔,胡瀟琨,李玲,馮廣慧.算法與數(shù)據(jù)結(jié)構(gòu)考研試題精析（第四版）[M].機械工業(yè)出版社,2020

教案講授章節(jié)第18講拓?fù)渑判颉⒆疃搪窂绞谡n時數(shù)2教學(xué)目的：1.了解有向無環(huán)圖的概念及應(yīng)用2.掌握拓?fù)渑判虻姆椒ê退惴ā?.掌握單源點到其它各頂點的最短路徑。4.掌握任意兩頂點間的最短路徑。教學(xué)內(nèi)容（講授提綱）一.課前導(dǎo)學(xué)（線上）1.觀看導(dǎo)學(xué)視頻2.論壇討論、反饋疑難點二.課堂教學(xué)1.有向無環(huán)圖（DAG）概念及應(yīng)用2.拓?fù)渑判颍?）基本概念和術(shù)語（2）AOV網(wǎng)進行拓?fù)渑判虻姆椒ǚ治觥芭耪n”問題—〉有向圖描述任務(wù)流程—〉手工模擬拓?fù)渑判蜻^程（3）拓?fù)渑判蛩惴ㄓ懻摶跅?隊列的算法求得的拓?fù)湫蛄锌赡艿牟町?