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

《算法與數(shù)據(jù)結(jié)構(gòu)》教學(xué)大綱課程英文名AlgorithmAnalysisandDataStructures課程代碼C0806Z12學(xué)分3．5總學(xué)時(shí)56理論學(xué)時(shí)40實(shí)驗(yàn)/實(shí)踐學(xué)時(shí)16課程類別學(xué)科基礎(chǔ)課課程性質(zhì)任選先修課程高等數(shù)學(xué)、線性代數(shù)、C語(yǔ)言程序設(shè)計(jì)、面向?qū)ο蟪绦蛟O(shè)計(jì)適用專業(yè)電子信息科學(xué)與技術(shù)開(kāi)課學(xué)院信息工程學(xué)院一、課程地位與課程目標(biāo)（一）課程地位本課程是電子信息科學(xué)與技術(shù)專業(yè)的一門重要的學(xué)科基礎(chǔ)選修課程。本課程應(yīng)用高等數(shù)學(xué)的微積分知識(shí)、線性代數(shù)的向量和矩陣的概念，在掌握C語(yǔ)言和面向?qū)ο蟪绦蛟O(shè)計(jì)基礎(chǔ)上，研究數(shù)據(jù)表示及數(shù)據(jù)處理，其任務(wù)主要是要求學(xué)生掌握常用數(shù)據(jù)結(jié)構(gòu)的基本概念及其不同的實(shí)現(xiàn)方法，通過(guò)系統(tǒng)學(xué)習(xí)能夠在不同存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)不同的運(yùn)算，并對(duì)算法設(shè)計(jì)進(jìn)行有效的分析，進(jìn)一步提升學(xué)生程序設(shè)計(jì)的能力。有助于學(xué)生獲取描述電子信息工程領(lǐng)域復(fù)雜工程問(wèn)題的工程基礎(chǔ)知識(shí)；求解電子信息工程問(wèn)題的模型，并對(duì)解決方法進(jìn)行評(píng)價(jià)；完成設(shè)計(jì)方案并分析闡明設(shè)計(jì)的合理性。由于是雙語(yǔ)教學(xué)，肯定有助于提高學(xué)生的專業(yè)英語(yǔ)能力，從而能夠就本專業(yè)的當(dāng)前熱點(diǎn)問(wèn)題發(fā)表自己的想法，進(jìn)行國(guó)際交流。同時(shí)，本課程為后續(xù)課程、畢業(yè)設(shè)計(jì)以及從事軟件開(kāi)發(fā)方面的工作打下堅(jiān)實(shí)的基礎(chǔ)。（二）課程目標(biāo)課程目標(biāo)畢業(yè)要求目標(biāo)分類1.掌握算法分析的數(shù)學(xué)基礎(chǔ)，具備對(duì)不同算法進(jìn)行運(yùn)行時(shí)間分析并比較其效率的能力。工程知識(shí)1.1問(wèn)題分析2.2理解分析2.掌握線性數(shù)據(jù)結(jié)構(gòu)原理與實(shí)現(xiàn)，具備對(duì)線性數(shù)據(jù)結(jié)構(gòu)在實(shí)際算法中的應(yīng)用能力。工程知識(shí)1.1問(wèn)題分析2.2分析應(yīng)用3.掌握非線性數(shù)據(jù)結(jié)構(gòu)原理與實(shí)現(xiàn)，具備對(duì)非線性數(shù)據(jù)結(jié)構(gòu)在實(shí)際算法中的應(yīng)用能力。工程知識(shí)1.1問(wèn)題分析2.2分析應(yīng)用4.理解各種排序算法原理與實(shí)現(xiàn)，具備比較不同排序算法運(yùn)行效率的能力。工程知識(shí)1.1問(wèn)題分析2.2分析評(píng)價(jià)5.理解和掌握專業(yè)英語(yǔ)詞匯，初步具備閱讀原版教科書(shū)、進(jìn)行國(guó)際交流的能力。溝通10.3記憶理解二、課程目標(biāo)達(dá)成的途徑與方法課程目標(biāo)教學(xué)環(huán)節(jié)對(duì)應(yīng)內(nèi)容課程目標(biāo)1講授第1、2章及作業(yè)實(shí)驗(yàn)一1.Introduction2.AlgorithmAnalysis課程目標(biāo)2講授第3章及作業(yè)實(shí)驗(yàn)二、實(shí)驗(yàn)三3.Lists,Stacks,andQueues課程目標(biāo)3講授第4章及作業(yè)實(shí)驗(yàn)八4.BinaryTrees課程目標(biāo)4講授第5章5.Sorting課程目標(biāo)5雙語(yǔ)講授所有章節(jié)，作業(yè)和考試用英語(yǔ)解答所有章節(jié)三、課程目標(biāo)與相關(guān)畢業(yè)要求的對(duì)應(yīng)關(guān)系課程目標(biāo)課程目標(biāo)對(duì)畢業(yè)要求的支撐程度（H、M、L）畢業(yè)要求1畢業(yè)要求2畢業(yè)要求10課程目標(biāo)1LH課程目標(biāo)2LH課程目標(biāo)3LH課程目標(biāo)4LH課程目標(biāo)5M四、課程主要內(nèi)容與基本要求1、IntroductionUnderstand:theneedfordatastructuresUnderstand:therelationshipbetweenabstractdatatypesanddatastructuresMaster:C++reviewCommand:mathematicalpreliminariessuchassetsandrecursion這部分是本課程的基礎(chǔ)部分，復(fù)習(xí)C++的基本概念，引入集合、遞歸等數(shù)學(xué)預(yù)備知識(shí)，為后續(xù)章節(jié)的學(xué)習(xí)做準(zhǔn)備。2、AlgorithmAnalysisCommand:thedefinitionofalgorithmanalysisUnderstand:thegrowthrateforanalgorithmCommand:best-case/worst-case/average-caseanalysisofanalgorithmMaster:big-Oh,big-Omega,andbig-ThetanotationsMaster:howtocalculatetherunningtimeofaprogram這部分是引入算法和算法分析的概念，并建立經(jīng)典的數(shù)學(xué)模型分析算法的時(shí)間復(fù)雜度。3、Lists,Stacks,andQueuesMaster:theADTforalistCommand:differentimplementationsforalistMaster:theADTforastackCommand:differentimplementationsforastackMaster:theADTforaqueueCommand:differentimplementationsforaqueue這部分是重點(diǎn)分析了三種基本的數(shù)據(jù)結(jié)構(gòu)（表、棧和隊(duì)列），詳細(xì)分析了其抽象數(shù)據(jù)類型和各種不同的實(shí)現(xiàn)方法，通過(guò)對(duì)各種算法的分析，能使學(xué)生熟悉程序設(shè)計(jì)的技巧。4、BinaryTreesMaster:definitionsandterminologyofabinarytreeCommand:binarytreetraversalsCommand:pointer-basedbinarytreenodeimplementationsMaster:binarysearchtreesUnderstand:AVLtrees這部分是重點(diǎn)分析了二叉樹(shù)結(jié)構(gòu)，詳細(xì)分析了其抽象數(shù)據(jù)類型和各種不同的實(shí)現(xiàn)方法，重點(diǎn)介紹了具有很強(qiáng)實(shí)用價(jià)值的AVL數(shù)結(jié)構(gòu)。通過(guò)對(duì)各種算法的分析，能使學(xué)生熟悉程序設(shè)計(jì)的技巧。5、SortingMaster:sortingterminologyandnotationCommand:insertionsort,bubblesort,andselectionsortCommand:shellsort,quicksort,mergesort,heapsortUnderstand:comparisonofsortingalgorithmsMaster:calculatetherunningtimeofaprogram這部分是詳細(xì)介紹了各種經(jīng)典的排序算法。在第二章的基礎(chǔ)上，對(duì)不同的排序算法進(jìn)行分析，能夠針對(duì)不同的應(yīng)用場(chǎng)合選擇最優(yōu)的算法。五、課程學(xué)時(shí)安排（與總學(xué)時(shí)數(shù)不符）章節(jié)號(hào)教學(xué)內(nèi)容學(xué)時(shí)數(shù)學(xué)生任務(wù)對(duì)應(yīng)課程目標(biāo)1Introduction6Exercises1.3,1.6課程目標(biāo)1課程目標(biāo)52AlgorithmAnalysis8（Include：2hours’lab.assignment）Exercises2.2,2.11課程目標(biāo)1課程目標(biāo)53Lists,Stacks,andQueues14（Include：6hours’lab.assignment）Exercises3.2,3.4,3.28課程目標(biāo)2課程目標(biāo)54BinaryTrees16（Include：4hours’lab.assignment）Exercises4.1,4.3,4.8,4.9課程目標(biāo)3課程目標(biāo)55Sorting4課程目標(biāo)4課程目標(biāo)5六、實(shí)踐環(huán)節(jié)及基本要求序號(hào)實(shí)驗(yàn)項(xiàng)目名稱學(xué)時(shí)基本要求學(xué)生任務(wù)實(shí)驗(yàn)性質(zhì)實(shí)驗(yàn)類別1Lab.Assignment1ApplicationofStructures—IntroductiontoVC++IDE2學(xué)會(huì)使用VC++IDE開(kāi)發(fā)應(yīng)用程序利用結(jié)構(gòu)存儲(chǔ)員工的工資、ID等，并進(jìn)行排序驗(yàn)證性必做2Lab.Assignment3ApplicationofaStack—Reversingaline2學(xué)會(huì)創(chuàng)建并使用棧結(jié)構(gòu)建立棧結(jié)構(gòu)，并應(yīng)用棧結(jié)構(gòu)實(shí)現(xiàn)一行字符的反向輸出設(shè)計(jì)性必做3Lab.Assignment2ApplicationofaLinkedList—AdditionofPolynomials4學(xué)會(huì)創(chuàng)建并使用鏈表建立鏈表，存儲(chǔ)兩個(gè)多項(xiàng)式，然后對(duì)兩個(gè)多項(xiàng)式進(jìn)行加法運(yùn)算綜合性必做4Lab.Assignment8Applicationofabinarytree—abinarytreeforStemma4學(xué)會(huì)創(chuàng)建并使用二叉樹(shù)建立二叉樹(shù)結(jié)構(gòu)，存儲(chǔ)家譜，并按層次結(jié)構(gòu)打印家譜綜合性必做七、考核方式、成績(jī)?cè)u(píng)定考核內(nèi)容考核方式評(píng)定標(biāo)準(zhǔn)（依據(jù)）占總成績(jī)比例過(guò)程考核含到課率、平時(shí)作業(yè)等點(diǎn)名記錄作業(yè)提交狀況及批改成績(jī)10%實(shí)驗(yàn)考核操作及實(shí)驗(yàn)報(bào)告操作成績(jī)報(bào)告批改成績(jī)20%期末考核閉卷卷面成績(jī)70%考核類別考查成績(jī)登記方式百分制八、推薦教材與主要參考書(shū)（一）推薦教材：1、MarkAllenWeiss.《DATASTRUCTURESANDALGORITHMANALYSISINC++》.FourthEdition，Pearson，2013年10月。2、CliffordA.Shaffer.《APRACTICALI