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

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

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

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

4、定教學(xué)方式本課程是“數(shù)據(jù)結(jié)構(gòu)與算法A”替代課程，針對(duì)基礎(chǔ)比較好、學(xué)習(xí)能力突出、學(xué)有余力的實(shí)驗(yàn)班學(xué)生設(shè)置。課程將加大“數(shù)據(jù)結(jié)構(gòu)與算法A”的深度和廣度，提供更多的研究和討論機(jī)會(huì)，因材施教、培養(yǎng)領(lǐng)袖人才。以課堂講授為主，同時(shí)借助網(wǎng)絡(luò)教學(xué)平臺(tái)，拓展課堂講授的相關(guān)知識(shí)，便于同學(xué)自主學(xué)習(xí)、鞏固課堂所學(xué)內(nèi)容。另外，組織3次以上的獨(dú)立習(xí)題課（6小時(shí)），針對(duì)學(xué)生作業(yè)中出現(xiàn)年的典型問(wèn)題進(jìn)行深入探討。鑒于數(shù)據(jù)結(jié)構(gòu)與算法是與實(shí)踐緊密結(jié)合的課程，配合理論教學(xué)，將加強(qiáng)上機(jī)實(shí)習(xí)的訓(xùn)練，通過(guò)合理、有效地設(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í)

5、分配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í)作業(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)，高等教

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í)：線性表、樹、圖等常用的數(shù)據(jù)結(jié)構(gòu)和算法的設(shè)計(jì)分析技術(shù)；常用的排序、檢索算法及其時(shí)間空間開銷；對(duì)算法復(fù)雜性進(jìn)行必要分析和控制。2）理解編譯棧的工作原理，熟習(xí)用棧消除遞歸的算法框架，并解決相關(guān)應(yīng)用問(wèn)題。3）初步掌握稀疏矩陣、廣義表等高級(jí)線性結(jié)構(gòu)技術(shù)

7、，了解Trie結(jié)構(gòu)、AVL樹等高級(jí)樹形結(jié)構(gòu)。4）對(duì)抽象數(shù)據(jù)類型有深入的理解，能根據(jù)所求解問(wèn)題的性質(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ù)結(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)題的能力。本課程針對(duì)實(shí)驗(yàn)班的學(xué)生，將以問(wèn)題求解為主線，從問(wèn)題抽象、數(shù)據(jù)抽象和算法抽象的角度來(lái)組織數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)，指導(dǎo)學(xué)生建立數(shù)學(xué)模型、使用不同的數(shù)據(jù)結(jié)構(gòu)不同的算法分別去解決問(wèn)題，最后去探討各種數(shù)據(jù)結(jié)構(gòu)和算法的優(yōu)缺點(diǎn)，同時(shí)讓學(xué)

8、生學(xué)會(huì)怎么樣根據(jù)實(shí)際問(wèn)題來(lái)取舍數(shù)據(jù)結(jié)構(gòu)和算法，并且在時(shí)間復(fù)雜度和空間復(fù)雜度之間進(jìn)行平衡。在講授過(guò)程中，將調(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)用技術(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í)的能力。本課程將通過(guò)設(shè)置的課程網(wǎng)站提供課堂講義和最新的參考材料。4課程內(nèi)容摘要和知識(shí)點(diǎn)章節(jié)課時(shí)內(nèi)容摘要和知識(shí)點(diǎn)

9、重要性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ī)制和方法難度重要性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ǔ)，樹

10、的順序存儲(chǔ)難度重要性6圖8圖的基本概念，圖的抽象數(shù)據(jù)類型，圖的存儲(chǔ)結(jié)構(gòu)圖的周游（深度優(yōu)先、搜索、廣度優(yōu)先、拓?fù)渑判颍┳疃搪窂絾?wèn)題，最小支撐樹（Prim算法、Kruskal算法）難度重要性7內(nèi)排序8排序問(wèn)題的基本概念，三種簡(jiǎn)單排序算法（插入排序、冒泡排序、選擇排序）Shell排序，快速排序，歸并排序，堆排序，基數(shù)排序各種排序算法的理論和實(shí)驗(yàn)時(shí)間代價(jià)的討論以及排序問(wèn)題的下限的研究難度重要性8文件管理和外排序2外排序的特點(diǎn)二路外排序置換選擇排序難度重要性9檢索4檢索的基本概念基于線性表的檢索基于集合的檢索散列方法難度重要性10索引技術(shù)2倒排索引B+樹等動(dòng)態(tài)索引組織紅黑樹難度重要性11高級(jí)數(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è)定課程編號(hào)04830050課程名稱數(shù)據(jù)結(jié)構(gòu)與算法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ì)語(yǔ)言原理教師設(shè)定教學(xué)方式以課堂講授為主，同時(shí)借

12、助網(wǎng)絡(luò)教學(xué)平臺(tái)，拓展課堂講授的相關(guān)知識(shí)，便于同學(xué)自主學(xué)習(xí)、鞏固課堂所學(xué)內(nèi)容。另外，組織3次以上的獨(dú)立習(xí)題課（6小時(shí)），針對(duì)學(xué)生作業(yè)中出現(xiàn)年的典型問(wèn)題進(jìn)行深入探討。鑒于數(shù)據(jù)結(jié)構(gòu)與算法是與實(shí)踐緊密結(jié)合的課程，配合理論教學(xué)，將加強(qiáng)上機(jī)實(shí)習(xí)的訓(xùn)練，通過(guò)合理、有效地設(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，期末40，考勤和態(tài)度5%。注重綜合能力的考評(píng)，平時(shí)表現(xiàn)突出、上機(jī)實(shí)踐能力較強(qiáng)的可以得到獎(jiǎng)勵(lì)加分。主要教材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)（線性表、串、棧和隊(duì)列）、二叉樹、樹、圖等；同時(shí)基于各種數(shù)據(jù)結(jié)構(gòu)所實(shí)施的運(yùn)算討論算法分析的基本技術(shù)，掌握時(shí)間和空間權(quán)衡的原則。2. 介紹排序、檢索和索引技術(shù)。這一部分將主要討論插入排序、Shell排序、堆排序、快速排序、歸并排序、基數(shù)排序等常用的各種排序算法及其時(shí)間和空間開銷，并介紹文件管理（數(shù)據(jù)在外存中的組織形式）和外排序技術(shù)，以及自組織線性表、散列表、倒排文件、B樹等常見的檢索和索引技術(shù)，及其各自相應(yīng)的時(shí)間和空間開銷。3. 理解編譯棧的工作原理，熟習(xí)用棧消除遞歸的算法框架，并解決相關(guān)應(yīng)用問(wèn)題；初步掌握稀疏矩陣、廣義表等高級(jí)線性結(jié)構(gòu)技術(shù)，了解Tri

15、e結(jié)構(gòu)、AVL樹等高級(jí)樹形結(jié)構(gòu)。4. 對(duì)抽象數(shù)據(jù)類型有深入的理解，能根據(jù)所求解問(wèn)題的性質(zhì)選擇合理的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)并完成處理海量數(shù)據(jù)的復(fù)雜應(yīng)用系統(tǒng)。5. 通過(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)與算法”是一門重要的計(jì)算機(jī)類骨干基礎(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)題的能力。本課程將以問(wèn)題求解為主線，從問(wèn)題抽象、數(shù)據(jù)抽象和算法抽象的角度來(lái)組織

16、數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)，指導(dǎo)學(xué)生建立數(shù)學(xué)模型、使用不同的數(shù)據(jù)結(jié)構(gòu)不同的算法分別去解決問(wèn)題，最后去探討各種數(shù)據(jù)結(jié)構(gòu)和算法的優(yōu)缺點(diǎn)，同時(shí)讓學(xué)生學(xué)會(huì)怎么樣根據(jù)實(shí)際問(wèn)題來(lái)取舍數(shù)據(jù)結(jié)構(gòu)和算法，并且在時(shí)間復(fù)雜度和空間復(fù)雜度之間進(jìn)行平衡。在講授過(guò)程中，將調(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)用技術(shù)，引入研讀論文并作報(bào)告的討論班形式，培養(yǎng)學(xué)生的捕捉新理論、新技術(shù)的科研能力。最后的合作大實(shí)習(xí)題由教師指導(dǎo)學(xué)生自己提出，并組織團(tuán)隊(duì)完成。由助教引導(dǎo)討論，從需求分析、模塊設(shè)計(jì)、編程實(shí)踐、調(diào)試測(cè)試各個(gè)階段進(jìn)行引導(dǎo)，加強(qiáng)

17、學(xué)生們綜合應(yīng)用數(shù)據(jù)結(jié)構(gòu)和算法知識(shí)的能力。課程通過(guò)設(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ì)列2線性表（向量、鏈表）難度重要性3線性表、棧和隊(duì)列6棧和隊(duì)列（順序、鏈接）、棧的應(yīng)用 選講遞歸到非遞歸的轉(zhuǎn)換機(jī)制和方法難度重要性4字符串4字符串抽象數(shù)據(jù)類型，存儲(chǔ)表示和類定義字符串的運(yùn)算字符串的模式匹配難度重要性5二叉樹10二叉樹的概念及性質(zhì)，二叉樹的抽象數(shù)據(jù)類型二叉樹的周游二叉樹的存儲(chǔ)實(shí)現(xiàn)二叉檢索樹、堆

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

19、外排序 選講置換選擇排序、多路歸并選擇樹難度重要性10檢索4檢索的基本概念基于線性表的檢索基于集合的檢索散列方法難度重要性11索引技術(shù)2倒排索引B+樹等動(dòng)態(tài)索引組織 選講紅黑樹難度重要性12高級(jí)數(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è)定課程編號(hào)課程名稱數(shù)據(jù)結(jié)構(gòu)與算法BData Structure And Algorithm B開課時(shí)間一年級(jí)二年級(jí)三年級(jí)四年級(jí)秋春夏秋春夏秋春夏秋春夏適用院系

20、信息學(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類課程的學(xué)生編程能力較弱，會(huì)安排助教加強(qiáng)對(duì)學(xué)生上機(jī)實(shí)習(xí)的輔導(dǎo)。課時(shí)分配3(課堂教學(xué))+1（教學(xué)實(shí)驗(yàn)）/周考核方式平時(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ú)立

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

23、開銷。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)與算法”是一門重要的計(jì)算機(jī)類基礎(chǔ)課程。其主要目的是使學(xué)生較全面地理解數(shù)據(jù)結(jié)構(gòu)的概念、掌握各種數(shù)據(jù)結(jié)構(gòu)與算法的實(shí)現(xiàn)方式，比較不同數(shù)據(jù)結(jié)構(gòu)和算法的特點(diǎn)。本課程專門針對(duì)編程基礎(chǔ)較弱的學(xué)生開設(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ù)

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

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

26、thms開課時(shí)間一年級(jí)二年級(jí)三年級(jí)四年級(jí)秋春夏秋春夏秋春夏秋春夏適用院系計(jì)算機(jī)系和智能系課程定位專業(yè)必修學(xué)分2學(xué)分總學(xué)時(shí)32+80(理論+上機(jī)實(shí)習(xí))先修課程數(shù)據(jù)結(jié)構(gòu)與算法A后續(xù)課程算法分析與設(shè)計(jì)教師設(shè)定教學(xué)方式理論與實(shí)踐結(jié)合課時(shí)分配理論32學(xué)時(shí)：教員課堂講授26小時(shí)，學(xué)生編程經(jīng)驗(yàn)交流6小時(shí)學(xué)生獨(dú)立實(shí)踐80學(xué)時(shí)： 數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)50小時(shí)，綜合上機(jī)實(shí)習(xí)30小時(shí)考核方式平時(shí)20%，算法實(shí)驗(yàn)20%，綜合上機(jī)題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è)計(jì)實(shí)踐，裘宗燕譯，機(jī)械工業(yè)出版社，2000年8月其它信息同修課程：數(shù)據(jù)結(jié)構(gòu)與算法A2）教學(xué)目的和要求配合“數(shù)據(jù)結(jié)構(gòu)與算法”理論課程的學(xué)習(xí)，介紹一些程序風(fēng)格、設(shè)計(jì)、測(cè)試和排錯(cuò)等軟件工程的基本知識(shí)和方法；通過(guò)一些趣味例題，系統(tǒng)地介紹“數(shù)據(jù)結(jié)構(gòu)與算法”理論課程涉及到的窮舉法、回溯法、貪心法、分治法、動(dòng)態(tài)規(guī)劃等算法基本思想；介紹圖和問(wèn)題建模、數(shù)據(jù)結(jié)構(gòu)與算法的應(yīng)用和實(shí)踐。培養(yǎng)學(xué)生獨(dú)立地實(shí)現(xiàn)常用基本數(shù)據(jù)結(jié)構(gòu)的ADT以及相應(yīng)的STL數(shù)據(jù)結(jié)構(gòu)，解決一些實(shí)際問(wèn)題，獨(dú)立編寫中小型應(yīng)用程序。靈活應(yīng)用基本數(shù)據(jù)結(jié)構(gòu)，并結(jié)合排序、檢索、文件、索引等技術(shù)，合作編寫比較綜合的大型應(yīng)用程，提高學(xué)生的實(shí)際動(dòng)手能力。通過(guò)本課程的學(xué)習(xí)，為后續(xù)的專業(yè)基礎(chǔ)課和專業(yè)課程打下堅(jiān)實(shí)的基礎(chǔ)。3）課程特色把數(shù)據(jù)結(jié)構(gòu)與算法實(shí)習(xí)作為輔助數(shù)據(jù)結(jié)構(gòu)與算法的計(jì)算機(jī)系學(xué)生必修課，強(qiáng)化了計(jì)算機(jī)系學(xué)生的實(shí)踐能力訓(xùn)練。實(shí)習(xí)課內(nèi)容劃分為C/C+基本程序技巧訓(xùn)練、界面排錯(cuò)和測(cè)試、基本數(shù)據(jù)結(jié)構(gòu)訓(xùn)練、基本算法、數(shù)學(xué)建模訓(xùn)練5個(gè)模塊。從問(wèn)題求解的角度，培養(yǎng)學(xué)生數(shù)據(jù)結(jié)構(gòu)理論基礎(chǔ)、問(wèn)題數(shù)據(jù)和算法抽象、數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)的能力。在培養(yǎng)基本問(wèn)題求解能力的同時(shí)，注重實(shí)踐能力和工程能力的培