2012級計科(1)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計教學(xué)大綱

1、數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計教學(xué)大綱課程編號：B課程中文名稱：數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計課程英文名稱：Curriculum-design of Data Structures and Algorithms課程類別：實踐教學(xué)周數(shù)：2學(xué) 分：2適用專業(yè)：計算機(jī)科學(xué)與技術(shù)一、課程設(shè)計的性質(zhì)、目的對學(xué)生數(shù)據(jù)結(jié)構(gòu)知識的全面綜合訓(xùn)練，把書上學(xué)到的知識用于解決實際問題、培養(yǎng)今后軟件開發(fā)工作所需的動手實踐能力，包括問題分析、總體結(jié)構(gòu)設(shè)計，用戶界面的設(shè)計、程序設(shè)計時的基本技能和技巧，以及一整套軟件工作規(guī)范的訓(xùn)練和團(tuán)體協(xié)作精神的培養(yǎng)。二、 課程設(shè)計基本要求（1）了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能

2、力；（2）初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；（3）提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力；（4）訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進(jìn)行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。三、課程設(shè)計教學(xué)內(nèi)容根據(jù)教材數(shù)據(jù)結(jié)構(gòu)題集（C語言版）（嚴(yán)蔚敏、吳偉民主編）選擇課程設(shè)計題目，或選擇下列與實際應(yīng)用緊密結(jié)合的較綜合性的題目，要求通過設(shè)計，在數(shù)據(jù)結(jié)構(gòu)的邏輯特性和物理表示、數(shù)據(jù)結(jié)構(gòu)的選擇應(yīng)用、算法的設(shè)計及其實現(xiàn)等方面加深對課程基本內(nèi)容的理解和綜合運用。以下列出一些可供選擇的題目：1.一元多項式的運算設(shè)計要求：計算任意兩個一元多項式的加法、

3、減法以及乘法。2.算術(shù)表達(dá)式求值設(shè)計要求：將任意一個算術(shù)表達(dá)式轉(zhuǎn)化為逆波蘭表示，并根據(jù)逆波蘭表示計算表達(dá)是的值。3.舞伴問題假定在一舞會上，男士排成一隊，女士排成一隊。跳舞開始時，依次從男隊和女隊的隊頭各出一人配成舞伴。若兩隊初始人數(shù)不相同，則較長的那一隊中未配對者等待下一輪舞曲。設(shè)計要求：模擬上述舞伴系統(tǒng)，并能計算對于任何男士A和女士B在哪一輪舞曲中的k次跳舞？4.集合的等價劃分設(shè)計要求：對于任何一個集合及其上的一個等價關(guān)系（要驗證此關(guān)系的等價性），給出該集合的等價劃分。5. 簡易家譜系統(tǒng)設(shè)計要求：輸入家族成員情況，建立樹結(jié)構(gòu)，統(tǒng)計家族成員人數(shù)，能查詢家族成員輩份情況。6. 哈夫曼樹的應(yīng)用設(shè)

4、計要求：針對字符集A及其各字符的頻率值（可統(tǒng)計獲得）給出其中給字符哈夫曼編碼，并針對一段文本（定義在A上）進(jìn)行編碼和譯碼，實現(xiàn)一個哈夫曼編碼/譯碼系統(tǒng)。7.地圖著色問題設(shè)計要求：已知中國地圖，對各省進(jìn)行著色，要求相鄰省所使用的顏色不同，并保證使用的顏色總數(shù)最少。8.小型文本編輯器設(shè)計要求：設(shè)計一個文本編輯器，使其具有通常編輯器（如Notepad）具備的功能。9.校園導(dǎo)航問題設(shè)計要求：設(shè)計你的學(xué)校的平面圖，至少包括10個以上的場所，每兩個場所間可以有不同的路，且路長也可能不同，找出從任意場所到達(dá)另一場所的最佳路徑（最短路徑）。10.學(xué)校超市選址問題（帶權(quán)有向圖的中心點）設(shè)計要求：對于某一學(xué)校超市

5、，其他各單位到其的距離不同，同時各單位人員去超市的頻度也不同。請為超市選址，要求實現(xiàn)總體最優(yōu)。11.教學(xué)計劃編制問題 設(shè)計要求：針對計算機(jī)本科課程，根據(jù)課程之間的依賴關(guān)系（如離散數(shù)學(xué)應(yīng)在數(shù)據(jù)結(jié)構(gòu)之前開設(shè)）制定課程安排計劃，并滿足各學(xué)期課程數(shù)目大致相同。12. 哈希表及其應(yīng)用建立一個小型信息管理系統(tǒng)（可以是圖書、人事、學(xué)生、物資、商品等任何信息管理系統(tǒng)）。要求：使用哈希查找表存儲信息；實現(xiàn)查找、插入、刪除、統(tǒng)計、輸出等功能；13.關(guān)鍵路徑設(shè)計要求：對于任何大型工程項目（由若干小工程組成），求其關(guān)鍵路徑。14.最小生成樹問題設(shè)計要求：在n個城市之間建設(shè)網(wǎng)絡(luò)，只需保證連通即可，求最經(jīng)濟(jì)的架設(shè)方法。1

6、5. 二叉排序樹與平衡二叉排序樹基本操作的實現(xiàn)設(shè)計要求：用二叉鏈表作存儲結(jié)構(gòu)，編寫程序?qū)崿F(xiàn)二叉排序樹上的基本操作。16. 運動會成績管理系統(tǒng)設(shè)計要求：學(xué)生運動會成績數(shù)據(jù)庫系統(tǒng)記錄某校運動會上全部運動項目，各系獲得的分?jǐn)?shù)及排名的情況，包括50、100、200，400，1500米，跳高，跳遠(yuǎn)，標(biāo)槍，鉛球鐵餅等。進(jìn)入系統(tǒng)后可以輸入和修改某個項目的結(jié)果情況，可以按各系院編號輸出總分；按總分排序；按男團(tuán)體總分排序 ；按系院編號查詢；按項目編號查詢；按女團(tuán)體總分排序。17哈夫曼樹的應(yīng)用設(shè)計要求：從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立哈夫曼樹并將它存于文件hfmTree中.將已在內(nèi)存中的哈夫曼

7、樹以直觀的方式（比如樹）顯示在終端上；利用已經(jīng)建好的哈夫曼樹（如不在內(nèi)存，則從文件htmTree中讀入），對文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中，并輸出結(jié)果，將文件CodeFile以緊湊格式先是在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrint中。利用已建好的哈夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中，并輸出結(jié)果。18圖的遍歷設(shè)計要求：實現(xiàn)圖的深度優(yōu)先, 廣度優(yōu)先遍歷算法，并輸出原圖結(jié)構(gòu)及遍歷結(jié)果。19矩陣乘法設(shè)計要求：設(shè)計一個矩陣相乘的程序，首先從鍵盤輸入兩個矩陣A，B的內(nèi)容，并輸出兩個矩陣

8、，輸出矩陣A、B相乘的結(jié)果。20數(shù)組應(yīng)用設(shè)計要求：按照行優(yōu)先順序?qū)⑤斎氲臄?shù)據(jù)建成4維數(shù)組，再按照列優(yōu)先順序輸出結(jié)果，給出任意處的元素值，并給出對應(yīng)的一維數(shù)組中的序號。21n元多項式乘法設(shè)計要求：完成兩個n元多項式作乘法，給出明確的等式形式。22集合運算設(shè)計要求：使用鏈表來表示集合，完成集合的合并，求交集等操作。23. 公園導(dǎo)游圖設(shè)計要求：給出一張某公園的導(dǎo)游圖，游客通過終端詢問可知：從某一景點到另一景點的最短路徑。游客從公園大門進(jìn)入，選一條最佳路線，使游客可以不重復(fù)地游覽各景點，最后回到出口（出口就在入口旁邊）。24. 商店存貨管理系統(tǒng)設(shè)計要求：建立一商店存貨管理系統(tǒng)，要求每次出貨時取進(jìn)貨時間

9、最早且最接近保質(zhì)期中止時間的貨物。25.漢諾塔的實現(xiàn)設(shè)計要求：編程序顯示n（n0)個人按順時針方向圍坐一圈，每個人持有一個正整數(shù)密碼。開始時任選一個正整數(shù)做為報數(shù)上限m，從第一個人開始順時針方向自1起順序報數(shù)，報到m是停止報數(shù)，報m的人出列，將他的密碼作為新的m值，從他的下一個人開始重新從1報數(shù)。如此下去，直到所有人全部出列為止。令n最大值取30。要求設(shè)計一個程序模擬此過程，求出出列編號序列。指導(dǎo)老師還可以根據(jù)學(xué)生實際掌握程度以及知識技術(shù)的更新適當(dāng)對題目進(jìn)行調(diào)整。四、課程設(shè)計時間分配教學(xué)內(nèi)容學(xué)時地點備注設(shè)計動員，布置任務(wù)1天教室查閱資料，分析、討論與設(shè)計2天圖書館、軟件實驗室編寫程序，進(jìn)行調(diào)試

10、4天軟件實驗室完成模塊聯(lián)調(diào)，進(jìn)行測試2天軟件實驗室成果驗收，完成設(shè)計報告1天軟件實驗室五、課程設(shè)計考核辦法與成績評定由指導(dǎo)教師根據(jù)學(xué)生完成任務(wù)的情況、課程設(shè)計說明書的質(zhì)量和課程設(shè)計過程中的工作態(tài)度等綜合打分，成績評定實行優(yōu)、良、中、及格和不及格五個等級，從三個方面評定成績：平時表現(xiàn)；設(shè)計報告；程序的演示。不及格者不能得到相應(yīng)的學(xué)分，需重新做課程設(shè)計，經(jīng)指導(dǎo)教師考核及格后，方可取得相應(yīng)學(xué)分。六、課程設(shè)計指導(dǎo)書教材：1 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）M. (第一版)北京：清華大學(xué)出版社.1997 參考書：2 Sartaj Sahni. Data Structure, Algorithms,

11、and Application in C+. The McGraw-Hill Company Inc.1998M (第一版) (數(shù)據(jù)結(jié)構(gòu)、算法與應(yīng)用C+語言描述.北京:機(jī)械工業(yè)出版社.19993 Willan Ford,Willian Topp. Data Structures with C+. New Jersey:Prentice Hall Inc, Adivision Simon & Schuster Company,1996M (第一版) (數(shù)據(jù)結(jié)構(gòu)C+語言描述.北京:清華大學(xué)出版社，19974 徐孝凱.數(shù)據(jù)結(jié)構(gòu)實用教程（C/C+描述）M. (第一版)北京:清華大學(xué)出版社.19995 陳慧南.數(shù)據(jù)結(jié)構(gòu)（使用C+語言描述）M. (第一版)南京:東南大學(xué)出版社.