數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題目2015匯總

1、課程設(shè)計題目1. 運動會分?jǐn)?shù)統(tǒng)計（限 1 人完成）任務(wù)：參加運動會有 n 個學(xué)校，學(xué)校編號為 1 n。比賽分成 m個男子項目，和 w 個 女子項目。 項目編號為男子 1 m，女子 m+1 m+w。不同的項目取前五名或前三名積分； 取前五名的積分分別為： 7、 5、3、2、 1，前三名的積分分別為： 5、 3、 2；哪些取前五名或 前三名由學(xué)生自己設(shè)定。 （ m=20,n=20）功能要求：可以輸入各個項目的前三名或前五名的成績；能統(tǒng)計各學(xué)?？偡?，可以按學(xué)校編號或名稱、學(xué)?？偡?、男女團(tuán)體總分排序輸出； 可以按學(xué)校編號查詢學(xué)校某個項目的情況； 可以按項目編號查詢?nèi)〉们叭蚯拔迕膶W(xué) 校。數(shù)據(jù)存入文件

2、并能隨時查詢規(guī)定：輸入數(shù)據(jù)形式和范圍：可以輸入學(xué)校的名稱，運動項目的名稱輸出形式：有中文提示，各學(xué)校分?jǐn)?shù)為整形界面要求： 有合理的提示，每個功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān)的功能要求。存儲結(jié)構(gòu)： 學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計， 但是要求運動會的相關(guān)數(shù)據(jù)要存儲在 數(shù)據(jù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關(guān)內(nèi)容在 c 語言程序設(shè)計的書上， 請自學(xué)解決） 請在最后的上交資料中指明你用到的存儲結(jié)構(gòu)；測試數(shù)據(jù)：要求使用 1、全部合法數(shù)據(jù)； 2、整體非法數(shù)據(jù)； 3、局部非法數(shù)據(jù)。進(jìn)行程 序測試，以保證程序的穩(wěn)定。測試數(shù)據(jù)及測試結(jié)果請在上交的資料中寫明；2. 飛機訂票系統(tǒng)（限 1 人完成）任務(wù)：

3、通過此系統(tǒng)可以實現(xiàn)如下功能：錄入：可以錄入航班情況（數(shù)據(jù)可以存儲在一個數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定） 。 查詢：可以查詢某個航線的情況 （如， 輸入航班號， 查詢起降時間， 起飛抵達(dá)城市， 航班票價，票價折扣，確定航班是否滿倉）可以輸入起飛抵達(dá)城市，查詢飛機航班情況； 訂票：（訂票情況可以存在一個數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定） ?？梢杂喥保绻摵桨?已經(jīng)無票，可以提供相關(guān) 可以提供相關(guān)可選擇航班 ;退票： 可退票，退票后修改相關(guān)數(shù)據(jù)文件； 客戶資料有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號。 修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件要求： 根據(jù)以上功能說明，設(shè)計航班信息，訂票

4、信息的存儲結(jié)構(gòu)，設(shè)計程序完成功能；3. 文章編輯（限 1 人完成） 功能：輸入一頁文字，程序可以統(tǒng)計出文字、數(shù)字、空格的個數(shù)。 靜態(tài)存儲一頁文章，每行最多不超過 80 個字符，共 N 行；要求（ 1）分別統(tǒng)計出其 中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)； （ 2）統(tǒng)計某一字符串在文章中出現(xiàn)的次數(shù)， 并輸 出該次數(shù)；（ 3）刪除某一子串，并將后面的字符前移。存儲結(jié)構(gòu)使用線性表，分別用幾個子函數(shù)實現(xiàn)相應(yīng)的功能； 輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標(biāo)點符號。 輸出形式：（1）分行輸出用戶輸入的各行字符； （2）分 4行輸出 全部字母數(shù) 、 數(shù)字個數(shù) 、 空格個數(shù) 、 文章總

5、字?jǐn)?shù) （ 3）輸出刪除某一字符串后的文章；4. 宿舍管理查詢軟件（限 1 人完成）1）任務(wù)：為宿舍管理人員編寫一個宿舍管理查詢軟件 , 程序設(shè)計要求：A. 采用交互工作方式（即列出管理功能，供選擇）B. 建立數(shù)據(jù)文件 ，數(shù)據(jù)文件按關(guān)鍵字（姓名、學(xué)號、房號）進(jìn)行排序 （ 冒泡、選 擇、插入排序等任選一種 ）2）查詢菜單 : （ 用二分查找實現(xiàn)以下操作 ）A. 按姓名查詢B. 按學(xué)號查詢C. 按房號查詢3）打印任一查詢結(jié)果（可以連續(xù)操作）5. 地圖著色問題（限 1 人完成） 設(shè)計要求：已知中國地圖，對各省進(jìn)行著色，要求相鄰省所使用的顏色不同，并保證使 用的顏色總數(shù)最少。6. 校園導(dǎo)航問題（限 1

6、人完成） 設(shè)計要求：設(shè)計你的學(xué)校的平面圖，至少包括 10 個以上的場所，每兩個場所間可以有 不同的路，且路長也可能不同，找出從任意場所到達(dá)另一場所的最佳路徑（最短路徑） 。7. 學(xué)校超市選址問題（帶權(quán)有向圖的中心點） （限 1 人完成） 設(shè)計要求：對于某一學(xué)校超市，其他各單位到其的距離不同，同時各單位人員去超市的 頻度也不同。請為超市選址，要求實現(xiàn)總體最優(yōu)。8. 教學(xué)計劃編制問題（限 1 人完成） 設(shè)計要求：針對計算機系本科課程，根據(jù)課程之間的依賴關(guān)系（如離散數(shù)學(xué)應(yīng)在數(shù)據(jù)結(jié) 構(gòu)之前開設(shè)）制定課程安排計劃，并滿足各學(xué)期課程數(shù)目大致相同。9. 散列法的實驗研究（限 1 人完成） 散列法中，散列函數(shù)

7、構(gòu)造方法多種多樣，同時對于同一散列函數(shù)解決沖突的方法也可以不同。 兩者是影響查詢算法性能的關(guān)鍵因素。 對于幾種典型的散列函數(shù)構(gòu)造方法， 做實驗觀 察，不同的解決沖突方法對查詢性能的影響。10. 圖書借閱管理系統(tǒng)（限 1 人完成） 主要分為兩大功能：1）圖書管理 （增加圖書、查詢圖書、刪除圖書、圖書借閱、還書） ；2）會員管理 （增加會員、查詢會員、刪除會員、借書信息） ；11. 構(gòu)造 01 串 （限 1 人完成）問題描述： 給定七個整數(shù) N、A、B、L、C、D、M，要求設(shè)計一個 01 串 S=S(1)S(2)S(N)?；疽螅?1) S(i)=0 或 S(i)=1,1 i N;(2) 對于

8、S的任何連續(xù)長度為 L 的子串 S(j)S(j+1) S(j+L-1), (1 j N-L+1), 0 的個數(shù)大于等于 A 且小于等于 B;(3) 對于 S的任何連續(xù)長度為 M的子串 S(j)S(j+1) S(j+M-1) , (1 j N-M+1),0 的個數(shù)大于等于 C且小于等于 D;例如 ,N=6,A=1,B=2,L=3,C=1,D=1,M=2, 則存在一個滿足上述所有條件的01 串 S=10101。12. 活期儲蓄帳目管理(限 1 人完成)活期儲蓄處理中，儲戶開戶、銷戶、存入、支出活動頻繁，系統(tǒng)設(shè)計要求：1) 能比較迅速地找到儲戶的帳戶，以實現(xiàn)存款、取款記賬；2) 能比較簡單，迅速地實

9、現(xiàn)插入和刪除，以實現(xiàn)開戶和銷戶的需要。13. 二叉排序樹的實現(xiàn)(限 1 人完成) 用順序和二叉鏈表作存儲結(jié)構(gòu)1) 以回車 (n) 為輸入結(jié)束標(biāo)志 , 輸入數(shù)列 L，生成一棵二叉排序樹 T；2) 對二叉排序樹 T 作中序遍歷，輸出結(jié)果；3) 輸入元素 x, 查找二叉排序樹 T,若存在含 x的結(jié)點 ,則刪除該結(jié)點 ,并作中序遍歷 (執(zhí) 行操作 2) ；否則輸出信息“無 x”；14. 最小生成樹問題(限 1 人完成)設(shè)計要求： 在 n 個城市之間建設(shè)網(wǎng)絡(luò)，只需保證連通即可，求最經(jīng)濟的架設(shè)方法。 存儲結(jié)構(gòu) 采用多種。求解算法多種。15. 通訊錄的制作(限 1 人完成) 設(shè)計目的：用數(shù)據(jù)結(jié)構(gòu)中的雙向鏈表

10、作數(shù)據(jù)結(jié)構(gòu)，結(jié)合C 語言基本知識。編寫一個通訊錄管理系統(tǒng)。以把所學(xué)數(shù)據(jù)結(jié)構(gòu)知識應(yīng)用到實際軟件開發(fā)中去。設(shè)計內(nèi)容：本系統(tǒng)應(yīng)完成一下幾方面的功能：1) 輸入信息 enter();2) 顯示信息 display( );3) 查找以姓名作為關(guān)鍵字 search( );4) 刪除信息 delete( );5) 存盤 save ( );6) 裝入 load( ) ;設(shè)計要求：1) 每條信息至包含 ：姓名(NAME) 街道(STREET)城市(CITY)郵編( EIP) 國家( STATE)幾項2) 作為一個完整的系統(tǒng)，應(yīng)具有友好的界面和較強的容錯能力3) 上機能正常運行，并寫出課程設(shè)計報告16. 哈夫曼編

11、碼 / 譯碼器(限 1 人完成)【問題描述】設(shè)計一個利用哈夫曼算法的編碼和譯碼系統(tǒng)， 重復(fù)地顯示并處理以下項目， 直到選擇退 出為止?！净疽蟆?) 將權(quán)值數(shù)據(jù)存放在數(shù)據(jù)文件 ( 文件名為 data.txt ，位于執(zhí)行程序的當(dāng)前目錄中 )2) 分別采用動態(tài)和靜態(tài)存儲結(jié)構(gòu)3) 初始化：鍵盤輸入字符集大小 n、n 個字符和 n個權(quán)值，建立哈夫曼樹；4) 編碼：利用建好的哈夫曼樹生成哈夫曼編碼；5) 輸出編碼；6) 設(shè)字符集及頻度如下表：字符 空格 A B C D E F G H I J K L M頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O

12、 P Q R S T U V W X Y Z頻度 57 63 15 1 48 51 80 23 8 18 1 16 1【進(jìn)一步完成內(nèi)容】1) 譯碼功能；2) 顯示哈夫曼樹；3) 界面設(shè)計的優(yōu)化。17. 圖書管理系統(tǒng)(限 1 人完成)【問題描述】設(shè)計一個計算機管理系統(tǒng)完成圖書管理基本業(yè)務(wù)?！净疽蟆?) 每種書的登記內(nèi)容包括書號、書名、著作者、現(xiàn)存量和庫存量；2) 對書號建立索引表(線性表)以提高查找效率；3) 系統(tǒng)主要功能如下： 采編入庫：新購一種書，確定書號后，登記到圖書帳目表中，如果表中已有，則只將庫 存量增加；借閱：如果一種書的現(xiàn)存量大于 0，則借出一本，登記借閱者的書證號和歸還期限，

13、改 變現(xiàn)存量；歸還：注銷對借閱者的登記，改變該書的現(xiàn)存量?！具M(jìn)一步完成內(nèi)容】1) 系統(tǒng)功能的進(jìn)一步完善；2) 索引表采用樹表。3) 設(shè)計內(nèi)容4) 程序流程圖5) 源程序6) 軟件測試報告(包括所用到的數(shù)據(jù)及結(jié)果)18. 散列表的設(shè)計與實現(xiàn)(限 1 人完成)【問題描述】設(shè)計散列表實現(xiàn)電話號碼查找系統(tǒng)?！净疽蟆?) 設(shè)每個記錄有下列數(shù)據(jù)項：電話號碼、用戶名、地址；2) 從鍵盤輸入各記錄，分別以電話號碼和用戶名為關(guān)鍵字建立散列表；3) 采用一定的方法解決沖突；4) 查找并顯示給定電話號碼的記錄；5) 查找并顯示給定用戶名的記錄。【進(jìn)一步完成內(nèi)容】1) 系統(tǒng)功能的完善；2) 設(shè)計不同的散列函數(shù)，比

14、較沖突率；3) 在散列函數(shù)確定的前提下， 嘗試各種不同類型處理沖突的方法， 考察平均查找長度 的變化。19. 走迷宮游戲(限 1 人完成) 程序開始運行時顯示一個迷宮地圖，迷宮中央有一只老鼠，迷宮的右下方有一個糧倉。游戲的任務(wù)是使用鍵盤上的方向鍵操縱老鼠在規(guī)定的時間內(nèi)走到糧倉處。要求：1) 老鼠形象可辨認(rèn)，可用鍵盤操縱老鼠上下左右移動；2) 迷宮的墻足夠結(jié)實，老鼠不能穿墻而過；3) 正確檢測結(jié)果，若老鼠在規(guī)定時間內(nèi)走到糧倉處，提示成功，否則提示失敗；4) 添加編輯迷宮功能，可修改當(dāng)前迷宮，修改內(nèi)容：墻變路、路變墻；5) 找出走出迷宮的所有路徑，以及最短路徑。6) 利用序列化功能實現(xiàn)迷宮地圖文件

15、的存盤和讀出等功能20. 順序結(jié)構(gòu)、動態(tài)鏈表結(jié)構(gòu)下的一元多項式的加法、減法、乘法的實現(xiàn)。 (限 1 人完成) 設(shè)有一元多項式 Am(x) 和 Bn(x).A m(x)=A 0+A1x1+A2x2+A3x3+ +A mxmB n(x)=B 0+B1x1+B2x2+B3x3+ +B nxn請實現(xiàn)求 M(x)= A m(x)+B n(x) 、 M(x)= A m(x)-B n(x) 和 M(x)= A m(x) Bn(x) 。要求：1) 首先判定多項式是否稀疏2) 分別采用順序和動態(tài)存儲結(jié)構(gòu)實現(xiàn)；3) 結(jié)果 M(x) 中無重復(fù)階項和無零系數(shù)項；4) 要求輸出結(jié)果的升冪和降冪兩種排列情況限 1 人完成

16、）21. 利用棧求表達(dá)式的值，可供小學(xué)生作業(yè)，并能給出分?jǐn)?shù)。要求： 建立試題庫文件，隨機產(chǎn)生 n 個題目；題目涉及加減乘除，帶括弧的混合運算； 隨時可以退出；保留歷史分?jǐn)?shù)，能回顧歷史，給出與歷史分?jǐn)?shù)比較后的評價。22. 簡易文本編輯器（限 1 人完成）要求：1）具有圖形菜單界面；2）查找，替換（等長，不等長） ，插入（插串，文本塊的插入） 、塊移動（行塊，列 塊移動），刪除3）可正確存盤、取盤；4）正確顯示總行數(shù)。23. 二叉樹的應(yīng)用（限 1 人完成）要求： 包括二叉樹的創(chuàng)建，二叉樹的中序、前序、后序的遞歸、非遞歸遍歷算法，層次 序的非遞歸遍歷算法的實現(xiàn)等。24. 學(xué)生搭配問題（限 1 人完成

17、）一班有 m個女生 , 有 n 個男生 （m 不等于 n）, 現(xiàn)要開一個舞會 . 男女生分別編號坐在舞池 的兩邊的椅子上 . 每曲開始時 , 依次從男生和女生中各出一人配對跳舞, 本曲沒成功配對者坐著等待下一曲找舞伴 .請設(shè)計一系統(tǒng)模擬動態(tài)地顯示出上述過程 , 要求如下 :1）輸出每曲配對情況。2）計算出任何一個男生 （編號為 X）和任意女生 （編號為 Y）,在第 K曲配對跳 舞的情況。至少求出 K 的兩個值。3）盡量設(shè)計出多種算法及程序 , 可視情況適當(dāng)加分 提示: 用隊列來解決比較方便。25. 敢死隊問題（限 1 人完成）有 M 個敢死隊員要炸掉敵人的一碉堡， 誰都不想去， 排長決定用輪回

18、數(shù)數(shù)的辦法來決定 哪個戰(zhàn)士去執(zhí)行任務(wù)。 如果前一個戰(zhàn)士沒完成任務(wù)， 則要再派一個戰(zhàn)士上去。 現(xiàn)給每個戰(zhàn)士 編一個號， 大家圍坐成一圈，隨便從某一個戰(zhàn)士開始計數(shù)，當(dāng)數(shù)到 5 時，對應(yīng)的戰(zhàn)士就去執(zhí) 行任務(wù)， 且此戰(zhàn)士不再參加下一輪計數(shù)。 如果此戰(zhàn)士沒完成任務(wù)， 再從下一個戰(zhàn)士開始數(shù)數(shù)， 被數(shù)到第 5 時，此戰(zhàn)士接著去執(zhí)行任務(wù)。以此類推，直到任務(wù)完成為止。排長是不愿意去的， 假設(shè)排長為 1 號，請你設(shè)計一程序， 求出從第幾號戰(zhàn)士開始計數(shù)才 能讓排長最后一個留下來而不去執(zhí)行任務(wù)。要求： 至少采用兩種不同的數(shù)據(jù)結(jié)構(gòu)的方法實現(xiàn)。 如果采用三種以上的方法者， 可加分。26. 排序綜合（限 1 人完成） 利用

19、隨機函數(shù)產(chǎn)生 N個隨機整數(shù)（ 20000 以上），對這些數(shù)進(jìn)行多種方法進(jìn)行排序。要求：1） 至少采用三種方法實現(xiàn)上述問題求解 （提示， 可采用的方法有插入排序、 希爾排序、 起泡排序、快速排序、選擇排序、堆排序、歸并排序） 。并把排序后的結(jié)果保存在 不同的文件中。2） 統(tǒng)計每一種排序方法的性能（以上機運行程序所花費的時間為準(zhǔn)進(jìn)行對比） ，找出 其中兩種較快的方法。3）如果采用 4種或 4 種以上的方法者，可適當(dāng)加分。27. 學(xué)生成績管理系統(tǒng)（限 1 人完成） 現(xiàn)有學(xué)生成績信息文件 1（ 1.txt ），內(nèi)容如下姓名學(xué)號語文數(shù)學(xué) 英語張明明01677882李成友02789188張輝燦036882

20、56王露04564577陳東明05673847學(xué)生成績信息文件 2（ 2.txt ）, 內(nèi)容如下 : 姓名 學(xué)號 語文 數(shù)學(xué) 英語 陳果 31 57 68 82李華明 32 88 90 68張明東33484256李明國34504587陳道亮35475877試編寫一管理系統(tǒng) , 要求如下 :1） 實現(xiàn)對兩個文件數(shù)據(jù)進(jìn)行合并 , 生成新文件 3.txt2） 抽取出三科成績中有補考的學(xué)生并保存在一個新文件 4.txt3）對合并后的文件 3.txt 中的數(shù)據(jù)按總分降序排序 （ 至少采用兩種排序方法實現(xiàn) ）4）輸入一個學(xué)生姓名后 , 能查找到此學(xué)生的信息并輸出結(jié)果（ 至少采用兩種查找方法實現(xiàn)）5）要求使

21、用結(jié)構(gòu)體 , 鏈或數(shù)組等實現(xiàn)上述要求。6）采用多種方法且算法正確者 , 可適當(dāng)加分。28. 圖的遍歷和生成樹求解實現(xiàn)（限 1 人完成）要求：（1）先任意創(chuàng)建一個圖；（2）圖的 DFS,BFS的遞歸和非遞歸算法的實現(xiàn)（3）最小生成樹（兩個算法）的實現(xiàn)，求連通分量的實現(xiàn)（4）要求用鄰接矩陣、鄰接表、十字鏈表多種結(jié)構(gòu)存儲實現(xiàn)29. 線索二叉樹的應(yīng)用（限 1 人完成） 要求：實現(xiàn)線索樹建立、插入、刪除、恢復(fù)線索的實現(xiàn)。30. 稀疏矩陣應(yīng)用（限 1 人完成） 要求：實現(xiàn)三元組，十字鏈表下的稀疏矩陣的加、轉(zhuǎn)、乘的實現(xiàn)。31. 樹的應(yīng)用（限 1 人完成） 要求：實現(xiàn)樹與二叉樹的轉(zhuǎn)換。以及樹的前序、后序的遞歸

22、、非遞歸算法，層次序的非 遞歸算法的實現(xiàn)，應(yīng)包含建樹的實現(xiàn)。34括號匹配問題（限 1 人完成）問題描述： 假設(shè)一個算術(shù)表達(dá)式中可包含三種括號： 圓括號， 方括號和花括號且這三種 括號可按任意次序嵌套使用。 試?yán)脳５倪\算， 編寫判別給定表達(dá)式中所含括號是否正確配 對出現(xiàn)的算法。35哈希表的設(shè)計與實現(xiàn)（限 1 人完成）問題描述 ： 設(shè)計哈希表實現(xiàn)電話號碼查詢系統(tǒng)?；疽?：1 、設(shè)每個記錄有下列數(shù)據(jù)項：電話號碼、用戶名、地址；2 、從鍵盤輸入各記錄，分別以電話號碼和用戶名為關(guān)鍵字建立哈希表；3 、采用再哈希法解決沖突；4 、查找并顯示給定電話號碼的記錄；5 、查找并顯示給定用戶名的記錄。6 、在哈希函數(shù)確定的前提下，嘗試各種不同類型處理沖突的方法（至少兩種） ，考察平 均查找長度的變化。36關(guān)鍵路徑問題 （限 1 人完成）問題