第一篇：數(shù)據結構課程設計題目要求2010-12-22

1.二叉樹的遍歷和應用

問題描述：以二叉鏈表表示二叉樹，在此基礎上實現(xiàn)對二叉樹的遍歷和應用。要求： 創(chuàng)建二叉樹

輸出二叉樹

二叉樹的先序、中序、后序遍歷

二叉樹的按層遍歷

統(tǒng)計二叉樹的葉子結點、計算二叉樹的深度

設計主函數(shù)測試該類。2.猴子選大王（約瑟夫環(huán)）

問題描述：一堆猴子都有編號，編號是1,2,3….m，這群猴子（m個）按照1-m的順序圍坐一圈，從1開始數(shù)，沒數(shù)到第N個，該猴子就要離開此圈，這樣依次下來，直到圈中只剩下最后一只猴子，則該猴子為大王。輸入數(shù)據：輸入m，n。（m，n為整數(shù)，且n

問題描述：設計一個利用赫夫曼算法的編碼和譯碼系統(tǒng)。要求：從鍵盤給出字符及頻度，建立赫夫曼樹并輸出； 4.圖的建立及輸出

問題描述：建立圖的存儲結構（圖的類型可以是有向圖，無向圖；有向網，無向網，任選一組或以上），能夠輸入圖的頂點和邊的信息，并存儲到相應的存儲結構中，而后輸出圖的鄰接矩陣。5.常用排序算法的實現(xiàn)

問題描述：對10000個隨機整數(shù)，利用插入排序，希爾排序，起泡排序，快速排序，選擇排序，堆排序，歸并排序等方法進行排序，并統(tǒng)計每一種排序上機所花費時間并列出統(tǒng)計表。數(shù)據的輸入：整數(shù) 數(shù)據的輸出：遞增

6.順序結構、動態(tài)鏈表結構下的一元多項式的加法，減法的實現(xiàn) 問題描述：先建立一元多項式Am（x）和Bn（x）

要求：完成兩個多項式的加法，減法；按照降冪排列顯示。

7.二叉平衡樹

問題描述：從一顆空樹開始創(chuàng)建，保證數(shù)的有序性，同時要針對數(shù)的平衡性做些微調。最終要把創(chuàng)建的二叉排序樹轉換成二叉平衡樹。基本要求：創(chuàng)建（插入，調整），輸出。

參考資料：1．《數(shù)據結構

（C語言版）》嚴蔚敏、吳偉民 主編 清華大學出版社 2004.11 2．《數(shù)據結構課程設計案例精編（用C/C++描述）》，李建學 等 編著，清華大學出版社 2007.2 3.《數(shù)據結構:用面向對象方法與C++語言描述》，殷人昆 主編，清華大學出版社 2007.6 課程設計報告的規(guī)范要求： 1.需求分析

進行需求分析，確定每個模塊的功能要求。即根據設計題目的要求，充分地分析和理解問題，明確問題要求做的內容。2.算法設計

進行概要設計和詳細設計。說明用到的數(shù)據結構定義，主程序的流程及各程序模塊的調用關系。并用自然語言描述每個模塊所設計的算法。3.測試數(shù)據

列出對于給定的輸入所產生的輸出結果。4.源程序及系統(tǒng)文件使用說明

附上關鍵數(shù)據結構的定義及關鍵算法的源代碼。5.心得體會

談談課程設計過程中的收獲，遇到的問題及解決問題過程的思考，程序調試能力的思考，對數(shù)據結構這么課程的思考，在課程設計過程中對《數(shù)據結構》課程認識等的思考。6.參考文獻

參考文獻要注明作者，出版社，出版日期。

7.提交內容包括：a.完整的程序系統(tǒng)（電子方式提交，以學號命名文件夾，由班長統(tǒng)一刻錄成光盤上交）；b.課程設計報告（字數(shù)不少于1500字）。8.課程設計考核方法及成績評定：課程設計成績分兩部分，設計報告占50%，設計作品占50%；其中設計報告需要答辯。9.報告封面格式

課程設計報告

題目：

班級：

學號：

姓名：

第二篇：2012級數(shù)據結構課程設計題目及要求

2012級數(shù)據結構課程設計題目及要求

一、要求

本次課程設計可以從以下的題目中任選其一，每個題目基本實現(xiàn)的要求是：

1、有菜單功能

2、有讀寫數(shù)據存盤功能

3、有數(shù)據圖形顯示或動畫顯示。

成品應包括以下內容：

1、程序設計書（Word格式）。

包括程序設計目標、問題描述、需求分析、概要設計、詳細設計、源程序清單（要求格式整齊400行以上，要有注釋說明）、軟件說明書（給出軟件如何使用，使用時的注意事項）、測試報告（每個函數(shù)的功能測試，輸入條件，輸出結果）和課程設計總結。

2、可執(zhí)行程序源代碼。

二、設計題目

三、上交作業(yè)及成績評定

1、上交要求

1）上交課程設計報告和源程序代碼。

2）每小組寫一份設計報告，以電子版形式上交，排版一定要規(guī)范，否則成績下降一檔。

3）以自己的“2012+專業(yè)+學號+姓名”建立文件夾，文件夾內容包括程序源碼、設計報告的電子文檔。

4）課程設計時間為二周，要求每人上機學時不低于20學時。

2、評分標準

根據完成任務的情況(必須進行系統(tǒng)演示)、課程設計報告書的質量和課程設計過程中的工作態(tài)度等按照30%、50%、20%加權綜合打分。成績評定實行優(yōu)秀、良好、中等、及格和不及格五個等級。上機程序檢查未通過者、無設計報告者以及嚴重抄襲他人設計者，成績?yōu)椴患案瘛?/p>

注：

每班分為十幾個小組，每組2人。

每個題目每班最多只能有兩小組選做。

每小組之間不得雷同，否則成績最多及格。

第三篇：數(shù)據結構課程設計題目.

數(shù)據結構課程設計題目

1.運動會分數(shù)統(tǒng)計（限1 人完成）

任務：參加運動會有n個學校，學校編號為1……n。比賽分成m個男子項目，和w個女子項目。項目編號為男子1……m，女子m+1……m+w。不同的項目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前三名由學生自己設定。（m<=20,n<=20）

功能要求：

1)可以輸入各個項目的前三名或前五名的成績； 2)能統(tǒng)計各學校總分，3)可以按學校編號或名稱、學校總分、男女團體總分排序輸出；

4)可以按學校編號查詢學校某個項目的情況；可以按項目編號查詢取得前三或前五名的學校。5)數(shù)據存入文件并能隨時查詢

6)規(guī)定：輸入數(shù)據形式和范圍：可以輸入學校的名稱，運動項目的名稱

輸出形式：有合理的提示，各學校分數(shù)為整形

界面要求：有合理的提示，每個功能可以設立菜單，根據提示，可以完成相關的功能要求。

存儲結構：學生自己根據系統(tǒng)功能要求自己設計，但是要求運動會的相關數(shù)據要存儲在數(shù)據文件中。（數(shù)據文件的數(shù)據讀寫方法等相關內容在c語言程序設計的書上，請自學解決）請在最后的上交資料中指明你用到的存儲結構；

測試數(shù)據：要求使用

1、全部合法數(shù)據；

2、整體非法數(shù)據；

3、局部非法數(shù)據。進行程序測試，以保證程序的穩(wěn)定。測試數(shù)據及測試結果請在上交的資料中寫明；

2.飛機訂票系統(tǒng)（限1 人完成）

任務：通過此系統(tǒng)可以實現(xiàn)如下功能：

錄入：

可以錄入航班情況（數(shù)據可以存儲在一個數(shù)據文件中，數(shù)據結構、具體數(shù)據自定）

查詢：

可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛抵達城市，航班票價，票價折扣，確定航班是否滿倉）；

可以輸入起飛抵達城市，查詢飛機航班情況；

訂票：（訂票情況可以存在一個數(shù)據文件中，結構自己設定）

可以訂票，如果該航班已經無票，可以提供相關可選擇航班；

退票： 可退票，退票后修改相關數(shù)據文件；

客戶資料有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號。

修改航班信息：

當航班信息改變可以修改航班數(shù)據文件

要求：

根據以上功能說明，設計航班信息，訂票信息的存儲結構，設計程序完成功能；

3.文章編輯（限1 人完成）

功能：輸入一頁文字，程序可以統(tǒng)計出文字、數(shù)字、空格的個數(shù)。

靜態(tài)存儲一頁文章，每行最多不超過80個字符，共N行；要求（1）分別統(tǒng)計出其中英文字母數(shù)和空格數(shù)及整篇文章總字數(shù)；（2）統(tǒng)計某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。

存儲結構使用線性表，分別用幾個子函數(shù)實現(xiàn)相應的功能；

輸入數(shù)據的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標點符號。

輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出“全部字母數(shù)”、“數(shù)字個數(shù)”、“空格個數(shù)”、“文章總字數(shù)”（3）輸出刪除某一字符串后的文章；

4.宿舍管理查詢軟件（限1 人完成）

1)任務：為宿舍管理人員編寫一個宿舍管理查詢軟件, 程序設計要求： A.采用交互工作方式

B.建立數(shù)據文件，數(shù)據文件按關鍵字（姓名、學號、房號）進行排序(冒泡、選擇、插入排序等任選一種)2)查詢菜單:(用二分查找實現(xiàn)以下操作)A.按姓名查詢

B.按學號查詢

C.按房號查詢

3)打印任一查詢結果（可以連續(xù)操作）

5.校園導航問題（限1 人完成）

設計要求：設計你的學校的平面圖，至少包括10個以上的場所，每兩個場所間可以有不同的路，且路長也可能不同，找出從任意場所到達另一場所的最佳路徑（最短路徑）。

6.教學計劃編制問題（限1 人完成）

設計要求：針對計算機系本科課程，根據課程之間的依賴關系（如離散數(shù)學應在數(shù)據結構之前開設）制定課程安排計劃，并滿足各學期課程數(shù)目大致相同。

7.散列法的實驗研究（限1 人完成）

散列法中，散列函數(shù)構造方法多種多樣，同時對于同一散列函數(shù)解決沖突的方法也可以不同。兩者是影響查詢算法性能的關鍵因素。對于幾種典型的散列函數(shù)構造方法，做實驗觀察，不同的解決沖突方法對查詢性能的影響。

8.圖書借閱管理系統(tǒng)（限1 人完成）

主要分為兩大功能：

1)圖書管理(增加圖書、查詢圖書、刪除圖書、圖書借閱、還書)； 2)會員管理(增加會員、查詢會員、刪除會員、借書信息)；

9.學生成績管理（限1 人完成）

實現(xiàn)功能：輸入、輸出、插入、刪除、查找、追加、讀入、顯示、保存、拷貝、排序、索引、分類合計、退出。

10.活期儲蓄帳目管理（限1 人完成）

活期儲蓄處理中，儲戶開戶、銷戶、存入、支出活動頻繁，系統(tǒng)設計要求： 1)能比較迅速地找到儲戶的帳戶，以實現(xiàn)存款、取款記賬； 2)能比較簡單，迅速地實現(xiàn)插入和刪除，以實現(xiàn)開戶和銷戶的需要。

11.二叉排序樹的實現(xiàn)（限1 人完成）

用順序和二叉鏈表作存儲結構

1)以回車('n')為輸入結束標志,輸入數(shù)列L，生成一棵二叉排 序樹T； 2)對二叉排序樹T作中序遍歷，輸出結果；

3)輸入元素x,查找二叉排序樹T,若存在含x的結點,則刪除該結點,并作中序遍歷(執(zhí)行操作2)；否則輸出信息“無x”；

12.最小生成樹問題（限1 人完成）

設計要求：在n個城市之間建設網絡，只需保證連通即可，求最經濟的架設方法。存儲結構采用多種。求解算法多種。

13.通訊錄的制作（限1 人完成）

設計目的：用〈〈數(shù)據結構〉〉中的雙向鏈表作數(shù)據結構，結合C語言基本知識。編寫一個通訊錄管理系統(tǒng)。以把所學數(shù)據結構知識應用到實際軟件開發(fā)中去。設計內容：本系統(tǒng)應完成一下幾方面的功能： 1)輸入信息——enter();2)顯示信息———display();3)查找以姓名作為關鍵字 ———search();4)刪除信息———delete();5)存盤———save();6)裝入———load();設計要求：

1)每條信息至包含 ：姓名（NAME）街道（STREET）城市（CITY）郵編（EIP）國家（STATE）幾項 2)作為一個完整的系統(tǒng)，應具有友好的界面和較強的容錯能力 3)上機能正常運行，并寫出課程設計報告

14.哈夫曼編碼/譯碼器（限1 人完成）【問題描述】

設計一個利用哈夫曼算法的編碼和譯碼系統(tǒng)，重復地顯示并處理以下項目，直到選擇退出為止。【基本要求】

1)將權值數(shù)據存放在數(shù)據文件(文件名為data.txt，位于執(zhí)行程序的當前目錄中)2)分別采用動態(tài)和靜態(tài)存儲結構

3)初始化：鍵盤輸入字符集大小n、n個字符和n個權值，建立哈夫曼樹； 4)編碼：利用建好的哈夫曼樹生成哈夫曼編碼； 5)輸出編碼；

6)設字符集及頻度如下表：

字符 空格 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 P Q R S T U V W X Y Z 頻度 57 63 15 1 48 51 80 23 8 18 1 16 1 【進一步完成內容】 1)譯碼功能； 2)顯示哈夫曼樹； 3)界面設計的優(yōu)化。

15.圖書管理系統(tǒng)（限1 人完成）【問題描述】

設計一個計算機管理系統(tǒng)完成圖書管理基本業(yè)務。【基本要求】

1)每種書的登記內容包括書號、書名、著作者、現(xiàn)存量和庫存量； 2)對書號建立索引表（線性表）以提高查找效率； 3)系統(tǒng)主要功能如下：

*采編入庫：新購一種書，確定書號后，登記到圖書帳目表中，如果表中已有，則只將庫存量增加； *借閱：如果一種書的現(xiàn)存量大于0，則借出一本，登記借閱者的書證號和歸還期限，改變現(xiàn)存量； *歸還：注銷對借閱者的登記，改變該書的現(xiàn)存量。【進一步完成內容】 1)系統(tǒng)功能的進一步完善； 2)索引表采用樹表。3)設計內容 4)程序流程圖 5)源程序

6)軟件測試報告（包括所用到的數(shù)據及結果）

16.散列表的設計與實現(xiàn)（限1 人完成）【問題描述】

設計散列表實現(xiàn)電話號碼查找系統(tǒng)。【基本要求】

1)設每個記錄有下列數(shù)據項：電話號碼、用戶名、地址；

2)從鍵盤輸入各記錄，分別以電話號碼和用戶名為關鍵字建立散列表； 3)采用一定的方法解決沖突； 4)查找并顯示給定電話號碼的記錄； 5)查找并顯示給定用戶名的記錄。【進一步完成內容】 1)系統(tǒng)功能的完善；

2)設計不同的散列函數(shù)，比較沖突率；

3)在散列函數(shù)確定的前提下，嘗試各種不同類型處理沖突的方法，考察平均查找長度的變化。

17.順序結構、動態(tài)鏈表結構下的一元多項式的加法、減法、乘法的實現(xiàn)。（限1 人完成）

設有一元多項式Am(x)和Bn(x).Am(x)=A0+A1x1+A2x2+A3x3+… +Amxm

Bn(x)=B0+B1x1+B2x2+B3x3+… +Bnxn

請實現(xiàn)求M(x)= Am(x)+Bn(x)、M(x)= Am(x)-Bn(x)和M(x)= Am(x)×Bn(x)。要求：

1)首先判定多項式是否稀疏

2)分別采用順序和動態(tài)存儲結構實現(xiàn)； 3)結果M(x)中無重復階項和無零系數(shù)項； 4)要求輸出結果的升冪和降冪兩種排列情況

18.利用棧求表達式的值，可供小學生作業(yè)，并能給出分數(shù)。（限1 人完成）

要求：建立試題庫文件，隨機產生n個題目；題目涉及加減乘除，帶括弧的混合運算；隨時可以退出；保留歷史分數(shù)，能回顧歷史，給出與歷史分數(shù)比較后的評價

19.簡易文本編輯器（限1 人完成）要求：

1)具有圖形菜單界面；

2)查找，替換（等長，不等長），插入（插串，文本塊的插入）、塊移動（行塊，列塊移動），刪除 3)可正確存盤、取盤； 4)正確顯示總行數(shù)。

20.二叉樹的中序、前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法的實現(xiàn)，應包含建樹的實現(xiàn)。（限1 人完成）

要求：遍歷的內容應是千姿百態(tài)的。

樹與二叉樹的轉換的實現(xiàn)。以及樹的前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法的實現(xiàn)，應包含建樹的實現(xiàn)。

要求：遍歷的內容應是千姿百態(tài)的。

21.學生搭配問題（限1 人完成）

一班有m個女生,有n個男生(m不等于n),現(xiàn)要開一個舞會.男女生分別編號坐在舞池的兩邊的椅子上.每曲開始時,依次從男生和女生中各出一人配對跳舞, 本曲沒成功配對者坐著等待下一曲找舞伴.請設計一系統(tǒng)模擬動態(tài)地顯示出上述過程,要求如下: 1)輸出每曲配對情況

2)計算出任何一個男生(編號為X)和任意女生(編號為Y),在第K曲配對跳舞的情況.至少求出K的兩個值.3)盡量設計出多種算法及程序,可視情況適當加分

提示:用隊列來解決比較方便.22.猴子吃桃子問題（限1 人完成）

有一群猴子摘了一堆桃子，他們每天都吃當前桃子的一半且再多吃一個，到了第10天就只余下一個桃子。用多種方法實現(xiàn)求出原來這群猴子共摘了多少個桃子。

要求：

1)采用數(shù)組數(shù)據結構實現(xiàn)上述求解 2)采用鏈數(shù)據結構實現(xiàn)上述求解 3)采用遞歸實現(xiàn)上述求解

23.數(shù)制轉換問題（限1 人完成）

任意給定一個M進制的數(shù)x，請實現(xiàn)如下要求 1)求出此數(shù)x的10進制值（用MD表示）2)實現(xiàn)對x向任意的一個非M進制的數(shù)的轉換。

3)至少用兩種或兩種以上的方法實現(xiàn)上述要求（用棧解決，用數(shù)組解決，其它方法解決）。

24.排序綜合（限1 人完成）

利用隨機函數(shù)產生N個隨機整數(shù)（20000以上），對這些數(shù)進行多種方法進行排序。要求：

1)至少采用三種方法實現(xiàn)上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結果保存在不同的文件中。

2)統(tǒng)計每一種排序方法的性能（以上機運行程序所花費的時間為準進行對比），找出其中兩種較快的方法。3)如果采用4種或4種以上的方法者，可適當加分。

25.學生成績管理系統(tǒng)（限1 人完成）現(xiàn)有學生成績信息文件1（1.txt），內容如下 姓名 學號 語文 數(shù)學 英語

張明明 01 67 78 82 李成友 02 78 91 88 張輝燦 03 68 82 56 王露 04 56 45 77 陳東明 05 67 38 47 ….......…

學生成績信息文件2（2.txt）,內容如下: 姓名 學號 語文 數(shù)學 英語

陳果 31 57 68 82 李華明 32 88 90 68 張明東 33 48 42 56 李明國 34 50 45 87 陳道亮 35 47 58 77 ….......… 試編寫一管理系統(tǒng),要求如下: 1)實現(xiàn)對兩個文件數(shù)據進行合并,生成新文件3.txt 2)抽取出三科成績中有補考的學生并保存在一個新文件4.txt 3)合并后的文件3.txt中的數(shù)據按總分降序排序(至少采用兩種排序方法實現(xiàn))4)輸入一個學生姓名后,能查找到此學生的信息并輸出結果(至少采用兩種查找方法實現(xiàn))5)要求使用結構體,鏈或數(shù)組等實現(xiàn)上述要求.6)采用多種方法且算法正確者,可適當加分.26.圖的遍歷的實現(xiàn)（限1 人完成）要求：

1)先任意創(chuàng)建一個圖；

2)圖的DFS,BFS的遞歸和非遞歸算法的實現(xiàn) 3)要求用有向圖和無向圖分別實現(xiàn)

4)要求用鄰接矩陣、鄰接表多種結構存儲實現(xiàn)

27.線索二叉樹的應用（限1 人完成）

要求：實現(xiàn)線索樹建立、插入、刪除、恢復線索的實現(xiàn)。

28.稀疏矩陣應用（限1 人完成）

要求：實現(xiàn)三元組，十字鏈表下的稀疏矩陣的加、轉、乘的實現(xiàn)。（1）稀疏矩陣的存儲（2）稀疏矩陣加法（3）矩陣乘法（4）矩陣轉置

29.樹的應用（限1 人完成）

要求：實現(xiàn)樹與二叉樹的轉換的實現(xiàn)。以及樹的前序、后序的遞歸、非遞歸算法，層次序的非遞歸算法的實現(xiàn)，應包含建樹的實現(xiàn)。

30.文本文件單詞的檢索與計數(shù) 設計要求與分析：

要求編程建立一個文本文件，每個單詞不包含空格且不跨行，單詞由字符序列構成且區(qū)分大小寫；統(tǒng)計給定單詞在文本文件中出現(xiàn)的總次數(shù)；檢索輸出某個單詞出現(xiàn)在文本中的行號、在該行中出現(xiàn)的次數(shù)以及位置。該設計要求可分為三個部分實現(xiàn)：其一，建立文本文件，文件名由用戶用鍵盤輸入；其二，給定單詞的計數(shù)，輸入一個不含空格的單詞，統(tǒng)計輸出該單詞在文本中的出現(xiàn)次數(shù)；其三，檢索給定單詞，輸入一個單詞，檢索并輸出該單詞所在的行號、該行中出現(xiàn)的次數(shù)以及在該行中的相應位置。（1）.建立文本文件（2）給定單詞的計數(shù)

（3）檢索單詞出現(xiàn)在文本文件中的行號、次數(shù)及其位置（4）主控菜單程序的結構 ① 頭文件包含 ② 菜單選項包含

建立文件、單詞定位、單詞計數(shù)、退出程序 ③ 選擇1-4執(zhí)行相應的操作，其他字符為非法。

31.任意長的整數(shù)加法（限1 人完成）

問題描述：設計一個程序實現(xiàn)兩個任意長的整數(shù)的求和運算。

基本要求：利用雙向循環(huán)鏈表，設計一個實現(xiàn)任意長的整數(shù)進行加法運算的演示程序。要求輸入和輸出每四位一組，組間用逗號隔開。如：1，0000，0000，0000，0000。

32.二叉平衡排序樹（限1 人完成）

問題描述：從一棵空樹開始創(chuàng)建，在創(chuàng)建過程中，保證樹的有序性，同時還要針對樹的平衡性做些調整。最終要把創(chuàng)建好的二叉排序樹轉換為二叉平衡排序樹。基本要求：1.創(chuàng)建（插入、調整、改組）

2.輸出

33.串的查找和替換（限1 人完成）

問題描述：打開一篇英文文章，在該文章中找出所有給定的單詞，然后對所有給定的單詞替換為另外一個單詞，再存盤。

34.約瑟夫環(huán)（限1 人完成）

問題描述：編號為1，2… n的n個人按順時針方向圍坐一圈，每人持有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)的上限值m，從第一個人開始按順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)，報m的人出列，將他的密碼作為新的m值，從他的順時針方向上的下一個開始重新從1報數(shù)，如此下去，直至所有人全部出列為止，設計一個程序求出出列順序。

基本要求：

1、利用單循環(huán)鏈表作為存儲結構模擬此過程；

2、鍵盤輸入總人數(shù)、初始報數(shù)上限值m及各人密碼；

3、按照出列順序輸出各人的編號。

35.構造可以使n個城市連接的最小生成樹（限1 人完成）

問題描述：給定一個地區(qū)的n個城市間的距離網，用Prim算法或Kruskal算法建立最小生成樹，并計算得到的最小生成樹的代價。基本要求：

1、城市間的距離網采用鄰接矩陣表示，鄰接矩陣的存儲結構定義采用課本中給出的定義，若兩個城市之間不存在道路，則將相應邊的權值設為自己定義的無窮大值。要求在屏幕上顯示得到的最小生成樹中包括了哪些城市間的道路，并顯示得到的最小生成樹的代價。

2、表示城市間距離網的鄰接矩陣（要求至少6個城市，10條邊）

3、最小生成樹中包括的邊及其權值，并顯示得到的最小生成樹的代價。

36.客戶消費積分管理系統(tǒng)（限1 人完成）

問題描述：針對客戶的消費情況，進行客戶管理，根據客戶的消費積分對客戶實行不同程度的打折優(yōu)惠。基本要求：

1.采用一定的存儲結構進行客戶信息的存儲； 2.對客戶的信息可以進行修改、刪除、添加； 3.能夠根據消費情況進行客戶積分的計算； 4.根據積分情況實行不同程度的打折優(yōu)惠；

37.產品進銷存管理系統(tǒng)（限1 人完成）

問題描述：針對某一種行業(yè)的庫房的產品進銷存情況進行管理。基本要求：

1.采用一定的存儲結構對庫房的貨品及其數(shù)量進行分類管理； 2.可以進行產品類的添加、產品的添加、產品數(shù)量的添加；

3.能夠查詢庫房每種產品的總量、進貨日期、銷出數(shù)量、銷售時間等；

38.特殊矩陣的壓縮存儲算法的實現(xiàn)（限1 人完成）問題描述：對于特殊矩陣可以通過壓縮存儲減少存儲空間。基本要求：

1.針對多種特殊矩陣進行壓縮存儲，并能顯示壓縮后的相關地址和值； 2.輸入在原來特殊矩陣中的地址，要求能從壓縮后的矩陣中讀出相應的值；

39.算術表達式的求解（限1 人完成）

問題描述：給定一個算術表達式，通過程序求出最后的結果。基本要求：

1． 從鍵盤輸入要求解的算術表達式； 2． 采用棧結構進行算術表達式的求解過程； 3． 能夠判斷算術表達式正確與否； 4． 對于錯誤表達式給出提示； 5． 對于正確的表達式給出最后的結果；

40.實時監(jiān)控報警系統(tǒng)（限1 人完成）問題描述：建立一個報警和出警管理的系統(tǒng) 基本要求：

1.采用一定的存儲結構存儲報警信息，要求有內容、時間； 2.有一次的出警就應該在待處理的信息中刪除這條信息； 3.記錄出警信息；

4.待處理信息過多時會發(fā)出警告；

41.車廂調度（限1 人完成）

問題描述：假設停在鐵路調度站入口處的車廂序列的編號一次為1，2，3，4。設計一個程序，求出所有可能由此輸出的長度為4的車廂序列。

42.迷宮問題（棧）問題描述：

以一個m*n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論。基本要求：

首先實現(xiàn)一個以鏈表作存儲結構的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i,j,d）的形式輸出，其中：（i,j）指示迷宮中的一個坐標，d表示走到下一坐標的方向，如：對于下列數(shù)據的迷宮，輸出的一條通路為：（1，1，1），（1,2,2）,(3,2,3),(3,1,2),…。測試數(shù)據：

迷宮的測試數(shù)據如下：左下角（1，1）為入口，右下角（8，9）為出口。實現(xiàn)提示： 計算機解迷宮通常用的是“窮舉求解”方法，即從入口出發(fā)，順著某個方向進行探索，若能走通，則繼續(xù)往前進；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設的迷宮沒有通路。

可以二維數(shù)組存儲迷宮數(shù)據，通常設定入口點的下標為（1，1），出口點的下標為（n,n）。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮中任一位置，均可約定有東、南、西、北四個方向可通。選做內容：

（1）編寫遞歸形式的算法，求得迷宮中所有可能的通路；（2）以方陣形式輸出迷宮及其通路。43.迷宮問題（隊列）（同上）44二叉搜索樹：各種搜索樹效率比較 題目要求：

本題目要求對普通的二叉排序樹、AVL樹分別實現(xiàn)制定操作，并分析比較這兩種不同數(shù)據結構對應的一系列插入和刪除操作的效率。要求測試對N個不同整數(shù)進行下列操作的效率：（1）按遞增順序插入N個整數(shù)，并按同樣順序刪除；（2）按遞增順序插入N個整數(shù)，并按相反順序刪除；（3）按隨機順序插入N個整數(shù)，并按隨機順序刪除；

要求N從1000到10000取值，并以數(shù)據規(guī)模N為橫軸，運行時間為縱軸，畫出3種不同數(shù)據結構對應的操作效率比較圖。

45.病毒測試程序 本題的任務是：

當整個網絡被感染后，計算有多少臺機器被某個特定變種所感染。輸入要求：

輸入由若干組測試數(shù)據組成。

每組數(shù)據的第1行包含2個整數(shù)M和N（1≤M,N≤500），接下來是一個M*N的矩陣表示網絡的初始感染狀態(tài)，其中的正、負整數(shù)的意義如題目描述中所定義。

下面一行給出一個正整數(shù)Q，是將要查詢的變種的個數(shù)。接下去的Q行里，每行給出一個變種的類型。當M或N為0時，表示全部測試結束，不要對該數(shù)據做任何處理。輸出要求：

對每一組測試，在一行里輸出被某個特定變種所感染的機器數(shù)量。

46關鍵路徑問題（限1 人完成）

問題描述：設計一個程序求出完成整項工程至少需要多少時間以及整項工程中的關鍵活動。基本要求：

（1）對一個描述工程的AOE網，應判斷其是否能夠順利進行。

（2）若該工程能順利進行，輸出完成整項工程至少需要多少時間，以及每一個關鍵活動所依附的兩個頂點、最早發(fā)生時間、最遲發(fā)生時間。

47.神秘國度的愛情故事

輸入要求：輸入由若干組測試數(shù)據組成。

每組數(shù)據的第1行包含一正整數(shù)N（1≤N≤50000），代表神秘國度中小村的個數(shù)，每個小村即從0到N-1編號。接下來有N-1行輸入，每行包含一條雙向道路的兩端小村的編號，中間用空格分開。之后一行包含一正整數(shù)M（1≤M≤500000），代表著該組測試問題的個數(shù)。接下來M行，每行給出A,B,C三個小村 的編號，中間用空格分開。當N為0時，表示全部測試結束，不要對該數(shù)據做任何處理。

輸出要求：對每一組測試給定的A,B,C，在一行里輸出答案，即：如果C在A和B之間的路徑上，輸出Yes,否則輸出No。

48.并查集：檢查網絡

題目要求：給定一個計算機網絡以及機器間的雙向連線列表，每一條連線允許兩端的計算機進行直接的文件傳輸，其他計算機間若存在一條連通路徑，也可以進行間接的文件傳輸。請寫出程序判斷：任意指定兩臺計算機，它們之間是否可以進行文件傳輸？

輸入要求：輸入若干測試數(shù)據組成。對于每一組測試，第1行包含一個整數(shù)N（≤10000），即網絡中計算機的總臺數(shù)，因而每臺計算機可用1到N之間的一個正整數(shù)表示。接下來的幾行輸入格式為I C1 C2或者 C或者C C1C2或者S，其中C1和C2是兩臺計算機的序號，I表示在C1和C2間輸入一條連線，C表示檢查C1和C2間是否可以傳輸文件，S表示該組測試結束。當N為0時，表示全部測試結束，不要對該數(shù)據做任何處理。

輸出要求：對每一組C開頭的測試，檢查C1和C2間是否可以傳輸文件，若可以，則在一行中輸出“yes”，否則輸出“no”。

當讀到S時，檢查整個網絡。若網絡中任意兩機器間都可以傳輸文件，則在一行中輸出“The network is connected.”，否則輸出“There are k components.”,其中k是網絡中連通集的個數(shù)。兩組測試數(shù)據之間請輸出一空行分隔。

49.廣義表的應用

由于廣義表在結構上較線性表復雜得多，因此，廣義表的運算也不如線性表簡單。本設計要求實現(xiàn)的廣義表的建立、查找、輸出、取表頭和取表尾以及求深度、求逆表等。本設計用一個主控菜單程序控制，共分為6個子系統(tǒng)。（1）.建立廣義表（2）輸出廣義表（3）結點的查找（4）求廣義表表頭（5）求廣義表表尾（6）求廣義表的深度

50.網絡流：宇宙旅行 題目要求：

在走遍了地球上的所有景點以后，旅游狂人開始計劃他的宇宙旅行項目。經過謹慎調查，他目前掌握了一張各衛(wèi)星空間站可以臨時容納的旅客人數(shù)列表。但旅客從一個星球飛往另一個星球時，需要在若干衛(wèi)星空間站臨時停靠中轉，而這些空間站不能接待任何旅客駐留，旅客必須立刻轉乘另一艘飛船離開，所以空間站不能接待超過自己最大容量的旅客流。為了估計預算，現(xiàn)在旅游狂人需要知道終點星球的接待站應該設計多大容量，才能使得每艘飛船在到達時都可以保證讓全部旅客下船。輸入要求：

輸入若干組測試數(shù)據組成。

每組測試數(shù)據的第1行包含旅行的起點星球和終點星球的名稱和一個不超過500的正整數(shù)N（N為0標志全部測試結束，不要對該數(shù)據做任何處理）。

接下來的N行里，數(shù)據格式為：sourcei capacityi，其中sourcei和destinationi是衛(wèi)星空間站的名稱或起點、終點星球的名稱，正整數(shù)capacityi是飛船從sourcei到destinationi一次能運載的最大旅客流量。每個名稱是由A～Z之間三個大寫字母組成的字符串，例如：ZJU。測試數(shù)據中不包含任何到達起點星球的信息以及任何從終點星球出發(fā)的信息。輸出要求：

對每一組測試，在一行里輸出終點星球接待站應具有的最小容量，使得每艘飛船在到達時都可以保證讓全部旅客下船。

第四篇：數(shù)據結構課程設計題目

數(shù)據結構課程設計題目 以下8個題目任選其一。

1．排序算法比較

利用隨機函數(shù)產生30000個隨機整數(shù)，利用插入排序、起泡排序、選擇排序、快速排序、堆排序、歸并排序等排序方法進行排序，并且（1）統(tǒng)計每一種排序上機所花費的時間。

（2）統(tǒng)計在完全正序，完全逆序情況下記錄的比較次數(shù)和移動次數(shù)。（3）比較的指標為關鍵字的比較次數(shù)和記錄的移動次數(shù)(一次記錄交換計為3次移動)。

（4）對結果作簡單分析，包括對各組數(shù)據得出結果波動大小的解釋。2．圖的深度遍歷

對任意給定的圖（頂點數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用堆棧的五種基本運算（清空堆棧、壓棧、彈出、取棧頂元素、判棧空）實現(xiàn)圖的深度優(yōu)先搜索遍歷。畫出搜索順序示意圖。3．圖的廣度遍歷

對任意給定的圖（頂點數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用隊列的五種基本運算（置空隊列、進隊、出隊、取隊頭元素、判隊空）實現(xiàn)圖的廣度優(yōu)先搜索遍歷。畫出搜索順序示意圖。4．二叉樹的遍歷

對任意給定的二叉樹（頂點數(shù)自定）建立它的二叉鏈表存貯結構，并利用棧的五種基本運算（置空棧、進棧、出棧、取棧頂元素、判棧空）實現(xiàn)二叉樹的先序、中序、后序三種遍歷，輸出三種遍歷的結果。畫出搜索順序示意圖。5．鏈表操作

利用鏈表的插入運算建立線性鏈表，然后利用鏈表的查找、刪除、計數(shù)、輸出等運算反復實現(xiàn)鏈表的這些操作（插入、刪除、查找、計數(shù)、輸出單獨寫成函數(shù)的形式），并能在屏幕上輸出操作前后的結果。畫出搜索順序示意圖。6．一元稀疏多項式簡單計數(shù)器（1）輸入并建立多項式

（2）輸出多項式，輸出形式為整數(shù)序列：n，c1，e1，c2，e2……cn，en，其中n是多項式的項數(shù)，ci，ei分別為第i項的系數(shù)和指數(shù)。序列按指數(shù)降序排列。（3）多項式a和b相加，建立多項式a+b，輸出相加的多項式。（4）多項式a和b相減，建立多項式a-b，輸出相減的多項式。用帶頭結點的單鏈表存儲多項式。測試數(shù)據：

（1）(2x+5x8-3.1x11)+(7-5x8+11x9)（2）(6x-3-x+4.4x2-1.2x9)-(-6x-3+5.4x2+7.8x15)（3）(x+x2+x3)+0（4）(x+x3)-(-x-x-3)7．實現(xiàn)兩個鏈表的合并 基本功能要求：（1）建立兩個鏈表A和B，鏈表元素個數(shù)分別為m和n個。

（2）假設元素分別為(x1,x2,…xm)，和(y1,y2, …yn)。把它們合并成一個線性表C，使得：

當m>=n時，C=x1,y1,x2,y2,…xn,yn,…,xm 當n>m時，C=y1,x1,y2,x2,…ym,xm,…,yn 輸出線性表C：

（1）用直接插入排序法對C進行升序排序，生成鏈表D，并輸出鏈表D。測試數(shù)據：

（1）A表（30，41，15，12，56，80）

B表（23，56，78，23，12，33，79，90，55）

（2）A表（30，41，15，12，56，80，23，12，34）B表（23，56，78，23，12）8．哈夫曼編碼的實現(xiàn)與應用

（1）從文件中讀入任意一篇英文短文（至少含3000個字符，文件為ASCII編碼的文本文件）

（2）統(tǒng)計不同字符在文章中出現(xiàn)的頻率（空格、換行、標點等也按字符處理）（3）根據字符頻率構造哈夫曼樹，并給出每個字符的哈夫曼編碼。

（4）用哈夫曼編碼來存儲文件，并和輸入文本文件大小進行比較，計算文件壓縮率

（5）根據相應哈夫曼編碼，對編碼后的文件進行解碼，恢復成ASCII編碼的英文短文后輸出。

分析及設計步驟（供參考）

1.分析問題，給出數(shù)學模型，設計相應的數(shù)據結構。

1)分析問題特點，用數(shù)學表達式或其它形式描述其數(shù)學模型。2)選擇能夠體現(xiàn)問題本身特點的一種或幾種邏輯結構。

3)依據邏輯結構和問題特點，設計并選擇相應的存儲結構（順序存儲結構和鏈式存儲結構對應的算法實現(xiàn)有區(qū)別）。

2.算法設計

1)確定所需模塊：對于復雜的程序設計，要充分利用模塊化程序設計方法和面向對象思想，自頂向下，逐步細化。

2)各子模塊功能描述：給出主要模塊的算法描述，用流程圖或偽代碼表示。3)模塊之間的調用關系：給出算法各模塊之間的關系圖示。3.上機實現(xiàn)程序

為提高工作效率，充分利用上機調試時間，在上機之前應列出程序清單。

4.用有代表性的各種測試數(shù)據去驗證算法及程序的正確性

5.算法分析及優(yōu)化

經過上機調試，源程序運行正確，并且實現(xiàn)算法要求的功能，解決課程設計題目中給出的問題后，分析算法的時間復雜度和空間復雜度，如有可能對程序進行優(yōu)化改進。

課程設計報告范例（參考）

約瑟夫環(huán)問題。

問題描述：設編號為1,2,…,n(n>0)個人按順時針方向圍坐一圈，每人持有一個正整數(shù)密碼。開始時任意給出一個報數(shù)上限值m，從第一個人開始順時針方向自1起順序報數(shù)，報到m時停止報數(shù)，抱m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人起重新自1起順序報數(shù)；如此下去，直到所有人全部出列為止。要求設計一個程序模擬此過程，并給出出列人的編號序列。基本要求：

（1）初始報數(shù)上限值m和測試數(shù)據在程序中確定；（2）用帶頭結點的單循環(huán)鏈表作數(shù)據元素的存儲結構；（3）把帶頭結點的單循環(huán)鏈表作為抽象數(shù)據類型設計。測試數(shù)據：

n = 7，七個人的密碼依次為3,1,7,2,4,8,4 初始報數(shù)上限值m = 20 算法思想：

JesephRing()函數(shù)是實現(xiàn)問題要求的主要函數(shù)，其算法思想是：從1至m對帶頭結點的單循環(huán)鏈表循環(huán)計數(shù)，到m時，輸出該結點的編號值，將該結點的密碼作為新的m值，再從該結點的下一個結點起重新自1起循環(huán)計數(shù)；如此下去，直到單循環(huán)鏈表空時循環(huán)過程結束。模塊劃分：

（1）帶頭結點的單循環(huán)鏈表抽象數(shù)據類型SCLinList，其中包括基本操作的函數(shù)有：初始化操作函數(shù)、插入一個結點操作函數(shù)、刪除一個結點操作函數(shù)、取一個結點數(shù)據操作函數(shù)和判表是否非空操作函數(shù)。該抽象數(shù)據類型文件名為SCLinList.h。

（2）void SCLLDeleteAfter(SCLNode *p)，其功能是刪除帶頭結點的單循環(huán)鏈表中指針p所指結點的下一個結點。這是對帶頭結點的單循環(huán)鏈表抽象數(shù)據類型SCLinList，補充本問題需要的一個操作函數(shù)。（3）void JesephRing(SCLNode *head, int m)，其功能是對帶頭結點的單循環(huán)鏈表head,以m為初始報數(shù)上限值實現(xiàn)問題要求。

（4）void main(void)，主函數(shù)，功能是給出測試數(shù)據值，建立測試數(shù)據值的帶頭結點單循環(huán)鏈表，調用JesephRing()函數(shù)實現(xiàn)問題要求。數(shù)據結構：

（1）數(shù)據類型DataType定義如下： typedef struct { int number;int cipher;} DataType;

（2）帶頭結點單循環(huán)鏈表抽象數(shù)據類型SCLinList。

（3）帶頭結點單循環(huán)鏈表抽象數(shù)據類型的結點結構定義如下：

typedef struct node { DataType data;struct node *next;} SCLNode;源程序：

源程序存放在兩個文件中，文件SCLinList.h是帶頭結點單循環(huán)鏈表抽象數(shù)據類型，文件Exam3-9.c是主程序。

文件SCLinList.h： typedef struct node { DataType data;struct node *next;} SCLNode;/*結點結構定義*/ void SCLLInitiate(SCLNode **head)/*初始化*/ { if((*head =(SCLNode *)malloc(sizeof(SCLNode)))== NULL)exit(1);(*head)->next = *head;} int SCLLInsert(SCLNode *head, int i, DataType x)/*插入一個結點*/ { SCLNode *p, *q;int j;p = head->next;j = 1;while(p!= head && j < i1 && i!= 1){ printf(“插入位置參數(shù)錯！”);return 0;} if((q =(SCLNode *)malloc(sizeof(SCLNode)))== NULL)exit(1);q->data = x;q->next = p->next;p->next = q;return 1;} int SCLLDelete(SCLNode *head, int i, DataType *x)/*刪除一個結點*/ { SCLNode *p, *q;int j;p = head;j = 0;while(p->next!= head && j < i1){ printf(“刪除位置參數(shù)錯！”);return 0;} q = p->next;p->next = p->next->next;*x = q->data;free(q);return 1;} int SCLLGet(SCLNode *head, int i, DataType *x)/*取一個結點數(shù)據元素值*/ { SCLNode *p;int j;p = head;j = 0;while(p->next!= head && j < i){ p = p->next;j++;} if(j!= i){ printf(“取元素位置參數(shù)錯！”);return 0;} *x = p->data;return 1;} int SCLLNotEmpty(SCLNode *head)/*鏈表非空否*/ { if(head->next == head)return 0;else return 1;} 文件Exam3-9.c： #include #include typedef struct { int number;int cipher;} DataType;/*定義具體的數(shù)據類型DataType*/ #include “SCLinList.h” /*包含SCLinList抽象數(shù)據類型*/ void SCLLDeleteAfter(SCLNode *p)/*刪除p指針所指結點的下一個結點*/ { SCLNode *q = p->next;p->next = p->next->next;free(q);} void JesephRing(SCLNode *head, int m)/*對帶頭結點單循環(huán)鏈表head，初始值為m的約瑟夫環(huán)問題函數(shù)*/ { SCLNode *pre, *curr;int i;pre = head;curr = head->next;while(SCLLNotEmpty(head)== 1){ for(i = 1;i < m;i++){ pre = curr;curr = curr->next;if(curr == head){ pre = curr;curr = curr->next;} }

printf(“ %d ”, curr->data.number);m = curr->data.cipher;curr = curr->next;if(curr == head)curr = curr->next;SCLLDeleteAfter(pre);} } void main(void){ DataType test[7]={{1,3},{2,1},{3,7},{4,2},{5,4},{6,8},{7,4}};int n = 7, m = 20, i;SCLNode *head;SCLLInitiate(&head);/*初始化*/ for(i = 1;i <= n;i++)/*循環(huán)插入建立單循環(huán)鏈表鏈表*/ SCLLInsert(head, i, test[i-1]);JesephRing(head, m);/*約瑟夫環(huán)問題函數(shù)*/ } 測試情況： 程序輸出為： 6 1 4 7 2 3 5

各種排序比較結果（參考）

直接插入的比較圖表***030002500直接插入的移動圖表比較次數(shù)2000系列1******4738291100次數(shù)移動次數(shù)2000系列1******4738291100次數(shù) 冒泡的比較次數(shù)***00冒泡的移動圖表***00比較次數(shù)移動次數(shù)*********1100執(zhí)行次數(shù)系列*********91100次數(shù)系列1

SHELL的比較次數(shù)12001000800***01200SHELL的移動圖表比較次數(shù)移動次數(shù)******1100執(zhí)行次數(shù)系列******564738291100次數(shù)系列1

快速排序的比較次數(shù)800700600快速排序的移動圖表540520500比較次數(shù)移動次數(shù)******4738291100執(zhí)行次數(shù)系列******8291100次數(shù)簡單選擇的移動圖表350300250系列1

簡單選擇的比較次數(shù)***0比較次數(shù)移動次數(shù)300025002000******4738291100執(zhí)行次數(shù)堆排序的比較次數(shù)107010601050系列1200系列1******8291100次數(shù) 堆排序的移動圖表***0比較次數(shù)移動次數(shù)*********00執(zhí)行次數(shù)系列117401720******65564738291100次數(shù)系列1

第五篇：數(shù)據結構課程設計參考題目

數(shù)據結構課程設計題目

數(shù)據結構課程設計題目(大題目).doc

一、公司銷售管理系統(tǒng) 項目開發(fā)基本要求

1．客戶信息管理：對客戶的基本信息進行添加、修改和刪除。2．產品信息管理：對產品的基本信息進行添加、修改和刪除。3．供應商信息管理：對供應商的基本信息進行添加、修改和刪除。4．訂單信息管理：對訂單的基本信息進行添加、修改和刪除。

二、高校科研管理系統(tǒng)

系統(tǒng)主要用于幫助高校或科研單位管理和維護各項科研相關資料 項目開發(fā)基本要求

1．系統(tǒng)用戶管理模塊：為系統(tǒng)新用戶設置用戶名及口令；操作員更改自己的系統(tǒng)口令。2．數(shù)據字典管理模塊：管理項目性質包括：分為國家自然科學基金、863、部省科委及企業(yè)集團四種情況；范圍包括：分為全國、國際、地方三種情況；檢索源包括：分為EI、SCI、核心和一般四種情況。

3．項目參加人員管理模塊包括：顯示添加修改刪除查詢。4．項目基本情況模塊包括：顯示添加修改刪除查詢。5．項目獲獎情況模塊包括：顯示添加修改刪除查詢。6．期刊論文管理模塊包括：顯示添加修改刪除查詢。7．著作管理模塊包括：顯示添加修改刪除查詢。

8．科研工作量統(tǒng)計模塊：按照學校科研工作量計算辦法，為每位科研人員進行科研工作量的計算和統(tǒng)計。

9．科研積分統(tǒng)計模塊：按照學校科研積分計算辦法，為每位科研人員進行科研計分的計算和統(tǒng)計。

三、網絡五子棋對戰(zhàn)

四、不同排序算法模擬

五、科學計算器

數(shù)據結構課程設計題目

1.運動會分數(shù)統(tǒng)計

任務：參加運動會有n個學校，學校編號為1……n。比賽分成m個男子項目，和w個女子項目。項目編號為男子1……m，女子m+1……m+w。不同的項目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前三名由學生自己設定。（m<=20,n<=20）

功能要求：

1)可以輸入各個項目的前三名或前五名的成績； 2)能統(tǒng)計各學校總分，3)可以按學校編號或名稱、學校總分、男女團體總分排序輸出； 4)可以按學校編號查詢學校某個項目的情況；可以按項目編號查詢取得前三或前五名的學校。5)數(shù)據存入文件并能隨時查詢

6)規(guī)定：輸入數(shù)據形式和范圍：可以輸入學校的名稱，運動項目的名稱

輸出形式：有合理的提示，各學校分數(shù)為整形

界面要求：有合理的提示，每個功能可以設立菜單，根據提示，可以完成相關的功能要求。

存儲結構：學生自己根據系統(tǒng)功能要求自己設計，但是要求運動會的相關數(shù)據要存儲在數(shù)據文件中。（數(shù)據文件的數(shù)據讀寫方法等相關內容在c語言程序設計的書上，請自學解決）請在最后的上交資料中指明你用到的存儲結構；

測試數(shù)據：要求使用

1、全部合法數(shù)據；

2、整體非法數(shù)據；

3、局部非法數(shù)據。進行程序測試，以保證程序的穩(wěn)定。測試數(shù)據及測試結果請在上交的資料中寫明；

2.飛機訂票系統(tǒng)

任務：通過此系統(tǒng)可以實現(xiàn)如下功能：

錄入：

可以錄入航班情況（數(shù)據可以存儲在一個數(shù)據文件中，數(shù)據結構、具體數(shù)據自定）

查詢：

可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛抵達城市，航班票價，票價折扣，確定航班是否滿倉）；

可以輸入起飛抵達城市，查詢飛機航班情況；

訂票：（訂票情況可以存在一個數(shù)據文件中，結構自己設定）

可以訂票，如果該航班已經無票，可以提供相關可選擇航班；

退票： 可退票，退票后修改相關數(shù)據文件；

客戶資料有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號。

修改航班信息：

當航班信息改變可以修改航班數(shù)據文件

要求：

根據以上功能說明，設計航班信息，訂票信息的存儲結構，設計程序完成功能；

3.文章編輯

功能：輸入一頁文字，程序可以統(tǒng)計出文字、數(shù)字、空格的個數(shù)。

靜態(tài)存儲一頁文章，每行最多不超過80個字符，共N行；要求（1）分別統(tǒng)計出其中英文字母數(shù)和空格數(shù)及整篇文章總字數(shù)；（2）統(tǒng)計某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。

存儲結構使用線性表，分別用幾個子函數(shù)實現(xiàn)相應的功能；

輸入數(shù)據的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標點符號。

輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出“全部字母數(shù)”、“數(shù)字個數(shù)”、“空格個數(shù)”、“文章總字數(shù)”（3）輸出刪除某一字符串后的文章；

4.宿舍管理查詢軟件

1)任務：為宿舍管理人員編寫一個宿舍管理查詢軟件, 程序設計要求： A.采用交互工作方式

B.建立數(shù)據文件，數(shù)據文件按關鍵字（姓名、學號、房號）進行排序(冒泡、選擇、插入排序等任選一種)2)查詢菜單:(用二分查找實現(xiàn)以下操作)A.按姓名查詢 B.按學號查詢 C.按房號查詢

3)打印任一查詢結果（可以連續(xù)操作）

5.校園導航問題

設計要求：設計你的學校的平面圖，至少包括10個以上的場所，每兩個場所間可以有不同的路，且路長也可能不同，找出從任意場所到達另一場所的最佳路徑（最短路徑）。

6.教學計劃編制問題

設計要求：針對計算機系本科課程，根據課程之間的依賴關系（如離散數(shù)學應在數(shù)據結構之前開設）制定課程安排計劃，并滿足各學期課程數(shù)目大致相同。

7.散列法的實驗研究

散列法中，散列函數(shù)構造方法多種多樣，同時對于同一散列函數(shù)解決沖突的方法也可以不同。兩者是影響查詢算法性能的關鍵因素。對于幾種典型的散列函數(shù)構造方法，做實驗觀察，不同的解決沖突方法對查詢性能的影響。

8.圖書借閱管理系統(tǒng)

主要分為兩大功能：

1)圖書管理(增加圖書、查詢圖書、刪除圖書、圖書借閱、還書)； 2)會員管理(增加會員、查詢會員、刪除會員、借書信息)；

9.學生成績管理

實現(xiàn)功能：輸入、輸出、插入、刪除、查找、追加、讀入、顯示、保存、拷貝、排序、索引、分類合計、退出。

10.活期儲蓄帳目管理

活期儲蓄處理中，儲戶開戶、銷戶、存入、支出活動頻繁，系統(tǒng)設計要求： 1)能比較迅速地找到儲戶的帳戶，以實現(xiàn)存款、取款記賬； 2)能比較簡單，迅速地實現(xiàn)插入和刪除，以實現(xiàn)開戶和銷戶的需要。

11.二叉排序樹的實現(xiàn)

用順序和二叉鏈表作存儲結構

1)以回車('n')為輸入結束標志,輸入數(shù)列L，生成一棵二叉排 序樹T； 2)對二叉排序樹T作中序遍歷，輸出結果；

3)輸入元素x,查找二叉排序樹T,若存在含x的結點,則刪除該結點,并作中序遍歷(執(zhí)行操作2)；否則輸出信息“無x”；

12.最小生成樹問題 設計要求：在n個城市之間建設網絡，只需保證連通即可，求最經濟的架設方法。存儲結構采用多種。求解算法多種。

13.通訊錄的制作

設計目的：用〈〈數(shù)據結構〉〉中的雙向鏈表作數(shù)據結構，結合C語言基本知識。編寫一個通訊錄管理系統(tǒng)。以把所學數(shù)據結構知識應用到實際軟件開發(fā)中去。設計內容：本系統(tǒng)應完成一下幾方面的功能： 1)輸入信息——enter();2)顯示信息———display();

3)查找以姓名作為關鍵字 ———search();4)刪除信息———delete();5)存盤———save();6)裝入———load();設計要求：

1)每條信息至包含 ：姓名（NAME）街道（STREET）城市（CITY）郵編（EIP）國家（STATE）幾項 2)作為一個完整的系統(tǒng)，應具有友好的界面和較強的容錯能力 3)上機能正常運行，并寫出課程設計報告

14.哈夫曼編碼/譯碼器 【問題描述】

設計一個利用哈夫曼算法的編碼和譯碼系統(tǒng)，重復地顯示并處理以下項目，直到選擇退出為止。【基本要求】

1)將權值數(shù)據存放在數(shù)據文件(文件名為data.txt，位于執(zhí)行程序的當前目錄中)2)分別采用動態(tài)和靜態(tài)存儲結構

3)初始化：鍵盤輸入字符集大小n、n個字符和n個權值，建立哈夫曼樹； 4)編碼：利用建好的哈夫曼樹生成哈夫曼編碼； 5)輸出編碼；

6)設字符集及頻度如下表：

字符 空格 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 P Q R S T U V W X Y Z 頻度 57 63 15 1 48 51 80 23 8 18 1 16 1 【進一步完成內容】 1)譯碼功能； 2)顯示哈夫曼樹； 3)界面設計的優(yōu)化。

15.圖書管理系統(tǒng) 【問題描述】

設計一個計算機管理系統(tǒng)完成圖書管理基本業(yè)務。【基本要求】

1)每種書的登記內容包括書號、書名、著作者、現(xiàn)存量和庫存量； 2)對書號建立索引表（線性表）以提高查找效率； 3)系統(tǒng)主要功能如下：

*采編入庫：新購一種書，確定書號后，登記到圖書帳目表中，如果表中已有，則只將庫存量增加； *借閱：如果一種書的現(xiàn)存量大于0，則借出一本，登記借閱者的書證號和歸還期限，改變現(xiàn)存量； *歸還：注銷對借閱者的登記，改變該書的現(xiàn)存量。【進一步完成內容】 1)系統(tǒng)功能的進一步完善； 2)索引表采用樹表。3)設計內容 4)程序流程圖 5)源程序

6)軟件測試報告（包括所用到的數(shù)據及結果）

16.散列表的設計與實現(xiàn) 【問題描述】

設計散列表實現(xiàn)電話號碼查找系統(tǒng)。【基本要求】

1)設每個記錄有下列數(shù)據項：電話號碼、用戶名、地址；

2)從鍵盤輸入各記錄，分別以電話號碼和用戶名為關鍵字建立散列表； 3)采用一定的方法解決沖突； 4)查找并顯示給定電話號碼的記錄； 5)查找并顯示給定用戶名的記錄。【進一步完成內容】 1)系統(tǒng)功能的完善；

2)設計不同的散列函數(shù)，比較沖突率；

3)在散列函數(shù)確定的前提下，嘗試各種不同類型處理沖突的方法，考察平均查找長度的變化。

17.順序結構、動態(tài)鏈表結構下的一元多項式的加法、減法、乘法的實現(xiàn)。

設有一元多項式Am(x)和Bn(x).Am(x)=A0+A1x1+A2x2+A3x3+… +Amxm

Bn(x)=B0+B1x1+B2x2+B3x3+… +Bnxn

請實現(xiàn)求M(x)= Am(x)+Bn(x)、M(x)= Am(x)-Bn(x)和M(x)= Am(x)×Bn(x)。

要求：

1)首先判定多項式是否稀疏

2)分別采用順序和動態(tài)存儲結構實現(xiàn)； 3)結果M(x)中無重復階項和無零系數(shù)項； 4)要求輸出結果的升冪和降冪兩種排列情況

18.利用棧求表達式的值，可供小學生作業(yè)，并能給出分數(shù)。

要求：建立試題庫文件，隨機產生n個題目；題目涉及加減乘除，帶括弧的混合運算；隨時可以退出；保留歷史分數(shù)，能回顧歷史，給出與歷史分數(shù)比較后的評價

19.簡易文本編輯器 要求：

1)具有圖形菜單界面；

2)查找，替換（等長，不等長），插入（插串，文本塊的插入）、塊移動（行塊，列塊移動），刪除 3)可正確存盤、取盤； 4)正確顯示總行數(shù)。

20.二叉樹的中序、前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法的實現(xiàn)，應包含建樹的實現(xiàn)。

要求：遍歷的內容應是千姿百態(tài)的。

樹與二叉樹的轉換的實現(xiàn)。以及樹的前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法的實現(xiàn)，應包含建樹的實現(xiàn)。

要求：遍歷的內容應是千姿百態(tài)的。

21.學生搭配問題

一班有m個女生,有n個男生(m不等于n),現(xiàn)要開一個舞會.男女生分別編號坐在舞池的兩邊的椅子上.每曲開始時,依次從男生和女生中各出一人配對跳舞, 本曲沒成功配對者坐著等待下一曲找舞伴.請設計一系統(tǒng)模擬動態(tài)地顯示出上述過程,要求如下: 1)輸出每曲配對情況

2)計算出任何一個男生(編號為X)和任意女生(編號為Y),在第K曲配對跳舞的情況.至少求出K的兩個值.3)盡量設計出多種算法及程序,可視情況適當加分

提示:用隊列來解決比較方便.22.猴子吃桃子問題

有一群猴子摘了一堆桃子，他們每天都吃當前桃子的一半且再多吃一個，到了第10天就只余下一個桃子。用多種方法實現(xiàn)求出原來這群猴子共摘了多少個桃子。

要求：

1)采用數(shù)組數(shù)據結構實現(xiàn)上述求解 2)采用鏈數(shù)據結構實現(xiàn)上述求解 3)采用遞歸實現(xiàn)上述求解

23.數(shù)制轉換問題

任意給定一個M進制的數(shù)x，請實現(xiàn)如下要求 1)求出此數(shù)x的10進制值（用MD表示）2)實現(xiàn)對x向任意的一個非M進制的數(shù)的轉換。

3)至少用兩種或兩種以上的方法實現(xiàn)上述要求（用棧解決，用數(shù)組解決，其它方法解決）。

24.排序綜合

利用隨機函數(shù)產生N個隨機整數(shù)（20000以上），對這些數(shù)進行多種方法進行排序。要求：

1)至少采用三種方法實現(xiàn)上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結果保存在不同的文件中。

2)統(tǒng)計每一種排序方法的性能（以上機運行程序所花費的時間為準進行對比），找出其中兩種較快的方法。3)如果采用4種或4種以上的方法者，可適當加分。

25.學生成績管理系統(tǒng)

現(xiàn)有學生成績信息文件1（1.txt），內容如下 姓名 學號 語文 數(shù)學 英語

張明明 01 67 78 82 李成友 02 78 91 88 張輝燦 03 68 82 56 王露 04 56 45 77 陳東明 05 67 38 47 ….......…

學生成績信息文件2（2.txt）,內容如下: 姓名 學號 語文 數(shù)學 英語

陳果 31 57 68 82 李華明 32 88 90 68 張明東 33 48 42 56 李明國 34 50 45 87 陳道亮 35 47 58 77 ….......… 試編寫一管理系統(tǒng),要求如下:

1)實現(xiàn)對兩個文件數(shù)據進行合并,生成新文件3.txt

2)抽取出三科成績中有補考的學生并保存在一個新文件4.txt

3)合并后的文件3.txt中的數(shù)據按總分降序排序(至少采用兩種排序方法實現(xiàn))

4)輸入一個學生姓名后,能查找到此學生的信息并輸出結果(至少采用兩種查找方法實現(xiàn))5)要求使用結構體,鏈或數(shù)組等實現(xiàn)上述要求.6)采用多種方法且算法正確者,可適當加分.26.圖的遍歷的實現(xiàn) 要求：

1)先任意創(chuàng)建一個圖；

2)圖的DFS,BFS的遞歸和非遞歸算法的實現(xiàn) 3)要求用有向圖和無向圖分別實現(xiàn)

4)要求用鄰接矩陣、鄰接表多種結構存儲實現(xiàn)

27.線索二叉樹的應用 要求：實現(xiàn)線索樹建立、插入、刪除、恢復線索的實現(xiàn)。

28.稀疏矩陣應用

要求：實現(xiàn)三元組，十字鏈表下的稀疏矩陣的加、轉、乘的實現(xiàn)。（1）稀疏矩陣的存儲（2）稀疏矩陣加法（3）矩陣乘法（4）矩陣轉置

29.樹的應用

要求：實現(xiàn)樹與二叉樹的轉換的實現(xiàn)。以及樹的前序、后序的遞歸、非遞歸算法，層次序的非遞歸算法的實現(xiàn)，應包含建樹的實現(xiàn)。

30.文本文件單詞的檢索與計數(shù) 設計要求與分析：

要求編程建立一個文本文件，每個單詞不包含空格且不跨行，單詞由字符序列構成且區(qū)分大小寫；統(tǒng)計給定單詞在文本文件中出現(xiàn)的總次數(shù)；檢索輸出某個單詞出現(xiàn)在文本中的行號、在該行中出現(xiàn)的次數(shù)以及位置。該設計要求可分為三個部分實現(xiàn)：其一，建立文本文件，文件名由用戶用鍵盤輸入；其二，給定單詞的計數(shù)，輸入一個不含空格的單詞，統(tǒng)計輸出該單詞在文本中的出現(xiàn)次數(shù)；其三，檢索給定單詞，輸入一個單詞，檢索并輸出該單詞所在的行號、該行中出現(xiàn)的次數(shù)以及在該行中的相應位置。（1）.建立文本文件（2）給定單詞的計數(shù)

（3）檢索單詞出現(xiàn)在文本文件中的行號、次數(shù)及其位置（4）主控菜單程序的結構 ① 頭文件包含 ② 菜單選項包含

建立文件、單詞定位、單詞計數(shù)、退出程序 ③ 選擇1-4執(zhí)行相應的操作，其他字符為非法。

31.任意長的整數(shù)加法

問題描述：設計一個程序實現(xiàn)兩個任意長的整數(shù)的求和運算。

基本要求：利用雙向循環(huán)鏈表，設計一個實現(xiàn)任意長的整數(shù)進行加法運算的演示程序。要求輸入和輸出每四位一組，組間用逗號隔開。如：1，0000，0000，0000，0000。

32.二叉平衡排序樹

問題描述：從一棵空樹開始創(chuàng)建，在創(chuàng)建過程中，保證樹的有序性，同時還要針對樹的平衡性做些調整。最終要把創(chuàng)建好的二叉排序樹轉換為二叉平衡排序樹。基本要求：1.創(chuàng)建（插入、調整、改組）2.輸出

33.串的查找和替換

問題描述：打開一篇英文文章，在該文章中找出所有給定的單詞，然后對所有給定的單詞替換為另外一個單詞，再存盤。

34.約瑟夫環(huán)

問題描述：編號為1，2… n的n個人按順時針方向圍坐一圈，每人持有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)的上限值m，從第一個人開始按順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)，報m的人出列，將他的密碼作為新的m值，從他的順時針方向上的下一個開始重新從1報數(shù)，如此下去，直至所有人全部出列為止，設計一個程序求出出列順序。基本要求：

1、利用單循環(huán)鏈表作為存儲結構模擬此過程；

2、鍵盤輸入總人數(shù)、初始報數(shù)上限值m及各人密碼；

3、按照出列順序輸出各人的編號。

35.構造可以使n個城市連接的最小生成樹

問題描述：給定一個地區(qū)的n個城市間的距離網，用Prim算法或Kruskal算法建立最小生成樹，并計算得到的最小生成樹的代價。基本要求：

1、城市間的距離網采用鄰接矩陣表示，鄰接矩陣的存儲結構定義采用課本中給出的定義，若兩個城市之間不存在道路，則將相應邊的權值設為自己定義的無窮大值。要求在屏幕上顯示得到的最小生成樹中包括了哪些城市間的道路，并顯示得到的最小生成樹的代價。

2、表示城市間距離網的鄰接矩陣（要求至少6個城市，10條邊）

3、最小生成樹中包括的邊及其權值，并顯示得到的最小生成樹的代價。

36.客戶消費積分管理系統(tǒng)

問題描述：針對客戶的消費情況，進行客戶管理，根據客戶的消費積分對客戶實行不同程度的打折優(yōu)惠。基本要求：

1.采用一定的存儲結構進行客戶信息的存儲； 2.對客戶的信息可以進行修改、刪除、添加； 3.能夠根據消費情況進行客戶積分的計算； 4.根據積分情況實行不同程度的打折優(yōu)惠；

37.產品進銷存管理系統(tǒng)

問題描述：針對某一種行業(yè)的庫房的產品進銷存情況進行管理。基本要求：

1.采用一定的存儲結構對庫房的貨品及其數(shù)量進行分類管理； 2.可以進行產品類的添加、產品的添加、產品數(shù)量的添加；

3.能夠查詢庫房每種產品的總量、進貨日期、銷出數(shù)量、銷售時間等；

38.特殊矩陣的壓縮存儲算法的實現(xiàn)

問題描述：對于特殊矩陣可以通過壓縮存儲減少存儲空間。基本要求：

1.針對多種特殊矩陣進行壓縮存儲，并能顯示壓縮后的相關地址和值； 2.輸入在原來特殊矩陣中的地址，要求能從壓縮后的矩陣中讀出相應的值；

39.算術表達式的求解

問題描述：給定一個算術表達式，通過程序求出最后的結果。基本要求：

1． 從鍵盤輸入要求解的算術表達式； 2． 采用棧結構進行算術表達式的求解過程； 3． 能夠判斷算術表達式正確與否； 4． 對于錯誤表達式給出提示； 5． 對于正確的表達式給出最后的結果；

40.實時監(jiān)控報警系統(tǒng)

問題描述：建立一個報警和出警管理的系統(tǒng) 基本要求：

1.采用一定的存儲結構存儲報警信息，要求有內容、時間； 2.有一次的出警就應該在待處理的信息中刪除這條信息； 3.記錄出警信息；

4.待處理信息過多時會發(fā)出警告；

41.車廂調度

問題描述：假設停在鐵路調度站入口處的車廂序列的編號一次為1，2，3，4。設計一個程序，求出所有可能由此輸出的長度為4的車廂序列。

42.迷宮問題（棧）問題描述：

以一個m*n的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論。基本要求：

首先實現(xiàn)一個以鏈表作存儲結構的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i,j,d）的形式輸出，其中：（i,j）指示迷宮中的一個坐標，d表示走到下一坐標的方向，如：對于下列數(shù)據的迷宮，輸出的一條通路為：（1，1，1），（1,2,2）,(3,2,3),(3,1,2),…。測試數(shù)據：

迷宮的測試數(shù)據如下：左下角（1，1）為入口，右下角（8，9）為出口。實現(xiàn)提示：

計算機解迷宮通常用的是“窮舉求解”方法，即從入口出發(fā)，順著某個方向進行探索，若能走通，則繼續(xù)往前進；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設的迷宮沒有通路。

可以二維數(shù)組存儲迷宮數(shù)據，通常設定入口點的下標為（1，1），出口點的下標為（n,n）。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮中任一位置，均可約定有東、南、西、北四個方向可通。選做內容：

（1）編寫遞歸形式的算法，求得迷宮中所有可能的通路；（2）以方陣形式輸出迷宮及其通路。43.迷宮問題（隊列）（同上）44二叉搜索樹：各種搜索樹效率比較 題目要求：

本題目要求對普通的二叉排序樹、AVL樹分別實現(xiàn)制定操作，并分析比較這兩種不同數(shù)據結構對應的一系列插入和刪除操作的效率。要求測試對N個不同整數(shù)進行下列操作的效率：（1）按遞增順序插入N個整數(shù)，并按同樣順序刪除；（2）按遞增順序插入N個整數(shù)，并按相反順序刪除；（3）按隨機順序插入N個整數(shù)，并按隨機順序刪除；

要求N從1000到10000取值，并以數(shù)據規(guī)模N為橫軸，運行時間為縱軸，畫出3種不同數(shù)據結構對應的操作效率比較圖。

45.病毒測試程序 本題的任務是：

當整個網絡被感染后，計算有多少臺機器被某個特定變種所感染。輸入要求：

輸入由若干組測試數(shù)據組成。

每組數(shù)據的第1行包含2個整數(shù)M和N（1≤M,N≤500），接下來是一個M*N的矩陣表示網絡的初始感染狀態(tài)，其中的正、負整數(shù)的意義如題目描述中所定義。

下面一行給出一個正整數(shù)Q，是將要查詢的變種的個數(shù)。接下去的Q行里，每行給出一個變種的類型。當M或N為0時，表示全部測試結束，不要對該數(shù)據做任何處理。輸出要求：

對每一組測試，在一行里輸出被某個特定變種所感染的機器數(shù)量。

46關鍵路徑問題

問題描述：設計一個程序求出完成整項工程至少需要多少時間以及整項工程中的關鍵活動。基本要求：

（1）對一個描述工程的AOE網，應判斷其是否能夠順利進行。

（2）若該工程能順利進行，輸出完成整項工程至少需要多少時間，以及每一個關鍵活動所依附的兩個頂點、最早發(fā)生時間、最遲發(fā)生時間。

47.神秘國度的愛情故事

輸入要求：輸入由若干組測試數(shù)據組成。

每組數(shù)據的第1行包含一正整數(shù)N（1≤N≤50000），代表神秘國度中小村的個數(shù)，每個小村即從0到N-1編號。接下來有N-1行輸入，每行包含一條雙向道路的兩端小村的編號，中間用空格分開。之后一行包含一正整數(shù)M（1≤M≤500000），代表著該組測試問題的個數(shù)。接下來M行，每行給出A,B,C三個小村 的編號，中間用空格分開。

當N為0時，表示全部測試結束，不要對該數(shù)據做任何處理。

輸出要求：對每一組測試給定的A,B,C，在一行里輸出答案，即：如果C在A和B之間的路徑上，輸出Yes,否則輸出No。

48.并查集：檢查網絡

題目要求：給定一個計算機網絡以及機器間的雙向連線列表，每一條連線允許兩端的計算機進行直接的文件傳輸，其他計算機間若存在一條連通路徑，也可以進行間接的文件傳輸。請寫出程序判斷：任意指定兩臺計算機，它們之間是否可以進行文件傳輸？

輸入要求：輸入若干測試數(shù)據組成。對于每一組測試，第1行包含一個整數(shù)N（≤10000），即網絡中計算機的總臺數(shù)，因而每臺計算機可用1到N之間的一個正整數(shù)表示。接下來的幾行輸入格式為I C1 C2或者 C或者C C1C2或者S，其中C1和C2是兩臺計算機的序號，I表示在C1和C2間輸入一條連線，C表示檢查C1和C2間是否可以傳輸文件，S表示該組測試結束。當N為0時，表示全部測試結束，不要對該數(shù)據做任何處理。

輸出要求：對每一組C開頭的測試，檢查C1和C2間是否可以傳輸文件，若可以，則在一行中輸出“yes”，否則輸出“no”。

當讀到S時，檢查整個網絡。若網絡中任意兩機器間都可以傳輸文件，則在一行中輸出“The network is connected.”，否則輸出“There are k components.”,其中k是網絡中連通集的個數(shù)。兩組測試數(shù)據之間請輸出一空行分隔。

49.廣義表的應用

由于廣義表在結構上較線性表復雜得多，因此，廣義表的運算也不如線性表簡單。本設計要求實現(xiàn)的廣義表的建立、查找、輸出、取表頭和取表尾以及求深度、求逆表等。本設計用一個主控菜單程序控制，共分為6個子系統(tǒng)。（1）.建立廣義表（2）輸出廣義表（3）結點的查找（4）求廣義表表頭（5）求廣義表表尾（6）求廣義表的深度

50.網絡流：宇宙旅行 題目要求：

在走遍了地球上的所有景點以后，旅游狂人開始計劃他的宇宙旅行項目。經過謹慎調查，他目前掌握了一張各衛(wèi)星空間站可以臨時容納的旅客人數(shù)列表。但旅客從一個星球飛往另一個星球時，需要在若干衛(wèi)星空間站臨時停靠中轉，而這些空間站不能接待任何旅客駐留，旅客必須立刻轉乘另一艘飛船離開，所以空間站不能接待超過自己最大容量的旅客流。為了估計預算，現(xiàn)在旅游狂人需要知道終點星球的接待站應該設計多大容量，才能使得每艘飛船在到達時都可以保證讓全部旅客下船。輸入要求：

輸入若干組測試數(shù)據組成。

每組測試數(shù)據的第1行包含旅行的起點星球和終點星球的名稱和一個不超過500的正整數(shù)N（N為0標志全部測試結束，不要對該數(shù)據做任何處理）。

接下來的N行里，數(shù)據格式為：sourcei capacityi，其中sourcei和destinationi是衛(wèi)星空間站的名稱或起點、終點星球的名稱，正整數(shù)capacityi是飛船從sourcei到destinationi一次能運載的最大旅客流量。每個名稱是由A～Z之間三個大寫字母組成的字符串，例如：ZJU。

測試數(shù)據中不包含任何到達起點星球的信息以及任何從終點星球出發(fā)的信息。輸出要求：

對每一組測試，在一行里輸出終點星球接待站應具有的最小容量，使得每艘飛船在到達時都可以保證讓全部旅客下船。

51：算術運算測試

功能要求：該程序用圖形界面實現(xiàn)十道100以內加減法數(shù)學題，能根據題目計算出答案，與輸入答案對比，判斷做題是否正確，最后計算分數(shù)。

界面要求：用圖形界面實現(xiàn)。52：猜數(shù)游戲 功能要求：計算機產生隨機數(shù)，猜中即勝，猜不中，提示是大了還是小了，繼續(xù)猜，直至猜到，給出所用時間和評語。

界面要示：用圖形界面實現(xiàn)。

53、學生成績管理

功能要求：

1)輸入十個同學的學號，姓名，四科成績（應用數(shù)學、大學英語、Java程序設計、計算機應用基礎）

2)計算出平均成績。以平均成績降序輸出成績表。3)輸出全組各科平均分，最高分和最低分。4)輸入姓名查詢成績

界面要示：用圖形界面實現(xiàn)。54．矩陣的運算

采用鏈表表示稀疏矩陣，并實現(xiàn)矩陣的加法，乘法，求逆運算, 要求：要檢查有關運算的條件，并對錯誤的條件產生報警。

55．建立二叉樹和線索二叉樹

分別用以下方法建立二叉樹并用圖型顯示出來：

用先序遍歷的輸入序列

用層次遍歷的輸入序列

用先序和中序遍歷的結果

最后對所建立的二叉樹進行中序線索化，并對此線索樹進行中序遍歷(不使用棧)。

56．銀行業(yè)務模擬：

客戶業(yè)務分為兩種。第一種是申請從銀行得到一筆資金，即取款或借款。第二種是向銀行投入一筆資金，即存款或還款。

銀行有兩個服務窗口，相應的有兩個隊列。客戶到達銀行后先排第一個隊。處理每個客戶業(yè)務時，如果屬于第一種，且申請額超出銀行現(xiàn)存資金總額而得不到滿足，則立即排入第二隊等候，直至滿足時才離開銀行，否則業(yè)務處理完后立即離開銀行。每接待完一個第二種業(yè)務的客戶，則順序檢查和處理（如果可能）第二個隊列的客戶，對能滿足的申請者予以滿足，不能滿足者重新排到第二個隊列的隊尾。注意，在此檢查過程中，一旦銀行資金總額少于或等于剛才第一個隊列中最后一個客戶（第二種業(yè)務）被接待之前的數(shù)額，或者本次已將第二個隊列檢查或處理了一遍，就停止檢查（因為此時已不可能還有能滿足者）轉而繼續(xù)接待第一個隊列的客戶。任何時刻都只開一個窗口。假設檢查不需要時間。營業(yè)時間結束時所有客戶立即離開銀行。寫一個上述銀行業(yè)務的事件驅動模擬系統(tǒng)，通過模擬方法求出客戶在銀行內逗留的平均時間。

57.假設一個賓館有n個標準的客房，每個標準客房有m個標準間，利用鏈表、棧或者隊列等數(shù)據結構設計出具有訂房和退房等功能的管理系統(tǒng)。