北大“數(shù)據(jù)結(jié)構(gòu)與算法A（實(shí)驗(yàn)班）”教學(xué)大綱

1、“數(shù)據(jù)結(jié)構(gòu)與算法A（實(shí)驗(yàn)班）”教學(xué)大綱“數(shù)據(jù)結(jié)構(gòu)與算法”是一門重要的計(jì)算機(jī)類基礎(chǔ)課程。其主要目的是使學(xué)生較全面地理解數(shù)據(jù)結(jié)構(gòu)的概念、掌握各種數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)現(xiàn)方式，比較不同數(shù)據(jù)結(jié)構(gòu)和算法的特點(diǎn)。通過學(xué)習(xí)，使學(xué)生能夠提高用計(jì)算機(jī)解決實(shí)際問題的能力。本課程注重?cái)?shù)據(jù)結(jié)構(gòu)與算法理論和實(shí)踐的結(jié)合，從問題求解的角度指導(dǎo)學(xué)生學(xué)習(xí)如何運(yùn)用數(shù)據(jù)結(jié)構(gòu)與算法知識(shí)來應(yīng)用和解決實(shí)際問題，為將來利用從事計(jì)算機(jī)相關(guān)的學(xué)習(xí)、研究和開發(fā)工作打下扎實(shí)的基礎(chǔ)。本課程是“數(shù)據(jù)結(jié)構(gòu)與算法A”的替代課程，專門為那些基礎(chǔ)比較好、學(xué)習(xí)能力突出、學(xué)有余力的學(xué)生設(shè)置。課程將加大數(shù)據(jù)結(jié)構(gòu)與算法的深度和廣度，提供更多的研究和討論機(jī)會(huì)，因材施教、培

2、養(yǎng)領(lǐng)袖人才。作為計(jì)算機(jī)和智能專業(yè)二年級(jí)的主干基礎(chǔ)課，參與此課程學(xué)習(xí)的學(xué)生需要有非常好的計(jì)算概論A、程序設(shè)計(jì)實(shí)習(xí)?？梢圆灰蠹险搱D論、計(jì)算概論的先修基礎(chǔ)。1課程基本情況學(xué)院設(shè)定課程編號(hào)04830540課程名稱數(shù)據(jù)結(jié)構(gòu)與算法A（實(shí)驗(yàn)班）Data Structure And Algorithm A開課時(shí)間一年級(jí)二年級(jí)三年級(jí)四年級(jí)秋春夏秋春夏秋春夏秋春夏適用院系信息學(xué)院全體學(xué)生課程定位骨干基礎(chǔ)課，必修課學(xué)分3學(xué)分總學(xué)時(shí)54學(xué)時(shí)先修課程計(jì)算引論，程序設(shè)計(jì)實(shí)習(xí)，集合論與圖論，概率統(tǒng)計(jì)A后續(xù)課程數(shù)據(jù)結(jié)構(gòu)與算法實(shí)習(xí)，程序設(shè)計(jì)語言原理教師設(shè)定教學(xué)方式以課堂講授為主，同時(shí)借助網(wǎng)絡(luò)教學(xué)平臺(tái)，拓展課堂講授的相關(guān)知識(shí)

3、，便于同學(xué)自主學(xué)習(xí)、鞏固課堂所學(xué)內(nèi)容。另外，組織3次以上的獨(dú)立習(xí)題課（6小時(shí)），針對(duì)學(xué)生作業(yè)中出現(xiàn)年的典型問題進(jìn)行深入探討。鑒于數(shù)據(jù)結(jié)構(gòu)與算法是與實(shí)踐緊密結(jié)合的課程，配合理論教學(xué)，將加強(qiáng)上機(jī)實(shí)習(xí)的訓(xùn)練，通過合理、有效地設(shè)計(jì)上機(jī)題目，改進(jìn)作業(yè)評(píng)核方式，調(diào)動(dòng)學(xué)生的積極性，啟發(fā)引導(dǎo)學(xué)生掌握基礎(chǔ)理論并能創(chuàng)新應(yīng)用,增強(qiáng)學(xué)生綜合運(yùn)用有關(guān)知識(shí)的能力。課時(shí)分配3(課堂教學(xué))+1（教學(xué)實(shí)驗(yàn)）/周考核方式平時(shí)(書面作業(yè)、課堂測(cè)試)20，上機(jī)(+報(bào)告)15，期中20，期末20，高級(jí)數(shù)據(jù)結(jié)構(gòu)20%，考勤和態(tài)度5%。 期中、期末考試，全學(xué)院的“數(shù)據(jù)結(jié)構(gòu)與算法A”和“數(shù)據(jù)結(jié)構(gòu)與算法A（實(shí)驗(yàn)班）”統(tǒng)一出題、統(tǒng)一閱卷。平時(shí)作

4、業(yè)和上機(jī)作業(yè)由各班根據(jù)專業(yè)要求靈活掌握，教員協(xié)調(diào)給出成績(jī)。 注重綜合能力的考評(píng)，平時(shí)表現(xiàn)突出、上機(jī)實(shí)踐能力較強(qiáng)的可以得到獎(jiǎng)勵(lì)加分。主要教材張銘、王騰蛟、趙海燕，數(shù)據(jù)結(jié)構(gòu)與算法，高等教育出版社，2008年6月。參考資料許卓群、楊冬青、唐世渭、張銘，數(shù)據(jù)結(jié)構(gòu)與算法，高等教育出版社，2004年7月。張銘、趙海燕、王騰蛟，數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題指導(dǎo)，高等教育出版社，2005年8月。Thomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest, Clifford Stein, Inroduction to Algorithms, MIT Press, 2nd

5、edition, 2001. 高等教育出版社影印。其它信息2教學(xué)目的和要求1）掌握并鞏固基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)知識(shí)：線性表、樹、圖等常用的數(shù)據(jù)結(jié)構(gòu)和算法的設(shè)計(jì)分析技術(shù)；常用的排序、檢索算法及其時(shí)間空間開銷；對(duì)算法復(fù)雜性進(jìn)行必要分析和控制。2）理解編譯棧的工作原理，熟習(xí)用棧消除遞歸的算法框架，并解決相關(guān)應(yīng)用問題。3）初步掌握稀疏矩陣、廣義表等高級(jí)線性結(jié)構(gòu)技術(shù)，了解Trie結(jié)構(gòu)、AVL樹等高級(jí)樹形結(jié)構(gòu)。4）對(duì)抽象數(shù)據(jù)類型有深入的理解，能根據(jù)所求解問題的性質(zhì)選擇合理的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)并完成處理海量數(shù)據(jù)的復(fù)雜應(yīng)用系統(tǒng)。3課程特色“數(shù)據(jù)結(jié)構(gòu)與算法”是一門重要的計(jì)算機(jī)類骨干基礎(chǔ)課程。其主要目的是使學(xué)生較全面地理解數(shù)據(jù)

6、結(jié)構(gòu)的概念、掌握各種數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)現(xiàn)方式，比較不同數(shù)據(jù)結(jié)構(gòu)和算法的特點(diǎn)。通過學(xué)習(xí)，使學(xué)生能夠提高用計(jì)算機(jī)解決實(shí)際問題的能力。本課程針對(duì)實(shí)驗(yàn)班的學(xué)生，將以問題求解為主線，從問題抽象、數(shù)據(jù)抽象和算法抽象的角度來組織數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)，指導(dǎo)學(xué)生建立數(shù)學(xué)模型、使用不同的數(shù)據(jù)結(jié)構(gòu)不同的算法分別去解決問題，最后去探討各種數(shù)據(jù)結(jié)構(gòu)和算法的優(yōu)缺點(diǎn)，同時(shí)讓學(xué)生學(xué)會(huì)怎么樣根據(jù)實(shí)際問題來取舍數(shù)據(jù)結(jié)構(gòu)和算法，并且在時(shí)間復(fù)雜度和空間復(fù)雜度之間進(jìn)行平衡。在講授過程中，將調(diào)動(dòng)學(xué)生的積極性，采取研究式的學(xué)習(xí)方法。有些較基礎(chǔ)的內(nèi)容采用學(xué)生綜述、答辯、小測(cè)驗(yàn)的形式，培養(yǎng)學(xué)生的自學(xué)能力。引導(dǎo)學(xué)生跟蹤數(shù)據(jù)結(jié)構(gòu)與算法的前沿應(yīng)用技

7、術(shù)，引入研讀論文并作報(bào)告的討論班形式，培養(yǎng)學(xué)生的捕捉新理論、新技術(shù)的科研能力。最后的合作大實(shí)習(xí)題由學(xué)生自己提出，并組織團(tuán)隊(duì)完成。由助教引導(dǎo)討論，從需求分析、模塊設(shè)計(jì)、編程實(shí)踐、調(diào)試測(cè)試各個(gè)階段進(jìn)行引導(dǎo)，加強(qiáng)學(xué)生們綜合應(yīng)用數(shù)據(jù)結(jié)構(gòu)和算法知識(shí)的能力。本課程將通過設(shè)置的課程網(wǎng)站提供課堂講義和最新的參考材料。4課程內(nèi)容摘要和知識(shí)點(diǎn)章節(jié)課時(shí)內(nèi)容摘要和知識(shí)點(diǎn)重要性1數(shù)據(jù)結(jié)構(gòu)和算法簡(jiǎn)介2數(shù)據(jù)結(jié)構(gòu)定義（邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、運(yùn)算）抽象數(shù)據(jù)類型算法及其算法度量和評(píng)價(jià)（大表示法及其運(yùn)算規(guī)則）難度重要性2線性表、棧和隊(duì)列8線性表（向量、鏈表）棧和隊(duì)列（順序、鏈接）、棧的應(yīng)用根據(jù)專業(yè)選講遞歸到非遞歸的轉(zhuǎn)換機(jī)制和方法難度

8、重要性3字符串4字符串抽象數(shù)據(jù)類型，存儲(chǔ)表示和類定義字符串的運(yùn)算字符串的模式匹配難度重要性4二叉樹10二叉樹的概念及性質(zhì)，二叉樹的抽象數(shù)據(jù)類型二叉樹的周游二叉樹的存儲(chǔ)實(shí)現(xiàn)二叉檢索樹、堆與優(yōu)先隊(duì)列、Huffman編碼樹非遞歸深度優(yōu)先周游二叉樹和穿線二叉樹難度重要性5樹與森林4樹的概念，森林與二叉樹的等價(jià)轉(zhuǎn)換，樹的抽象數(shù)據(jù)類型樹的周游樹的鏈?zhǔn)酱鎯?chǔ)，樹的順序存儲(chǔ)難度重要性6圖8圖的基本概念，圖的抽象數(shù)據(jù)類型，圖的存儲(chǔ)結(jié)構(gòu)圖的周游（深度優(yōu)先、搜索、廣度優(yōu)先、拓?fù)渑判颍┳疃搪窂絾栴}，最小支撐樹（Prim算法、Kruskal算法）難度重要性7內(nèi)排序8排序問題的基本概念，三種簡(jiǎn)單排序算法（插入排序、冒泡排序、選擇排序）Shell排序，快速排序，歸并排序，堆排序，基數(shù)排序各種排序算法的理論和實(shí)驗(yàn)時(shí)間代價(jià)的討論以及排序問題的下限的研究