數(shù)據(jù)結(jié)構(gòu)課設(shè)題目及要求

1、2014春 佃2121-2班數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)【成績(jī)?cè)u(píng)定】課程設(shè)計(jì)的最終成績(jī)由平時(shí)表現(xiàn)、演示程序并回答問(wèn)題、課程設(shè)計(jì)報(bào)告三部 分綜合評(píng)定?！皵?shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)”是一門必修的實(shí)踐課程，和平時(shí)上課一樣， 要求大家一定要按時(shí)到機(jī)房上機(jī)，不遲到不早退。如果不來(lái)上機(jī)（累計(jì)三次點(diǎn)名 未到）、或者未經(jīng)老師驗(yàn)收程序并回答提問(wèn)、或者不交實(shí)習(xí)報(bào)告都將作為“不及 格”處理；此外，如果發(fā)現(xiàn)完全抄襲他人實(shí)習(xí)報(bào)告，則抄襲者與被抄襲者的成績(jī) 一律為“不及格”?！緯r(shí)間地點(diǎn)安排】上機(jī)時(shí)間：2014年2月27日、28日 下午3月1日、6日、7日、8日、13日下午3月14日晚上 3月15日下午下午 14:00-18:00 晚上 18:

2、00-22:00上機(jī)地點(diǎn)：綜合樓313（地點(diǎn)若有變化，指導(dǎo)老師會(huì)另行通知）驗(yàn)收程序時(shí)間：3月14日、15日提交課程設(shè)計(jì)報(bào)告時(shí)間：3月27日注意：報(bào)告紙質(zhì)雙面打印（后面附有報(bào)告內(nèi)容及格式要求），不打印源程序; 同時(shí)，每個(gè)同學(xué)提交報(bào)告和源程序的電子檔，以班級(jí)為單位刻錄光盤?！绢}目及分組情況】本次課程設(shè)計(jì)的題目共9題，分為三組，每組3題，每人任選一組題目完成。 在第一次課程設(shè)計(jì)時(shí)，每個(gè)人必須確定選擇哪一組。第一組：1、4、7第二組：2、5、8第三組：3、6、91. 電梯模擬模擬某校九層教學(xué)樓的電梯系統(tǒng)。該樓有一個(gè)自動(dòng)電梯，能在每層停留，其中第一層是大樓的進(jìn)出層，即是電梯的“本壘層”，電梯“空閑”時(shí)，

3、將來(lái)到該層候命。電梯一共有七個(gè)狀態(tài)，即正在開(kāi)門（Opening）、已開(kāi)門（Opened）、正在關(guān)門（Closing ）、 已關(guān)門(Closed)、等待(Waiting )、移動(dòng)(Moving )、減速(Decelerate)。乘客可隨機(jī)地進(jìn)出于任何層。 對(duì)每個(gè)人來(lái)說(shuō)， 他有一個(gè)能容忍的最長(zhǎng)等待時(shí)間， 一旦等 候電梯時(shí)間過(guò)長(zhǎng)，他將放棄。模擬時(shí)鐘從 0 開(kāi)始，時(shí)間單位為 0.1 秒。人和電梯的各種動(dòng)作均要消耗一定的時(shí)間單位(簡(jiǎn)記為t),比如：有人進(jìn)出時(shí)，電梯每隔40t測(cè)試一次，若無(wú)人進(jìn)出，則關(guān)門；關(guān)門和開(kāi)門各需要20t ;每個(gè)人進(jìn)出電梯均需要 25t;電梯加速需要 15t;上升時(shí)，每一層需要 51

4、t， 減速需要14t；下降時(shí)，每一層需要61t，減速需要23t；如果電梯在某層靜止時(shí)間超過(guò) 300t， 則駛回 1 層候命。要求：按時(shí)序顯示系統(tǒng)狀態(tài)的變化過(guò)程，即發(fā)生的全部人和電梯的動(dòng)作序列。224 點(diǎn)游戲24 點(diǎn)游戲是一種使用撲克牌來(lái)進(jìn)行的益智類游戲，游戲內(nèi)容是：從一副撲克牌中抽去 大小王剩下 52 張，任意抽取 4 張牌，把牌面上的數(shù)( A 代表 1 )運(yùn)用加、減、乘、除和括 號(hào)進(jìn)行運(yùn)算得出 24。每張牌都必須使用一次，但不能重復(fù)使用。要求：設(shè)計(jì)算法完成 24 點(diǎn)游戲的計(jì)算。 擴(kuò)展內(nèi)容：實(shí)現(xiàn) 24 點(diǎn)游戲的可視化界面。3洗車仿真 假設(shè)洗車站有三個(gè)洗車處，每個(gè)洗車處可構(gòu)成一個(gè)等待隊(duì)列。根據(jù)系

5、統(tǒng)時(shí)間隨機(jī)生成 每輛車的到達(dá)時(shí)間，相鄰兩輛車的到達(dá)時(shí)間間隔為2,15分鐘之間的隨機(jī)值，每輛車接受服務(wù)的時(shí)間選項(xiàng)為 10、 15或 25 分鐘其中之一(隨機(jī)產(chǎn)生) 。第一輛車的到達(dá)時(shí)間在洗車站開(kāi) 門 30 分鐘之內(nèi)(隨機(jī)產(chǎn)生) 。平均等待時(shí)間是將每輛車的等待時(shí)間加起來(lái)再除以車的數(shù)量。 下面是關(guān)于車輛到達(dá)和離開(kāi)的具體條件：( 1 )如果當(dāng)隊(duì)列為空且沒(méi)有車被清洗時(shí)， 到達(dá)了一輛車， 那么就馬上開(kāi)始清洗這輛車； 它無(wú)需進(jìn)入隊(duì)列。 每當(dāng)一輛車通過(guò)清洗后， 它就馬上離開(kāi)洗車處， 隨之相應(yīng)隊(duì)頭的車輛出隊(duì) 進(jìn)入清洗過(guò)程。( 2)每當(dāng)一輛車到達(dá)時(shí)，它直接進(jìn)入三個(gè)隊(duì)列中等待時(shí)間最短的隊(duì)列。( 3)每個(gè)隊(duì)列中每次至

6、多有 5 輛車在等待洗車。當(dāng)正在清洗并且三個(gè)隊(duì)列中均有 5 輛 車時(shí)，如果此時(shí)有一輛車到達(dá)，那么它將作為“溢出”不準(zhǔn)入內(nèi)且不計(jì)算在內(nèi)。( 4)每輛車的等待時(shí)間不含其接受服務(wù)的時(shí)間。 要求：寫一個(gè)上述洗車業(yè)務(wù)的事件驅(qū)動(dòng)模擬系統(tǒng)，并實(shí)現(xiàn)以下功能：( 1)產(chǎn)生 6 個(gè)小時(shí)內(nèi)車輛的隨機(jī)到達(dá)時(shí)刻和接受服務(wù)時(shí)間。( 2)輸出所有車輛(包括未能進(jìn)隊(duì)洗車的車輛)的洗車情況(到達(dá)時(shí)間、所處等待隊(duì) 列及等待時(shí)間、接受服務(wù)時(shí)間、離開(kāi)時(shí)間等) 。( 3)計(jì)算所有車輛的平均等待時(shí)間。4文件目錄管理與顯示 給出目錄和文件信息，編程實(shí)現(xiàn)將其排列成一棵有一定縮進(jìn)的樹(shù)。要求：( 1 )設(shè)計(jì)文件和目錄信息樹(shù)的存儲(chǔ)結(jié)構(gòu)。( 2)從

7、文件或鍵盤輸入目錄和文件信息，輸入格式采用絕對(duì)路徑法，即： AAAA1AAA1aa1.doc創(chuàng)建時(shí)要檢查同一路徑下不能有同名的目錄或文件名。（3）設(shè)計(jì)文件和目錄信息樹(shù)的輸出格式（以凹入表的形式顯示）。（4）查找指定目錄和文件。（5）添加新目錄或新文件。（6）刪除指定目錄或文件，子目錄能夠被刪除的前提是其為空，既不包含任何子目錄 和文件；根目錄不能刪除。（7）擴(kuò)充目錄或文件信息，如創(chuàng)建時(shí)間、讀寫權(quán)限、文件長(zhǎng)度或子目錄包含的子目錄 和文件數(shù)等。（8）對(duì)同一層次下的子目錄或文件按創(chuàng)建時(shí)間有序輸出。（9） 通配符的使用。如用“？”代表任意一個(gè)字符，用“*”表示任意多個(gè)多個(gè)任意字符。擴(kuò)展內(nèi)容：實(shí)現(xiàn)相對(duì)路

8、徑表示法。5. 基于Huffman編碼的壓縮軟件準(zhǔn)備一個(gè)源文件（可以是你的源程序），統(tǒng)計(jì)該文件中各種字符出現(xiàn)的頻率，對(duì)各字符進(jìn)行Huffman編碼，將該源文件壓縮成編碼文件，再將Huffman編碼文件譯碼成源文件。要求：（1）設(shè)計(jì)合適的哈夫曼樹(shù)存儲(chǔ)結(jié)構(gòu)，并設(shè)計(jì)編碼和譯碼方法；（2） 將輸入的源文件（比如l.cpp）壓縮到文件2.txt中，輸出源文件字符數(shù)（一個(gè)字 符是8位二進(jìn)制數(shù)）和壓縮后字符數(shù)，并計(jì)算壓縮比；（3）將壓縮文件2.txt再還原到文件3.txt，比較3.txt與源文件是否一致。擴(kuò)展內(nèi)容：采用范式哈夫曼編碼（ Canonical Huffman Code ）實(shí)現(xiàn)文件壓縮。6. 取火

9、柴游戲在盤中放著n根火柴，A和B兩人輪流從盤中取火柴，規(guī)定每次可取一根、二根或三 根，不可不取也不可多取，誰(shuí)拿走最后一根便算誰(shuí)輸。這就是所謂的取火柴游戲。其實(shí)，這 種游戲如同下棋，雙方都有可能取勝。為了自己取勝，就必須每走一步（即取一次火柴）都 要?jiǎng)觿?dòng)腦筋，為自己的最后勝利創(chuàng)造條件，也就是說(shuō)，每走一步都要有個(gè)較好的對(duì)策。我們可以利用樹(shù)結(jié)構(gòu)，把取火柴游戲的過(guò)程描述出來(lái)。為方便起見(jiàn)，假定n=6。開(kāi)始時(shí)有六根火柴，A先走的話，他可有拿 1根、2根或3根火柴三種不同的走法。如果把原始狀 態(tài)一一6根火柴，作為根結(jié)點(diǎn)，A的三種不同走法將產(chǎn)生盤中剩5根、4根、3根火柴三種狀態(tài)，可用根結(jié)點(diǎn)的三個(gè)子結(jié)點(diǎn)表示（圖

10、 1 ）。A走以后，不論 A走哪一步，B接著走時(shí)， 他也可在A取剩的火柴中拿走 1根、2根或3根，因此共有3X3= 9種可能性，再可產(chǎn)生 9 個(gè)子結(jié)點(diǎn)，接下來(lái) A再走，。由于火柴的根數(shù)是有限的，而且每走一步都要減少些火 柴，因此火柴總會(huì)取完， 游戲隨之結(jié)束。整個(gè)過(guò)程可用一棵樹(shù)來(lái)表示。這課樹(shù)反映了 A和B雙方所有可能的對(duì)策，因此可以稱為對(duì)策樹(shù)。圖1要求：設(shè)計(jì)程序?qū)崿F(xiàn)兩個(gè)人或人與計(jì)算機(jī)的取火柴游戲。7 農(nóng)夫過(guò)河問(wèn)題一個(gè)農(nóng)夫帶著一只狼、一只羊和一棵白菜，身處河的南岸。他要把這些東西全部運(yùn)到北 岸。他面前只有一條小船，船只能容下他和一件物品，另外只有農(nóng)夫才能撐船。如果農(nóng)夫在 場(chǎng)，則狼不能吃羊，羊不能吃

11、白菜，否則狼會(huì)吃羊，羊會(huì)吃白菜，所以農(nóng)夫不能留下羊和白 菜自己離開(kāi)，也不能留下狼和羊自己離開(kāi)，而狼不吃白菜。要求：利用圖的存儲(chǔ)結(jié)構(gòu)和圖的搜索算法，求出農(nóng)夫?qū)⑺械臇|西運(yùn)過(guò)河的方案。8. 全國(guó)交通咨詢模擬出于不同目的的旅客對(duì)交通工具有不同的要求。例如，因公出差的旅客希望在旅途中 的時(shí)間盡可能短，出門旅游的游客則期望旅費(fèi)盡可能省，而老年旅客則要求中轉(zhuǎn)次數(shù)最少。 編制一個(gè)全國(guó)城市間的交通咨詢程序，為旅客提供兩種或三種最優(yōu)決策的交通咨詢。要求：（1）提供對(duì)城市信息進(jìn)行編輯（如添加或刪除）的功能。（2）城市之間有兩種交通工具：火車和飛機(jī)。提供對(duì)列車時(shí)刻表和飛機(jī)航班進(jìn)行編輯 （增設(shè)或刪除）的功能。（3）提

12、供兩種最優(yōu)決策：最快到達(dá)或最省錢到達(dá)。全程只考慮一種交通工具。（4）旅途中耗費(fèi)的總時(shí)間應(yīng)該包括中轉(zhuǎn)站的等候時(shí)間。（5）咨詢以用戶和計(jì)算機(jī)的對(duì)話方式進(jìn)行。9. 研究生入學(xué)考試成績(jī)處理假設(shè)某大學(xué)計(jì)算機(jī)應(yīng)用技術(shù)專業(yè)招收研究生n名，現(xiàn)在要根據(jù)報(bào)考者的考試成績(jī)擇優(yōu)錄取。考試課程有政治、英語(yǔ)、數(shù)學(xué)、專業(yè)綜合四門?？荚嚦煽?jī)分為兩類：第一類為每門課 程都達(dá)到最低錄取線；第二類為有一門或多門課程未達(dá)到最低錄取線。錄取方法是在每門課程達(dá)到最低錄取線的考生中按總分從高到低錄取。試設(shè)計(jì)一個(gè)成績(jī)處理程序?qū)崿F(xiàn)以上功能。要求：根據(jù)錄取方法，打印輸出n份錄取通知書，列出錄取者四門課程的成績(jī)及總分（要求采用堆排序）。并能實(shí)現(xiàn)對(duì)

13、任一考生或任一門課程成績(jī)的查找（要求兩種查找方式，根據(jù)考號(hào) 或姓名進(jìn)行查找，采用高效的查找算法）。錄取通知書的格式如下：ADMISSION NOTICEXX XX XX （姓名）：You have bee n admittedYour scores:PoliticsXX（成績(jī)）En glishXXMathematicsXXMajorXXTotalXXXXXUNIVERSITY數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告格式封面包括：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告，班級(jí)，學(xué)號(hào)，學(xué)生姓名，指導(dǎo)老師，日期(寫 年3月)報(bào)告內(nèi)容：針對(duì)自己做的每個(gè)題目分別按下面內(nèi)容寫：題號(hào)題目：1 需求分析2設(shè)計(jì)2.1設(shè)計(jì)思想(1) 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)包括邏

14、輯結(jié)構(gòu)設(shè)計(jì)和存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)(2) 算法設(shè)計(jì)2.2設(shè)計(jì)表示(1) 函數(shù)調(diào)用關(guān)系圖(2) 函數(shù)接口規(guī)格說(shuō)明2.3詳細(xì)設(shè)計(jì)3 .調(diào)試分析4用戶手冊(cè)5 測(cè)試數(shù)據(jù)及測(cè)試結(jié)果6 源程序清單說(shuō)明：1、正文文字請(qǐng)使用 5號(hào)宋體單倍行距，其它標(biāo)題類按上述字體大小。2、需求分析的內(nèi)容：描述問(wèn)題，簡(jiǎn)述題目要解決的問(wèn)題是什么。規(guī)定程序的功能，輸入和輸出的形式。條件不足時(shí)補(bǔ)全。3、設(shè)計(jì)部分的內(nèi)容：(1)設(shè)計(jì)思想數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)主要介紹在實(shí)驗(yàn)中采用(或設(shè)計(jì))的數(shù)據(jù)結(jié)構(gòu)，以及原因。算法設(shè)計(jì)主要包括總體設(shè)計(jì)思路和主要算法的基本思想?？傮w設(shè)計(jì)包括劃分為幾個(gè)模 塊，每個(gè)模塊要完成的主要功能等等，還可畫出主程序的流程圖。(2 )設(shè)計(jì)表示

15、畫出函數(shù)的調(diào)用關(guān)系圖，定義每個(gè)模塊對(duì)應(yīng)的函數(shù)接口。(3 )詳細(xì)設(shè)計(jì)主要算法的實(shí)現(xiàn)用偽碼和圖示描述。關(guān)鍵的地方添加注釋。注意：此部分不是源代碼的直接拷貝；要寫出主要操作的偽碼算法。4、調(diào)試分析：(1)調(diào)試過(guò)程中遇到的問(wèn)題是如何解決的以及對(duì)設(shè)計(jì)和編碼的回顧討論與分析；(2 )算法的時(shí)間空間復(fù)雜度分析；(3) 不局限于題目要求使用的算法，探討更多解決問(wèn)題的途徑，或者提出自己的見(jiàn)解， 給出改進(jìn)算法以得到更好結(jié)果的建議。5、用戶手冊(cè)：2014原題用戶使用該系統(tǒng)或程序的詳細(xì)說(shuō)明/步驟。6、測(cè)試數(shù)據(jù)及測(cè)試結(jié)果：設(shè)計(jì)一張測(cè)試用例表，每個(gè)測(cè)試用例包括以下內(nèi)容： 測(cè)試輸入：設(shè)計(jì)一組輸入數(shù)據(jù)； 測(cè)試目的：設(shè)計(jì)該輸入的目的在于測(cè)試程序在哪方面可能存在漏洞； 正確輸出：對(duì)應(yīng)該輸入，若程序正確，應(yīng)該輸出的內(nèi)容； 實(shí)際輸出：該數(shù)據(jù)輸入后，實(shí)際測(cè)試得到的輸出內(nèi)容； 錯(cuò)誤原因：如果實(shí)際輸出與正確輸出不符，分