數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)計(jì)劃書(shū)---2(11級(jí))

1、計(jì)算機(jī)科學(xué)與工程學(xué)院集中性實(shí)踐教學(xué)計(jì)劃書(shū)（ 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í)和程序

2、設(shè)計(jì)基本知識(shí)解決實(shí)際問(wèn)題，培養(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é)生選擇題目，明確問(wèn)題描述和要求，查閱資料。（1天）；各班長(zhǎng)或?qū)W習(xí)委員將本班的選題表交給輔導(dǎo)教師，一人一題，每道題的選擇人數(shù)原則上不能超過(guò)3人，第一天課程設(shè)計(jì)結(jié)束后，每名學(xué)生都要確定題目。第2階段：明確題目要求、確定數(shù)據(jù)結(jié)構(gòu)、設(shè)計(jì)算法，編寫(xiě)程序、調(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ì)、編碼與

3、調(diào)試。第三周，完成剩余任務(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ī)演示，回答教師提問(wèn)）（1天）；第5階段：撰寫(xiě)課程設(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)收）班車(chē)時(shí)刻表（第第教學(xué)周執(zhí)行）時(shí)間學(xué)生發(fā)車(chē)時(shí)間備注周一計(jì)科11級(jí)新校區(qū)->老校區(qū)中午12:55老校區(qū)->新校區(qū)下午:40周二計(jì)科11級(jí)軟件11級(jí)網(wǎng)絡(luò)11級(jí)新校區(qū)->老校區(qū)上午:45老校區(qū)->新校區(qū)中午11:45，（計(jì)科）老校區(qū)->新校區(qū)下午:40，(軟件、網(wǎng)絡(luò)）周三軟件11級(jí)網(wǎng)絡(luò)1

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

6、沒(méi)成功配對(duì)者坐著等待下一曲找舞伴，設(shè)計(jì)一個(gè)程序模擬舞伴配對(duì)過(guò)程。基本要求：輸入男、女學(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ì)跳舞的男、女

7、學(xué)生信息。并把本支舞曲的配對(duì)情況保存到文件中。完成上述任務(wù)，成績(jī)?yōu)榧案?。?） 在完成考核要求（1）的基礎(chǔ)上，直接輸出第K支舞曲的配對(duì)情況，能夠處理異常，如文件空、只有男生或只有女生等。成績(jī)?yōu)橹械取?. 成績(jī)管理問(wèn)題描述：給出n個(gè)學(xué)生的考試成績(jī)表，成績(jī)表包括學(xué)生的學(xué)號(hào)、姓名、考試成績(jī)（高等數(shù)學(xué)、英語(yǔ)、物理），設(shè)計(jì)一個(gè)簡(jiǎn)單的成績(jī)管理程序?；疽螅海?）建立成績(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é)生在

8、考試中獲得的名次，分?jǐn)?shù)相同的為同一名次，按名次輸出成績(jī)表。(6) 成績(jī)表保存在文件中, 可以從文件讀取數(shù)據(jù)。測(cè)試數(shù)據(jù)：學(xué)生可以根據(jù)自己班級(jí)的考試成績(jī)單，任意截取一部分做為測(cè)試數(shù)據(jù)提高要求：成績(jī)表用鏈?zhǔn)浇Y(jié)構(gòu)表示，實(shí)現(xiàn)上述全部要求?？己艘螅海?） 用順序結(jié)構(gòu)表示成績(jī)單，完成任務(wù)（1）（6），成績(jī)?yōu)榧案?；?） 用鏈表表示成績(jī)單，完成任務(wù)（1）（6），且軟件容錯(cuò)能力強(qiáng)，成績(jī)?yōu)橹械?. 文學(xué)研究助手（*）問(wèn)題描述：文學(xué)研究人員需要統(tǒng)計(jì)某篇英文小說(shuō)中某些形容詞的出現(xiàn)次數(shù)和位置。試寫(xiě)一個(gè)實(shí)現(xiàn)這一目標(biāo)的文字統(tǒng)計(jì)系統(tǒng)，稱為“文學(xué)研究助手”?；疽螅河⑽男≌f(shuō)存于一個(gè)文本文件中，待統(tǒng)計(jì)的詞匯集合要一次輸入完畢

9、，即統(tǒng)計(jì)工作必須在程序的一次運(yùn)行之后就全部完成。文本文件名和待統(tǒng)計(jì)的詞匯從鍵盤(pán)輸入，程序的輸出結(jié)果是每個(gè)詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號(hào)，格式自行設(shè)計(jì), 結(jié)果保存到文件中。提高要求：包含是否區(qū)別大、小寫(xiě)兩種匹配模式，且讓用戶選擇。測(cè)試數(shù)據(jù)：以你的C/C+/JAVA源程序模擬英文小說(shuō)，相應(yīng)語(yǔ)言的保留字集作為待統(tǒng)計(jì)的詞匯集?？己艘螅海?） 用線性結(jié)構(gòu)表示文本文件和待統(tǒng)計(jì)的單詞，動(dòng)態(tài)分配內(nèi)存，完成基本要求的功能，成績(jī)?yōu)橹械取＃?） 在完成基本要求的基礎(chǔ)上，完成提高要求，且用戶界面友好，能夠處理異常，成績(jī)?yōu)榱己谩?. 哈希表的設(shè)計(jì)與實(shí)現(xiàn)（*）問(wèn)題描述：針對(duì)某個(gè)單位電話號(hào)碼簿，設(shè)計(jì)一個(gè)哈希表，并完成

10、相應(yīng)的建表和查表程序?；疽螅涸O(shè)每個(gè)記錄有下列數(shù)據(jù)項(xiàng)：電話號(hào)碼、用戶名、住址。從鍵盤(pán)輸入各記錄，以用戶名為關(guān)鍵字建立哈希表，哈希函數(shù)用除留取余數(shù)法構(gòu)造，采用線性探測(cè)法解決沖突。可以插入、查找、刪除并顯示給定用戶名的記錄，并計(jì)算查找長(zhǎng)度, 哈希表保存到文件中，并能從文件中讀取數(shù)據(jù)。 測(cè)試數(shù)據(jù)：取某個(gè)單位電話號(hào)碼簿中的100個(gè)以上記錄。提高要求：(1) 將電話號(hào)碼薄以文件形式保存到盤(pán)上，能夠按用戶名和電話號(hào)碼兩種形式建立哈希表并實(shí)現(xiàn)插入、查找、刪除表中元素的功能。(2) 對(duì)于相同的哈希函數(shù)，采用兩種或兩種以上的處理沖突的方法，如線性探測(cè)法和拉鏈法，比較不同的處理沖突的方法平均查找長(zhǎng)度的

11、變化。測(cè)試時(shí)，采用同一組測(cè)試數(shù)據(jù)，分別用不同的方法處理沖突，記錄并輸出各自的平均查找長(zhǎng)度。(3) 設(shè)計(jì)圖形用戶界面考核要求：（1） 能夠從鍵盤(pán)和文件輸入原始數(shù)據(jù)，能夠把變化的哈希表重新寫(xiě)回到文件中，同時(shí)完成其它的基本要求，成績(jī)?yōu)橹械取＃?） 達(dá)到提高要求中的（1）或（2），或者同時(shí)達(dá)到（1）和（2），成績(jī)?yōu)榱己谩＃?） 用C+或MFC實(shí)現(xiàn)圖形用戶界面，成績(jī)?yōu)榱己?. 安排教學(xué)計(jì)劃（*）問(wèn)題描述：大學(xué)的每個(gè)專業(yè)都要制定教學(xué)計(jì)劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩個(gè)學(xué)期，每學(xué)期的時(shí)間長(zhǎng)度和學(xué)分上限值均相等。每個(gè)專業(yè)開(kāi)設(shè)的課程都是確定的，而且課程在開(kāi)設(shè)時(shí)間的安排上必須滿足先修關(guān)系。每門(mén)課程有

12、哪些先修課程是確定的，可以有任意多門(mén)，也可以沒(méi)有。每門(mén)課程恰好占一個(gè)學(xué)期。試在這樣的前提下設(shè)計(jì)一個(gè)教學(xué)計(jì)劃編制程序?；疽螅狠斎?yún)?shù)包括學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門(mén)課程的課程號(hào)、學(xué)分和直接先修課的課程號(hào)；允許兩種策略，一是使學(xué)生在各學(xué)期的學(xué)習(xí)負(fù)擔(dān)盡量均勻，二是使課程盡量集中在前幾個(gè)學(xué)期；若根據(jù)給定的條件問(wèn)題無(wú)解，則報(bào)告適當(dāng)?shù)男畔?，否則輸出教學(xué)計(jì)劃表（如每個(gè)學(xué)期所開(kāi)設(shè)的課程的課程號(hào)及學(xué)分），同時(shí)將教學(xué)計(jì)劃輸出到用戶指定的文件中。教學(xué)計(jì)劃的表格格式自行設(shè)定, 可以從鍵盤(pán)讀取數(shù)據(jù)也可以從文件讀取數(shù)據(jù), 結(jié)果保存到文件中。測(cè)試數(shù)據(jù)：學(xué)期總數(shù)為6，學(xué)分上限為10，該專業(yè)共開(kāi)設(shè)12門(mén)。以10級(jí)某專業(yè)

13、必修課與選修課為例，選擇12門(mén)課程及相應(yīng)學(xué)分，制定一個(gè)表明各門(mén)課程先后約束關(guān)系的有向圖。提高要求：產(chǎn)生多種不同的方案，并使方案之間的差異盡可能地大。考核要求：（1） 達(dá)到基本要求，成績(jī)?yōu)榱己?，如果不能把結(jié)果保存到文件中，成績(jī)?yōu)椴患案?。?） 在達(dá)到基本要求的基礎(chǔ)上，產(chǎn)生3種以上的解決方案，且用戶界面友好，成績(jī)?yōu)閮?yōu)秀。6. 計(jì)算表達(dá)式的值(*)問(wèn)題描述：對(duì)于給定的一個(gè)表達(dá)式，表達(dá)式中可以包括常數(shù)、算術(shù)運(yùn)行符（“+”、“-”、“*”、“/”）和括號(hào)，編寫(xiě)程序計(jì)算表達(dá)式的值?；疽螅簭逆I盤(pán)輸入一個(gè)正確的中綴表達(dá)式，將中綴表達(dá)式轉(zhuǎn)換為對(duì)應(yīng)的后綴表達(dá)式，計(jì)算后綴表達(dá)式的值。測(cè)試數(shù)據(jù)：任意選取一個(gè)符合題

14、目要求的表達(dá)式。提高要求：（1）對(duì)于表達(dá)式中的簡(jiǎn)單錯(cuò)誤，能夠給出提示；（2）不僅提示錯(cuò)誤，也能給出錯(cuò)誤信息（3）表達(dá)式中可以包括單個(gè)字母表示的變量（4）能夠處理多種操作符（5）實(shí)現(xiàn)包含簡(jiǎn)單運(yùn)算的計(jì)算器（6）實(shí)現(xiàn)一個(gè)包含簡(jiǎn)單運(yùn)算和函數(shù)運(yùn)算的計(jì)算器考核要求：（1） 表達(dá)式中的數(shù)據(jù)可以是整數(shù)或小數(shù)，達(dá)到基本要求，成績(jī)?yōu)榱己谩Ｈ绻麅H能處理個(gè)位數(shù)，成績(jī)?yōu)榧案瘢绻麅H能處理整數(shù)，成績(jī)?yōu)橹械?。?） 在達(dá)到基本要求的基礎(chǔ)之上，如果達(dá)到提高要求的2項(xiàng)或以上，成績(jī)可以為優(yōu)秀。鼓勵(lì)設(shè)計(jì)圖形用戶界面。7. 設(shè)計(jì)Huffman 編碼器與解碼器（*）問(wèn)題描述：利用哈夫曼編碼進(jìn)行信息通訊可以大大提高信道的利用率，縮短信息

15、傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳輸數(shù)據(jù)預(yù)先編碼；在接受端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼。對(duì)于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站編寫(xiě)一個(gè)哈夫曼碼的編/譯碼系統(tǒng)?；疽螅焊鶕?jù)某字符文件統(tǒng)計(jì)字符出現(xiàn)頻度，構(gòu)造Huffman 樹(shù)，編制Huffman編碼，并將給定字符文件編碼，生成編碼文件；再將給定編碼文件解碼，生成字符文件。（要求按二進(jìn)制位表示編碼）提高要求：改進(jìn)Huffman編碼，產(chǎn)生兩種以上的編碼方案，對(duì)同一組測(cè)試數(shù)據(jù)，用不同的編碼方案編碼，從文件長(zhǎng)度、算法復(fù)雜度等方面進(jìn)行比較。測(cè)試數(shù)據(jù)：英文文檔文件或中文文檔文件

16、。考核要求：（1） 對(duì)原文件編碼后，保存到新建文件中，將原文件與新文件比較，如果新文件長(zhǎng)度大于原文件，則編碼失敗，成績(jī)不及格。如果達(dá)到題目的基本要求，成績(jī)?yōu)榱己?。?） 達(dá)到提高要求，成績(jī)可以為優(yōu)秀。8. 銀行業(yè)務(wù)模擬（*）問(wèn)題描述：設(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ù)。寫(xiě)一個(gè)上述銀行業(yè)務(wù)的模擬系統(tǒng),通過(guò)模擬方法求出客戶在銀行內(nèi)逗留的平均時(shí)間和每個(gè)窗口辦理的客戶數(shù)及辦

17、理的每種業(yè)務(wù)數(shù)?；疽螅好總€(gè)客戶到達(dá)銀行的時(shí)間和需要辦理的業(yè)務(wù)隨機(jī)產(chǎn)生，輸出一天客戶在銀行的平均逗留時(shí)間和每個(gè)窗口每天辦理的客戶數(shù)和每種業(yè)務(wù)數(shù)。提高要求：設(shè)計(jì)圖形用戶界面，模擬中國(guó)銀行真實(shí)的打號(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)(*)問(wèn)題描述： 航空客運(yùn)訂票大的業(yè)務(wù)活動(dòng)包括：查詢航線，客票預(yù)訂，辦理退票等。試設(shè)計(jì)一個(gè)航空客運(yùn)訂票系統(tǒng)，以使上述業(yè)務(wù)可以借助計(jì)算機(jī)來(lái)

18、完成?；疽?每條航線涉及的信息：航班號(hào)，起飛城市，終到城市，中轉(zhuǎn)城市(可選項(xiàng))，起飛時(shí)間，到達(dá)時(shí)間，機(jī)型，飛行班期(星期幾)，乘員定額，余票量，已訂票的客戶名單(包括姓名，訂票量，艙位等級(jí)，等候替補(bǔ)的客戶名單(包括姓名，所需票量)，乘客信息（身份證號(hào)、姓名等），票價(jià)等。系統(tǒng)實(shí)現(xiàn)的功能：（） 查詢功能：航班查詢：根據(jù)出發(fā)地、目的地、出發(fā)時(shí)間查詢，依據(jù)航班號(hào)查詢等輸出信息包括：航班號(hào)，出發(fā)地，終到地，星期幾飛行，最近一天航班的日期和余票額；按航班號(hào)查詢時(shí)，要求采用二分查找法，航班號(hào)是字母、數(shù)字混編的，因此需要首先采用基數(shù)排序進(jìn)行排序。訂票人查詢：輸入訂票人身份證號(hào)碼或姓名查詢訂票人詳細(xì)信息并輸

19、出。 乘客查詢：輸入乘客的身份證號(hào)碼或姓名查詢乘客的詳細(xì)信息并輸出。 (）錄入功能航班信息錄入：錄入航班的相關(guān)信息。訂票：根據(jù)輸入的訂票人身份證號(hào)驗(yàn)證訂票人身份后，輸入詳細(xì)的乘客信息并進(jìn)行保存。取消訂票：保存訂票人取消訂票信息。(）修改功能修改乘客信息：將查找到的乘客信息，進(jìn)行修改，然后進(jìn)行保存。修改訂票人信息：將查找到的訂票人的信息進(jìn)行修改然后進(jìn)行保存。修改航班信息：將查找到的航班信息進(jìn)行修改后保存。(） 刪除功能刪除乘客信息：將查找到的乘客信息，進(jìn)行刪除。刪除訂票人信息：將查找到的訂票人的信息進(jìn)行刪除。刪除航班信息：將查找到的航班信息進(jìn)行刪除。()航班推薦功能：要求按最省錢(qián)和最省時(shí)間兩種方

20、式對(duì)顧客進(jìn)行推薦，要求如果有中轉(zhuǎn)站要給出詳細(xì)的出發(fā)到終點(diǎn)的路線，中轉(zhuǎn)時(shí)需包括候機(jī)的時(shí)間。提高要求：（） 設(shè)計(jì)圖形用戶界面（） 增加會(huì)員管理功能，包括保存常旅客、積分管理、優(yōu)惠信息通知等，也可自行設(shè)計(jì)其它功能。測(cè)試數(shù)據(jù)：至少選擇50組數(shù)據(jù)（測(cè)試數(shù)據(jù)保存在文件中），包括航班號(hào)、起飛地、目的地、起飛時(shí)間、到達(dá)時(shí)間、最大乘客數(shù)、票價(jià)、飛行時(shí)間、經(jīng)停等信息，其他信息自行設(shè)定?？己艘螅海ǎ?數(shù)據(jù)結(jié)構(gòu)選擇合理，達(dá)到題目的基本要求，成績(jī)?yōu)榱己?。（?達(dá)到提高要求，用戶界面友好，能夠處理異常，成績(jī)可以為優(yōu)秀10. 最小滿覆蓋問(wèn)題（*）問(wèn)題描述：在8×8的國(guó)際象棋棋盤(pán)上，如果在放置若干個(gè)馬以后，使得整

21、個(gè)棋盤(pán)的任意空位置上所放置的棋子均能被這些馬吃掉，則稱這組放置為棋盤(pán)的一個(gè)滿覆蓋。若去掉滿覆蓋中的任意一個(gè)棋子都會(huì)使這組放置不再是滿覆蓋，則稱這一滿覆蓋為極小滿覆蓋。設(shè)計(jì)程序完成如下要求。基本要求：求解一個(gè)極小滿覆蓋，按照矩陣形式給出，用特殊符號(hào)表示馬。提高要求：（1） 能畫(huà)出棋盤(pán)的圖形形式，或在其上動(dòng)態(tài)第演示試探過(guò)程；（2） 程序能方便地移植到其他規(guī)格的棋盤(pán)上。提示：國(guó)際象棋中馬吃其他棋子的方式為馬走3×2格的對(duì)角線，有點(diǎn)像中國(guó)象棋中的馬走日，沒(méi)有“蹩馬腿”的規(guī)定?？梢杂眠@個(gè)方法判定走棋是否正確：如果馬在白格，走一步后一定落在黑格。測(cè)試數(shù)據(jù)：8*8的矩陣?？己艘螅哼_(dá)到基本要求，成

22、績(jī)?yōu)榱己?；達(dá)到提高要求（）和（）成績(jī)?yōu)閮?yōu)秀。11. 迷宮游戲（*）問(wèn)題描述：程序開(kāi)始運(yùn)行時(shí)顯示一個(gè)迷宮地圖，迷宮中央有一只老鼠，迷宮的右下方有一個(gè)糧倉(cāng)。游戲的任務(wù)是使用鍵盤(pán)上的方向健操縱老鼠在規(guī)定的時(shí)間內(nèi)走到糧倉(cāng)處。基本要求：（1） 老鼠形象可以辨認(rèn)，可用鍵盤(pán)操縱老鼠上下左右移動(dòng)；（2） 迷宮的墻足夠結(jié)實(shí)，老鼠不能穿墻而過(guò)；（3） 正確檢測(cè)結(jié)果，若老鼠在規(guī)定時(shí)間內(nèi)走到糧倉(cāng)處，提示成功，并給出一條路徑，否則提示失敗。提高要求：（1） 添加編輯迷宮功能，可修改當(dāng)前迷宮，修改內(nèi)容：墻變路、路變墻；（2） 增加闖關(guān)和計(jì)分功能；（3） 找出走出迷宮的所有路徑，以及最短路徑。測(cè)試數(shù)據(jù)：要求用10*10及以

23、上的方陣或長(zhǎng)方陣?？己艘螅哼_(dá)到基本要求（）（），成績(jī)?yōu)榱己?；達(dá)到提高要求（）（）成績(jī)?yōu)閮?yōu)秀。12. 程序源代碼的相似性（*）問(wèn)題描述：對(duì)于兩個(gè)C+語(yǔ)言的源程序代碼，用哈希表的方法分別統(tǒng)計(jì)兩個(gè)程序中使用C+語(yǔ)言關(guān)鍵字的情況，并最終按定量的計(jì)算結(jié)果，得出兩份程序的相似性。     基本要求：建立C+語(yǔ)言關(guān)鍵字的哈希表，統(tǒng)計(jì)在每個(gè)源程序中C+關(guān)鍵字出現(xiàn)的頻度, 得到兩個(gè)向量X1和X2，通過(guò)計(jì)算向量X1和X2的相對(duì)距離來(lái)判斷兩個(gè)源程序的相似性。例如:     關(guān)鍵字 Void Int For Char if else while do break class程

24、序1關(guān)鍵字頻度 4 3 0 4 3 0 7 0 0 2程序2關(guān)鍵字頻度 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  設(shè)s是向量X1和X2的相對(duì)距離，s=sqrt( (xi1-xi2) 2 )，當(dāng)X1=X2時(shí)，s=0, 反映出可能是同一個(gè)程序；s值越大，則兩個(gè)程序的差別可能也越大，分析計(jì)算結(jié)果，給出相似度的結(jié)論。測(cè)試數(shù)據(jù): 選擇若干組編譯和運(yùn)行都無(wú)誤的C+程序，程序之間有相近的和差別大的，用上述方法求s, 對(duì)比兩個(gè)程序的相似性。     提高要求：建立源代碼用戶標(biāo)識(shí)符表，比較兩個(gè)

25、源代碼用戶標(biāo)識(shí)符出現(xiàn)的頻度，綜合關(guān)鍵字頻度和用戶標(biāo)識(shí)符頻度判斷兩個(gè)程序的相似性?？己艘螅簭脑创a中分解單詞，判斷是否為關(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. 小型文本編輯器（*）問(wèn)題描述：設(shè)計(jì)一個(gè)行編輯程序，使其具有通常行編輯器(如Vi、Edlin)應(yīng)具備的基本功能?；疽螅壕庉嬈鲬?yīng)具備對(duì)文本文件的查找、插人、刪除、修改、字符串替換、統(tǒng)計(jì)字?jǐn)?shù)，統(tǒng)計(jì)行數(shù)等功能，對(duì)于超過(guò)一屏的長(zhǎng)文件，應(yīng)能夠分頁(yè)顯示，

26、查找功能用字符串匹配算法實(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ù)：任一文本文件。提高要求：.可以支持“* ”、“? ”等通配符； .支持復(fù)制、粘貼等功能3. 支持多文檔同時(shí)編輯；考核要求：（1） 界面可以是菜單形式，完成基本要求，成績(jī)可為優(yōu)秀，如果只實(shí)現(xiàn)了基本要求的部分功能，成績(jī)向下浮動(dòng)。（2） 可以用MFC設(shè)計(jì)界面，但其中的功能實(shí)現(xiàn)不能用類(lèi)庫(kù)中的類(lèi)。提示：可以考慮用雙向鏈表實(shí)現(xiàn)，每一結(jié)點(diǎn)表示一行字符，注意每行字符不能超過(guò)255。14. 小型英漢詞典（*）問(wèn)題描述：設(shè)計(jì)一個(gè)英漢詞典，支持Member的查找、插入、刪除操作?；疽螅簩?shí)現(xiàn)字典的常用方法有：有序線性表（用二分檢索實(shí)現(xiàn)）、AVL樹(shù)（二叉搜索樹(shù)）、Patricia Tree、散列表等，任選一種方法實(shí)現(xiàn)字典的操作，查找單詞、插入單詞（插入時(shí)，先查找，