數(shù)據(jù)結構與算法課程設計計劃書

1、計算機科學與工程學院集中性實踐教學計劃書（ 2014-2015 學年第 一 學期）課程名稱： 數(shù)據(jù)結構與算法課程設計 專 業(yè)：計算機科學與技術 軟件工程、網(wǎng)絡工程班 級：計算機科學與技術131-6軟件工程131-4網(wǎng)絡工程131-4課程負責人： 李錫祚 指導教師分配情況：專業(yè)指導教師計算機科學與技術孟佳娜(1班) 張恒博(2班) 王巍(3班)劉爽(4班) 李威(5班) 李笑牛(6班) 軟件工程王玲芬(1班) 趙丹丹(2班) 王存睿(3班) 宋海玉(4班)網(wǎng)絡工程王曉強(1班) 郭海(2班) 于艷莉(3班) 王波(4班)教學起止周：第 17 至 19 教學周一、 教學目的：使學生能夠根據(jù)數(shù)據(jù)對象

2、的特性，合理的組織數(shù)據(jù)并能綜合運用數(shù)據(jù)結構與算法基本知識和程序設計基本知識解決實際問題，培養(yǎng)基本的、良好的程序設計技能。二、 主要階段、內(nèi)容、時間及地點安排（以天為單位計）：1、階段與內(nèi)容第1階段（17周，校企合作指導）在為期一周校企合作模式的訓練中，讓學生對數(shù)據(jù)結構有一定的掌握，熟悉數(shù)據(jù)結構的常用算法并靈活運用，熟練使用開發(fā)工具，簡單了解開發(fā)流程和團隊協(xié)作的開發(fā)模式，并充分認識到數(shù)據(jù)結構在以后實際的項目開發(fā)中的重要作用。（具體流程見企業(yè)實訓計劃書）第2階段：(18-19周，校內(nèi)教師指導)通過為期二周的課程設計集中訓練, 使學生能夠根據(jù)數(shù)據(jù)對象的特性，合理的組織數(shù)據(jù)并能綜合運用數(shù)據(jù)結構與算法基

3、本知識和程序設計基本知識解決實際問題。1. 指導教師布置設計任務并解析有關題目的設計指標和任務的具體內(nèi)容，學生選擇題目，明確問題描述和要求，查閱資料（要求：各班長或?qū)W習委員將本班的選題表交給輔導教師，一人一題，每道題的選擇人數(shù)原則上不能超過3人，第一天課程設計結束后，每名學生都要確定題目）（1天）。2. 明確題目要求、確定數(shù)據(jù)結構、設計算法，編寫程序、調(diào)試程序、測試程序（7天）（要求：準備足夠的測試數(shù)據(jù)，對軟件進行測試與調(diào)試。）。3. 驗收與答辯（上機演示，回答教師提問）（1天）；4. 撰寫課程設計報告（1天）。2、地點與時間 地點：金石灘校區(qū)計算機科學與工程學院實驗中心計科131-2班: f

4、401、計科133-4班f405、計科135-6班f409軟件工程131、4班: f209、軟件工程132-3班: f205網(wǎng)絡工程131-2班: f303、網(wǎng)絡工程123-4班: f307時間：上午8:3011:20 下午1:304:20計算機科學與技術：課 程 設 計 上 機 時 間 表周一周二周三周四周五17周上午、下午上午、下午上午、下午上午、下午上午、下午18周上午、下午上午計科12班i405計科56班i301元旦放假上午、下午(串到周日)19周上午、下午上午計科34班i405計科56班i301上午、下午（驗收）撰寫報告軟件工程： 課 程 設 計 上 機 時 間 表周一周二周三周四周

5、五17周上午、下午上午、下午上午、下午上午、下午上午、下午18周上午上午上午元旦休息上午(串到周日)19周上午下午上午下午(驗收)撰寫報告網(wǎng)絡工程： 課 程 設 計 上 機 時 間 表周一周二周三周四周五17周上午、下午上午、下午上午、下午上午、下午上午、下午18周上午下午上午元旦休息上午(串到周日)19周上午下午上午下午(驗收)撰寫報告三、課程設計題目及具體要求：1. 日歷系統(tǒng)問題描述：設計并實現(xiàn)輸出日歷的程序,根據(jù)用戶輸入的年份,按格式輸入該年度的日歷,包括月份,星期。基本要求:輸入任一年份, 顯示出該年的所有月份日期，對應的星期, 注意閏年情況顯示格式：1）月份：中文英文都可以，2）下一

6、行顯示星期，從周日到周六，中英文都可以3）下一行開始顯示日期從1號開始，并按其是周幾實際情況與上面的星期數(shù)垂直對齊測試數(shù)據(jù)：以2004年度為例輸入年份:2004輸入該年1月1日是星期幾：4輸出日歷如下：the calendar of the year 2004. januray 1 february 2 sun mon tue wed thu fri sat sun mon tue wed thu fri sat 1 2 3 1 2 3 4 5 6 7 4 5 6 7 8 9 10 8 9 10 11 12 13 14 11 12 13 14 15 16 17 15 16 17 18 19 2

7、0 21 18 19 20 21 22 23 24 22 23 24 25 26 27 28 25 26 27 28 29 30 31 29 = = march 3 april 4 sun mon tue wed thu fri sat sun mon tue wed thu fri sat 1 2 3 4 5 6 1 2 3 7 8 9 10 11 12 13 4 5 6 7 8 9 10 14 15 16 17 18 19 20 11 12 13 14 15 16 17 21 22 23 24 25 26 27 18 19 20 21 22 23 24 28 29 30 31 25 26

8、27 28 29 30 = =提高要求: 如果能自動對應星期，可得到良好成績。2. 舞伴問題問題描述：一班有m個女生、n個男生(m不等于n), 舉辦一場舞會. 男女生分別編號坐在舞池兩邊的椅子上，每曲開始時, 依次從男生和女生中各出一人配對跳舞, 本曲沒成功配對者坐著等待下一曲找舞伴，設計一個程序模擬舞伴配對過程?；疽螅狠斎肽小⑴畬W生的姓名、性別，由程序自動為男女生編號，可以順序編號，也可以隨機編號，輸出每曲配對情況（包括男、女生的姓名、性別和編號）。原始數(shù)據(jù)和結果數(shù)據(jù)要保存到文件中。測試數(shù)據(jù)：分別選擇男生多于女生、女生多于男生、男女生相等的三組測試數(shù)據(jù)提高要求：計算出任意一位男生(編號為

9、x)和任意一位女生(編號為y), 在第k曲配對跳舞的情況。考核要求：（1） 用隊列表示男、女學生，能夠從文件中讀取數(shù)據(jù)，文件中至少包括三組測試數(shù)據(jù)，分別為男生多于女生、女生多于男生、男女生人數(shù)相等。順序輸入舞曲的編號，對于每支舞曲，輸入配對跳舞的男、女學生信息。并把本支舞曲的配對情況保存到文件中。完成上述任務，成績?yōu)榧案?。?） 在完成考核要求（1）的基礎上，直接輸出第k支舞曲的配對情況，能夠處理異常，如文件空、只有男生或只有女生等。成績?yōu)橹械取?. 安排教學計劃問題描述：大學的每個專業(yè)都要制定教學計劃。假設任何專業(yè)都有固定的學習年限，每學年含兩個學期，每學期的時間長度和學分上限值均相等。每個

10、專業(yè)開設的課程都是確定的，而且課程在開設時間的安排上必須滿足先修關系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課程恰好占一個學期。試在這樣的前提下設計一個教學計劃編制程序?；疽螅狠斎?yún)?shù)包括學期總數(shù)，一學期的學分上限，每門課程的課程號、學分和直接先修課的課程號；允許兩種策略，一是使學生在各學期的學習負擔盡量均勻，二是使課程盡量集中在前幾個學期；若根據(jù)給定的條件問題無解，則報告適當?shù)男畔ⅲ駝t輸出教學計劃表（如每個學期所開設的課程的課程號及學分），同時將教學計劃輸出到用戶指定的文件中。教學計劃的表格格式自行設定, 可以從鍵盤讀取數(shù)據(jù)也可以從文件讀取數(shù)據(jù), 結果保存到文

11、件中。測試數(shù)據(jù)：學期總數(shù)為6，學分上限為10，該專業(yè)共開設12門課。以12級某專業(yè)必修課與選修課為例，選擇12門課程及相應學分，制定一個表明各門課程先后約束關系的有向圖。提高要求：產(chǎn)生多種不同的方案，并使方案之間的差異盡可能地大?？己艘螅海?） 達到基本要求，成績?yōu)榱己?，如果不能把結果保存到文件中，成績?yōu)椴患案?。?） 在達到基本要求的基礎上，產(chǎn)生3種以上的解決方案，且用戶界面友好，成績?yōu)閮?yōu)秀。4. 計算表達式的值問題描述：對于給定的一個表達式，表達式中可以包括常數(shù)、算術運行符（“+”、“-”、“*”、“/”）和括號，編寫程序計算表達式的值?；疽螅簭逆I盤輸入一個正確的中綴表達式，將中綴表

12、達式轉(zhuǎn)換為對應的后綴表達式，計算后綴表達式的值。測試數(shù)據(jù)：任意選取一個符合題目要求的表達式。提高要求：（1）對于表達式中的簡單錯誤，能夠給出提示；（2）不僅提示錯誤，也能給出錯誤信息（3）表達式中可以包括單個字母表示的變量（4）能夠處理多種操作符（5）實現(xiàn)包含簡單運算的計算器（6）實現(xiàn)一個包含簡單運算和函數(shù)運算的計算器考核要求：（1） 表達式中的數(shù)據(jù)可以是整數(shù)或小數(shù)，達到基本要求，成績?yōu)榱己谩Ｈ绻麅H能處理個位數(shù)，成績?yōu)榧案?，如果僅能處理整數(shù)，成績?yōu)橹械?。?） 在達到基本要求的基礎之上，如果達到提高要求的2項或以上，成績可以為優(yōu)秀。鼓勵設計圖形用戶界面。5. 設計huffman 編碼器與解碼器

13、問題描述：利用哈夫曼編碼進行信息通訊可以大大提高信道的利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳輸數(shù)據(jù)預先編碼；在接受端將傳來的數(shù)據(jù)進行譯碼。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站編寫一個哈夫曼碼的編/譯碼系統(tǒng)?；疽螅焊鶕?jù)某字符文件統(tǒng)計字符出現(xiàn)頻度，構造huffman 樹，編制huffman編碼，并將給定字符文件編碼，生成編碼文件；再將給定編碼文件解碼，生成字符文件。（要求按二進制位表示編碼）提高要求：改進huffman編碼，產(chǎn)生兩種以上的編碼方案，對同一組測試數(shù)據(jù)，用不同的編碼方案編碼，從文

14、件長度、算法復雜度等方面進行比較。測試數(shù)據(jù)：英文文檔文件或中文文檔文件。考核要求：（1） 對原文件編碼后，保存到新建文件中，將原文件與新文件比較，如果新文件長度大于原文件，則編碼失敗，成績不及格。如果達到題目的基本要求，成績?yōu)榱己?。?） 達到提高要求，成績可以為優(yōu)秀。6. 銀行業(yè)務模擬問題描述：設銀行有四個服務窗口，一個等待隊列, 每個窗口均可以辦理存款、取款、掛失、還貸業(yè)務，每種業(yè)務所需的服務時間不同，客戶到達銀行后，先到打號機上打號，號票上包括到達時間、編號和需要辦理的業(yè)務，然后在銀行內(nèi)等候, 當任一服務窗口空閑時,處理等候客戶中排在最前面的客戶的業(yè)務。寫一個上述銀行業(yè)務的模擬系統(tǒng),通過

15、模擬方法求出客戶在銀行內(nèi)逗留的平均時間和每個窗口辦理的客戶數(shù)及辦理的每種業(yè)務數(shù)?；疽螅好總€客戶到達銀行的時間和需要辦理的業(yè)務隨機產(chǎn)生，輸出一天客戶在銀行的平均逗留時間和每個窗口每天辦理的客戶數(shù)和每種業(yè)務數(shù)。提高要求：設計圖形用戶界面，模擬中國銀行真實的打號機操作界面，當用戶選擇一種業(yè)務后，要提示用戶排在前面的人數(shù)。測試數(shù)據(jù)：營業(yè)時間為8小時，其他模擬量自行設定?？己艘螅海?） 用隊列實現(xiàn);（2） 數(shù)據(jù)結構選擇合理，達到題目的基本要求，成績?yōu)榱己?。?） 達到提高要求，用戶界面友好，能夠處理異常，成績可以為優(yōu)秀7. 航空訂票系統(tǒng)問題描述：航空客運訂票的業(yè)務活動包括：查詢航線，客票預訂，辦理

16、退票等。試設計一個航空客運訂票系統(tǒng)，以使上述業(yè)務可以借助計算機來完成?；疽? 每條航線涉及的信息：航班號，起飛城市，終到城市，中轉(zhuǎn)城市(可選項)，起飛時間，到達時間，機型，飛行班期(星期幾)，乘員定額，余票量，已訂票的客戶名單(包括姓名，訂票量，艙位等級），等候替補的客戶名單(包括姓名，所需票量)，乘客信息（身份證號、姓名等），票價等。系統(tǒng)實現(xiàn)的功能：（） 查詢功能：航班查詢：根據(jù)出發(fā)地、目的地、出發(fā)時間查詢，依據(jù)航班號查詢等輸出信息包括：航班號，出發(fā)地，終到地，星期幾飛行，最近一天航班的日期和余票額；按航班號查詢時，要求采用二分查找法，航班號是字母、數(shù)字混編的，因此需要首先采用基數(shù)排序進

17、行排序。訂票人查詢：輸入訂票人身份證號碼或姓名查詢訂票人詳細信息并輸出。 乘客查詢：輸入乘客的身份證號碼或姓名查詢乘客的詳細信息并輸出。 (）錄入功能航班信息錄入：錄入航班的相關信息。訂票：根據(jù)輸入的訂票人身份證號驗證訂票人身份后，輸入詳細的乘客信息并進行保存。取消訂票：取消訂票信息。(）修改功能修改乘客信息：將查找到的乘客信息，進行修改，然后進行保存。修改訂票人信息：將查找到的訂票人的信息進行修改然后進行保存。修改航班信息：將查找到的 的航班信息進行修改后保存。(） 刪除功能刪除乘客信息：將查找到的乘客信息，進行刪除。刪除訂票人信息：將查找到的訂票人的信息進行刪除。刪除航班信息：將查找到的航

18、班信息進行刪除。()航班推薦功能：要求按最省錢和最省時間兩種方式對顧客進行推薦，要求如果有中轉(zhuǎn)站要給出詳細的出發(fā)到終點的路線，中轉(zhuǎn)時需包括候機的時間。提高要求：（） 設計圖形用戶界面。（） 增加會員管理功能，包括保存常旅客、積分管理、優(yōu)惠信息通知等，也可自行設計其它功能。測試數(shù)據(jù)：至少選擇50組數(shù)據(jù)（測試數(shù)據(jù)保存在文件中），包括航班號、起飛地、目的地、起飛時間、到達時間、最大乘客數(shù)、票價、飛行時間、經(jīng)停等信息，其他信息自行設定?？己艘螅海ǎ?數(shù)據(jù)結構選擇合理，達到題目的基本要求，成績?yōu)榱己谩＃ǎ?達到提高要求，用戶界面友好，能夠處理異常，成績可以為優(yōu)秀。8. 最小滿覆蓋問題問題描述：在88的

19、國際象棋棋盤上，如果在放置若干個馬以后，使得整個棋盤的任意空位置上所放置的棋子均能被這些馬吃掉，則稱這組放置為棋盤的一個滿覆蓋。若去掉滿覆蓋中的任意一個棋子都會使這組放置不再是滿覆蓋，則稱這一滿覆蓋為極小滿覆蓋。設計程序完成如下功能?；疽?求解一個極小滿覆蓋，按照矩陣形式給出，用特殊符號表示馬。并驗證你的方法滿足極小滿覆蓋。提高要求：（1） 得到最優(yōu)滿覆蓋問題，并能證明。能畫出棋盤的圖形形式，或在其上動態(tài)演示試探過程；（2） 程序能方便地移植到其他規(guī)格的棋盤上，如1616等。提示：國際象棋中馬吃其他棋子的方式為馬走32格的對角線，有點像中國象棋中的馬走日，沒有“蹩馬腿”的規(guī)定?？梢杂眠@個方

20、法判定走棋是否正確：如果馬在白格，走一步后一定落在黑格。測試數(shù)據(jù)：8*8的矩陣?？己艘螅哼_到基本要求，成績?yōu)榱己?；達到提高要求（1）和（2）成績?yōu)閮?yōu)秀。9. 迷宮游戲問題描述：程序開始運行時顯示一個迷宮地圖，迷宮中央有一只老鼠，迷宮的右下方有一個糧倉。游戲的任務是使用鍵盤上的方向健操縱老鼠在規(guī)定的時間內(nèi)走到糧倉處?；疽螅海?） 老鼠形象可以辨認，可用鍵盤操縱老鼠上下左右移動；（2） 迷宮的墻足夠結實，老鼠不能穿墻而過；（3） 正確檢測結果，若老鼠在規(guī)定時間內(nèi)走到糧倉處，提示成功，并給出一條路徑，否則提示失敗。提高要求：（1） 添加編輯迷宮功能，可修改當前迷宮，修改內(nèi)容：墻變路、路變墻；（

21、2） 增加闖關和計分功能；（3） 找出走出迷宮的所有路徑，以及最短路徑。測試數(shù)據(jù)：要求用10*10及以上的方陣或長方陣?？己艘螅哼_到基本要求（1）（3），成績?yōu)榱己茫贿_到提高要求（1）（3）成績?yōu)閮?yōu)秀。10. 程序源代碼的相似性問題描述：對于兩個c+語言的源程序代碼，用哈希表的方法分別統(tǒng)計兩個程序中使用c+語言關鍵字的情況，并最終按定量的計算結果，得出兩份程序的相似性。 基本要求：建立c+語言關鍵字的哈希表，統(tǒng)計在每個源程序中c+關鍵字出現(xiàn)的頻度, 得到兩個向量x1和x2，通過計算向量x1和x2的相對距離來判斷兩個源程序的相似性。例如: 關鍵字： void int for char if e

22、lse while do break class程序1關鍵字頻度： 4 3 0 4 3 0 7 0 0 2程序2關鍵字頻度： 4 2 0 5 4 0 5 2 0 1 x1=4,3,0,4,3,0,7,0,0,2x2=4,2,0,5,4,0,5,2,0,1 設s是向量x1和x2的相對距離，s=sqrt( (xi1-xi2) 2 )，當x1=x2時，s=0, 反映出可能是同一個程序；s值越大，則兩個程序的差別可能也越大，分析計算結果，給出相似度的結論。測試數(shù)據(jù): 選擇若干組編譯和運行都無誤的c+程序，程序之間有相近的和差別大的，用上述方法求s, 對比兩個程序的相似性。 提高要求：建立源代碼用戶標識

23、符表，比較兩個源代碼用戶標識符出現(xiàn)的頻度，綜合關鍵字頻度和用戶標識符頻度判斷兩個程序的相似性?？己艘螅簭脑创a中分解單詞，判斷是否為關鍵字要采用效率高的方法，設計的哈希函數(shù)盡量產(chǎn)生較少的沖突，任選處理沖突的方法，選擇的測試數(shù)據(jù)要盡量包含多種情況，能夠處理異常，達到這些要求成績?yōu)閮?yōu)秀，否則成績向下浮動。鼓勵按關鍵字和用戶標識符判斷相似性，鼓勵設計圖形用戶界面。11. 小型文本編輯器問題描述：設計一個行編輯程序，使其具有通常行編輯器(如vi、edlin)應具備的基本功能?；疽螅壕庉嬈鲬邆鋵ξ谋疚募牟檎摇⒉迦?、刪除、修改、字符串替換、統(tǒng)計字數(shù)，統(tǒng)計行數(shù)等功能，對于超過一屏的長文件，應能夠分

24、頁顯示，查找功能用字符串匹配算法實現(xiàn)。設計用戶接口命令，實現(xiàn)對文本的編輯。具體的編輯命令，可參考數(shù)據(jù)結構算法網(wǎng)絡教學平臺上提供的edlin、vi的命令集。測試數(shù)據(jù)：任一文本文件。提高要求：（1）可以支持“* ”、“? ”等通配符； （2）支持復制、粘貼等功能； （3）支持多文檔同時編輯?？己艘螅海?） 界面可以是菜單形式，完成基本要求，成績可為優(yōu)秀，如果只實現(xiàn)了基本要求的部分功能，成績向下浮動。（2） 可以用mfc設計界面，但其中的功能實現(xiàn)不能用類庫中的類。提示：可以考慮用雙向鏈表實現(xiàn)，每一結點表示一行字符，注意每行字符不能超過255。12. 小型英漢詞典問題描述：設計一個英漢詞典，支持member的查找、插入、刪除操