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

《數(shù)據(jù)結(jié)構(gòu)與算法》理論教學(xué)大綱(DataStructureandAlgorithm)課程代碼：0610009總學(xué)時：80學(xué)時(其中：講課50學(xué)時、實驗30學(xué)時)先修課程：《C語言程序設(shè)計》、《離散數(shù)學(xué)》一、課程的性質(zhì)、目的與任務(wù)《數(shù)據(jù)結(jié)構(gòu)與算法》是數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)、計算機科學(xué)與技術(shù)專業(yè)的一門重要專業(yè)基礎(chǔ)課，是計算機及相關(guān)學(xué)科的公認(rèn)主干課。計算機科學(xué)各領(lǐng)域及有關(guān)的系統(tǒng)和應(yīng)用軟件都要用到各種數(shù)據(jù)結(jié)構(gòu)。本課程是數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)、計算機科學(xué)與技術(shù)專業(yè)的專業(yè)課，主要介紹用計算機解決一系列問題，特別是非數(shù)值計算類問題時所用的各種數(shù)據(jù)組織方法、存儲結(jié)構(gòu)，以及在各種結(jié)構(gòu)上執(zhí)行的主要操作。通過本課程的學(xué)習(xí)，要使學(xué)生熟練地掌握數(shù)據(jù)結(jié)構(gòu)的內(nèi)在邏輯關(guān)系及其在計算機中的表示方法(存儲結(jié)構(gòu))，以及有關(guān)基本操作的算法實現(xiàn)；熟悉它們在計算機科學(xué)中的基本應(yīng)用；培養(yǎng)和訓(xùn)練學(xué)生結(jié)合實際應(yīng)用，根據(jù)求解的問題合理選擇數(shù)據(jù)結(jié)構(gòu)、應(yīng)用高級語言編寫和實現(xiàn)結(jié)構(gòu)清晰、正確易讀的有效算法的能力；并為學(xué)習(xí)《操作系統(tǒng)》、《編譯原理》、《數(shù)據(jù)庫原理》等后續(xù)課程和研制開發(fā)各種系統(tǒng)和應(yīng)用軟件打下扎實的理論和實踐基礎(chǔ)。二、教學(xué)基本內(nèi)容與基本要求.基本內(nèi)容本課程主要教學(xué)基本內(nèi)容包括：線性表、棧與隊列、串、數(shù)組和廣義表、樹和二叉樹、圖、查找表、內(nèi)部排序等。每種數(shù)據(jù)結(jié)構(gòu)都要介紹數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)定義和物理存儲實現(xiàn)以及該數(shù)據(jù)結(jié)構(gòu)的主要應(yīng)用。.基本要求通過本課程的學(xué)習(xí)，要求學(xué)生了解數(shù)據(jù)結(jié)構(gòu)及其分類、數(shù)據(jù)結(jié)構(gòu)與算法的密切關(guān)系；熟悉各種基本數(shù)據(jù)結(jié)構(gòu)及其操作，學(xué)會根據(jù)實際問題要求來選擇數(shù)據(jù)結(jié)構(gòu)；掌握設(shè)計算法的步驟和算法分析方法；掌握數(shù)據(jù)結(jié)構(gòu)在排序和查找等常用算法中的應(yīng)用。三、教學(xué)內(nèi)容及學(xué)時分配

教學(xué)內(nèi)容教學(xué)要求重點(☆)難點(△)學(xué)時安排備注第一章緒論1、什么是數(shù)據(jù)結(jié)構(gòu)B☆2、基本概念和術(shù)語B33、抽象數(shù)據(jù)類型的表示與實現(xiàn)AA4、算法與算法分析A☆A(yù)第二章線性表1、線性表的類型定義A☆A(yù)2、線性表的順序表示與實現(xiàn)AA63、線性表的鏈?zhǔn)奖硎九c實現(xiàn)AA4、一元多項式的表示及相加C第三章棧和隊列1、棧A☆A(yù)2、棧的應(yīng)用舉例BA53、棧與遞歸的實現(xiàn)C4、隊列A☆A(yù)第四章串1、串類型的定義CA2、串的表示與實現(xiàn)A☆A(yù)33、串的模式匹配算法B☆4、串操作應(yīng)用舉例第五章數(shù)組與廣義表1、數(shù)組的定義C2、數(shù)組的順序表示與實現(xiàn)BAr3、矩陣的壓縮存儲A☆A(yù)u4、廣義表的定義B5、廣義表的存儲結(jié)構(gòu)BA第六章樹和二叉樹1、樹的定義和基本術(shù)語C2、二叉樹AAQ3、遍歷二叉樹和線索二叉樹A☆A(yù)O4、樹和森林B5、赫夫曼樹及其應(yīng)用AA

（教學(xué)要求：A一熟練掌握；B一掌握；C—了解）四、建議實驗項目及學(xué)時分配第七章圖1、圖的定義和術(shù)語BA2、圖的存儲結(jié)構(gòu)AA3、圖的遍歷AA94、圖的連通性問題B☆A(yù)5、有向無環(huán)圖及其應(yīng)用B☆A(yù)6、最短路徑B☆A(yù)第八章查找1、靜態(tài)查找表AA52、動態(tài)查找表B☆A(yù)3、哈希表AA第九章內(nèi)部排序1、概述C2、插入排序AA3、快速排序B☆A(yù)64、選擇排序AA5、歸并排序B☆A(yù)6、基數(shù)排序BA合計55序a實驗項目名稱實驗學(xué)時內(nèi)容提要實驗要求實驗類型1單鏈表的建立、插入和刪除3掌握線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)操作算法必做驗證2棧的建立、入棧和出棧2掌握棧的操作算法必做驗證3隊列的建立、入隊和出隊3掌握隊列的操作算法必做驗證4模式串的匹配3掌握串的模式匹配算法必做驗證5稀疏矩陣的轉(zhuǎn)置2掌握稀疏矩陣轉(zhuǎn)置的操作算法必做驗證6二叉樹操作3掌握用指針類型描述、訪問和處理二叉樹的操作算法必做驗證7圖的最小生成樹5掌握圖的最小生成樹算法必做驗證8直接插入排序3掌握直接插入排序操作算法必做驗證9哈夫曼編碼/譯碼器6完成一個大作業(yè)，利用哈夫曼樹的知識來設(shè)計，并在VisualC++6.0環(huán)境下實現(xiàn)必做綜合合計30五、教學(xué)方法與教學(xué)手段.教學(xué)方法：在重視課堂講授的同時，加強實驗教學(xué)，培養(yǎng)學(xué)生的實際應(yīng)用能力及實踐能力。在課堂教學(xué)中采用啟發(fā)式、討論式、參與式等教學(xué)方法，調(diào)動學(xué)生的積極性和學(xué)習(xí)興趣，提高教學(xué)質(zhì)量，促進教學(xué)相長。.教學(xué)手段：利用多媒體、CAI課件等現(xiàn)代化教學(xué)手段，提高課堂教學(xué)水平。采取講練結(jié)合、理論聯(lián)系實際等方式，提高課堂教學(xué)效果。六、建議教材與參考書目.建議教材：①《數(shù)據(jù)結(jié)構(gòu)》，嚴(yán)蔚敏、吳偉民編著，清華大學(xué)出版社，2008年3月。②《數(shù)據(jù)結(jié)構(gòu)題集》，嚴(yán)蔚敏，吳偉民編著，清華大學(xué)出版社，2004年7月。.參考書目：①《數(shù)據(jù)結(jié)構(gòu)實踐教程》，胡元義等編著，西安電子科技大學(xué)出版社，2002年。②《數(shù)據(jù)結(jié)構(gòu)算法設(shè)計指導(dǎo)》，胡學(xué)鋼編著，清華大學(xué)出版社，1999年2月。③《數(shù)據(jù)結(jié)構(gòu)》，黃劉生，唐策善編著，中國科學(xué)技術(shù)大學(xué)出版社，2000年8月。④《數(shù)據(jù)結(jié)構(gòu)》，王曉東編著，電子工業(yè)出版社，2007年7月。七、大綱編寫的依據(jù)與說明本課程教學(xué)大綱，是根據(jù)數(shù)據(jù)科學(xué)與大數(shù)據(jù)技術(shù)專業(yè)培養(yǎng)目標(biāo)，向計算機軟件方向拓展的要求，結(jié)合本課程的性