數(shù)據(jù)結(jié)構(gòu)與算法課程實(shí)施方案計(jì)劃安排書

1、計(jì)算機(jī)科學(xué)與工程學(xué)院集中性實(shí)踐教學(xué)計(jì)劃書（2012-2013 學(xué)年第 二 學(xué)期）課程名稱：數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)專業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù)軟件工程、網(wǎng)絡(luò)工程班級(jí)：計(jì)算機(jī)科學(xué)與技術(shù) 111-6軟件工程111 -4網(wǎng)絡(luò)工程111 -4課程負(fù)責(zé)人：李錫祚、王玲芬、李威指導(dǎo)教師分配情況:專業(yè)指導(dǎo)教師計(jì)算機(jī)科學(xué)與技術(shù)李威、孟佳娜、李靈華、李志潔、張恒博、劉爽軟件工程王玲芬、宋海玉、王存睿、崔永睿網(wǎng)絡(luò)工程李錫祚、郭海、王波、盧桂艷教學(xué)起止周：第 1至3教學(xué)周一、 教學(xué)目地與要求：數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)地目地是使同學(xué)們能夠根據(jù)數(shù)據(jù)對(duì)象地特性， 合理地組 織數(shù)據(jù)并能綜合運(yùn)用數(shù)據(jù)結(jié)構(gòu)與算法基本知識(shí)和程序設(shè)計(jì)基本知

2、識(shí)解決實(shí)際問題， 培 養(yǎng)基本地、良好地程序設(shè)計(jì)技能.二、主要階段、內(nèi)容、時(shí)間及地點(diǎn)安排（以天為單位計(jì)）：階段與內(nèi)容第1階段：指導(dǎo)教師布置設(shè)計(jì)任務(wù)并解析有關(guān)題目地設(shè)計(jì)指標(biāo)和任務(wù)地具體內(nèi)容，學(xué)生選擇題目，明確問題描述和要求，查閱資料 .（1天）；各班長(zhǎng)或?qū)W習(xí)委員將本班地選題表交給輔導(dǎo)教師，一人一題，每道題地選擇人數(shù)原則上不能超過3人，第一天課程設(shè)計(jì)結(jié)束后，每名學(xué)生都要確定題目.第2階段：明確題目要求、確定數(shù)據(jù)結(jié)構(gòu)、設(shè)計(jì)算法，編寫程序、調(diào)試程序、測(cè) 試程序（11天）；第一周，學(xué)生應(yīng)明確題目要求、確定數(shù)據(jù)地邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)、實(shí)現(xiàn)基本操作地編碼與調(diào)試、實(shí)現(xiàn)主菜單.第二周，完成核心算法地設(shè)計(jì)、編碼與調(diào)試

3、.第三周，完成剩余任務(wù)地編碼與調(diào)試，準(zhǔn)備足夠地測(cè)試數(shù)據(jù)，對(duì)軟件進(jìn)行測(cè)試與 調(diào)試.第3階段：完成設(shè)計(jì)任務(wù)，準(zhǔn)備驗(yàn)收、答辯（1天）；第4階段：答辯（上機(jī)演示，回答教師提問）（1天）；第5階段：撰寫課程設(shè)計(jì)報(bào)告（2天）.地點(diǎn)與時(shí)間地點(diǎn)：主校區(qū)計(jì)算機(jī)科學(xué)與工程學(xué)院機(jī)房時(shí)間：上午8:3011:30下午 1:304:30計(jì)算機(jī)科學(xué)與技術(shù)：地點(diǎn)：1-4班 二教 五樓大機(jī)房（549）一5-6班二教一樓嵌入式機(jī)房（124）課程設(shè)計(jì)上機(jī) 時(shí)間表周一周二周三周四周五第一周下午上午下午上午、下午第二周下午上午下午上午、下午第三周下午上午下午上午、下午（驗(yàn)收）軟件工程：課程設(shè)計(jì)上機(jī)時(shí)間表周一周二周三周四周五第一周上午、

4、下午下午上午、下午第二周上午、下午下午上午、下午:第三周上午、下午下午上午、下午（驗(yàn)收）網(wǎng)絡(luò)工程:課程設(shè)計(jì)上機(jī)時(shí)間表周一周二周三周四周五第一周上午、下午下午上午、下午第二周上午、下午下午上午、下午第三周上午、下午下午上午、下午（驗(yàn)收）班車時(shí)刻表（第1-第3教學(xué)周執(zhí)行）時(shí)間學(xué)生發(fā)車時(shí)間備注周一計(jì)科11級(jí)新校區(qū)- 老校區(qū) 中午12:55 老校區(qū)- 新校區(qū) 下午4 :40周二計(jì)科11級(jí)軟件11級(jí) 網(wǎng)絡(luò)11級(jí)新校區(qū)- 老校區(qū) 上午7 :45老校區(qū)- 新校區(qū) 中午11:45 ,（計(jì)科） 老校區(qū)- 新校區(qū) 下午4 :40,（軟件、網(wǎng)絡(luò)）周三軟件11級(jí)網(wǎng)絡(luò)11級(jí)新校區(qū)- 老校區(qū) 中午12:55 老校區(qū)- 新

5、校區(qū) 下午4 :40周四計(jì)科11級(jí)新校區(qū)- 老校區(qū) 中午12:55 老校區(qū)- 新校區(qū) 下午4 :40周五計(jì)科11級(jí)軟件11級(jí)網(wǎng)絡(luò)11級(jí)新校區(qū)- 老校區(qū)上午7 :45老校區(qū)- 新校區(qū)下午4 :40周日軟件12級(jí)網(wǎng)絡(luò)12級(jí)新校區(qū)- 老校區(qū)上午7 :45老校區(qū)- 新校區(qū)下午4 :40發(fā)車地點(diǎn)新校區(qū)：新校區(qū)北門學(xué)生公寓門口老校區(qū)：正門旗竿下三、課程設(shè)計(jì)題目及具體要求：1. 舞伴問題問題描述：一班有 m個(gè)女生、n個(gè)男生（m不等于n）,舉辦一場(chǎng)舞會(huì).男女生分別編號(hào)坐在 舞池兩邊地椅子上，每曲開始時(shí)，依次從男生和女生中各出一人配對(duì)跳舞 ，本曲沒成功配對(duì)者坐 著等待下一曲找舞伴，設(shè)計(jì)一個(gè)程序模擬舞伴配對(duì)過程基

6、本要求：輸入男、女學(xué)生地姓名、性別，由程序自動(dòng)為男女生編號(hào)，可以順序編號(hào)，也可 以隨機(jī)編號(hào)，輸出每曲配對(duì)情況（包括男、女生地姓名、性別和編號(hào)）原始數(shù)據(jù)和結(jié)果數(shù)據(jù)要保存到文件中測(cè)試數(shù)據(jù)：分別選擇男生多于女生、女生多于男生、男女生相等地三組測(cè)試數(shù)據(jù)提高要求：計(jì)算出任意一位男生（編號(hào)為X）和任意一位女生（編號(hào)為Y）,在第K曲配對(duì)跳舞地情況考核要求：（1）用隊(duì)列表示男、女學(xué)生，能夠從文件中讀取數(shù)據(jù)，文件中至少包括三組測(cè)試數(shù)據(jù)，分別為男生多于女生、女生多于男生、男女生人數(shù)相等順序輸入舞曲地編號(hào)，對(duì)于每支舞曲，輸入配對(duì)跳舞地男、女學(xué)生信息并把本支舞曲地配對(duì)情況保存到文件中完成上述任務(wù)，成績(jī)?yōu)榧案瘢?） 在

7、完成考核要求（1）地基礎(chǔ)上，直接輸出第 K支舞曲地配對(duì)情況，能夠處理異常，如 文件空、只有男生或只有女生等成績(jī)?yōu)橹械?. 成績(jī)管理問題描述：給出n個(gè)學(xué)生地考試成績(jī)表，成績(jī)表包括學(xué)生地學(xué)號(hào)、姓名、考試成績(jī)（高等數(shù) 學(xué)、英語(yǔ)、物理），設(shè)計(jì)一個(gè)簡(jiǎn)單地成績(jī)管理程序 基本要求：（1）建立成績(jī)表，能夠插入、刪除、修改學(xué)生地成績(jī)記錄；（2 ）按任一單科成績(jī)排序；（3）計(jì)算每名學(xué)生地平均成績(jī)；（4）統(tǒng)計(jì)任一單科成績(jī)不及格地學(xué)生人數(shù)，輸出不及格人數(shù)及不及格地學(xué)生名單（5）根據(jù)平均成績(jī)將成績(jī)表按由高到低地次序排列，統(tǒng)計(jì)每名學(xué)生在考試中獲得地名次，分?jǐn)?shù)相同地為同一名次，按名次輸出成績(jī)表（6）成績(jī)表保存在文件中，可以

8、從文件讀取數(shù)據(jù)測(cè)試數(shù)據(jù)：學(xué)生可以根據(jù)自己班級(jí)地考試成績(jī)單，任意截取一部分做為測(cè)試數(shù)據(jù)提高要求：成績(jī)表用鏈?zhǔn)浇Y(jié)構(gòu)表示，實(shí)現(xiàn)上述全部要求考核要求：（1 ）用順序結(jié)構(gòu)表示成績(jī)單，完成任務(wù)（1 ）（6）,成績(jī)?yōu)榧案?；?）用鏈表表示成績(jī)單，完成任務(wù)（1）（6）,且軟件容錯(cuò)能力強(qiáng)，成績(jī)?yōu)橹械?. 文學(xué)研究助手（*）問題描述：文學(xué)研究人員需要統(tǒng)計(jì)某篇英文小說中某些形容詞地出現(xiàn)次數(shù)和位置試寫一個(gè)實(shí)現(xiàn)這一目標(biāo)地文字統(tǒng)計(jì)系統(tǒng)，稱為文學(xué)研究助手”基本要求：英文小說存于一個(gè)文本文件中，待統(tǒng)計(jì)地詞匯集合要一次輸入完畢，即統(tǒng)計(jì)工作 必須在程序地一次運(yùn)行之后就全部完成文本文件名和待統(tǒng)計(jì)地詞匯從鍵盤輸入，程序地輸出結(jié)果是每

9、個(gè)詞地出現(xiàn)次數(shù)和出現(xiàn)位置所在行地行號(hào)，格式自行設(shè)計(jì)，結(jié)果保存到文件中提高要求：包含是否區(qū)別大、小寫兩種匹配模式，且讓用戶選擇測(cè)試數(shù)據(jù)：以你地 C/C+/JAVA源程序模擬英文小說，相應(yīng)語(yǔ)言地保留字集作為待統(tǒng)計(jì)地詞 匯集.考核要求：（1）用線性結(jié)構(gòu)表示文本文件和待統(tǒng)計(jì)地單詞，動(dòng)態(tài)分配內(nèi)存，完成基本要求地功能，成 績(jī)?yōu)橹械龋?）在完成基本要求地基礎(chǔ)上，完成提高要求，且用戶界面友好，能夠處理異常，成績(jī)?yōu)?良好4. 哈希表地設(shè)計(jì)與實(shí)現(xiàn)（*）問題描述：針對(duì)某個(gè)單位電話號(hào)碼簿，設(shè)計(jì)一個(gè)哈希表，并完成相應(yīng)地建表和查表程序基本要求：設(shè)每個(gè)記錄有下列數(shù)據(jù)項(xiàng)：電話號(hào)碼、用戶名、住址從鍵盤輸入各記錄，以用戶名為關(guān)鍵

10、字建立哈希表，哈希函數(shù)用除留取余數(shù)法構(gòu)造，采用線性探測(cè)法解決沖突可以插入、查找、刪除并顯示給定用戶名地記錄，并計(jì)算查找長(zhǎng)度，哈希表保存到文件中，并能從文件中讀取數(shù)據(jù)測(cè)試數(shù)據(jù)：取某個(gè)單位電話號(hào)碼簿中地100個(gè)以上記錄提高要求：（1）將電話號(hào)碼薄以文件形式保存到盤上，能夠按用戶名和電話號(hào)碼兩種形式建立哈希表并實(shí)現(xiàn)插入、查找、刪除表中元素地功能（2）對(duì)于相同地哈希函數(shù)，采用兩種或兩種以上地處理沖突地方法，如線性探測(cè)法和拉鏈法，比較不同地處理沖突地方法平均查找長(zhǎng)度地變化測(cè)試時(shí)，采用同一組測(cè)試數(shù)據(jù)，分別用不同地方法處理沖突，記錄并輸出各自地平均查找長(zhǎng)度（3）設(shè)計(jì)圖形用戶界面考核要求：（1）能夠從鍵盤和文

11、件輸入原始數(shù)據(jù)，能夠把變化地哈希表重新寫回到文件中，同時(shí)完成其它地基本要求，成績(jī)?yōu)橹械龋?）達(dá)到提高要求中地（1 ）或（2），或者同時(shí)達(dá)到（1 ）和（2），成績(jī)?yōu)榱己茫?）用C+或 MFC實(shí)現(xiàn)圖形用戶界面，成績(jī)?yōu)榱己?. 安排教學(xué)計(jì)劃（* ）問題描述：大學(xué)地每個(gè)專業(yè)都要制定教學(xué)計(jì)劃假設(shè)任何專業(yè)都有固定地學(xué)習(xí)年限，每學(xué)年含兩個(gè)學(xué)期，每學(xué)期地時(shí)間長(zhǎng)度和學(xué)分上限值均相等每個(gè)專業(yè)開設(shè)地課程都是確定地，而且課程在開設(shè)時(shí)間地安排上必須滿足先修關(guān)系每門課程有哪些先修課程是確定地，可以有任意多門，也可以沒有每門課程恰好占一個(gè)學(xué)期試在這樣地前提下設(shè)計(jì)一個(gè)教學(xué)計(jì)劃編制程序基本要求：輸入?yún)?shù)包括學(xué)期總數(shù)，一學(xué)期地學(xué)

12、分上限，每門課程地課程號(hào)、學(xué)分和直接先修課地課程號(hào)；允許兩種策略，一是使學(xué)生在各學(xué)期地學(xué)習(xí)負(fù)擔(dān)盡量均勻，二是使課程盡量集中 在前幾個(gè)學(xué)期；若根據(jù)給定地條件問題無解，則報(bào)告適當(dāng)?shù)匦畔?，否則輸出教學(xué)計(jì)劃表（如每個(gè) 學(xué)期所開設(shè)地課程地課程號(hào)及學(xué)分），同時(shí)將教學(xué)計(jì)劃輸出到用戶指定地文件中教學(xué)計(jì)劃地表格格式自行設(shè)定，可以從鍵盤讀取數(shù)據(jù)也可以從文件讀取數(shù)據(jù)，結(jié)果保存到文件中測(cè)試數(shù)據(jù)：學(xué)期總數(shù)為6,學(xué)分上限為10，該專業(yè)共開設(shè)12門.以10級(jí)某專業(yè)必修課與選修課為例，選擇12門課程及相應(yīng)學(xué)分，制定一個(gè)表明各門課程先后約束關(guān)系地有向圖提高要求：產(chǎn)生多種不同地方案，并使方案之間地差異盡可能地大考核要求：（1）達(dá)

13、到基本要求，成績(jī)?yōu)榱己?，如果不能把結(jié)果保存到文件中，成績(jī)?yōu)椴患案瘢?） 在達(dá)到基本要求地基礎(chǔ)上，產(chǎn)生3種以上地解決方案，且用戶界面友好，成績(jī)?yōu)閮?yōu)秀 6. 計(jì)算表達(dá)式地值（*）問題描述：對(duì)于給定地一個(gè)表達(dá)式，表達(dá)式中可以包括常數(shù)、算術(shù)運(yùn)行符（“ +”、“-”、“*”、“/”）和括號(hào)，編寫程序計(jì)算表達(dá)式地值基本要求：從鍵盤輸入一個(gè)正確地中綴表達(dá)式，將中綴表達(dá)式轉(zhuǎn)換為對(duì)應(yīng)地后綴表達(dá)式，計(jì)算后綴表達(dá)式地值測(cè)試數(shù)據(jù)：任意選取一個(gè)符合題目要求地表達(dá)式提高要求：（1）對(duì)于表達(dá)式中地簡(jiǎn)單錯(cuò)誤，能夠給出提示；（2）不僅提示錯(cuò)誤，也能給出錯(cuò)誤信息（3）表達(dá)式中可以包括單個(gè)字母表示地變量（4）能夠處理多種操作符（5

14、）實(shí)現(xiàn)包含簡(jiǎn)單運(yùn)算地計(jì)算器（6 ）實(shí)現(xiàn)一個(gè)包含簡(jiǎn)單運(yùn)算和函數(shù)運(yùn)算地計(jì)算器考核要求：（1 ）表達(dá)式中地?cái)?shù)據(jù)可以是整數(shù)或小數(shù)，達(dá)到基本要求，成績(jī)?yōu)榱己萌绻麅H能處理個(gè)位數(shù)，成績(jī)?yōu)榧案?，如果僅能處理整數(shù)，成績(jī)?yōu)橹械龋?）在達(dá)到基本要求地基礎(chǔ)之上，如果達(dá)到提高要求地2項(xiàng)或以上，成績(jī)可以為優(yōu)秀鼓勵(lì)設(shè)計(jì)圖形用戶界面7. 設(shè)計(jì)Huffman編碼器與解碼器（* ）問題描述：禾U用哈夫曼編碼進(jìn)行信息通訊可以大大提高信道地利用率，縮短信息傳輸時(shí)間，降低傳輸成本但是，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對(duì)待傳輸數(shù)據(jù)預(yù)先編碼；在接受端將傳 來地?cái)?shù)據(jù)進(jìn)行譯碼.對(duì)于雙工信道（即可以雙向傳輸信息地信道），每端都需要一個(gè)完整地編 /

15、譯碼系統(tǒng)試為這樣地信息收發(fā)站編寫一個(gè)哈夫曼碼地編/譯碼系統(tǒng)基本要求：根據(jù)某字符文件統(tǒng)計(jì)字符出現(xiàn)頻度，構(gòu)造Hufman樹，編制Hufman編碼，并將給定字符文件編碼，生成編碼文件；再將給定編碼文件解碼，生成字符文件（要求按二進(jìn)制位表示編碼）提高要求：改進(jìn) Huffman編碼，產(chǎn)生兩種以上地編碼方案，對(duì)同一組測(cè)試數(shù)據(jù)，用不同地編碼方案編碼，從文件長(zhǎng)度、算法復(fù)雜度等方面進(jìn)行比較測(cè)試數(shù)據(jù)：英文文檔文件或中文文檔文件考核要求：（1 ）對(duì)原文件編碼后，保存到新建文件中，將原文件與新文件比較，如果新文件長(zhǎng)度大于 原文件，則編碼失敗，成績(jī)不及格.如果達(dá)到題目地基本要求，成績(jī)?yōu)榱己茫?）達(dá)到提高要求，成績(jī)可以為

16、優(yōu)秀.8. 銀行業(yè)務(wù)模擬（*）問題描述：設(shè)銀行有四個(gè)服務(wù)窗口，一個(gè)等待隊(duì)列，每個(gè)窗口均可以辦理存款、取款、掛失、還貸業(yè)務(wù)，每種業(yè)務(wù)所需地服務(wù)時(shí)間不同，客戶到達(dá)銀行后，先到打號(hào)機(jī)上打號(hào)，號(hào)票上包括到 達(dá)時(shí)間、編號(hào)和需要辦理地業(yè)務(wù)，然后在銀行內(nèi)等候，當(dāng)任一服務(wù)窗口空閑時(shí)，處理等候客戶中排在最前面地客戶地業(yè)務(wù) 寫一個(gè)上述銀行業(yè)務(wù)地模擬系統(tǒng)，通過模擬方法求出客戶在銀行內(nèi)逗 留地平均時(shí)間和每個(gè)窗口辦理地客戶數(shù)及辦理地每種業(yè)務(wù)數(shù).基本要求：每個(gè)客戶到達(dá)銀行地時(shí)間和需要辦理地業(yè)務(wù)隨機(jī)產(chǎn)生，輸出一天客戶在銀行地平 均逗留時(shí)間和每個(gè)窗口每天辦理地客戶數(shù)和每種業(yè)務(wù)數(shù).提高要求：設(shè)計(jì)圖形用戶界面，模擬中國(guó)銀行真實(shí)地

17、打號(hào)機(jī)操作界面，當(dāng)用戶選擇一種業(yè)務(wù) 后，要提示用戶排在前面地人數(shù)測(cè)試數(shù)據(jù)：營(yíng)業(yè)時(shí)間為 8小時(shí)，其他模擬量自行設(shè)定考核要求：（1）數(shù)據(jù)結(jié)構(gòu)選擇合理，達(dá)到題目地基本要求，成績(jī)?yōu)榱己茫?）達(dá)到提高要求，用戶界面友好，能夠處理異常，成績(jī)可以為優(yōu)秀9. 航空訂票系統(tǒng)（*）問題描述：航空客運(yùn)訂票大地業(yè)務(wù)活動(dòng)包括：查詢航線，客票預(yù)訂，辦理退票等試設(shè)計(jì)一個(gè)航空客運(yùn)訂票系統(tǒng)，以使上述業(yè)務(wù)可以借助計(jì)算機(jī)來完成基本要求：每條航線涉及地信息：航班號(hào)，起飛城市，終到城市，中轉(zhuǎn)城市 （可選項(xiàng)），起飛時(shí)間，到達(dá) 時(shí)間，機(jī)型，飛行班期（星期幾），乘員定額，余票量，已訂票地客戶名單（包括姓名，訂票量， 艙位等級(jí)，等候替補(bǔ)地客戶

18、名單 (包括姓名，所需票量)，乘客信息(身份證號(hào)、姓名等)， 票價(jià)等系統(tǒng)實(shí)現(xiàn)地功能：(1)查詢功能：航班查詢：根據(jù)出發(fā)地、目地地、出發(fā)時(shí)間查詢，依據(jù)航班號(hào)查詢等輸出信息包括：航班號(hào)，出發(fā)地，終到地，星期幾飛行，最近一天航班地日期和余票額；按航班 號(hào)查詢時(shí)，要求采用二分查找法，航班號(hào)是字母、數(shù)字混編地，因此需要首先采用基數(shù)排序進(jìn)行 排序訂票人查詢：輸入訂票人身份證號(hào)碼或姓名查詢訂票人詳細(xì)信息并輸出乘客查詢：輸入乘客地身份證號(hào)碼或姓名查詢乘客地詳細(xì)信息并輸出(2) 錄入功能航班信息錄入：錄入航班地相關(guān)信息訂票：根據(jù)輸入地訂票人身份證號(hào)驗(yàn)證訂票人身份后，輸入詳細(xì)地乘客信息并進(jìn)行保存取消訂票：保存訂票

19、人取消訂票信息(3) 修改功能修改乘客信息：將查找到地乘客信息，進(jìn)行修改，然后進(jìn)行保存 修改訂票人信息：將查找到地訂票人地信息進(jìn)行修改然后進(jìn)行保存 修改航班信息：將查找到地航班信息進(jìn)行修改后保存(4) 刪除功能刪除乘客信息：將查找到地乘客信息，進(jìn)行刪除刪除訂票人信息：將查找到地訂票人地信息進(jìn)行刪除 刪除航班信息：將查找到地航班信息進(jìn)行刪除(5 )航班推薦功能：要求按最省錢和最省時(shí)間兩種方式對(duì)顧客進(jìn)行推薦，要求如果有中轉(zhuǎn) 站要給出詳細(xì)地出發(fā)到終點(diǎn)地路線，中轉(zhuǎn)時(shí)需包括候機(jī)地時(shí)間提高要求：(1) 設(shè)計(jì)圖形用戶界面(2) 增加會(huì)員管理功能，包括保存常旅客、積分管理、優(yōu)惠信息通知等，也可自行設(shè)計(jì)其 它功

20、能測(cè)試數(shù)據(jù)：至少選擇 50組數(shù)據(jù)(測(cè)試數(shù)據(jù)保存在文件中)，包括航班號(hào)、起飛地、目地地 、起飛時(shí)間、到達(dá)時(shí)間、最大乘客數(shù)、票價(jià)、飛行時(shí)間、經(jīng)停等信息，其他信息自行設(shè)定 考核要求：(1) 數(shù)據(jù)結(jié)構(gòu)選擇合理，達(dá)到題目地基本要求，成績(jī)?yōu)榱己?2) 達(dá)到提高要求，用戶界面友好，能夠處理異常，成績(jī)可以為優(yōu)秀10. 最小滿覆蓋問題(* )問題描述：在 8X8地國(guó)際象棋棋盤上，如果在放置若干個(gè)馬以后，使得整個(gè)棋盤地任意空.若去掉滿覆蓋中地.設(shè)計(jì)程序完成如下位置上所放置地棋子均能被這些馬吃掉，則稱這組放置為棋盤地一個(gè)滿覆蓋 任意一個(gè)棋子都會(huì)使這組放置不再是滿覆蓋，則稱這一滿覆蓋為極小滿覆蓋 要求.基本要求:求解

21、一個(gè)極小滿覆蓋，按照矩陣形式給出，用特殊符號(hào)表示馬提高要求:(1) 能畫出棋盤地圖形形式，或在其上動(dòng)態(tài)第演示試探過程;(2) 程序能方便地移植到其他規(guī)格地棋盤上提示：國(guó)際象棋中馬吃其他棋子地方式為馬走3X2格地對(duì)角線，有點(diǎn)像中國(guó)象棋中地馬走日,沒有“蹩馬腿”地規(guī)定可以用這個(gè)方法判定走棋是否正確：如果馬在白格，走一步后一定落在 黑格測(cè)試數(shù)據(jù)：8*8地矩陣考核要求：達(dá)到基本要求，成績(jī)?yōu)榱己?；達(dá)到提高要求(1)和(2)成績(jī)?yōu)閮?yōu)秀.11. 迷宮游戲(* )問題描述：程序開始運(yùn)行時(shí)顯示一個(gè)迷宮地圖，迷宮中央有一只老鼠，迷宮地右下方有一個(gè) 糧倉(cāng).游戲地任務(wù)是使用鍵盤上地方向健操縱老鼠在規(guī)定地時(shí)間內(nèi)走到糧倉(cāng)

22、處基本要求:(1) 老鼠形象可以辨認(rèn)，可用鍵盤操縱老鼠上下左右移動(dòng)；(2) 迷宮地墻足夠結(jié)實(shí)，老鼠不能穿墻而過；(3) 正確檢測(cè)結(jié)果，若老鼠在規(guī)定時(shí)間內(nèi)走到糧倉(cāng)處，提示成功，并給出一條路徑，否則提示失敗.提高要求:(1) 添加編輯迷宮功能，可修改當(dāng)前迷宮，修改內(nèi)容：墻變路、路變墻;(2) 增加闖關(guān)和計(jì)分功能；(3) 找出走出迷宮地所有路徑，以及最短路徑.測(cè)試數(shù)據(jù)：要求用10*10及以上地方陣或長(zhǎng)方陣考核要求：達(dá)到基本要求(1)(3)，成績(jī)?yōu)榱己?；達(dá)到提高要求(1)(3 )成績(jī)?yōu)閮?yōu)秀12. 程序源代碼地相似性(* )問題描述：對(duì)于兩個(gè) C+語(yǔ)言地源程序代碼，用哈希表地方法分別統(tǒng)計(jì)兩個(gè)程序中使用C

23、+ 語(yǔ)言關(guān)鍵字地情況，并最終按定量地計(jì)算結(jié)果，得出兩份程序地相似性基本要求：建立 C+語(yǔ)言關(guān)鍵字地哈希表，統(tǒng)計(jì)在每個(gè)源程序中C+關(guān)鍵字出現(xiàn)地頻度，得到兩個(gè)向量X1和X2,通過計(jì)算向量 X1和X2地相對(duì)距離來判斷兩個(gè)源程序地相似性.例如：關(guān)鍵字 Void Int For Charifelse while do break class程序1關(guān)鍵字頻度4304 307002程序2關(guān)鍵字頻度4 205 405 201X1=4,3,0,4,3,0,7,0,0,2X2=4,2,0,5,4,0,5,2,0,1設(shè)s是向量X1和X2地相對(duì)距離，s=sqrt（刀（Xi1-Xi2）2 ），當(dāng)X仁X2時(shí)，s=0,反映

24、出可能是 同一個(gè)程序；s值越大，則兩個(gè)程序地差別可能也越大，分析計(jì)算結(jié)果，給出相似度地結(jié)論測(cè)試數(shù)據(jù)：選擇若干組編譯和運(yùn)行都無誤地C+程序，程序之間有相近地和差別大地，用上述方法求s,對(duì)比兩個(gè)程序地相似性提高要求：建立源代碼用戶標(biāo)識(shí)符表，比較兩個(gè)源代碼用戶標(biāo)識(shí)符出現(xiàn)地頻度，綜合關(guān)鍵 字頻度和用戶標(biāo)識(shí)符頻度判斷兩個(gè)程序地相似性考核要求：從源代碼中分解單詞，判斷是否為關(guān)鍵字要采用效率高地方法，設(shè)計(jì)地哈希函數(shù)盡量產(chǎn)生較少地沖突，任選處理沖突地方法，選擇地測(cè)試數(shù)據(jù)要盡量包含多種情況，能夠處理異 常，達(dá)到這些要求成績(jī)?yōu)閮?yōu)秀，否則成績(jī)向下浮動(dòng)鼓勵(lì)按關(guān)鍵字和用戶標(biāo)識(shí)符判斷相似性，鼓勵(lì)設(shè)計(jì)圖形用戶界面13. 小

25、型文本編輯器（* ）問題描述：設(shè)計(jì)一個(gè)行編輯程序，使其具有通常行編輯器（如Vi、Edlin ）應(yīng)具備地基本功能.基本要求：編輯器應(yīng)具備對(duì)文本文件地查找、插人、刪除、修改、字符串替換、統(tǒng)計(jì)字?jǐn)?shù)，統(tǒng)計(jì)行數(shù)等功能，對(duì)于超過一屏地長(zhǎng)文件，應(yīng)能夠分頁(yè)顯示，查找功能用字符串匹配算法實(shí)現(xiàn)設(shè)計(jì)用戶接口命令，實(shí)現(xiàn)對(duì)文本地編輯具體地編輯命令，可參考數(shù)據(jù)結(jié)構(gòu)算法網(wǎng)絡(luò)教學(xué)平臺(tái)上提供地edlin、Vi地命令集.測(cè)試數(shù)據(jù)：任一文本文件.提高要求：1.可以支持“* ”、“ ? ”等通配符；2. 支持復(fù)制、粘貼等功能3. 支持多文檔同時(shí)編輯；考核要求：（1）界面可以是菜單形式，完成基本要求，成績(jī)可為優(yōu)秀，如果只實(shí)現(xiàn)了基本要求

26、地部分 功能，成績(jī)向下浮動(dòng).（2）可以用MFC設(shè)計(jì)界面，但其中地功能實(shí)現(xiàn)不能用類庫(kù)中地類提示：可以考慮用雙向鏈表實(shí)現(xiàn)，每一結(jié)點(diǎn)表示一行字符，注意每行字符不能超過255.14. 小型英漢詞典（* ）問題描述：設(shè)計(jì)一個(gè)英漢詞典，支持Member地查找、插入、刪除操作.基本要求：實(shí)現(xiàn)字典地常用方法有：有序線性表（用二分檢索實(shí)現(xiàn)）、AVL樹（二叉搜索樹）、 Patricia Tree、散列表等，任選一種方法實(shí)現(xiàn)字典地操作， 查找單詞、插入單詞（插入時(shí)，先查找， 找不到插入，找到提示用戶）、刪除單詞（刪除時(shí)，先查找，找到刪除，找不到提示用戶）字典是按字母順序排列地，不能用順序查找，插入或刪除單詞后，要保

27、持字典地有序性測(cè)試數(shù)據(jù)：任一英文單詞.提高要求：選用兩種以上地方法實(shí)現(xiàn)字典地操作，要比較不同實(shí)現(xiàn)算法地時(shí)間復(fù)雜度和空間復(fù)雜度考核要求：（1） 如果采用線性結(jié)構(gòu)且無序，成績(jī)?yōu)椴患案?（2）選擇合適地?cái)?shù)據(jù)結(jié)構(gòu)，達(dá)到了基本要求，成績(jī)?yōu)閮?yōu)秀（3 ）鼓勵(lì)設(shè)計(jì)圖形用戶界面提示：字典可以自己建立，但必須按字母az建立26個(gè)文件，建議從網(wǎng)上下載，文件類型為 txt.備注：1. 每道題目后面地*號(hào)，表示題目地難度系數(shù)；對(duì)應(yīng)地評(píng)定成績(jī)等級(jí)為及格（無 *號(hào)）、中等（*號(hào)）、良好（*號(hào)）、優(yōu)秀（*號(hào)），學(xué)生完成題目地基本要求，即可得到程序設(shè)計(jì)部分地相 應(yīng)等級(jí)成績(jī)，完成題目提高要求，成績(jī)可以向上浮動(dòng)，如果沒有完成基本要

28、求，成績(jī)向下浮動(dòng)， 直至不及格.2. 所有題目原則上需用 C+完成，不能用 C,也不能用類庫(kù)中地類完成題目，如用MFC則只能用MFC實(shí)現(xiàn)界面部分.3. 選擇附加題目地學(xué)生，對(duì)題目有疑問，找老師咨詢4. 特別注意：每道題地選擇人數(shù)不能超過3人，開學(xué)第一天，各班長(zhǎng)將選題情況表報(bào)給各班負(fù)責(zé)教師.四、應(yīng)閱讀地基本文獻(xiàn)：1 王紅梅，胡明，王濤編著.數(shù)據(jù)結(jié)構(gòu)（C+版）.北京：清華大學(xué)出版社，2005.7.2 譚浩強(qiáng)編著.C+面向?qū)ο蟪绦蛟O(shè)計(jì).北京：清華大學(xué)出版社，2006.1.面向?qū)ο蟪绦蛟O(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)、算法分析與設(shè)計(jì)相關(guān)地其它書籍和資料五、 考核方式（包括總成績(jī)地組成及分配比例）：課程設(shè)計(jì)總成績(jī)=平時(shí)出

29、勤（20% +設(shè)計(jì)報(bào)告（40% +上機(jī)驗(yàn)收及答辯（40%題目中給出地考核要求，相應(yīng)地成績(jī)僅僅是上機(jī)驗(yàn)收部分，課程設(shè)計(jì)總成績(jī)要結(jié)合學(xué)生地實(shí)踐能力、獨(dú)立分析解決問題地能力和創(chuàng)新精神，總結(jié)報(bào)告和答辯水平以及學(xué)習(xí)態(tài)度綜合考評(píng)成績(jī)分為優(yōu)、良、中、及格和不及格五個(gè)檔次六、其他有關(guān)問題地說明：無年月日課程負(fù)責(zé)人（簽字）：年月日專業(yè)教研室主任（簽字）：版權(quán)申明本文部分內(nèi)容，包括文字、圖片、以及設(shè)計(jì)等在網(wǎng)上搜集整理版權(quán)為個(gè)人所有This article in eludes some parts, in clud ing text, pictures, anddesig n. Copyright is pers onal own ership.b5E2RGbCAP用戶可將本文地內(nèi)容或服務(wù)用于個(gè)人學(xué)習(xí)、研究或欣賞，以及其他非商 業(yè)性或非盈利性用途，但同時(shí)應(yīng)遵守著作權(quán)法及其他相關(guān)法律地規(guī)定，不得 侵犯本網(wǎng)站及相關(guān)權(quán)利人地合法權(quán)利.除此以外，將本文任何內(nèi)容或