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

1、“數(shù)據(jù)結(jié)構(gòu)與算法”教學(xué)大綱美國IEEE和ACM的教學(xué)計劃CC2005和教育部計算機教指委“計算機科學(xué)與技術(shù)專業(yè)規(guī)范”2006都明確地把“程序設(shè)計”、“算法與數(shù)據(jù)結(jié)構(gòu)”列入計算機以及信息技術(shù)相關(guān)學(xué)科專業(yè)的本科必修基礎(chǔ)課程。教育部計算機專業(yè)教指委“中國計算機本科專業(yè)發(fā)展戰(zhàn)略研究報告”、“計算機科學(xué)與技術(shù)專業(yè)規(guī)范”等明確地強調(diào)了實踐教學(xué)和學(xué)生動手能力培養(yǎng)的重要性。數(shù)據(jù)結(jié)構(gòu)是計算機系的本科核心課程之一，上承計算引論（或計算概論）與程序設(shè)計實習(xí)，下啟高級算法和計算理論，向來是計算機本科教學(xué)的重中之重。作為一門重要的專業(yè)必修課程，“數(shù)據(jù)結(jié)構(gòu)與算法”課程既是對以往課程的深入和擴展，也是為將來更加深入地學(xué)習(xí)其

2、他專業(yè)課程打下基礎(chǔ)。課程中所學(xué)習(xí)的排序問題的算法，以及基本的樹、圖等數(shù)據(jù)結(jié)構(gòu)，是計算機科學(xué)的基本功。B+樹、Hash等高級數(shù)據(jù)結(jié)構(gòu)，也是數(shù)據(jù)庫、操作系統(tǒng)、編譯原理、計算機網(wǎng)絡(luò)等后續(xù)課程的基礎(chǔ)。“數(shù)據(jù)結(jié)構(gòu)與算法”介紹基本數(shù)據(jù)結(jié)構(gòu)、基本算法分析技術(shù)、排序、檢索和索引技術(shù)。對常用的基本數(shù)據(jù)結(jié)構(gòu)，討論相應(yīng)的存儲實現(xiàn)技術(shù)和經(jīng)典算法，并通過算法時間空間的效率分析，介紹時空權(quán)衡的原則。對常用的各種經(jīng)典排序算法深入討論其時間和空間開銷。介紹文件管理和外排序技術(shù)，以及常見的檢索和索引技術(shù)。通過該課程的學(xué)習(xí)，學(xué)生將基本掌握數(shù)據(jù)結(jié)構(gòu)和算法的設(shè)計分析技術(shù)，提高程序設(shè)計的質(zhì)量；根據(jù)所求解問題的性質(zhì)選擇合理的數(shù)據(jù)結(jié)構(gòu)并對

3、時間空間復(fù)雜性進行必要的控制。一、數(shù)據(jù)結(jié)構(gòu)與算法A（實驗班）（ HYPERLINK /pkujpk/course/sjjg/report/frame/ds_outline.htm l toptop t _self 返回頂部）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è)

4、定教學(xué)方式本課程是“數(shù)據(jù)結(jié)構(gòu)與算法A”替代課程，針對基礎(chǔ)比較好、學(xué)習(xí)能力突出、學(xué)有余力的實驗班學(xué)生設(shè)置。課程將加大“數(shù)據(jù)結(jié)構(gòu)與算法A”的深度和廣度，提供更多的研究和討論機會，因材施教、培養(yǎng)領(lǐng)袖人才。以課堂講授為主，同時借助網(wǎng)絡(luò)教學(xué)平臺，拓展課堂講授的相關(guān)知識，便于同學(xué)自主學(xué)習(xí)、鞏固課堂所學(xué)內(nèi)容。另外，組織3次以上的獨立習(xí)題課（6小時），針對學(xué)生作業(yè)中出現(xiàn)年的典型問題進行深入探討。鑒于數(shù)據(jù)結(jié)構(gòu)與算法是與實踐緊密結(jié)合的課程，配合理論教學(xué)，將加強上機實習(xí)的訓(xùn)練，通過合理、有效地設(shè)計上機題目，改進作業(yè)評核方式，調(diào)動學(xué)生的積極性，啟發(fā)引導(dǎo)學(xué)生掌握基礎(chǔ)理論并能創(chuàng)新應(yīng)用,增強學(xué)生綜合運用有關(guān)知識的能力。課時

5、分配3(課堂教學(xué))+1（教學(xué)實驗）/周考核方式平時(書面作業(yè)、課堂測試)20，上機(+報告)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)一閱卷。平時作業(yè)和上機作業(yè)由各班根據(jù)專業(yè)要求靈活掌握，教員協(xié)調(diào)給出成績。注重綜合能力的考評，平時表現(xiàn)突出、上機實踐能力較強的可以得到獎勵加分。主要教材張銘、王騰蛟、趙海燕，數(shù)據(jù)結(jié)構(gòu)與算法，高等教育出版社，2008年6月。參考資料許卓群、楊冬青、唐世渭、張銘，數(shù)據(jù)結(jié)構(gòu)與算法，高等教育出版社，2004年7月。張銘、趙海燕、王騰蛟，數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題指導(dǎo)，高等教

6、育出版社，2005年8月。Thomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest, Clifford Stein, Inroduction to Algorithms, MIT Press, 2nd edition, 2001.高等教育出版社影印。其它信息2教學(xué)目的和要求1）掌握并鞏固基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)知識：線性表、樹、圖等常用的數(shù)據(jù)結(jié)構(gòu)和算法的設(shè)計分析技術(shù)；常用的排序、檢索算法及其時間空間開銷；對算法復(fù)雜性進行必要分析和控制。2）理解編譯棧的工作原理，熟習(xí)用棧消除遞歸的算法框架，并解決相關(guān)應(yīng)用問題。3）初步掌握稀疏矩陣、廣義表等高級線性結(jié)構(gòu)技術(shù)

7、，了解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)與算法”是一門重要的計算機類骨干基礎(chǔ)課程。其主要目的是使學(xué)生較全面地理解數(shù)據(jù)結(jié)構(gòu)的概念、掌握各種數(shù)據(jù)結(jié)構(gòu)與算法的實現(xiàn)方式，比較不同數(shù)據(jù)結(jié)構(gòu)和算法的特點。通過學(xué)習(xí)，使學(xué)生能夠提高用計算機解決實際問題的能力。本課程針對實驗班的學(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é)

8、生學(xué)會怎么樣根據(jù)實際問題來取舍數(shù)據(jù)結(jié)構(gòu)和算法，并且在時間復(fù)雜度和空間復(fù)雜度之間進行平衡。在講授過程中，將調(diào)動學(xué)生的積極性，采取研究式的學(xué)習(xí)方法。有些較基礎(chǔ)的內(nèi)容采用學(xué)生綜述、答辯、小測驗的形式，培養(yǎng)學(xué)生的自學(xué)能力。引導(dǎo)學(xué)生跟蹤數(shù)據(jù)結(jié)構(gòu)與算法的前沿應(yīng)用技術(shù)，引入研讀論文并作報告的討論班形式，培養(yǎng)學(xué)生的捕捉新理論、新技術(shù)的科研能力。最后的合作大實習(xí)題由學(xué)生自己提出，并組織團隊完成。由助教引導(dǎo)討論，從需求分析、模塊設(shè)計、編程實踐、調(diào)試測試各個階段進行引導(dǎo)，加強學(xué)生們綜合應(yīng)用數(shù)據(jù)結(jié)構(gòu)和算法知識的能力。本課程將通過設(shè)置的課程網(wǎng)站提供課堂講義和最新的參考材料。4課程內(nèi)容摘要和知識點章節(jié)課時內(nèi)容摘要和知識點

9、重要性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)換機制和方法難度重要性3字符串4字符串抽象數(shù)據(jù)類型，存儲表示和類定義字符串的運算字符串的模式匹配難度重要性4二叉樹10二叉樹的概念及性質(zhì)，二叉樹的抽象數(shù)據(jù)類型二叉樹的周游二叉樹的存儲實現(xiàn)二叉檢索樹、堆與優(yōu)先隊列、Huffman編碼樹非遞歸深度優(yōu)先周游二叉樹和穿線二叉樹難度重要性5樹與森林4樹的概念，森林與二叉樹的等價轉(zhuǎn)換，樹的抽象數(shù)據(jù)類型樹的周游樹的鏈?zhǔn)酱鎯?，?/p>

10、的順序存儲難度重要性6圖8圖的基本概念，圖的抽象數(shù)據(jù)類型，圖的存儲結(jié)構(gòu)圖的周游（深度優(yōu)先、搜索、廣度優(yōu)先、拓?fù)渑判颍┳疃搪窂絾栴}，最小支撐樹（Prim算法、Kruskal算法）難度重要性7內(nèi)排序8排序問題的基本概念，三種簡單排序算法（插入排序、冒泡排序、選擇排序）Shell排序，快速排序，歸并排序，堆排序，基數(shù)排序各種排序算法的理論和實驗時間代價的討論以及排序問題的下限的研究難度重要性8文件管理和外排序2外排序的特點二路外排序置換選擇排序難度重要性9檢索4檢索的基本概念基于線性表的檢索基于集合的檢索散列方法難度重要性10索引技術(shù)2倒排索引B+樹等動態(tài)索引組織紅黑樹難度重要性11高級數(shù)據(jù)結(jié)構(gòu)2廣

11、義表字符樹AVL樹伸展樹難度重要性二、數(shù)據(jù)結(jié)構(gòu)與算法A（ HYPERLINK /pkujpk/course/sjjg/report/frame/ds_outline.htm l toptop 返回頂部）1）課程基本情況學(xué)院設(shè)定課程編號04830050課程名稱數(shù)據(jù)結(jié)構(gòu)與算法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é)方式以課堂講授為主，同時借

12、助網(wǎng)絡(luò)教學(xué)平臺，拓展課堂講授的相關(guān)知識，便于同學(xué)自主學(xué)習(xí)、鞏固課堂所學(xué)內(nèi)容。另外，組織3次以上的獨立習(xí)題課（6小時），針對學(xué)生作業(yè)中出現(xiàn)年的典型問題進行深入探討。鑒于數(shù)據(jù)結(jié)構(gòu)與算法是與實踐緊密結(jié)合的課程，配合理論教學(xué)，將加強上機實習(xí)的訓(xùn)練，通過合理、有效地設(shè)計上機題目，改進作業(yè)評核方式，調(diào)動學(xué)生的積極性，啟發(fā)引導(dǎo)學(xué)生掌握基礎(chǔ)理論并能創(chuàng)新應(yīng)用,增強學(xué)生綜合運用有關(guān)知識的能力。課時分配3(課堂教學(xué))+1（教學(xué)實驗）/周考核方式平時(書面作業(yè)、課堂測試)20，上機(+報告)15，期中20，期末40，考勤和態(tài)度5%。注重綜合能力的考評，平時表現(xiàn)突出、上機實踐能力較強的可以得到獎勵加分。主要教材1.張銘

13、、王騰蛟、趙海燕，數(shù)據(jù)結(jié)構(gòu)與算法，高等教育出版社，2008年6月。參考資料2.許卓群、楊冬青、唐世渭、張銘，數(shù)據(jù)結(jié)構(gòu)與算法，高等教育出版社，2004年7月。3.張銘、趙海燕、王騰蛟，數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題指導(dǎo)，高等教育出版社，2005年8月。4.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ù)。這一部分將介紹常

14、用基本數(shù)據(jù)結(jié)構(gòu)的ADT及其應(yīng)用，包括線性結(jié)構(gòu)（線性表、串、棧和隊列）、二叉樹、樹、圖等；同時基于各種數(shù)據(jù)結(jié)構(gòu)所實施的運算討論算法分析的基本技術(shù)，掌握時間和空間權(quán)衡的原則。2. 介紹排序、檢索和索引技術(shù)。這一部分將主要討論插入排序、Shell排序、堆排序、快速排序、歸并排序、基數(shù)排序等常用的各種排序算法及其時間和空間開銷，并介紹文件管理（數(shù)據(jù)在外存中的組織形式）和外排序技術(shù)，以及自組織線性表、散列表、倒排文件、B樹等常見的檢索和索引技術(shù)，及其各自相應(yīng)的時間和空間開銷。3. 理解編譯棧的工作原理，熟習(xí)用棧消除遞歸的算法框架，并解決相關(guān)應(yīng)用問題；初步掌握稀疏矩陣、廣義表等高級線性結(jié)構(gòu)技術(shù)，了解Tri

15、e結(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)。5. 通過本課程的學(xué)習(xí)，學(xué)生將基本掌握數(shù)據(jù)結(jié)構(gòu)和算法的設(shè)計分析技術(shù)，提高程序設(shè)計的質(zhì)量；根據(jù)所求解問題的性質(zhì)選擇合理的數(shù)據(jù)結(jié)構(gòu)并對時間空間復(fù)雜性進行必要的控制。3）課程特色“數(shù)據(jù)結(jié)構(gòu)與算法”是一門重要的計算機類骨干基礎(chǔ)課程。其主要目的是使學(xué)生較全面地理解數(shù)據(jù)結(jié)構(gòu)的概念、掌握各種數(shù)據(jù)結(jié)構(gòu)與算法的實現(xiàn)方式，比較不同數(shù)據(jù)結(jié)構(gòu)和算法的特點。通過學(xué)習(xí)，使學(xué)生能夠提高用計算機解決實際問題的能力。本課程將以問題求解為主線，從問題抽象、數(shù)據(jù)抽象和算法抽象的角度來組織

16、數(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ù)雜度之間進行平衡。在講授過程中，將調(diào)動學(xué)生的積極性，采取研究式的學(xué)習(xí)方法。有些較基礎(chǔ)的內(nèi)容采用學(xué)生綜述、答辯、小測驗的形式，培養(yǎng)學(xué)生的自學(xué)能力。引導(dǎo)學(xué)生跟蹤數(shù)據(jù)結(jié)構(gòu)與算法的前沿應(yīng)用技術(shù)，引入研讀論文并作報告的討論班形式，培養(yǎng)學(xué)生的捕捉新理論、新技術(shù)的科研能力。最后的合作大實習(xí)題由教師指導(dǎo)學(xué)生自己提出，并組織團隊完成。由助教引導(dǎo)討論，從需求分析、模塊設(shè)計、編程實踐、調(diào)試測試各個階段進行引導(dǎo)，加強

17、學(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線性表、棧和隊列2線性表（向量、鏈表）難度重要性3線性表、棧和隊列6棧和隊列（順序、鏈接）、棧的應(yīng)用 選講遞歸到非遞歸的轉(zhuǎn)換機制和方法難度重要性4字符串4字符串抽象數(shù)據(jù)類型，存儲表示和類定義字符串的運算字符串的模式匹配難度重要性5二叉樹10二叉樹的概念及性質(zhì)，二叉樹的抽象數(shù)據(jù)類型二叉樹的周游二叉樹的存儲實現(xiàn)二叉檢索樹、堆

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

19、外排序 選講置換選擇排序、多路歸并選擇樹難度重要性10檢索4檢索的基本概念基于線性表的檢索基于集合的檢索散列方法難度重要性11索引技術(shù)2倒排索引B+樹等動態(tài)索引組織 選講紅黑樹難度重要性12高級數(shù)據(jù)結(jié)構(gòu)2廣義表字符樹 選講AVL樹 選講伸展樹難度重要性三、數(shù)據(jù)結(jié)構(gòu)與算法B（ HYPERLINK /pkujpk/course/sjjg/report/frame/ds_outline.htm l toptop 返回頂部）1）課程基本情況學(xué)院設(shè)定課程編號課程名稱數(shù)據(jù)結(jié)構(gòu)與算法BData Structure And Algorithm B開課時間一年級二年級三年級四年級秋春夏秋春夏秋春夏秋春夏適用院系

20、信息學(xué)院編程能力不太強的學(xué)生課程定位骨干基礎(chǔ)課，必修課學(xué)分3學(xué)分總學(xué)時54學(xué)時先修課程計算引論，程序設(shè)計實習(xí)后續(xù)課程數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)，程序設(shè)計語言原理教師設(shè)定教學(xué)方式以課堂講授為主，同時借助網(wǎng)絡(luò)教學(xué)平臺，拓展課堂講授的相關(guān)知識，便于同學(xué)自主學(xué)習(xí)、鞏固課堂所學(xué)內(nèi)容。考慮到選修B類課程的學(xué)生編程能力較弱，會安排助教加強對學(xué)生上機實習(xí)的輔導(dǎo)。課時分配3(課堂教學(xué))+1（教學(xué)實驗）/周考核方式平時(書面作業(yè)、課堂測試)20，上機(+報告)15，期中20，期末40，考勤和態(tài)度5%。期中考試、期末考試與學(xué)院的數(shù)據(jù)結(jié)構(gòu)與算法A和數(shù)據(jù)結(jié)構(gòu)與算法A（實驗班）有60%的基礎(chǔ)內(nèi)容統(tǒng)一出題、統(tǒng)一閱卷，另外40%獨立

21、命題。平時作業(yè)和上機作業(yè)由各班根據(jù)專業(yè)要求靈活掌握，教員協(xié)調(diào)給出成績。注重綜合能力的考評，平時表現(xiàn)突出、上機實踐能力較強的可以得到獎勵加分。主要教材1.張銘、王騰蛟、趙海燕，數(shù)據(jù)結(jié)構(gòu)與算法，高等教育出版社，2008年6月。參考資料2.許卓群、楊冬青、唐世渭、張銘，數(shù)據(jù)結(jié)構(gòu)與算法，高等教育出版社，2004年7月。3.張銘、趙海燕、王騰蛟，數(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

22、, 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)（線性表、串、棧和隊列）、二叉樹、樹、圖等；同時基于各種數(shù)據(jù)結(jié)構(gòu)所實施的運算討論算法分析的基本技術(shù)，掌握時間和空間權(quán)衡的原則。2. 介紹排序、檢索技術(shù)。這一部分將主要討論插入排序、Shell排序、堆排序、快速排序、歸并排序、基數(shù)排序等常用的各種排序算法及其時間和空間開銷，并介紹二分檢索、散列表等常見的檢索技術(shù)，及其各自相應(yīng)的時間和空間

23、開銷。3. 通過本課程的學(xué)習(xí)，學(xué)生將基本掌握數(shù)據(jù)結(jié)構(gòu)和算法的設(shè)計分析技術(shù)，提高程序設(shè)計的質(zhì)量；根據(jù)所求解問題的性質(zhì)選擇合理的數(shù)據(jù)結(jié)構(gòu)并對時間空間復(fù)雜性進行必要的控制。3）課程特色“數(shù)據(jù)結(jié)構(gòu)與算法”是一門重要的計算機類基礎(chǔ)課程。其主要目的是使學(xué)生較全面地理解數(shù)據(jù)結(jié)構(gòu)的概念、掌握各種數(shù)據(jù)結(jié)構(gòu)與算法的實現(xiàn)方式，比較不同數(shù)據(jù)結(jié)構(gòu)和算法的特點。本課程專門針對編程基礎(chǔ)較弱的學(xué)生開設(shè)，刪減了一些較艱深的知識點之外，注重數(shù)據(jù)結(jié)構(gòu)與算法核心內(nèi)容的講解。安排助教加強對學(xué)生上機實習(xí)的輔導(dǎo)。為將來利用了利用計算機解決相關(guān)問題打下一定的基礎(chǔ)。4）課程內(nèi)容摘要和知識點章節(jié)課時內(nèi)容摘要和知識點重要性1數(shù)據(jù)結(jié)構(gòu)和算法簡介4數(shù)

24、據(jù)結(jié)構(gòu)定義（邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)、運算）抽象數(shù)據(jù)類型算法及其算法度量和評價（大表示法及其運算規(guī)則）難度重要性2線性表、棧和隊列10線性表（向量、鏈表）棧和隊列（順序、鏈接）、棧的應(yīng)用難度重要性3字符串4字符串抽象數(shù)據(jù)類型，存儲表示和類定義字符串的運算字符串的模式匹配難度重要性4二叉樹10二叉樹的概念及性質(zhì)，二叉樹的抽象數(shù)據(jù)類型二叉樹的周游二叉樹的存儲實現(xiàn)二叉檢索樹、堆與優(yōu)先隊列、Huffman編碼樹難度重要性5樹與森林4樹的概念，森林與二叉樹的等價轉(zhuǎn)換，樹的抽象數(shù)據(jù)類型樹的周游樹的鏈?zhǔn)酱鎯﹄y度重要性6圖8圖的基本概念，圖的抽象數(shù)據(jù)類型，圖的存儲結(jié)構(gòu)圖的周游（深度優(yōu)先、搜索、廣度優(yōu)先、拓?fù)渑判颍┳?/p>

25、短路徑問題，最小支撐樹（Prim算法、Kruskal算法）難度重要性7內(nèi)排序8排序問題的基本概念，三種簡單排序算法（插入排序、冒泡排序、選擇排序）Shell排序，快速排序，歸并排序，堆排序，基數(shù)排序難度重要性8檢索4檢索的基本概念基于線性表的檢索基于集合的檢索散列方法難度重要性四、數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)（ HYPERLINK /pkujpk/course/sjjg/report/frame/ds_outline.htm l toptop 返回頂部）1）課程基本情況學(xué)院設(shè)定課程編號048305170課程名稱數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)Practice of Data Structures and Algori

26、thms開課時間一年級二年級三年級四年級秋春夏秋春夏秋春夏秋春夏適用院系計算機系和智能系課程定位專業(yè)必修學(xué)分2學(xué)分總學(xué)時32+80(理論+上機實習(xí))先修課程數(shù)據(jù)結(jié)構(gòu)與算法A后續(xù)課程算法分析與設(shè)計教師設(shè)定教學(xué)方式理論與實踐結(jié)合課時分配理論32學(xué)時：教員課堂講授26小時，學(xué)生編程經(jīng)驗交流6小時學(xué)生獨立實踐80學(xué)時： 數(shù)據(jù)結(jié)構(gòu)與算法實驗50小時，綜合上機實習(xí)30小時考核方式平時20%，算法實驗20%，綜合上機題40%，期末考試20%。主要教材1.張銘、趙海燕、王騰蛟，數(shù)據(jù)結(jié)構(gòu)與算法習(xí)題指導(dǎo)，高等教育出版社，2005年8月。參考資料2.張銘、王騰蛟、趙海燕，數(shù)據(jù)結(jié)構(gòu)與算法，高等教育出版社，2008年6

27、月。3.許卓群、楊冬青、唐世渭、張銘，數(shù)據(jù)結(jié)構(gòu)與算法，高等教育出版社，2004年7月。4.Thomas H.Cormen, Charles E.Leiserson, Ronald L. Rivest, Clifford Stein, Inroduction to Algorithms, MIT Press, 2nd edition, 2001.高等教育出版社影印。5.M. H. Alsuwaiyel,Algorithms Design Techniques and Analysis,電子工業(yè)出版社影印，2003年1月。6.B. Kernighan & R. Pike , The Practic

28、e of Programming, Addison-Wesley, 1999. (中譯本：程序設(shè)計實踐，裘宗燕譯，機械工業(yè)出版社，2000年8月其它信息同修課程：數(shù)據(jù)結(jié)構(gòu)與算法A2）教學(xué)目的和要求配合“數(shù)據(jù)結(jié)構(gòu)與算法”理論課程的學(xué)習(xí)，介紹一些程序風(fēng)格、設(shè)計、測試和排錯等軟件工程的基本知識和方法；通過一些趣味例題，系統(tǒng)地介紹“數(shù)據(jù)結(jié)構(gòu)與算法”理論課程涉及到的窮舉法、回溯法、貪心法、分治法、動態(tài)規(guī)劃等算法基本思想；介紹圖和問題建模、數(shù)據(jù)結(jié)構(gòu)與算法的應(yīng)用和實踐。培養(yǎng)學(xué)生獨立地實現(xiàn)常用基本數(shù)據(jù)結(jié)構(gòu)的ADT以及相應(yīng)的STL數(shù)據(jù)結(jié)構(gòu)，解決一些實際問題，獨立編寫中小型應(yīng)用程序。靈活應(yīng)用基本數(shù)據(jù)結(jié)構(gòu)，并結(jié)合排序、檢索、文件、索引等技術(shù)，合作編寫比較綜合的大型應(yīng)用程，提高學(xué)生的實際動手能力。通過本課程的學(xué)習(xí)，為后續(xù)的專業(yè)基礎(chǔ)課和專業(yè)課程打下堅實的基礎(chǔ)。3）課程特色把數(shù)據(jù)結(jié)構(gòu)與算法實習(xí)作為輔助數(shù)據(jù)結(jié)構(gòu)與算法的計算機系學(xué)生必修課，強化了計算機系學(xué)生的實踐能力訓(xùn)練。實習(xí)課內(nèi)容劃分為C/C+基本程序技巧訓(xùn)練、界面排錯和測試、基本數(shù)據(jù)結(jié)構(gòu)訓(xùn)練、基本算法、數(shù)學(xué)建模訓(xùn)練5個模塊。從問題求解的角度，培養(yǎng)學(xué)生數(shù)據(jù)結(jié)構(gòu)理論基礎(chǔ)、問題數(shù)據(jù)和算法抽象、數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計的能力。在培養(yǎng)基本問題求解能力的同時，注重實踐能力和工程能力的培