《2012級(jí)計(jì)科專業(yè)《算法與數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)題》由會(huì)員分享，可在線閱讀，更多相關(guān)《2012級(jí)計(jì)科專業(yè)《算法與數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)題（11頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、2012級(jí)計(jì)科專業(yè)《算法與數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)題 指導(dǎo)教師:宗瑜 指導(dǎo)題目： 題目1、最小生成樹問題 問題描述:給定一個(gè)地區(qū)的n個(gè)城市間的距離網(wǎng)，用Prim算法或Kruskal算法建 立最小生成樹,并計(jì)算得到的最小生成樹的代價(jià)。 基本要求： (1城市間的距離網(wǎng)采用鄰接矩陣表示，鄰接矩陣的存儲(chǔ)結(jié)構(gòu)定義采用課本中給 出的定義,若兩個(gè)城市之間不存在道路，則將相應(yīng)邊的權(quán)值設(shè)為自己定義的無窮大 值。 (2表示城市間距離網(wǎng)的鄰接矩陣(要求至少6個(gè)城市，10條邊 (3要求在屏幕上顯示得到的最小生成樹中包括哪些城市間的道路及其權(quán)值 ，并 顯示得到的最小生成樹的代價(jià)。 題目2、哈希表的設(shè)計(jì)與實(shí)

2、現(xiàn) 問題描述:設(shè)計(jì)哈希表實(shí)現(xiàn)電話號(hào)碼查詢系統(tǒng)。 基本要求： (1設(shè)每個(gè)記錄有下列數(shù)據(jù)項(xiàng)：電話號(hào)碼、用戶名； (2從鍵盤輸入各記錄，分別以電話號(hào)碼和用戶名為關(guān)鍵字建立哈希表； (3采用線性探測再散列處理沖突； (4查找并顯示給定電話號(hào)碼的記錄 (5查找并顯示給定用戶名的記錄。 選做內(nèi)容:在哈希函數(shù)確定的前提下，嘗試各種不同類型處理沖突的方法(至少 兩種，考察平均查找長度的變化。 題目3、排序算法包的實(shí)現(xiàn) 問題描述:用程序?qū)崿F(xiàn)快速排序、堆排序和歸并排序?qū)⒁唤M隨機(jī)數(shù)列按非遞減 的順序排列。 基本要求： (1待排序列為由隨機(jī)函數(shù)生成的一組整數(shù)數(shù)列。 (2程序以用戶和計(jì)算機(jī)的對

3、話方式執(zhí)行，即在屏幕上顯示所能進(jìn)行的操作，用戶 根據(jù)提示輸入相應(yīng)命令，計(jì)算機(jī)處理完畢將運(yùn)算結(jié)果在屏幕上顯示，并等待用戶的后 續(xù)操作。選做內(nèi)容:實(shí)現(xiàn)希爾排序和基數(shù)排序。 要求:圖形界面設(shè)計(jì) 題目4、任意長的整數(shù)加減器 問題描述:設(shè)計(jì)一個(gè)程序?qū)崿F(xiàn)兩個(gè)任意長的整數(shù)的求和運(yùn)算。 基本要求:利用雙向循環(huán)鏈表，設(shè)計(jì)一個(gè)實(shí)現(xiàn)任意長的整數(shù)進(jìn)行加法運(yùn)算的演示 程序。要求輸入和輸出每四位一組,組間用逗號(hào)隔開。女口 :1, 0000, 0000, 0000, 0000。 指導(dǎo)教師:金萍 指導(dǎo)題目： 題目1、迷宮求解 問題描述：以一個(gè)m >n的長方形表示迷宮，0和1分別表示迷宮中的通路和障 礙。設(shè)計(jì)一

4、個(gè)程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通 路的結(jié)論。 基本要求:首先實(shí)現(xiàn)一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的棧類型，然后編寫一個(gè)求解迷宮的 非遞歸程序。求得的通路以三元組(i,j,d的形式輸出，其中:(i,j指示迷宮中的一個(gè)坐 標(biāo),d表示走到下一坐標(biāo)的方向。 如:對于下列數(shù)據(jù)的迷宮，輸出的一條通路 為:(1,1,1 , (1,2,2 , (2,2,2 (3,2,3 , (3,1,2 ,。 … 測試數(shù)據(jù)：迷宮的測試數(shù)據(jù)如下：左上角(1,1為入口，右下角(9,8為出口。 1 2 3 4 5 6 7 8 實(shí)現(xiàn)提示:計(jì)算機(jī)解迷宮通常用的是 窮舉求解”方法,即從入口出發(fā)，

5、順著某一個(gè) 方向進(jìn)行探索,若能走通,則繼續(xù)往前進(jìn)；否則沿著原路退回，換一個(gè)方向繼續(xù)探索，直 至出口位置,求得一條通路。假如所有可能的通路都探索到而未能到達(dá)出口 ，則所 設(shè)定的迷宮沒 有通路?？梢杂枚S數(shù)組存儲(chǔ)迷宮數(shù)據(jù)，通常設(shè)定入口點(diǎn)的下標(biāo)為 (1,1，出口點(diǎn)的下標(biāo)為(n,n。為處理方便起見，可在迷宮的四周加一障礙。對于迷宮 任一位置，均可約定有東、南、西、北四個(gè)方向可通。 選作內(nèi)容： (1編寫遞歸形式的算法，求得迷宮中所有可能的通路； (2以方陣形式輸出迷宮及其通路。 題目2、哈夫曼編碼器的實(shí)現(xiàn) 問題描述:根據(jù)輸入的字符和對應(yīng)的權(quán)重，生成一棵哈夫曼樹,再打印各字符對 應(yīng)的哈夫曼編碼

6、。并要求利用建好的哈夫曼樹對字符串進(jìn)行編碼 ，對哈夫曼編碼進(jìn) 行譯碼。 實(shí)現(xiàn)提示:元素類型選用字符型，對應(yīng)的權(quán)重值選用整型，請從鍵盤輸入。并從 鍵盤 輸入要編碼和譯碼的字符串或代碼串。 題目3、校園導(dǎo)游程序 問題描述： 設(shè)計(jì)一個(gè)校園導(dǎo)游程序，為來訪的客人提供各種信息查詢服務(wù)。 基本要求： (1設(shè)計(jì)你的學(xué)校的校園平面圖，所含景點(diǎn)不少于10個(gè)。以圖中頂點(diǎn)表示校內(nèi)各 景點(diǎn),存放景點(diǎn)名稱、代號(hào)、簡介等信息；以邊表示路徑，存放路徑長度等相關(guān)信 息。 0010 0010 1101 0010 0000 0101100101010000 (2為來訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。

7、 (3為來訪客人提供圖中任意景點(diǎn)的問路查詢，即查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的上條 最短的簡單路徑。 數(shù)據(jù)測試: 由讀者根據(jù)實(shí)際情況指定。 實(shí)現(xiàn)提示： 一般情況下，校園的道路是雙向通行的，可設(shè)校園平面圖是一個(gè)無向網(wǎng)，頂點(diǎn)和 邊均含有相關(guān)信息。 選作內(nèi)容： (1求校園圖的關(guān)節(jié)點(diǎn)。 (2提供圖中任意景點(diǎn)問路查詢，即求任意兩個(gè)景點(diǎn)之間的所有路徑。 (3提供校園圖中多個(gè)景點(diǎn)的最佳訪問路線查詢，即求途經(jīng)這多個(gè)景點(diǎn)的最佳(短 路徑。 (4校園導(dǎo)游圖的景點(diǎn)和道路的修改擴(kuò)充功能。 題目4、病房管理 問題描述:一所醫(yī)院中可能包括若干個(gè)病房，每個(gè)病房中又有若干個(gè)床位，建立 一個(gè)簡單的醫(yī)院病房管理程序

8、能夠?qū)Σ∪诉M(jìn)行出入院和床位分配進(jìn)行管理。 基本要求： 此系統(tǒng)應(yīng)具有如下功能： (1 I :初始化(Initialization。建立病房和床位信息。此醫(yī)院中可能包括若干個(gè) 病房，而每個(gè)病房中又有若干個(gè)床位。 (2 E :住院(en terhospital。在列出的有空位的病房中，選擇其一,入住。 (3 O :出院(Outhospital。選擇某一病房中某個(gè)病人，令其出院。 (4 Q :查詢(Query。查詢每個(gè)病房中空床位數(shù),入住病人數(shù);查詢整個(gè)醫(yī) 院的空 床位數(shù)和入住病人數(shù)。 測試數(shù)據(jù)： 建立一個(gè)包含3個(gè)病房的醫(yī)院，其中1病房有2張床位,2病房有6張床位,3病 房有8張床位;

9、張三和李四住1病房，王五也要住1病房，此時(shí)，床位已滿,于是將其調(diào) 入2病房。 實(shí)現(xiàn)提示： (1可建立若干個(gè)不定長鏈表，每個(gè)鏈表代表一個(gè)病房，病房數(shù)可用n表示,床位數(shù) 用m表示。 (2判斷病房是否住滿，直接對m進(jìn)行操作即可。 指導(dǎo)教師:嚴(yán)仍榮 指導(dǎo)題目： 題目1、舞伴問題 問題描述:一班有m個(gè)女生、n個(gè)男生(m不等于n,舉辦一場舞會(huì).男女生分 別編號(hào)坐在舞池兩邊的椅子上，每曲開始時(shí)，依次從男生和女生中各出一人配對跳 舞，本曲沒成功配 對者坐著等待下一曲找舞伴，設(shè)計(jì)一個(gè)程序模擬舞伴配對過程。 基本要求:輸入男、女學(xué)生的姓名、性別，由程序自動(dòng)為男女生編號(hào)，可以順序編 號(hào),也可以隨機(jī)編

10、號(hào)，輸出每曲配對情況(包括男、女生的姓名、性別和編號(hào) 。原始數(shù)據(jù)和結(jié)果數(shù)據(jù)要保存到文件中。 測試數(shù)據(jù):分別選擇男生多于女生、女生多于男生、男女生相等的三組測試數(shù) 提高要求：計(jì)算出任意一位男生(編號(hào)為X和任意一位女生(編號(hào)為丫,在第K 曲配對跳舞的情況。 題目2、管道鋪設(shè)施工的最佳方案 問題描述：需要在某個(gè)城市的n個(gè)小區(qū)鋪設(shè)管道，則在這n個(gè)小區(qū)之間鋪設(shè)n-1 條管道 即可,假設(shè)任意兩個(gè)居民區(qū)之間都可以架設(shè)管道，但由于地理環(huán)境的不同，所需 經(jīng)費(fèi)不同，選擇最優(yōu)的施工方案使總投資盡可能的少。 基本要求： 輸入表示小區(qū)間關(guān)系的圖及每條管道的權(quán)值，選擇出n-1條管道,使總投資最 小。圖的 信

11、息輸入一次后，保存到文件中，選擇的n-1條管道輸出到顯示器的同時(shí) 也保存于文件中。測試用例:任意選擇一個(gè)圖，模擬小區(qū)間可能鋪設(shè)的管道及費(fèi) 用。提高要求:顯示原始圖及選擇n-1條管道后的圖。 題目3、商店存貨管理系統(tǒng) 功能:建立一商店存貨管理系統(tǒng)，要求每次出貨時(shí)取進(jìn)貨時(shí)間最早且最接近保質(zhì) 期中止時(shí)間的貨物。 分步實(shí)施： (1初步完成總體設(shè)計(jì)，搭好框架,確定人機(jī)對話的界面，確定函數(shù)個(gè)數(shù)； (2完成最低要求：建立一個(gè)文件,包括5個(gè)種類的貨物情況，能對商品信息進(jìn)行擴(kuò) 充(追加，修改和刪除以及簡單的排序； (3進(jìn)一步要求：擴(kuò)充商品數(shù)量，以及完成系統(tǒng)查詢功能。有興趣的同學(xué)可以自己 擴(kuò)充系統(tǒng)功能

12、。 要求： 1界面友好，函數(shù)功能要?jiǎng)澐趾? 2總體設(shè)計(jì)應(yīng)畫一流程圖 3程序要加必要的注釋 4要提供程序測試方案 題目4、通訊錄的制作 設(shè)計(jì)目的：編寫一個(gè)通訊錄管理系統(tǒng)。 設(shè)計(jì)任務(wù):本系統(tǒng)應(yīng)完成幾方面的功能： 1輸入信息 en ter（; 2顯示信息 display（; 3查找以姓名作為關(guān)鍵字 search（; 4刪除信息 delete（; 5 存盤 save （; 6 裝入 load（; 設(shè)計(jì)要求:1每條信息至包含：姓名（NAME街道（STREET城市（CITY郵編（EIP 國家（STATE幾項(xiàng)；2作為一個(gè)完整的系統(tǒng)，應(yīng)具有友好的界面和較強(qiáng)的容錯(cuò)能 力；3 需要鏈表

13、實(shí)現(xiàn)；4上機(jī)能正常運(yùn)行。 指導(dǎo)教師：楊洋 指導(dǎo)題目：題目1、火車訂票系統(tǒng) 任務(wù)：通過此系統(tǒng)可以實(shí) 現(xiàn)如下功能：1錄入：可以錄入車次情況（數(shù)據(jù)可以存儲(chǔ)在一個(gè)數(shù)據(jù)文件中，數(shù) 據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）2查詢：可以查詢某個(gè)車次的情況（如，輸入車次號(hào)， 查詢起止時(shí)間，起止城市，票價(jià)，票 價(jià)折扣，確定是否滿座）；可以輸入起止城 市，查詢車次情況；3訂票：（訂票情況可以存在一個(gè)數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè) 定）可以訂票，如果該車次已經(jīng)無票，可以提供相關(guān)可選擇； 4退票：可退票， 退票后修改相關(guān)數(shù)據(jù)文件； 客戶資料有姓名，證件號(hào)，訂票數(shù)量及車次情況，訂 單要有編號(hào)。5修改信息：當(dāng)信息改變可以修改數(shù)據(jù)文件 要求：

14、根據(jù)以上功能說 明，設(shè)計(jì)車次信息，訂票信息的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)程序完成功能。 題目2、數(shù)制轉(zhuǎn)換 問題任意給定一個(gè)M進(jìn)制的數(shù)x，請實(shí)現(xiàn)如下要求1求出此數(shù)x的10進(jìn)制值 （用MD表示）2實(shí)現(xiàn)對x向任意的一個(gè)非M進(jìn)制的數(shù)的轉(zhuǎn)換。3至少用兩種或 兩種以上的方法實(shí)現(xiàn)上述要求 （用棧解決，用數(shù)組解決，其它方法解決）。題 目3、學(xué)生成績管理系統(tǒng) 現(xiàn)有學(xué)生成績信息文件1（ 1.txt），內(nèi)容自定義 學(xué)生成 績信息文件2 （2.txt）,內(nèi)容自定義 … 試編寫一管理系統(tǒng)，要求如下：1實(shí)現(xiàn) 對兩個(gè)文件數(shù)據(jù)進(jìn)行合并，生成新文件3.txt 2抽取出三科成績中有補(bǔ)考的學(xué)生并保 存在一個(gè)新文件4.txt 3合并后的文件3.txt中的數(shù)據(jù)按總分降序排序（至少采用兩種 排序方法實(shí)現(xiàn)4輸入一個(gè)學(xué)生姓名后，能查找到此學(xué)生的信息并輸出結(jié)果（至少采用 兩種查找方法實(shí) 現(xiàn)5要求使用結(jié)構(gòu)體，鏈或數(shù)組等實(shí)現(xiàn)上述要求? 6采用多種方法且 算法正確者，可適當(dāng)加分.題目4、商品銷售管理系統(tǒng) 針對某一種行業(yè)的庫房的產(chǎn)品 進(jìn)銷存情況進(jìn)行管理。基本要求：1采用一定的存儲(chǔ)結(jié)構(gòu)對庫房的貨品及其數(shù)量 進(jìn)行分類管理；2可以進(jìn)行產(chǎn)品類的添加、產(chǎn)品的添加、產(chǎn)品數(shù)量的添加； 能夠 查詢庫房每種產(chǎn)品的總量、進(jìn)貨日期、銷出數(shù)量、銷售時(shí)間等；