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

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

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

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

4、個(gè)程序，對(duì)任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒(méi)有通 路的結(jié)論。 基本要求:首先實(shí)現(xiàn)一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的棧類(lèi)型，然后編寫(xiě)一個(gè)求解迷宮的 非遞歸程序。求得的通路以三元組(i,j,d的形式輸出，其中:(i,j指示迷宮中的一個(gè)坐 標(biāo),d表示走到下一坐標(biāo)的方向。 如:對(duì)于下列數(shù)據(jù)的迷宮，輸出的一條通路 為:(1,1,1 , (1,2,2 , (2,2,2 (3,2,3 , (3,1,2 ,。 … 測(cè)試數(shù)據(jù)：迷宮的測(cè)試數(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è)定的迷宮沒(méi) 有通路?？梢杂枚S數(shù)組存儲(chǔ)迷宮數(shù)據(jù)，通常設(shè)定入口點(diǎn)的下標(biāo)為 (1,1，出口點(diǎn)的下標(biāo)為(n,n。為處理方便起見(jiàn)，可在迷宮的四周加一障礙。對(duì)于迷宮 任一位置，均可約定有東、南、西、北四個(gè)方向可通。 選作內(nèi)容： (1編寫(xiě)遞歸形式的算法，求得迷宮中所有可能的通路； (2以方陣形式輸出迷宮及其通路。 題目2、哈夫曼編碼器的實(shí)現(xiàn) 問(wèn)題描述:根據(jù)輸入的字符和對(duì)應(yīng)的權(quán)重，生成一棵哈夫曼樹(shù),再打印各字符對(duì) 應(yīng)的哈夫曼編碼

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

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

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

10、號(hào)，輸出每曲配對(duì)情況(包括男、女生的姓名、性別和編號(hào) 。原始數(shù)據(jù)和結(jié)果數(shù)據(jù)要保存到文件中。 測(cè)試數(shù)據(jù):分別選擇男生多于女生、女生多于男生、男女生相等的三組測(cè)試數(shù) 提高要求：計(jì)算出任意一位男生(編號(hào)為X和任意一位女生(編號(hào)為丫,在第K 曲配對(duì)跳舞的情況。 題目2、管道鋪設(shè)施工的最佳方案 問(wèn)題描述：需要在某個(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í) 也保存于文件中。測(cè)試用例:任意選擇一個(gè)圖，模擬小區(qū)間可能鋪設(shè)的管道及費(fèi) 用。提高要求:顯示原始圖及選擇n-1條管道后的圖。 題目3、商店存貨管理系統(tǒng) 功能:建立一商店存貨管理系統(tǒng)，要求每次出貨時(shí)取進(jìn)貨時(shí)間最早且最接近保質(zhì) 期中止時(shí)間的貨物。 分步實(shí)施： (1初步完成總體設(shè)計(jì)，搭好框架,確定人機(jī)對(duì)話(huà)的界面，確定函數(shù)個(gè)數(shù)； (2完成最低要求：建立一個(gè)文件,包括5個(gè)種類(lèi)的貨物情況，能對(duì)商品信息進(jìn)行擴(kuò) 充(追加，修改和刪除以及簡(jiǎn)單的排序； (3進(jìn)一步要求：擴(kuò)充商品數(shù)量，以及完成系統(tǒng)查詢(xún)功能。有興趣的同學(xué)可以自己 擴(kuò)充系統(tǒng)功能

12、。 要求： 1界面友好，函數(shù)功能要?jiǎng)澐趾? 2總體設(shè)計(jì)應(yīng)畫(huà)一流程圖 3程序要加必要的注釋 4要提供程序測(cè)試方案 題目4、通訊錄的制作 設(shè)計(jì)目的：編寫(xiě)一個(gè)通訊錄管理系統(tǒng)。 設(shè)計(jì)任務(wù):本系統(tǒng)應(yīng)完成幾方面的功能： 1輸入信息 en ter（; 2顯示信息 display（; 3查找以姓名作為關(guān)鍵字 search（; 4刪除信息 delete（; 5 存盤(pán) save （; 6 裝入 load（; 設(shè)計(jì)要求:1每條信息至包含：姓名（NAME街道（STREET城市（CITY郵編（EIP 國(guó)家（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、火車(chē)訂票系統(tǒng) 任務(wù)：通過(guò)此系統(tǒng)可以實(shí) 現(xiàn)如下功能：1錄入：可以錄入車(chē)次情況（數(shù)據(jù)可以存儲(chǔ)在一個(gè)數(shù)據(jù)文件中，數(shù) 據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）2查詢(xún)：可以查詢(xún)某個(gè)車(chē)次的情況（如，輸入車(chē)次號(hào)， 查詢(xún)起止時(shí)間，起止城市，票價(jià)，票 價(jià)折扣，確定是否滿(mǎn)座）；可以輸入起止城 市，查詢(xún)車(chē)次情況；3訂票：（訂票情況可以存在一個(gè)數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè) 定）可以訂票，如果該車(chē)次已經(jīng)無(wú)票，可以提供相關(guān)可選擇； 4退票：可退票， 退票后修改相關(guān)數(shù)據(jù)文件； 客戶(hù)資料有姓名，證件號(hào)，訂票數(shù)量及車(chē)次情況，訂 單要有編號(hào)。5修改信息：當(dāng)信息改變可以修改數(shù)據(jù)文件 要求：

14、根據(jù)以上功能說(shuō) 明，設(shè)計(jì)車(chē)次信息，訂票信息的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)程序完成功能。 題目2、數(shù)制轉(zhuǎn)換 問(wèn)題任意給定一個(gè)M進(jìn)制的數(shù)x，請(qǐng)實(shí)現(xiàn)如下要求1求出此數(shù)x的10進(jìn)制值 （用MD表示）2實(shí)現(xiàn)對(duì)x向任意的一個(gè)非M進(jìn)制的數(shù)的轉(zhuǎn)換。3至少用兩種或 兩種以上的方法實(shí)現(xiàn)上述要求 （用棧解決，用數(shù)組解決，其它方法解決）。題 目3、學(xué)生成績(jī)管理系統(tǒng) 現(xiàn)有學(xué)生成績(jī)信息文件1（ 1.txt），內(nèi)容自定義 學(xué)生成 績(jī)信息文件2 （2.txt）,內(nèi)容自定義 … 試編寫(xiě)一管理系統(tǒng)，要求如下：1實(shí)現(xiàn) 對(duì)兩個(gè)文件數(shù)據(jù)進(jìn)行合并，生成新文件3.txt 2抽取出三科成績(jī)中有補(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、商品銷(xiāo)售管理系統(tǒng) 針對(duì)某一種行業(yè)的庫(kù)房的產(chǎn)品 進(jìn)銷(xiāo)存情況進(jìn)行管理?；疽螅?采用一定的存儲(chǔ)結(jié)構(gòu)對(duì)庫(kù)房的貨品及其數(shù)量 進(jìn)行分類(lèi)管理；2可以進(jìn)行產(chǎn)品類(lèi)的添加、產(chǎn)品的添加、產(chǎn)品數(shù)量的添加； 能夠 查詢(xún)庫(kù)房每種產(chǎn)品的總量、進(jìn)貨日期、銷(xiāo)出數(shù)量、銷(xiāo)售時(shí)間等；