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

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

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

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

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

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

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

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

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