1、上海交通大學(xué)網(wǎng)絡(luò)教育學(xué)院算法與數(shù)據(jù)結(jié)構(gòu)學(xué)位課程大綱一、基本信息1、教材名稱:推薦教材:嚴(yán)蔚敏等編數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言版清華大學(xué)出版社參考教材:1、嚴(yán)蔚敏等編數(shù)據(jù)結(jié)構(gòu)習(xí)題集(C語(yǔ)言版清華大學(xué)出版社5、傅清祥等編算法與數(shù)據(jù)結(jié)構(gòu)電子工業(yè)出版社2、考試題型及分值:選擇題20分,填空題20分,操作題40分,算法設(shè)計(jì)題20分3、考試形式:閉卷4、考試時(shí)間:2小時(shí)二、課程內(nèi)容情況(一課程內(nèi)容簡(jiǎn)介本課程是計(jì)算機(jī)專業(yè)的核心課程之一,是計(jì)算機(jī)專業(yè)的學(xué)生進(jìn)行軟件開發(fā)的重要基礎(chǔ)。其主要任務(wù)是:學(xué)習(xí)算法設(shè)計(jì)與分析的基本知識(shí),各種基本數(shù)據(jù)結(jié)構(gòu)的特點(diǎn),了解數(shù)據(jù)結(jié)構(gòu)與算法的關(guān)系。使學(xué)生具有對(duì)數(shù)據(jù)結(jié)構(gòu)和算法的理解和使用能力,培養(yǎng)學(xué)

2、生設(shè)計(jì)有效的算法及數(shù)據(jù)結(jié)構(gòu)的基本能力。本課程要求學(xué)生掌握算法設(shè)計(jì)與分析的基本知識(shí)和基本概念,時(shí)間和空間復(fù)雜性的級(jí)別與評(píng)價(jià)方法,掌握如何設(shè)計(jì)一個(gè)有效的算法,如何選擇常用的數(shù)據(jù)結(jié)構(gòu),以及如何應(yīng)用抽象數(shù)據(jù)結(jié)構(gòu)類型進(jìn)行數(shù)據(jù)抽象,掌握高級(jí)語(yǔ)言對(duì)數(shù)據(jù)結(jié)構(gòu)及抽象數(shù)據(jù)類型的支持。(二重點(diǎn)內(nèi)容簡(jiǎn)介(1數(shù)據(jù)結(jié)構(gòu)與算法的基本概念(5%考核內(nèi)容:算法、算法正確性、復(fù)雜性算法的時(shí)間與空間復(fù)雜性級(jí)別數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)和表示、實(shí)現(xiàn);固有數(shù)據(jù)類型的特點(diǎn)抽象數(shù)據(jù)類型的說明、高級(jí)語(yǔ)言對(duì)抽象數(shù)據(jù)類型的支持考核要求:理解算法、算法正確性、復(fù)雜性的概念;了解算法的時(shí)間與空間復(fù)雜性級(jí)別及遞歸及循環(huán)程序設(shè)計(jì)的算法復(fù)雜性的求解及基礎(chǔ)理論;重

3、點(diǎn)掌握數(shù)據(jù)類型、數(shù)據(jù)結(jié)構(gòu)和表示、實(shí)現(xiàn)的概念;掌握抽象數(shù)據(jù)類型的說明、高級(jí)語(yǔ)言對(duì)抽象數(shù)據(jù)類型的支持。(2線性表、棧和隊(duì)列(25%考核內(nèi)容:順序分配、鏈接分配的表示及實(shí)現(xiàn);各種鏈表:單鏈、雙鏈、多鏈、循環(huán)鏈表;棧、隊(duì)列、雙向隊(duì)列的順序、鏈?zhǔn)奖硎炯捌渌惴◤?fù)雜度分析;表達(dá)式計(jì)算考核要求:熟練掌握順序分配、鏈接分配的表示及實(shí)現(xiàn)方法;熟練掌握各種鏈表:單鏈、雙鏈、多鏈、循環(huán)鏈表;理解棧、隊(duì)列、雙向隊(duì)列的順序、鏈?zhǔn)奖硎炯捌渌惴◤?fù)雜度分析;熟練掌握表達(dá)式計(jì)算原理。(3樹、二叉樹、森林(25%考核內(nèi)容:樹的基本概念、性質(zhì);二叉樹的基本概念、性質(zhì),二叉樹的存儲(chǔ)結(jié)構(gòu);二叉樹的各種遍歷方法、各種線索樹、最優(yōu)二叉樹及H

4、UFFUMAN算法;樹的存儲(chǔ)結(jié)構(gòu)、遍歷、樹與二叉樹的轉(zhuǎn)換森林的遍歷、森林與二叉樹的轉(zhuǎn)換考核要求:熟練掌握樹的基本概念、性質(zhì);熟練掌握二叉樹的基本概念、性質(zhì)、存儲(chǔ)結(jié)構(gòu);熟練掌握二叉樹的遍歷方法,各種線索二叉樹的方法、樹與二叉樹的轉(zhuǎn)換、最優(yōu)二叉樹的構(gòu)造方法及HUFFUMAN編碼方法;掌握樹及森林與二叉樹的轉(zhuǎn)換方法;掌握樹及森林的遍歷方法(4圖的各種操作及算法分析比較(20%考核內(nèi)容:圖的基本概念、性質(zhì)、存儲(chǔ)結(jié)構(gòu)遍歷:廣度優(yōu)先遍歷、深度優(yōu)先遍歷方法;連通分量的求法;最小生成樹、最短路徑;拓?fù)渑判颉㈥P(guān)鍵路徑的求法及實(shí)現(xiàn);考核要求:熟練掌握:圖的基本概念、性質(zhì)、存儲(chǔ)結(jié)構(gòu);熟練掌握:廣度優(yōu)先遍歷、深度優(yōu)先

5、遍歷方法;熟練掌握:廣度優(yōu)先生成樹、深度優(yōu)先生產(chǎn)樹、連通分量的求法;熟練掌握最小生成樹、最短路徑概念與方法;掌握拓?fù)渑判颉㈥P(guān)鍵路徑的求法。(5查找技術(shù)(13%考核內(nèi)容:順序查找、有序表的查找、索引順序查找、二分查找法及HASHING查找技術(shù);動(dòng)態(tài)查找:二叉排序樹;平衡二叉樹、B樹及B+樹的基本概念;查找速度的分析及比較、算法復(fù)雜性的級(jí)別。考核要求:熟練掌握順序查找、有序表的查找、二分查找法;熟練掌握動(dòng)態(tài)查找:二叉排序樹;了解索引順序查找、HASHING查找的基本技術(shù);掌握平衡二叉樹、B樹及B+樹的基本概念;理解查找速度的分析及比較、算法復(fù)雜性的級(jí)別。(6排序技術(shù)(12%考核內(nèi)容:插入排序、快速排序、堆及選擇排序、歸并排序、基數(shù)排序法;最好、最壞、平均排序的時(shí)間復(fù)雜性分析。考核要求:熟練掌握插入排序、快速排序、堆及選擇排序、歸并排序、基數(shù)排序法;了解最好、最