數(shù)據(jù)結(jié)構(gòu)教學(xué)設(shè)計(jì)方案

1、數(shù)據(jù)結(jié)構(gòu)教學(xué)設(shè)計(jì)方案1課程的一般信息1.1 教學(xué)對象計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)2012級本科學(xué)生1.2 課程名稱數(shù)據(jù)結(jié)構(gòu)1.3 課程教材及分析1.3.1 中文教材及分析數(shù)據(jù)Z勾（C語言版），嚴(yán)蔚敏，北京：清華大學(xué)出版社（國家精品課程配套教材），2011.11。該教材為國內(nèi)關(guān)于數(shù)據(jù)結(jié)構(gòu)最知名的教材之一，受到國內(nèi)計(jì)算機(jī)教育界廣泛的認(rèn)可。1.3.2 教材選取的背景選取本教材的原因主要是受到本人對于該課程的教學(xué)改革驅(qū)動(dòng)，在該課程教學(xué)中強(qiáng)調(diào)實(shí)踐性，注重理論聯(lián)系實(shí)際。1.4 課程類型專業(yè)必修課（開設(shè)時(shí)間為計(jì)算機(jī)科學(xué)學(xué)院各專業(yè)本科生二年級第一學(xué)期）1.5 教師的基本信息肖冰，1981年生，博士，講師，計(jì)算機(jī)科學(xué)學(xué)

2、院。主要研究方向?yàn)槟Ｊ阶R別、機(jī)器學(xué)習(xí)、智能信息處理等。博士畢業(yè)后從事一線教學(xué)和科研工作，主講了計(jì)算機(jī)基礎(chǔ)、ACCESS數(shù)據(jù)庫應(yīng)用技術(shù)，數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)庫原理與設(shè)計(jì)及相關(guān)課程設(shè)計(jì)等課程。在PatternRecognition（SCI二區(qū)）、Neurocomputing（SCI三區(qū)）、SignalProcessing（SCI三區(qū)）、電子學(xué)報(bào)（中、英文版）等國際、國內(nèi)權(quán)威期刊和會(huì)議上發(fā)表論文15篇，其中SCI檢索6篇，EI檢索9篇，在重要期刊上發(fā)表教學(xué)論文一篇。主持國家博士后科學(xué)基金、陜西省博士后科學(xué)基金、陜西師范大學(xué)中央高校基本科研業(yè)務(wù)費(fèi)、西安電子科技大學(xué)優(yōu)秀博士學(xué)位論文資助基金、陜西師范大學(xué)青年基

3、金各一項(xiàng)，以第三完成人參與國家自然科學(xué)基金、博士點(diǎn)基金等多項(xiàng)科研項(xiàng)目。授權(quán)專利三項(xiàng)，獲得陜西省科學(xué)技術(shù)獎(jiǎng)一等獎(jiǎng)（第三完成人）一項(xiàng)，陜西省自然科學(xué)優(yōu)秀學(xué)術(shù)論文二等獎(jiǎng)（第一完成人）一項(xiàng)。2該單元的教學(xué)目標(biāo)2.1 單元內(nèi)容概要第9章查找第3節(jié)哈希表2.2 知識與技能目標(biāo)(1)深刻理解哈希查找與順序查找、折半查找的本質(zhì)區(qū)別(2)掌握哈希查找的原理；(3)掌握哈希表構(gòu)造過程；(4)理解哈希函數(shù)設(shè)計(jì)思想和沖突處理方法；(5)理解面對不同類型的查找對象，關(guān)鍵字類型不同，哈希函數(shù)的設(shè)計(jì)方法不同；(6)培養(yǎng)學(xué)生活躍的思維能力，能靈活運(yùn)用哈希函數(shù)進(jìn)行信息查找。2.3 過程與方法目標(biāo)通過對大數(shù)據(jù)時(shí)代的介紹，分析順序

4、查找、折半查找方法的缺陷以及哈希查找的優(yōu)勢，引入實(shí)例學(xué)習(xí)哈希表建立和基于哈希表進(jìn)行查詢的邏輯思路。通過對哈希表建立過程的分析，學(xué)習(xí)和掌握其存在的沖突和如何解決沖突的邏輯思路。2.4 情感態(tài)度與價(jià)值觀目標(biāo)體驗(yàn)數(shù)據(jù)結(jié)構(gòu)這門課程的內(nèi)涵及魅力，產(chǎn)生對程序設(shè)計(jì)的求知欲，形成積極主動(dòng)地學(xué)習(xí)算法與程序設(shè)計(jì)的態(tài)度；2)從分析數(shù)據(jù)的特定關(guān)系和算法性能兩個(gè)方面，使學(xué)生逐步養(yǎng)成嚴(yán)謹(jǐn)、科學(xué)的程序設(shè)計(jì)思想，并樹立實(shí)踐是檢驗(yàn)真理之唯一標(biāo)準(zhǔn)的價(jià)值觀。3學(xué)生特點(diǎn)分析3.1 教學(xué)對象的知識基礎(chǔ)本課程的教學(xué)對象為計(jì)算機(jī)科學(xué)學(xué)院各專業(yè)二年級本科學(xué)生，該課程所需的前導(dǎo)課程：C/C+程序設(shè)計(jì)、離散數(shù)學(xué)等均已學(xué)習(xí)完畢。因此，教學(xué)對象已具

5、備本課程所需的基礎(chǔ)知識。在本單元內(nèi)容學(xué)習(xí)之前，該班學(xué)生已經(jīng)學(xué)習(xí)了有關(guān)數(shù)組、順序查找和折半查找的相關(guān)原理和知識，經(jīng)過課后作業(yè)以及實(shí)驗(yàn)的驗(yàn)證，說明同學(xué)們已經(jīng)初步掌握了相關(guān)知識節(jié)點(diǎn)，上一單元的教學(xué)目標(biāo)基本完成，為本單元的知識學(xué)習(xí)奠定了基礎(chǔ)。3.2 教學(xué)對象的認(rèn)知特點(diǎn)根據(jù)培養(yǎng)計(jì)劃，本課程開設(shè)時(shí)間為第二學(xué)年的第一學(xué)期。2012級學(xué)生在學(xué)習(xí)本課程以前，已經(jīng)學(xué)習(xí)了如C、C+等多門程序設(shè)計(jì)語言，但往往編寫的程序依然停留在課本的習(xí)題水平，而這些習(xí)題僅僅是對程序設(shè)計(jì)語言中某個(gè)或者某幾個(gè)語法點(diǎn)的測試，要想利用程序設(shè)計(jì)語言設(shè)計(jì)和實(shí)現(xiàn)相應(yīng)的程序以解決實(shí)際問題，還需要掌握數(shù)據(jù)結(jié)構(gòu)以及建立在數(shù)據(jù)結(jié)構(gòu)之上的算法，學(xué)生對數(shù)據(jù)結(jié)

6、構(gòu)這門課程充滿興趣和期待。另一方面，大學(xué)生樂于接受新事物，不拘泥于舊事物和方法，能容納不同觀念，善于根據(jù)情況變化而改變認(rèn)知策略，在認(rèn)知過程中表現(xiàn)出比較好的靈活性。3.3 教學(xué)對象的學(xué)習(xí)風(fēng)格基于前期課程教學(xué)過程中的觀察和分析，根據(jù)學(xué)生先入為主的認(rèn)知特點(diǎn)，宜采用對比和實(shí)驗(yàn)開發(fā)為主的學(xué)習(xí)風(fēng)格。在教學(xué)活動(dòng)的設(shè)計(jì)中專門安排了類比實(shí)例的分析，通過學(xué)生具體操作的方式來理解掌握該單元教學(xué)內(nèi)容。4教學(xué)重點(diǎn)、難點(diǎn)及處理措施由于數(shù)據(jù)結(jié)構(gòu)內(nèi)容抽象而復(fù)雜，本課程采用了國內(nèi)知名大學(xué)采用較多的教材，在講述各種數(shù)據(jù)機(jī)構(gòu)基本思想和基本知識的基礎(chǔ)上，強(qiáng)調(diào)實(shí)踐環(huán)節(jié)，使學(xué)生在學(xué)習(xí)過程中充滿興趣和挑戰(zhàn)，尤其是把課堂內(nèi)容與配套實(shí)驗(yàn)相結(jié)合

7、，使學(xué)生真正做到理論聯(lián)系實(shí)際，強(qiáng)化學(xué)生解決各種實(shí)際問題的能力。4.1 教學(xué)重點(diǎn)及處理措施本單元教學(xué)重點(diǎn)為：哈希查找過程，為講解并讓學(xué)生掌握該知識點(diǎn)，在教學(xué)過程中通過總體概述、重點(diǎn)指出、重復(fù)講解、加強(qiáng)記憶的方式幫助同學(xué)們掌握其概念和原理。并以實(shí)例說明整個(gè)哈希查找原理及理論。4.2 教學(xué)難點(diǎn)及處理措施第一，哈希函數(shù)設(shè)計(jì)和沖突處理是本單元教學(xué)內(nèi)容的難點(diǎn)。在課堂講解時(shí)，處理措施是通過實(shí)例與啟發(fā)相結(jié)合的方式，幫助同學(xué)們理解和記憶。第二，數(shù)據(jù)如何被哈希表合理地管理起來，相應(yīng)的解決方法是通過多媒體課件動(dòng)畫讓學(xué)生實(shí)時(shí)觀察數(shù)據(jù)的變化情況。5教學(xué)內(nèi)容及教學(xué)活動(dòng)的描述5.1 教學(xué)組織形式本節(jié)課的教學(xué)組織形式主要包括

8、課堂的理論教學(xué)、基于實(shí)例的類比分析，與學(xué)生的課堂互動(dòng)，以及課后實(shí)驗(yàn)指導(dǎo)和學(xué)生須在課后完成的思考題和作業(yè)。5.2 教師的活動(dòng)教師的活動(dòng)主要包括課堂上的知識講解、提問及互動(dòng)，以及課后的實(shí)驗(yàn)指導(dǎo)和作業(yè)批改。5.3 學(xué)生的活動(dòng)學(xué)生的活動(dòng)主要包括課堂上認(rèn)真聽講，回答教師提出的問題并進(jìn)行課堂互動(dòng)，以及課后需要完成的思考題和作業(yè)。5.4 教學(xué)內(nèi)容及教學(xué)活動(dòng)的詳細(xì)安排表1教學(xué)內(nèi)容及教學(xué)活動(dòng)教學(xué)過程導(dǎo)入（共10分鐘）教師活動(dòng)學(xué)生活動(dòng)1.復(fù)習(xí)查找的概念，順序查找和折半查找的思想，通過對大數(shù)據(jù)時(shí)代的介紹和前兩種查找方式的缺點(diǎn)引入哈希查找。2,使學(xué)生明確本節(jié)的學(xué)習(xí)目的，激發(fā)學(xué)習(xí)動(dòng)力和興趣。新課（共35分鐘）1 .明確

9、今天的學(xué)習(xí)內(nèi)容；2 .講授新課內(nèi)容；1 .用動(dòng)態(tài)圖回顧上次課學(xué)習(xí)的順序查找和折半查找。（3分鐘）2 .提問學(xué)生相關(guān)要點(diǎn)；（1分鐘）3 .分析順序查找和折半查找的局限性，引出今天的課程內(nèi)容：Hash查找。（6分鐘）顯示教學(xué)目標(biāo)、教學(xué)內(nèi)容，并講解：1.內(nèi)容提綱：第9章:查找第3節(jié)哈希表使用哈希查找的背景哈希查找過程哈希查找中的沖突問題1:使用哈希查找的背景（5分鐘）大數(shù)據(jù)：互聯(lián)網(wǎng)中數(shù)據(jù)量過百億；增加速度驚人；維數(shù)災(zāi)難：信息不局限于單個(gè)數(shù)字，多樣化，蘊(yùn)含信息豐富；2:哈希查找過程（15分鐘）存儲過程：設(shè)計(jì)哈希函數(shù),根據(jù)哈希函數(shù)建立哈希表，實(shí)現(xiàn)信息儲存；查找過程：根據(jù)哈希函數(shù)將待查找信息映射為其對應(yīng)的

10、存儲單元，直接獲取信息。3:哈希查找中的沖突問題（10分鐘）不同查詢內(nèi)容可能會(huì)對應(yīng)相同哈希值，使得數(shù)據(jù)儲存單元發(fā)生沖突，解決方式兩類：重新查找空閑位置；重新組織沖突信息，啟發(fā)學(xué)生學(xué)習(xí)這兩類方法回顧前面內(nèi)容，回答教師提問觀看圖片演示，聽講解根據(jù)老師的舉例和課件的動(dòng)態(tài)演示，理解記憶哈希表的結(jié)構(gòu)和哈希查找的思想。通過提問使學(xué)生參與到?jīng)_突處理中，通過回答問題使學(xué)生積極思考解決方案。三、總結(jié)(共5分鐘)1 .學(xué)生回顧本堂課所學(xué)知識；2 .針對本節(jié)內(nèi)容提出疑問，并由教師解答；3 .課后完成思考問題，并預(yù)習(xí)下節(jié)課程的內(nèi)容。本節(jié)課通過具體實(shí)例，學(xué)習(xí)了哈希查找的思想。布置課后思考問題：啟發(fā)學(xué)生將哈希查找應(yīng)用于電

11、話簿查找(5分鐘)，難點(diǎn)在于：電話簿的關(guān)鍵字是字符而不是數(shù)字，要編碼；首字符重復(fù)率高；6教學(xué)媒體的選擇和使用方法6.1 課堂教學(xué)課堂教學(xué)采用傳統(tǒng)板書和現(xiàn)代多媒體技術(shù)相結(jié)合的方法。具體選擇和實(shí)施如下：(1)在基礎(chǔ)知識講解時(shí)，利用多媒體軟件MicrosoftOfficePowerPoint制作的課件，在短時(shí)間內(nèi)有條理、有層次地呈現(xiàn)大信息量；(2)在過程講解中利用傳統(tǒng)板書和學(xué)生紙筆記錄的方式跟蹤協(xié)議的交互和變化過程；(3)借助激光筆或MicrosoftOfficePowerPoint中提供的符號筆跟蹤講解焦點(diǎn)，幫助學(xué)生跟蹤老師講解過程；(4)在程序?qū)嵗v解和演示時(shí)，利用MicrosoftOffice

12、PowerPoint中提供的動(dòng)畫功能，形象地展現(xiàn)協(xié)議交互的實(shí)際變化過程。6.2 配套實(shí)驗(yàn)數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)課在學(xué)院智能信息處理實(shí)驗(yàn)室進(jìn)行，保證每個(gè)學(xué)生可以有一臺獨(dú)立操作的計(jì)算機(jī)，學(xué)生按照本單元配套的實(shí)驗(yàn)進(jìn)行理論驗(yàn)證和實(shí)踐練習(xí)。實(shí)驗(yàn)中有疑問，教師予以講解指導(dǎo)。7教學(xué)反思與自我評價(jià)該教學(xué)單元的突出特點(diǎn)：教學(xué)內(nèi)容體現(xiàn)在選取合適的數(shù)據(jù)結(jié)構(gòu)來存儲數(shù)據(jù)，并基于此查找數(shù)據(jù)。因此，應(yīng)讓學(xué)生充分體會(huì)到不同查找方法的優(yōu)缺點(diǎn)，以及海量數(shù)據(jù)查找中哈希查找的優(yōu)勢，引導(dǎo)學(xué)生設(shè)計(jì)適用于不同背景的哈希函數(shù)。以往教學(xué)的反思：大部分學(xué)生在學(xué)習(xí)完該課程后，雖然掌握了不少數(shù)據(jù)結(jié)構(gòu)知識，但是以至于還是無動(dòng)手能力差，在面對實(shí)際問題時(shí)，不知如何

13、將它們應(yīng)用到具體的程序設(shè)計(jì)中,法處理并解決實(shí)際問題。由于該課程的抽象性、復(fù)雜性，如何能在有限的課時(shí)內(nèi)，使學(xué)生掌握數(shù)據(jù)結(jié)構(gòu)的思想，并且靈活將其運(yùn)用到程序設(shè)計(jì)開發(fā)中，是這門課程教學(xué)實(shí)踐中的主要問題。改進(jìn)方法：1）課堂講授突出某種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)和工作原理而不是僅僅羅列出其概念和定義，重要或者難以理解的知識點(diǎn)選擇合適的案例輔助理解。2）重視實(shí)踐環(huán)節(jié)，做到課堂教學(xué)和實(shí)驗(yàn)教學(xué)緊密結(jié)合。通過同步實(shí)驗(yàn)，使學(xué)生深入領(lǐng)會(huì)數(shù)據(jù)結(jié)構(gòu)的功能和作用，理解程序的設(shè)計(jì)、運(yùn)行機(jī)理，加深對數(shù)據(jù)結(jié)構(gòu)的認(rèn)識。通過實(shí)驗(yàn)教學(xué)，幫助學(xué)生理解和消化課堂內(nèi)容，培養(yǎng)自主學(xué)習(xí)的能力，為今后在專業(yè)領(lǐng)域中用計(jì)算機(jī)解決問題打下扎實(shí)基礎(chǔ)。8板書設(shè)計(jì)或課件

14、8.1本單元課件本單元課件詳見附件。8.3輔助學(xué)生學(xué)習(xí)的課件或材料1）國家精品課程數(shù)據(jù)結(jié)構(gòu)，網(wǎng)址為2）教育部-微軟精品教育課程項(xiàng)目數(shù)據(jù)結(jié)構(gòu)與算法，網(wǎng)址為：3）北京市暨國家精品課程數(shù)據(jù)結(jié)構(gòu)與算法，網(wǎng)址為O9教學(xué)改革（1）傳統(tǒng)的教學(xué)模式：傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)課程教學(xué)采用課堂講授、布置作業(yè)及實(shí)驗(yàn)，這種“教本位”的教學(xué)模式強(qiáng)調(diào)教師是課堂的中心，注重教的原發(fā)性和主動(dòng)性，忽視了學(xué)生的主體性，師生之間缺少互動(dòng)，學(xué)生的主觀能動(dòng)性沒有被激發(fā)出來。加之課堂時(shí)間限，只能傳授基本知識點(diǎn)，學(xué)生一直是在考試體制的管制下學(xué)習(xí)的，因此學(xué)習(xí)不主動(dòng)、教學(xué)效果不明顯，部分學(xué)生對實(shí)踐環(huán)節(jié)不夠重視，導(dǎo)致學(xué)生在上機(jī)時(shí)不會(huì)融會(huì)貫通，缺乏獨(dú)立解決

15、問題的能力。與以往傳統(tǒng)教學(xué)相比，本節(jié)教學(xué)內(nèi)容和方法的新穎之處在于：第一，強(qiáng)調(diào)結(jié)構(gòu)的工作原理而不僅僅是其概念和定義。首先，分析問題，根據(jù)問題的特點(diǎn)，選取合適的數(shù)據(jù)結(jié)構(gòu)，再進(jìn)行實(shí)例的講解和演示；第二，在教學(xué)過程中采用啟發(fā)式教學(xué)，包括對新知識的引入和講授，注重學(xué)生的主動(dòng)參與，引導(dǎo)學(xué)生得出正確的結(jié)論。（2）本課程的教學(xué)改革：1）教學(xué)內(nèi)容，充分結(jié)合前導(dǎo)課程C語言，各種數(shù)據(jù)結(jié)構(gòu)的邏輯模型的教授必須最終以程序代碼編制成為可以運(yùn)行的程序?yàn)樽罱K目標(biāo)，使學(xué)生不僅在理論層次了解數(shù)據(jù)結(jié)構(gòu)，而且能夠在程序的實(shí)際運(yùn)行中感受數(shù)據(jù)結(jié)構(gòu)在程序設(shè)計(jì)和實(shí)現(xiàn)方面的作用。2）教學(xué)方法，注重理論和實(shí)踐相結(jié)合，強(qiáng)調(diào)實(shí)踐環(huán)節(jié)。實(shí)驗(yàn)課制定了驗(yàn)

16、證性實(shí)驗(yàn)、設(shè)計(jì)性實(shí)驗(yàn)和大作業(yè)三類。將學(xué)生分成討論小組，選擇合適的內(nèi)容讓學(xué)生自己討論講解。從不同方面培養(yǎng)學(xué)生的動(dòng)手實(shí)踐能力和團(tuán)隊(duì)協(xié)作能力。3）在教學(xué)過程中使用啟發(fā)式教學(xué)。由于本課程是一門邏輯性強(qiáng)、知識內(nèi)在聯(lián)系緊密的課程，通過該教學(xué)方法能改變傳統(tǒng)的一講到底的方式，講到一定程度便提出一些思考性和概念性強(qiáng)的問題，讓學(xué)生自己學(xué)會(huì)分析、研究和討論，引導(dǎo)學(xué)生得出正確的結(jié)論，充分發(fā)揮學(xué)生的主體地位。4）改變成績考核體系，采用結(jié)構(gòu)化評分方法，筆試占60%,實(shí)驗(yàn)占20%,平時(shí)成績占20%。附件1：本單元內(nèi)容的PPT課件本科專業(yè)必修課程哈希查找?授課名稱：數(shù)據(jù)結(jié)構(gòu)?授課教師：肖冰計(jì)用in科學(xué)學(xué)睛本節(jié)主要內(nèi)容?o使用

17、哈希查找的背景哈希查找中的沖突問題顧II順序查找51319213756647580889288順序查找折半查找51319213756647580889288tttLowMidHigh使用哈希查詢的背景日增長3.5億為2500億即增長904超過100億幅圖片幅圖片標(biāo)新浪堤博Wei&D,CWTTWeb4.0版ebookOb3i0州桃eSJP爾口LJ"marhcntdHhd-MUHf9NL信息語義LghSer聞巾i.SeaKhi而二w的2沁做她干出.q1H需求FTPDfttWiy-(MSIg3-"WebFaceboo曲戶產(chǎn)生內(nèi)容，創(chuàng)造超過40億幅圖片EMiiFTPIRCU

18、5OIETPCiFb加上fPC19N雅虎提供靜態(tài)的導(dǎo)航信息Googl吩析用戶搜索信息，滿足用戶需求?維數(shù)災(zāi)難社會(huì)關(guān)系語義解決途徑一哈希查找避免比較?存儲過程4700口合-構(gòu)造哈希表Num3哈希查找構(gòu)造哈希表3哈希函數(shù)：H(Number)=Numbermod701插入新的記錄580625685mod70700Number155778322NumNumber155778322012345Number281942902Number233667136Number580625685AkH(Number)=Numbermod701H(Number)=Numbermod701?出現(xiàn)沖突，如何處理？尋找空閑位置沖突信息再組織0123457