2012級計科專業(yè)《算法與數(shù)據(jù)結構》課程設計題

2012級計科專業(yè)算法與數(shù)據(jù)結構課程設計題指導教師:宗瑜指導題目：題目1、最小生成樹問題問題描述:給定一個地區(qū)的n個城市間的距離網(wǎng)，用Prim算法或Kruskal算法建 立最小生成樹,并計算得到的最小生成樹的代價。基本要求：(1城市間的距離網(wǎng)采用鄰接矩陣表示，鄰接矩陣的存儲結構定義采用課本中給 出的定義,若兩個城市之間不存在道路，則將相應邊的權值設為自己定義的無窮大 值。(2表示城市間距離網(wǎng)的鄰接矩陣(要求至少6個城市，10條邊(3要求在屏幕上顯示得到的最小生成樹中包括哪些城市間的道路及其權值，并顯示得到的最小生成樹的代價。題目2、哈希表的設計與實現(xiàn)問題描述:設計哈希表實現(xiàn)電話號碼查詢系統(tǒng)?；疽螅?1設每個記錄有下列數(shù)據(jù)項：電話號碼、用戶名；(2從鍵盤輸入各記錄，分別以電話號碼和用戶名為關鍵字建立哈希表；(3采用線性探測再散列處理沖突；(4查找并顯示給定電話號碼的記錄(5查找并顯示給定用戶名的記錄。選做內(nèi)容:在哈希函數(shù)確定的前提下，嘗試各種不同類型處理沖突的方法(至少 兩種，考察平均查找長度的變化。題目3、排序算法包的實現(xiàn)問題描述:用程序?qū)崿F(xiàn)快速排序、堆排序和歸并排序?qū)⒁唤M隨機數(shù)列按非遞減 的順序排列?；疽螅?1待排序列為由隨機函數(shù)生成的一組整數(shù)數(shù)列。(2程序以用戶和計算機的對話方式執(zhí)行，即在屏幕上顯示所能進行的操作，用戶 根據(jù)提示輸入相應命令，計算機處理完畢將運算結果在屏幕上顯示，并等待用戶的后 續(xù)操作。選做內(nèi)容:實現(xiàn)希爾排序和基數(shù)排序。要求:圖形界面設計題目4、任意長的整數(shù)加減器問題描述:設計一個程序?qū)崿F(xiàn)兩個任意長的整數(shù)的求和運算。基本要求:利用雙向循環(huán)鏈表，設計一個實現(xiàn)任意長的整數(shù)進行加法運算的演示 程序。要求輸入和輸出每四位一組,組間用逗號隔開。女口 :1, 0000, 0000, 0000, 0000。指導教師:金萍指導題目：題目1、迷宮求解問題描述：以一個m >n的長方形表示迷宮，0和1分別表示迷宮中的通路和障 礙。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通 路的結論?；疽?首先實現(xiàn)一個以鏈表作存儲結構的棧類型，然后編寫一個求解迷宮的 非遞歸程序。求得的通路以三元組(i,j,d的形式輸出，其中:(i,j指示迷宮中的一個坐 標,d表示走到下一坐標的方向。如:對于下列數(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實現(xiàn)提示:計算機解迷宮通常用的是 窮舉求解”方法,即從入口出發(fā)，順著某一個 方向進行探索,若能走通,則繼續(xù)往前進；否則沿著原路退回，換一個方向繼續(xù)探索，直 至出口位置,求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設定的迷宮沒 有通路?？梢杂枚S數(shù)組存儲迷宮數(shù)據(jù)，通常設定入口點的下標為 (1,1，出口點的下標為(n,n。為處理方便起見，可在迷宮的四周加一障礙。對于迷宮 任一位置，均可約定有東、南、西、北四個方向可通。選作內(nèi)容：(1編寫遞歸形式的算法，求得迷宮中所有可能的通路；(2以方陣形式輸出迷宮及其通路。題目2、哈夫曼編碼器的實現(xiàn)問題描述:根據(jù)輸入的字符和對應的權重，生成一棵哈夫曼樹,再打印各字符對 應的哈夫曼編碼。并要求利用建好的哈夫曼樹對字符串進行編碼 ，對哈夫曼編碼進 行譯碼。實現(xiàn)提示:元素類型選用字符型，對應的權重值選用整型，請從鍵盤輸入。并從 鍵盤 輸入要編碼和譯碼的字符串或代碼串。題目3、校園導游程序問題描述：設計一個校園導游程序，為來訪的客人提供各種信息查詢服務?；疽螅?1設計你的學校的校園平面圖，所含景點不少于10個。以圖中頂點表示校內(nèi)各 景點,存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等相關信 息。001000101101001000000101100101010000(2為來訪客人提供圖中任意景點相關信息的查詢。(3為來訪客人提供圖中任意景點的問路查詢，即查詢?nèi)我鈨蓚€景點之間的上條 最短的簡單路徑。數(shù)據(jù)測試:由讀者根據(jù)實際情況指定。實現(xiàn)提示：一般情況下，校園的道路是雙向通行的，可設校園平面圖是一個無向網(wǎng)，頂點和 邊均含有相關信息。選作內(nèi)容：(1求校園圖的關節(jié)點。(2提供圖中任意景點問路查詢，即求任意兩個景點之間的所有路徑。(3提供校園圖中多個景點的最佳訪問路線查詢，即求途經(jīng)這多個景點的最佳(短 路徑。(4校園導游圖的景點和道路的修改擴充功能。題目4、病房管理問題描述:一所醫(yī)院中可能包括若干個病房，每個病房中又有若干個床位，建立 一個簡單的醫(yī)院病房管理程序能夠?qū)Σ∪诉M行出入院和床位分配進行管理?；疽螅捍讼到y(tǒng)應具有如下功能：(1 I :初始化(Initialization。建立病房和床位信息。此醫(yī)院中可能包括若干個 病房，而每個病房中又有若干個床位。(2 E :住院(en terhospital。在列出的有空位的病房中，選擇其一,入住。(3 O :出院(Outhospital。選擇某一病房中某個病人，令其出院。(4 Q :查詢(Query。查詢每個病房中空床位數(shù),入住病人數(shù);查詢整個醫(yī) 院的空 床位數(shù)和入住病人數(shù)。測試數(shù)據(jù)：建立一個包含3個病房的醫(yī)院，其中1病房有2張床位,2病房有6張床位,3病 房有8張床位;張三和李四住1病房，王五也要住1病房，此時，床位已滿,于是將其調(diào) 入2病房。實現(xiàn)提示：(1可建立若干個不定長鏈表，每個鏈表代表一個病房，病房數(shù)可用n表示,床位數(shù) 用m表示。(2判斷病房是否住滿，直接對m進行操作即可。指導教師:嚴仍榮指導題目：題目1、舞伴問題問題描述:一班有m個女生、n個男生(m不等于n,舉辦一場舞會.男女生分 別編號坐在舞池兩邊的椅子上，每曲開始時，依次從男生和女生中各出一人配對跳 舞，本曲沒成功配 對者坐著等待下一曲找舞伴，設計一個程序模擬舞伴配對過程?；疽?輸入男、女學生的姓名、性別，由程序自動為男女生編號，可以順序編 號,也可以隨機編號，輸出每曲配對情況(包括男、女生的姓名、性別和編號。原始數(shù)據(jù)和結果數(shù)據(jù)要保存到文件中。測試數(shù)據(jù):分別選擇男生多于女生、女生多于男生、男女生相等的三組測試數(shù)提高要求：計算出任意一位男生(編號為X和任意一位女生(編號為丫,在第K 曲配對跳舞的情況。題目2、管道鋪設施工的最佳方案問題描述：需要在某個城市的n個小區(qū)鋪設管道，則在這n個小區(qū)之間鋪設n-1 條管道 即可,假設任意兩個居民區(qū)之間都可以架設管道，但由于地理環(huán)境的不同，所需 經(jīng)費不同，選擇最優(yōu)的施工方案使總投資盡可能的少。基本要求：輸入表示小區(qū)間關系的圖及每條管道的權值，選擇出n-1條管道,使總投資最 小。圖的 信息輸入一次后，保存到文件中，選擇的n-1條管道輸出到顯示器的同時 也保存于文件中。測試用例:任意選擇一個圖，模擬小區(qū)間可能鋪設的管道及費 用。提高要求:顯示原始圖及選擇n-1條管道后的圖。題目3、商店存貨管理系統(tǒng)功能:建立一商店存貨管理系統(tǒng)，要求每次出貨時取進貨時間最早且最接近保質(zhì) 期中止時間的貨物。分步實施：(1初步完成總體設計，搭好框架,確定人機對話的界面，確定函數(shù)個數(shù)；(2完成最低要求：建立一個文件,包括5個種類的貨物情況，能對商品信息進行擴 充(追加，修改和刪除以及簡單的排序；(3進一步要求：擴充商品數(shù)量，以及完成系統(tǒng)查詢功能。有興趣的同學可以自己 擴充系統(tǒng)功能。要求：1界面友好，函數(shù)功能要劃分好2總體設計應畫一流程圖3程序要加必要的注釋4要提供程序測試方案題目4、通訊錄的制作設計目的：編寫一個通訊錄管理系統(tǒng)。設計任務:本系統(tǒng)應完成幾方面的功能：1輸入信息en ter（;2顯示信息display（;3查找以姓名作為關鍵字search（;4刪除信息delete（;5 存盤save （;6 裝入load（;設計要求:1每條信息至包含：姓名（NAME街道（STREET城市（CITY郵編（EIP 國家（STATE幾項；2作為一個完整的系統(tǒng)，應具有友好的界面和較強的容錯能 力；3 需要鏈表實現(xiàn)；4上機能正常運行。指導教師：楊洋 指導題目：題目1、火車訂票系統(tǒng) 任務：通過此系統(tǒng)可以實現(xiàn)如下功能：1錄入：可以錄入車次情況（數(shù)據(jù)可以存儲在一個數(shù)據(jù)文件中，數(shù) 據(jù)結構、具體數(shù)據(jù)自定）2查詢：可以查詢某個車次的情況（如，輸入車次號， 查詢起止時間，起止城市，票價，票 價折扣，確定是否滿座）；可以輸入起止城 市，查詢車次情況；3訂票：（訂票情況可以存在一個數(shù)據(jù)文件中，結構自己設 定）可以訂票，如果該車次已經(jīng)無票，可以提供相關可選擇；4退票：可退票，退票后修改相關數(shù)據(jù)文件； 客戶資料有姓名，證件號，訂票數(shù)量及車次情況，訂 單要有編號。5修改信息：當信息改變可以修改數(shù)據(jù)文件 要求：根據(jù)以上功能說 明，設計車次信息，訂票信息的存儲結構，設計程序完成功能。題目2、數(shù)制轉(zhuǎn)換問題任意給定一個M進制的數(shù)x，請實現(xiàn)如下要求1求出此數(shù)x的10進制值（用MD表示）2實現(xiàn)對x向任意的一個非M進制的數(shù)的轉(zhuǎn)換。3至少用兩種或 兩種以上的方法實現(xiàn)上述要求（用棧解決，用數(shù)組解決，其它方法解決）。題目3、學生成績管理系統(tǒng) 現(xiàn)有學生成績信息文件1（ 1.txt），內(nèi)容自定義 學生成 績信息文件2 （2.txt）,內(nèi)容自定義 試編寫一管理系統(tǒng)，要求如下：1實現(xiàn)對兩個文件數(shù)據(jù)進行合并，生成新文件3.txt 2抽取出三科成績中有補考的學生并保 存在一個新文件4.txt 3合并后的文件3.txt中的數(shù)據(jù)按總分降序排序（至少采用兩種 排序方法實現(xiàn)4輸入一個學生姓名后，能查找到此學生的信息并輸出結果（至少采用 兩種查找方法實 現(xiàn)5要求使用結構體，鏈或數(shù)組等實現(xiàn)上述要求 6采用多種方法且 算法正確者，可適當加分.題目4、商品銷售管理系統(tǒng) 針對某一種行業(yè)的庫房的產(chǎn)品 進銷存情況進行管理?；疽螅?采用一定的存儲結構對庫房的貨品及其數(shù)量 進行分類管理；2可以進行產(chǎn)品類的添加、產(chǎn)品的添加、產(chǎn)品數(shù)量的添加；能夠查詢庫房每種產(chǎn)品的總量、進貨日期、銷出數(shù)量、銷售時間等；