《數(shù)據(jù)結(jié)構(gòu)與算法》本科課程實驗大綱

PAGEPAGE21《數(shù)據(jù)結(jié)構(gòu)與算法》本科課程實驗大綱一、課程信息課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法課程代碼：ZX0240082課程類別：專業(yè)發(fā)展必修課程/必修適用專業(yè)：數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)課程性質(zhì)：實驗課（可帶實驗）課程學(xué)時：32課程學(xué)分：2先修課程：《Java程序設(shè)計》、《離散數(shù)學(xué)》等附屬實驗說明：見實驗課程大綱選用教材：《數(shù)據(jù)結(jié)構(gòu)與算法教程》(第5版),李春葆主編，清華大學(xué)出版社,2019年.主要參考書目：[1]《數(shù)據(jù)結(jié)構(gòu)與算法C語言版》(第1版)，程海英編著，清華大學(xué)出版社，2014年09.[2]《數(shù)據(jù)結(jié)構(gòu)與算法題集C語言版》(第1版)，嚴(yán)蔚敏吳偉民編著，清華大學(xué)出版社，2020.[3]《計算機軟件技術(shù)基礎(chǔ)（第3版）》，沈被娜、劉祖照等編著，清華大學(xué)出版社，2000年.[4]《軟件技術(shù)基礎(chǔ)》(第2版)，馮博琴等編著，清華大學(xué)出版社，2018年.[5]《實用數(shù)據(jù)結(jié)構(gòu)與算法》(第1版)，徐孝凱編著，清華大學(xué)出版社，2000年.[6]《數(shù)據(jù)結(jié)構(gòu)與算法與算法》(第1版)，許卓群等，高等教育出版社，2004年7月.二、課程目標(biāo)（一）目標(biāo)設(shè)置通過本課程的學(xué)習(xí)，使學(xué)生達(dá)到以下目標(biāo)：課程目標(biāo)1：了解《數(shù)據(jù)結(jié)構(gòu)與算法》的發(fā)展歷史，理解《數(shù)據(jù)結(jié)構(gòu)與算法》中的基本概念，熟練掌握《數(shù)據(jù)結(jié)構(gòu)與算法》中的基本方法，加強學(xué)生的運算和解題能力?！井厴I(yè)要求1工程知識】課程目標(biāo)2：掌握《數(shù)據(jù)結(jié)構(gòu)與算法》中的基本理論，培養(yǎng)學(xué)生的邏輯推理能力、抽象思維能力以及嚴(yán)謹(jǐn)?shù)挠嬎銠C語言表達(dá)能力，為學(xué)習(xí)后續(xù)課程以及進(jìn)一步獲得更高層次的計算機專業(yè)知識奠定系統(tǒng)的理論基礎(chǔ)?！井厴I(yè)要求2問題分析】課程目標(biāo)3：掌握《數(shù)據(jù)結(jié)構(gòu)與算法》中各類結(jié)構(gòu)存儲問題的構(gòu)造思想及算法，能運用計算機語言編寫相應(yīng)的程序并能夠在計算機上實現(xiàn)，培養(yǎng)學(xué)生借助計算機來解決各種計算機問題的能力，使學(xué)生具備一定的科學(xué)研究能力。【畢業(yè)要求3設(shè)計解決方案】課程目標(biāo)4：通過課前預(yù)習(xí)、課堂引導(dǎo)和啟發(fā)、上機實驗、課后作業(yè)等方式，激發(fā)學(xué)生探索與求知的欲望，培養(yǎng)學(xué)生自主學(xué)習(xí)的能力?！井厴I(yè)要求4研究工程問題】（二）課程目標(biāo)與畢業(yè)要求的關(guān)系1、課程目標(biāo)與畢業(yè)要求的對應(yīng)關(guān)系課程目標(biāo)支撐的畢業(yè)要求支撐的畢業(yè)要求指標(biāo)點課程目標(biāo)11.工程知識1.2能夠應(yīng)用工程原理和知識，分析并解決工程問題。課程目標(biāo)22.問題分析2.1擁有計算思維能力，能夠運用抽象思維進(jìn)行軟件系統(tǒng)的理論建模。課程目標(biāo)33.設(shè)計解決方案3.1掌握程序設(shè)計理論與方法，具備軟件開發(fā)技能。課程目標(biāo)44.研究工程問題4.1能夠運用數(shù)據(jù)科學(xué)的設(shè)計思路和基本原理，設(shè)計實驗，并對實驗結(jié)果進(jìn)行科學(xué)有效的分析。2、課程目標(biāo)與畢業(yè)要求的矩陣關(guān)系圖名稱工程知識問題分析設(shè)計解決方案研究工程問題3.14.1數(shù)據(jù)結(jié)構(gòu)與算法HHMM數(shù)據(jù)結(jié)構(gòu)與算法HMM課程目標(biāo)1H課程目標(biāo)2H課程目標(biāo)3M課程目標(biāo)4M三、課程內(nèi)容（一）課程內(nèi)容與課程目標(biāo)的關(guān)系課程內(nèi)容教法建議支撐的課程目標(biāo)學(xué)時安排算法的誤差與穩(wěn)定性基本概念及相關(guān)實驗數(shù)據(jù)分析講授法、演示法、驗證法、綜合法課程目標(biāo)1-42棧和隊列講授法、演示法、驗證法、綜合法課程目標(biāo)1-43線性表講授法、演示法、驗證法、綜合法課程目標(biāo)1-46字符串和數(shù)組講授法、演示法、驗證法、綜合法課程目標(biāo)1-44樹和二叉樹講授法、演示法、驗證法、綜合法課程目標(biāo)1-46圖講授法、演示法、驗證法課程目標(biāo)1-44內(nèi)排序講授法、演示法、驗證法、綜合法課程目標(biāo)1-46查找講授法、演示法、驗證法、綜合法課程目標(biāo)1-41合計32學(xué)時（二）具體內(nèi)容實驗一算法的誤差與穩(wěn)定性【學(xué)習(xí)目標(biāo)】掌握數(shù)據(jù)結(jié)構(gòu)與算法的概念，理解算法的穩(wěn)定性。能夠根據(jù)實際算法公式，寫出時間復(fù)雜度和空間復(fù)雜度的表示形式。【重點難點】利用計算機編程實現(xiàn)算法的時間復(fù)雜度和空間復(fù)雜度的表示形式。【學(xué)習(xí)內(nèi)容】計算機軟件的編程理論與技巧及完成算法的編程實現(xiàn)。時間復(fù)雜度和空間復(fù)雜度的理解?！緦嶒炓蟆繉嶒瀸傩裕壕C合型實驗；開出要求：必做；分組要求：1人1組；實驗準(zhǔn)備：（1）在開始本實驗之前，請回顧教科書的相關(guān)內(nèi)容；（2）需要安裝WindowsXPProfessional操作系統(tǒng)和計算機等計算機軟件的計算機。教師講授時長占本次課總學(xué)時的20%，學(xué)生操作時長占80%；學(xué)生平均完成本實驗項目的時長為2學(xué)時?！窘谭ńㄗh】結(jié)合多媒體課件，講授本次實驗課的學(xué)習(xí)內(nèi)容及重點難點。演示同類實驗題目的編程實現(xiàn)過程等。指導(dǎo)學(xué)生實驗操作?！舅伎纪卣埂坷糜嬎銠C軟件求解算法的時間復(fù)雜度。實驗二線性表【學(xué)習(xí)目標(biāo)】1.掌握順序表的基本思想和基本步驟，能夠根據(jù)實際問題選用適當(dāng)?shù)鼐€性表進(jìn)行實驗。2.掌握鏈表的基本思想和基本步驟，能夠根據(jù)實際問題選用適當(dāng)?shù)鼐€性表進(jìn)行實驗。3.理解兩種線性表之間的聯(lián)系與區(qū)別?！局攸c難點】1.掌握順序表、鏈表的基本思想和基本步驟，能夠根據(jù)實際問題選用適當(dāng)?shù)倪M(jìn)行實驗。2.理解兩種線性表之間的聯(lián)系與區(qū)別?！緦W(xué)習(xí)內(nèi)容】1.編程實現(xiàn)兩種線性表的基本思想和基本步驟。2.分析二者之間的區(qū)別和聯(lián)系。3.計算機軟件編程技巧。【實驗要求】1.實驗屬性：綜合型實驗；2.開出要求：必做；3.分組要求：1人1組；4.實驗準(zhǔn)備：（1）在開始本實驗之前，請回顧教科書的相關(guān)內(nèi)容；（2）需要安裝WindowsXPProfessional操作系統(tǒng)和計算機等計算機軟件的計算機。5.教師講授時長占本次課總學(xué)時的20%，學(xué)生操作時長占80%；6.學(xué)生平均完成本實驗項目的時長為3學(xué)時。【教法建議】1.結(jié)合多媒體課件，講授本次實驗課的學(xué)習(xí)內(nèi)容及重點難點。2.演示同類實驗題目的編程實現(xiàn)過程等。3.指導(dǎo)學(xué)生實驗操作。【思考拓展】利用計算機軟件的工具箱實驗題目進(jìn)行求解，并與上面的實驗結(jié)果進(jìn)行比較，會得到什么樣的結(jié)論？實驗三棧和隊列【學(xué)習(xí)目標(biāo)】1.掌握棧和隊列的基本思想和基本步驟。2.理解棧和隊的特征，并能自行編程求解對應(yīng)實際問題。3.比較二者的差別?！局攸c難點】理解棧和隊的特征，并能自行編程求解對應(yīng)實際問題?！緦W(xué)習(xí)內(nèi)容】1.棧和隊列的基本思想和基本步驟。2.理解棧和隊的特征，并能自行編程求解對應(yīng)實際問題。3.計算機軟件編程技巧?！緦嶒炓蟆?.實驗屬性：綜合型實驗；2.開出要求：必做；3.分組要求：1人1組；4.實驗準(zhǔn)備：（1）在開始本實驗之前，請回顧教科書的相關(guān)內(nèi)容；（2）需要安裝WindowsXPProfessional操作系統(tǒng)和計算機等計算機軟件的計算機。5.教師講授時長占本次課總學(xué)時的20%，學(xué)生操作時長占80%；6.學(xué)生平均完成本實驗項目的時長為6學(xué)時?！窘谭ńㄗh】1.結(jié)合多媒體課件，講授本次實驗課的學(xué)習(xí)內(nèi)容及重點難點。2.演示同類實驗題目的編程實現(xiàn)過程、數(shù)據(jù)整理、誤差分析等。3.指導(dǎo)學(xué)生實驗操作?！舅伎纪卣埂坷糜嬎銠C軟件的數(shù)據(jù)結(jié)構(gòu)與算法和算法進(jìn)行求解，并與上面的實驗結(jié)果進(jìn)行比較，會得到什么樣的結(jié)論？實驗四串和數(shù)組【學(xué)習(xí)目標(biāo)】1.掌握字符串的基本思想和基本步驟。2.掌握數(shù)組的基本思想和基本步驟。，并能自行編程求解。【重點難點】1.掌握字符串的基本思想和基本步驟。2.掌握數(shù)組的基本思想和基本步驟，并能自行編程求解。【學(xué)習(xí)內(nèi)容】1.掌握字符串的基本思想和基本步驟。2.編程實現(xiàn)一維數(shù)組、二維數(shù)組的基本原理和解決實際問題。3.計算機軟件編程技巧?！緦嶒炓蟆?.實驗屬性：綜合型實驗；2.開出要求：必做；3.分組要求：1人1組；4.實驗準(zhǔn)備：（1）在開始本實驗之前，請回顧教科書的相關(guān)內(nèi)容；（2）需要安裝WindowsXPProfessional操作系統(tǒng)和計算機等計算機軟件的計算機。5.教師講授時長占本次課總學(xué)時的20%，學(xué)生操作時長占80%；6.學(xué)生平均完成本實驗項目的時長為4學(xué)時?！窘谭ńㄗh】1.結(jié)合多媒體課件，講授本次實驗課的學(xué)習(xí)內(nèi)容及重點難點。2.演示同類實驗題目的編程實現(xiàn)過程、數(shù)據(jù)整理、誤差分析等。3.指導(dǎo)學(xué)生實驗操作?！舅伎纪卣埂孔孕胁殚嗁Y料對實驗題目利用最速下降法進(jìn)行求解，并與牛頓方法實驗結(jié)果進(jìn)行比較，會得到什么樣的結(jié)論？實驗五樹和二叉樹【學(xué)習(xí)目標(biāo)】1.掌握樹的基本思想和基本步驟。2.掌握二叉樹的基本思想和基本步驟，并能自行編程求解。3.理解遍歷方法對時間復(fù)雜度的影響?！局攸c難點】1.掌握樹的基本思想和基本步驟、編程實現(xiàn)。2.掌握二叉樹的基本思想和基本步驟、編程實現(xiàn)。3.對常見遍歷方法進(jìn)行對比?！緦W(xué)習(xí)內(nèi)容】1.樹的基本思想和基本步驟。2.二叉樹的基本思想和基本步驟和常見遍歷方法的比較分析。3.計算機軟件編程技巧?！緦嶒炓蟆?.實驗屬性：綜合型實驗；2.開出要求：必做；3.分組要求：1人1組；4.實驗準(zhǔn)備：（1）在開始本實驗之前，請回顧教科書的相關(guān)內(nèi)容；（2）需要安裝WindowsXPProfessional操作系統(tǒng)和計算機等計算機軟件的計算機。5.教師講授時長占本次課總學(xué)時的20%，學(xué)生操作時長占80%；6.學(xué)生平均完成本實驗項目的時長為6學(xué)時?！窘谭ńㄗh】1.結(jié)合多媒體課件，講授本次實驗課的學(xué)習(xí)內(nèi)容及重點難點。2.演示同類實驗題目的編程實現(xiàn)過程、數(shù)據(jù)整理、誤差分析等。3.指導(dǎo)學(xué)生實驗操作?！舅伎纪卣埂坷糜嬎銠C軟件進(jìn)行求解，并與上面的實驗結(jié)果進(jìn)行比較，會得到什么樣的結(jié)論？實驗六圖【學(xué)習(xí)目標(biāo)】1.掌握圖的基本思想和基本步驟。2.理解圖的表示形式，并能自行編程求解。3.了解圖在求解最短路徑問題中的應(yīng)用?！局攸c難點】1.掌握圖的基本思想和基本步驟，能夠根據(jù)實際問題選用適當(dāng)方法進(jìn)行實驗。2.理解追圖的表示形式，并能自行編程求。3.對求解最短路徑問題進(jìn)行編程實現(xiàn)。【學(xué)習(xí)內(nèi)容】1.圖的基本思想和基本步驟，求解最短路徑問題。2.精度分析與收斂性分析。3.計算機軟件編程技巧。【實驗要求】1.實驗屬性：綜合型實驗；2.開出要求：必做；3.分組要求：1人1組；4.實驗準(zhǔn)備：（1）在開始本實驗之前，請回顧教科書的相關(guān)內(nèi)容；（2）需要安裝WindowsXPProfessional操作系統(tǒng)和計算機等計算機軟件的計算機。5.教師講授時長占本次課總學(xué)時的20%，學(xué)生操作時長占80%；6.學(xué)生平均完成本實驗項目的時長為4學(xué)時?！窘谭ńㄗh】1.結(jié)合多媒體課件，講授本次實驗課的學(xué)習(xí)內(nèi)容及重點難點。2.演示同類實驗題目的編程實現(xiàn)過程、數(shù)據(jù)整理、誤差分析等。3.指導(dǎo)學(xué)生實驗操作?！舅伎纪卣埂勘容^線性方程組的迭代法和直接法，利用同一個實驗題目進(jìn)行驗證你的比較結(jié)果？實驗七內(nèi)部排序【學(xué)習(xí)目標(biāo)】1.掌握內(nèi)部排序的基本思想和基本步驟。2.理解各類排序方法的優(yōu)缺點，并能自行編程求解。3.掌握定量定性分析內(nèi)部排序的時間復(fù)雜度和空間復(fù)雜度。【重點難點】1.掌握內(nèi)部排序的基本思想和基本步驟。2.理解各類排序方法的優(yōu)缺點，并能自行編程求解。3.定量定性分析內(nèi)部排序的時間復(fù)雜度和空間復(fù)雜度?！緦W(xué)習(xí)內(nèi)容】1.各類內(nèi)部排序的基本思想和基本步驟。2.時間復(fù)雜度和空間復(fù)雜度分析。3.計算機軟件編程技巧?！緦嶒炓蟆?.實驗屬性：綜合型實驗；2.開出要求：必做；3.分組要求：1人1組；4.實驗準(zhǔn)備：（1）在開始本實驗之前，請回顧教科書的相關(guān)內(nèi)容；（2）需要安裝WindowsXPProfessional操作系統(tǒng)和計算機等計算機軟件的計算機。5.教師講授時長占本次課總學(xué)時的20%，學(xué)生操作時長占80%；6.學(xué)生平均完成本實驗項目的時長為6學(xué)時。?！窘谭ńㄗh】1.結(jié)合多媒體課件，講授本次實驗課的學(xué)習(xí)內(nèi)容及重點難點。2.演示同類實驗題目的編程實現(xiàn)過程、數(shù)據(jù)整理、誤差分析等。3.指導(dǎo)學(xué)生實驗操作。【思考拓展】利用計算機軟件進(jìn)行求解，并與上面的實驗結(jié)果進(jìn)行比較，會得到什么樣的結(jié)論？實驗八查找【學(xué)習(xí)目標(biāo)】1.掌握二分查找、哈希查找的基本思想和基本步驟。2.理解二分查找、哈希查找方法的優(yōu)缺點，并能自行編程求解。3.掌握定量定性分析二分查找、哈希查找的時間復(fù)雜度和空間復(fù)雜度?！局攸c難點】1.掌握二分查找、哈希查找的基本思想和基本步驟。2.理解二分查找、哈希查找方法的優(yōu)缺點，并能自行編程求解。3.定量定性分析二分查找、哈希查找的時間復(fù)雜度和空間復(fù)雜度?！緦W(xué)習(xí)內(nèi)容】1.各類二分查找、哈希查找的基本思想和基本步驟。2.時間復(fù)雜度和空間復(fù)雜度分析。3.計算機軟件編程技巧?！緦嶒炓蟆?.實驗屬性：綜合型實驗；2.開出要求：必做；3.分組要求：1人1組；4.實驗準(zhǔn)備：（1）在開始本實驗之前，請回顧教科書的相關(guān)內(nèi)容；（2）需要安裝WindowsXPProfessional操作系統(tǒng)和計算機等計算機軟件的計算機。5.教師講授時長占本次課總學(xué)時的20%，學(xué)生操作時長占80%；6.學(xué)生平均完成本實驗項目的時長為1學(xué)時?！窘谭ńㄗh】1.結(jié)合多媒體課件，講授本次實驗課的學(xué)習(xí)內(nèi)容及重點難點。2.演示同類實驗