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

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

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

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

4、業(yè)和上機(jī)作業(yè)由各班根據(jù)專業(yè)要求靈活掌握，教員協(xié)調(diào)給出成績。 注重綜合能力的考評，平時表現(xiàn)突出、上機(jī)實踐能力較強(qiáng)的可以得到獎勵加分。主要教材張銘、王騰蛟、趙海燕，數(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ù)據(jù)結(jié)構(gòu)和算法的設(shè)計分析技術(shù)；常用的排序、檢索算法及其時間空間開銷；對算法復(fù)雜性進(jìn)行必要分析和控制。2）理解編譯棧的工作原理，熟習(xí)用棧消除遞歸的算法框架，并解決相關(guān)應(yīng)用問題。3）初步掌握稀疏矩陣、廣義表等高級線性結(jié)構(gòu)技術(shù)，了解Trie結(jié)構(gòu)、AVL樹等高級樹形結(jié)構(gòu)。4）對抽象數(shù)據(jù)類型有深入的理解，能根據(jù)所求解問題的性質(zhì)選擇合理的數(shù)據(jù)結(jié)構(gòu)，設(shè)計并完成處理海量數(shù)據(jù)的復(fù)雜應(yīng)用系統(tǒng)。3課程特色“數(shù)據(jù)結(jié)構(gòu)與算法”是一門重要的計算機(jī)類骨干基礎(chǔ)課程。其主要目的是使學(xué)生較全面地理解數(shù)據(jù)

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

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

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