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

1、“數(shù)據(jù)結(jié)構(gòu)與算法B”教學(xué)大綱“數(shù)據(jù)結(jié)構(gòu)與算法”是一門(mén)重要的計(jì)算機(jī)類(lèi)基礎(chǔ)課程。其主要目的是使學(xué)生較全面地理解數(shù)據(jù)結(jié)構(gòu)的概念、掌握各種數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)現(xiàn)方式，比較不同數(shù)據(jù)結(jié)構(gòu)和算法的特點(diǎn)。通過(guò)學(xué)習(xí)，使學(xué)生能夠提高用計(jì)算機(jī)解決實(shí)際問(wèn)題的能力。本課程注重?cái)?shù)據(jù)結(jié)構(gòu)與算法理論和實(shí)踐的結(jié)合，從問(wèn)題求解的角度指導(dǎo)學(xué)生學(xué)習(xí)如何運(yùn)用數(shù)據(jù)結(jié)構(gòu)與算法知識(shí)來(lái)應(yīng)用和解決實(shí)際問(wèn)題，為將來(lái)利用從事計(jì)算機(jī)相關(guān)的學(xué)習(xí)、研究和開(kāi)發(fā)工作打下扎實(shí)的基礎(chǔ)。本課程是“數(shù)據(jù)結(jié)構(gòu)與算法A”的替代課程，針對(duì)編程基礎(chǔ)較弱的學(xué)生，尤其是電子微電子專(zhuān)業(yè)的學(xué)生開(kāi)設(shè)。減少外排序和索引等知識(shí)點(diǎn)要求，注重?cái)?shù)據(jù)結(jié)構(gòu)與算法核心內(nèi)容的講解，同時(shí)安排助教加強(qiáng)對(duì)學(xué)生

2、上機(jī)實(shí)習(xí)的輔導(dǎo)，為學(xué)生將來(lái)利用計(jì)算機(jī)解決相關(guān)問(wèn)題打下一定的基礎(chǔ)。1課程基本情況學(xué)院設(shè)定課程編號(hào)01034340課程名稱(chēng)數(shù)據(jù)結(jié)構(gòu)與算法BData Structure And Algorithm B開(kāi)課時(shí)間一年級(jí)二年級(jí)三年級(jí)四年級(jí)秋春夏秋春夏秋春夏秋春夏適用院系信息學(xué)院編程能力不太強(qiáng)的學(xué)生課程定位骨干基礎(chǔ)課，必修課學(xué)分3學(xué)分總學(xué)時(shí)54學(xué)時(shí)先修課程計(jì)算引論，程序設(shè)計(jì)實(shí)習(xí)后續(xù)課程數(shù)據(jù)結(jié)構(gòu)與算法實(shí)習(xí)，程序設(shè)計(jì)語(yǔ)言原理教師設(shè)定教學(xué)方式以課堂講授為主，同時(shí)借助網(wǎng)絡(luò)教學(xué)平臺(tái)，拓展課堂講授的相關(guān)知識(shí)，便于同學(xué)自主學(xué)習(xí)、鞏固課堂所學(xué)內(nèi)容。考慮到選修B類(lèi)課程的學(xué)生編程能力較弱，會(huì)安排助教加強(qiáng)對(duì)學(xué)生上機(jī)實(shí)習(xí)的輔導(dǎo)。課

3、時(shí)分配 3(課堂教學(xué))+1（教學(xué)實(shí)驗(yàn)）/周考核方式平時(shí)(書(shū)面作業(yè)、課堂測(cè)試)20，上機(jī)(+報(bào)告)15，期中20，期末40，考勤和態(tài)度5%。期中考試、期末考試與學(xué)院的“數(shù)據(jù)結(jié)構(gòu)與算法A”和“數(shù)據(jù)結(jié)構(gòu)與算法A（實(shí)驗(yàn)班）”有60%的基礎(chǔ)內(nèi)容統(tǒng)一出題、統(tǒng)一閱卷，另外40%獨(dú)立命題。平時(shí)作業(yè)和上機(jī)作業(yè)由各班根據(jù)專(zhuān)業(yè)要求靈活掌握，教員協(xié)調(diào)給出成績(jī)。注重綜合能力的考評(píng)，平時(shí)表現(xiàn)突出、上機(jī)實(shí)踐能力較強(qiáng)的可以得到獎(jiǎng)勵(lì)加分。主要教材1. 張銘、王騰蛟、趙海燕，數(shù)據(jù)結(jié)構(gòu)與算法，高等教育出版社，2008年6月。參考資料2. 許卓群、楊冬青、唐世渭、張銘，數(shù)據(jù)結(jié)構(gòu)與算法，高等教育出版社，2004年7月。3. 張銘、趙海

4、燕、王騰蛟，數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題指導(dǎo)，高等教育出版社，2005年8月。4. 算法與數(shù)據(jù)結(jié)構(gòu)，張乃孝主編，高等教育出版社，2006年1月5. Thomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest, Clifford Stein, Inroduction to Algorithms, MIT Press, 2nd edition, 2001. 高等教育出版社影印。其它信息2教學(xué)目的和要求1）介紹基本數(shù)據(jù)結(jié)構(gòu)和基本算法分析技術(shù)。這一部分將介紹常用基本數(shù)據(jù)結(jié)構(gòu)的ADT及其應(yīng)用，包括線性結(jié)構(gòu)（線性表、串、棧和隊(duì)列）、二叉樹(shù)、樹(shù)、圖等；同時(shí)基于各種數(shù)據(jù)

5、結(jié)構(gòu)所實(shí)施的運(yùn)算討論算法分析的基本技術(shù)，掌握時(shí)間和空間權(quán)衡的原則。2）介紹排序、檢索技術(shù)。這一部分將主要討論插入排序、Shell排序、堆排序、快速排序、歸并排序、基數(shù)排序等常用的各種排序算法及其時(shí)間和空間開(kāi)銷(xiāo)，并介紹二分檢索、散列表等常見(jiàn)的檢索技術(shù)，及其各自相應(yīng)的時(shí)間和空間開(kāi)銷(xiāo)。3）通過(guò)本課程的學(xué)習(xí)，學(xué)生將基本掌握數(shù)據(jù)結(jié)構(gòu)和算法的設(shè)計(jì)分析技術(shù)，提高程序設(shè)計(jì)的質(zhì)量；根據(jù)所求解問(wèn)題的性質(zhì)選擇合理的數(shù)據(jù)結(jié)構(gòu)并對(duì)時(shí)間空間復(fù)雜性進(jìn)行必要的控制。3課程特色“數(shù)據(jù)結(jié)構(gòu)與算法”是一門(mén)重要的計(jì)算機(jī)類(lèi)基礎(chǔ)課程。其主要目的是使學(xué)生較全面地理解數(shù)據(jù)結(jié)構(gòu)的概念、掌握各種數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)現(xiàn)方式，比較不同數(shù)據(jù)結(jié)構(gòu)和算法的

6、特點(diǎn)。本課程專(zhuān)門(mén)針對(duì)編程基礎(chǔ)較弱的學(xué)生開(kāi)設(shè)，刪減了一些較艱深的知識(shí)點(diǎn)之外，注重?cái)?shù)據(jù)結(jié)構(gòu)與算法核心內(nèi)容的講解。安排助教加強(qiáng)對(duì)學(xué)生上機(jī)實(shí)習(xí)的輔導(dǎo)。為將來(lái)利用了利用計(jì)算機(jī)解決相關(guān)問(wèn)題打下一定的基礎(chǔ)。4課程內(nèi)容摘要和知識(shí)點(diǎn)章節(jié)課時(shí)內(nèi)容摘要和知識(shí)點(diǎn)重要性 1數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介4數(shù)據(jù)結(jié)構(gòu)定義（邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、運(yùn)算）抽象數(shù)據(jù)類(lèi)型算法及其算法度量和評(píng)價(jià)（大表示法及其運(yùn)算規(guī)則）難度重要性2線性表、棧和隊(duì)列10線性表（向量、鏈表）棧和隊(duì)列（順序、鏈接）、棧的應(yīng)用難度重要性3字符串4字符串抽象數(shù)據(jù)類(lèi)型，存儲(chǔ)表示和類(lèi)定義字符串的運(yùn)算字符串的模式匹配難度重要性4二叉樹(shù)10二叉樹(shù)的概念及性質(zhì)，二叉樹(shù)的抽象數(shù)據(jù)類(lèi)型二叉樹(shù)的周游二叉樹(shù)的存儲(chǔ)實(shí)現(xiàn)二叉檢索樹(shù)、堆與優(yōu)先隊(duì)列、Huffman編碼樹(shù)難度重要性5樹(shù)與森林4樹(shù)的概念，森林與二叉樹(shù)的等價(jià)轉(zhuǎn)換，樹(shù)的抽象數(shù)據(jù)類(lèi)型樹(shù)的周游樹(shù)的鏈?zhǔn)酱鎯?chǔ)難度重要性6圖8圖的基本概念，圖的抽象數(shù)據(jù)類(lèi)型，圖的存儲(chǔ)結(jié)構(gòu)圖的周游（深度優(yōu)先、搜索、廣度優(yōu)先、拓?fù)渑判颍┳疃搪窂絾?wèn)題，最小支撐樹(shù)（Prim算法、Kruskal算法）難度重要性7內(nèi)