在日常學習、工作或生活中，大家總少不了接觸作文或者范文吧，通過文章可以把我們那些零零散散的思想，聚集在一塊。范文怎么寫才能發(fā)揮它最大的作用呢？以下是我為大家搜集的優(yōu)質范文，僅供參考，一起來看看吧
數(shù)據(jù)結構與算法課程設計題目答案篇一
一、基本信息
課程編號：e1132107 課程類別：學科基礎課必修課 適用層次：本科
適用專業(yè)：計算機科學與技術、網(wǎng)絡工程、軟件工程等 開課學期：3 學 分：2學分 學 時：2周 考核方式：考查
二、教學目的
數(shù)據(jù)結構與算法課程設計不僅是數(shù)據(jù)結構與算法課程的實踐教學環(huán)節(jié)，而且是一門綜合性實驗項目。通過這個實驗，培養(yǎng)學生綜合運用數(shù)據(jù)結構基本知識和程序設計基本知識，解決實際問題，提高程序設計的能力和團隊協(xié)作精神。
本課程設計的目的就是要達到理論與實際應用相結合，使同學們能夠根據(jù)數(shù)據(jù)對象的特性，學會數(shù)據(jù)組織的方法，能把現(xiàn)實世界中的實際問題在計算機內部表示出來，并培養(yǎng)基本的、良好的程序設計技能。
1．學生通過實踐掌握線性表、樹、圖等數(shù)據(jù)結構的存儲結構及算法實現(xiàn)； 2．培養(yǎng)學生利用數(shù)據(jù)結構知識解決實際問題的能力;3．使學生初步具備查閱資料、分析設計、上機實現(xiàn)和書寫科技 報告的能力。
三、基本要求
1.指導教師要在選題、設計、上機實現(xiàn)等諸環(huán)節(jié)上投入精力，加強指導、討論和答疑的力度。尤其在選題上，要充分考慮學生目前所具有的知識水平、掌握的開發(fā)工具、以及綜合設計能力的現(xiàn)狀，使題目取材合理、大小適中、難易適度，使學生在完成設計工作后，能有所收獲。2.參加課程設計的學生要珍惜機會、勤奮工作、勇于創(chuàng)新、勇于探索、勇于實踐，虛心向指導教師請教，向同學學習，獨立完成設計任務。
3.學生需保質、保量、保時間進度地提交規(guī)范的課程設計報告，審查由指導教師負責。
四、教學內容
1.主要內容：應用所掌握的線性表、樹、圖等數(shù)據(jù)結構知識解決實際問題。2.軟件開發(fā)工具：c/c++、java。
3.課程設計題目：指導教師擬定（參考題目見附錄1）
4.具體步驟：指導教師擬定設計題目，學生研究具體問題、進行需求分析、選擇合適的數(shù)據(jù)結構、設計算法、編寫并調試代碼、書寫文檔材料、提交設計報告，最后，由指導教師驗收并評定成績。
5.設計內容及時間安排：第1-3天，選定題目，明確題目要求、確定數(shù)據(jù)結構、設計算法，并分析算法復雜度；第4-8天，編寫程序、調試程序、測試程序；第9-10天，撰寫設計報告，準備答辯（上機演示，回答教師提問）。6.設計報告書寫要求：按照軟件開發(fā)規(guī)范的要求書寫設計報告（參見附錄三報告書寫格式）；要求報告層次結構清晰、圖表完整、語言通順、字跡工整。7.驗收要求：1）運行所設計的程序；2）回答有關問題；3）提交課程設計報告（打印或手寫在實習報告冊上）；4）提交軟盤（源程序）。（鼓勵學生創(chuàng)新。對內容有創(chuàng)新者，成績評定將適當提高）。
五、考核方法
學習成績的評定方式：考查。
課程設計成績評定 =平時出勤（20%）+設計報告（40%）+答辯（40%）通過設計答辯方式，并結合學生的動手能力，獨立分析解決問題的能力和創(chuàng)新精神，總結報告和答辯水平以及學習態(tài)度綜合考評。成績分為優(yōu)、良、中、及格和不及格五等。
六、教材與參考資料 1.建議教材：
[1] 數(shù)據(jù)結構(c++)版，王紅梅、胡明、王濤編著，清華大學出版社，2005.7 [2] 自編教材
2.建議參考書目：
[1] 許卓群，楊冬青，唐世渭，張銘.數(shù)據(jù)結構與算法.高等教育出版社，2004.7 [2] 嚴蔚敏, 陳文博.數(shù)據(jù)結構及應用算法教程.清華大學出版社, 2001.2 [3] 朱晉蜀.數(shù)據(jù)結構(第一版).成都: 電子科技大學出版社, 2000.1 [4] clifford r著.張銘，劉曉丹譯.數(shù)據(jù)結構與算法分析.電子工業(yè)出版社，1998.8 [5] 殷人昆等.數(shù)據(jù)結構（用面向對象方法與c++描述）.清華大學出版社，1999.7 [6] ford w., topp structures with c++.清華大學出版社（影印版），1997.3
附錄一
參考題目（可分若干組，每個學生選擇其中一個題目）
1．商廈家電庫存管理 2.排序算法的時間比較
3．使用哈希表技術判斷兩個源程序的相似性 4．以隊列實現(xiàn)的仿真技術預測理發(fā)館的經(jīng)營狀況 5.某公園導游圖
6．用樹型結構的搜索算法模擬因特網(wǎng)域名的查詢 7．管道鋪設施工的最佳方案選擇 8．表達式分析與求值程序 9．安排教學計劃
10.設計huffman 編碼器與解碼器 11．在國際象棋盤上馬遍歷問題 12．八皇后問題 13．民航售票系統(tǒng) 14．模擬旅館管理系統(tǒng)中的床位分配和加收 15．銀行業(yè)務活動的模擬
16．文字統(tǒng)計系統(tǒng)—文字研究助手 17．修道士野人問題 18．考試問題
19．計算機輔助考核系統(tǒng) 20．學籍管理系統(tǒng)
注：學生可以自選題目或選擇指導老師擬定的題目。
附錄二
開發(fā)步驟
1.分析題目的要求、目的； 2.選擇適當?shù)臄?shù)據(jù)結構；
3.抽象數(shù)據(jù)類型的設計； 4.抽象數(shù)據(jù)類型的實現(xiàn)； 5.編寫代碼、上機調試； 6.總結驗收、評價。
附錄三 報告書寫格式
1．問題描述
題目內容、基本要求 2．需求分析
軟件的基本功能、輸入/輸出形式、測試數(shù)據(jù)要求 3．概要設計
所需的adt及作用、主程序流程及模塊調用關系 4．詳細設計
實現(xiàn)概要設計的數(shù)據(jù)類型、每個操作的偽碼算法、主程序和其它模塊的偽碼算法、函數(shù)調用關系圖 5．編碼與調試分析
編碼與調試過程中遇到的問題及解決的辦法，還存在哪些沒有解決的問題？ 6．使用說明
簡要說明程序運行操作步驟 7．測試結果
8．課程設計心得體會
數(shù)據(jù)結構與算法課程設計題目答案篇二
數(shù)據(jù)結構與算法課程設計題目
1．成績管理
問題描述：給出n個學生的考試成績表，成績表包括學生的學號、姓名、考試成績（高等數(shù)
學、英語、物理），設計一個簡單的成績管理程序。
基本要求：
（1）建立成績表，能夠插入、刪除、修改學生的成績記錄；（2）按任一單科成績排序；(3)計算每名學生的平均成績；
(4)統(tǒng)計任一單科成績不及格的學生人數(shù), 輸出不及格人數(shù)及不及格的學生名單(5)根據(jù)平均成績將成績表按由高到低的次序排列，統(tǒng)計每名學生在考試中獲得的名次，分數(shù)相同的為同一名次，按名次輸出成績表。
(6)成績表保存在文件中, 可以從文件讀取數(shù)據(jù)。
測試數(shù)據(jù)：學生可以根據(jù)自己班級的考試成績單，任意截取一部分做為測試數(shù)據(jù) 2．一元多項式簡單計算
問題描述：設計一個簡單一元多項式計算器?；疽螅?1)輸入并建立多項式；(2)輸出多項式；
(3)兩個多項式相加，輸出結果多項式；(4)兩個多項式相減，輸出結果多項式。
提高要求：可以根據(jù)輸入變量的值，計算出多項式的結果，且算法的效率高。測試數(shù)據(jù)：可任意選取兩個一元多項式，可以是一般的多項式，也可以是稀疏多項式。3．舞伴問題
問題描述：一班有m個女生、n個男生(m不等于n), 舉辦一場舞會.男女生分別編號坐在舞池兩邊的椅子上，每曲開始時, 依次從男生和女生中各出一人配對跳舞, 本曲沒成功配對者坐著等待下一曲找舞伴，設計一個程序模擬舞伴配對過程。
基本要求：輸入男、女學生的姓名、性別，由程序自動為男女生編號，可以順序編號，也可以隨機編號，輸出每曲配對情況（包括男、女生的姓名、性別和編號）。原始數(shù)據(jù)和結果數(shù)據(jù)要保存到文件中。
測試數(shù)據(jù)：分別選擇男生多于女生、女生多于男生、男女生相等的三組測試數(shù)據(jù) 提高要求：計算出任意一位男生(編號為x)和任意一位女生(編號為y), 在第k曲配對跳舞的情況。
4．文學研究助手（*）
問題描述：文學研究人員需要統(tǒng)計某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。試寫一個實現(xiàn)這一目標的文字統(tǒng)計系統(tǒng)，稱為“文學研究助手”?；疽螅河⑽男≌f存于一個文本文件中，待統(tǒng)計的詞匯集合要一次輸入完畢，即統(tǒng)計工作必須在程序的一次運行之后就全部完成。程序的輸出結果是每個詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號，格式自行設計, 結果保存到文件中。
提高要求：模式匹配選取kmp算法
測試數(shù)據(jù)：以你的c/c++/java源程序模擬英文小說，相應語言的保留字集作為待統(tǒng)計的詞匯集。
5．哈希表的設計與實現(xiàn)（*）
問題描述：針對某個單位電話號碼簿，設計一個哈希表，并完成相應的建表和查表程序?；疽螅涸O每個記錄有下列數(shù)據(jù)項：電話號碼、用戶名、住址。從鍵盤輸入各記錄，以用戶名為關鍵字建立哈希表，哈希函數(shù)用除留取余數(shù)法構造，采用線性探測法解決沖突。可以插入、查找、刪除并顯示給定用戶名的記錄，并計算查找長度, 哈希表保存到文件中。
測試數(shù)據(jù)：取某個單位電話號碼簿中的30個記錄。
提高要求：將電話號碼薄以文件形式保存到盤上，能夠按用戶名和電話號碼兩種形式建立哈希表并實現(xiàn)插入、查找、刪除表中元素的功能。
6．管道鋪設施工的最佳方案（*）
問題描述:需要在某個城市的n個小區(qū)鋪設管道，則在這n個小區(qū)之間鋪設n-1條管道即可，假設任意兩個居民區(qū)之間都可以架設管道，但由于地理環(huán)境的不同，所需經(jīng)費不同，選擇最優(yōu)的施工方案使總投資盡可能的少。
基本要求：輸入表示小區(qū)間關系的圖及每條管道的權值，選擇出n-1條管道, 使總投資最小。圖的信息輸入一次后, 保存到文件中, 選擇的n-1條管道輸出到顯示器的同時, 也保存于文件中。
測試用例：任意選擇一個圖，模擬小區(qū)間可能鋪設的管道及費用。提高要求：顯示原始圖及選擇n-1條管道后的圖。
7．安排教學計劃（**）
問題描述：大學的每個專業(yè)都要制定教學計劃。假設任何專業(yè)都有固定的學習年限，每學年含兩個學期，每學期的時間長度和學分上限值均相等。每個專業(yè)開設的課程都是確定的，而且課程在開設時間的安排上必須滿足先修關系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課程恰好占一個學期。試在這樣的前提下設計一個教學計劃編制程序。
基本要求：輸入?yún)?shù)包括學期總數(shù)，一學期的學分上限，每門課程的課程號、學分和直接先修課的課程號；允許兩種策略，一是使學生在各學期的學習負擔盡量均勻，二是使課程盡量集中在前幾個學期；若根據(jù)給定的條件問題無解，則報告適當?shù)男畔ⅲ駝t將教學計劃輸出到用戶指定的文件中。教學計劃的表格格式自行設定, 可以從鍵盤讀取數(shù)據(jù)也可以從文件讀取數(shù)據(jù), 結果保存到文件中。
測試數(shù)據(jù)：學期總數(shù)為6，學分上限為10，該專業(yè)共開設12門。以08級某專業(yè)必修課與選修課為例，選擇12門課程及相應學分，制定一個表明各門課程先后約束關系的有向圖。
提高要求：產(chǎn)生多種不同的方案，并使方案之間的差異盡可能地大。8．停車場管理程序(**)問題描述：設停車場內只有一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車在停車場內按車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先到達的第一輛車停放在車場的最北端），若車場內已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場內某輛車要離開時，在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序進入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述要求進行管理的模擬程序。
基本要求：每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車牌照號碼及到達或離去的時刻，對每一組輸入數(shù)據(jù)進行操作后的輸出數(shù)據(jù)為：若是車輛到達，則輸出汽車在停車場內或便道上的停車位置；若是車離去；則輸出汽車在停車場內停留的時間和應交納的費用（在便道上停留的時間不收費，單位時間的停車費用由用戶從鍵盤輸入）。
測試數(shù)據(jù)：設輸入數(shù)據(jù)為：（‘a(chǎn)’，1，5），（‘a(chǎn)’，2，10），（‘d’，1，15），（‘a(chǎn)’，3，20），（‘a(chǎn)’，4，25），（‘a(chǎn)’，5，30），（‘d’，2，35），（‘d’，4，40），（‘e’，0，0）。其中，‘a(chǎn)’表示到達；‘d’表示離去，‘e’表示輸入結束。
提高要求：設停車場有南、北兩個門，每個門都可以進、出車輛。9．計算表達式的值(**)問題描述：對于給定的一個表達式，表達式中可以包括常數(shù)、算術運行符（“+”、“-”、“*”、“/”）和括號，編寫程序計算表達式的值。
基本要求：從鍵盤輸入一個正確的中綴表達式，將中綴表達式轉換為對應的后綴表達式，計算后綴表達式的值。
測試數(shù)據(jù)：任意選取一個符合題目要求的表達式。提高要求：（1）對于表達式中的簡單錯誤，能夠給出提示；
（2）表達式中可以包括單個字母表示的變量。
10．設計huffman 編碼器與解碼器（***）
問題描述：利用哈夫曼編碼進行信息通訊可以大大提高信道的利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳輸數(shù)據(jù)預先編碼；在接受端將傳來的數(shù)據(jù)進行譯碼。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站編寫一個哈夫曼碼的編/譯碼系統(tǒng)。
基本要求：根據(jù)某字符文件統(tǒng)計字符出現(xiàn)頻度，構造huffman 樹，編制huffman編碼，并將給定字符文件編碼，生成編碼文件；再將給定編碼文件解碼，生成字符文件。（要求按二進制位表示編碼）測試數(shù)據(jù)：英文文件。
提高要求：用二進制表示編碼，生成二進制的編碼文件。11．銀行業(yè)務模擬（***）
問題描述：設銀行有四個服務窗口，一個等待隊列, 每個窗口均可以辦理存款、取款、掛失、還貸業(yè)務，每種業(yè)務所需的服務時間不同，客戶到達銀行后，先到打號機上打號，號票上包括到達時間、編號和需要辦理的業(yè)務，然后在銀行內等候, 當任一服務窗口空閑時,處理等候客戶中排在最前面的客戶的業(yè)務。寫一個上述銀行業(yè)務的模擬系統(tǒng),通過模擬方法求出客戶在銀行內逗留的平均時間和每個窗口辦理的客戶數(shù)及辦理的每種業(yè)務數(shù)。
基本要求：每個客戶到達銀行的時間和需要辦理的業(yè)務隨機產(chǎn)生，輸出一天客戶在銀行的平均逗留時間和每個窗口每天辦理的客戶數(shù)和每種業(yè)務數(shù)。
測試數(shù)據(jù)：營業(yè)時間為8小時，其他模擬量自行設定。12．程序源代碼的相似性（***）
問題描述：對于兩個c++語言的源程序代碼，用哈希表的方法分別統(tǒng)計兩個程序中使用c++語言關鍵字的情況，并最終按定量的計算結果，得出兩份程序的相似性。
基本要求：建立c++語言關鍵字的哈希表，統(tǒng)計在每個源程序中c++關鍵字出現(xiàn)的頻度, 得到兩個向量x1和x2，通過計算向量x1和x2的相對距離來判斷兩個源程序的相似性。
例如: 關鍵字 void int for char if else while do break class 程序1關鍵字頻度 4 3 0 4 3 0 7 0 0 2 程序2關鍵字頻度 4 2 0 5 4 0 5 2 0 1 x1=[4,3,0,4,3,0,7,0,0,2] x2=[4,2,0,5,4,0,5,2,0,1] 設s是向量x1和x2的相對距離，s=sqrt(∑(xi1-xi2)2)，當x1=x2時，s=0, 反映出可能是同一個程序；s值越大，則兩個程序的差別可能也越大。
測試數(shù)據(jù): 選擇若干組編譯和運行都無誤的c++程序，程序之間有相近的和差別大的，用上述方法求s, 對比兩個程序的相似性。
提高要求：建立源代碼用戶標識符表，比較兩個源代碼用戶標識符出現(xiàn)的頻度，綜合關鍵字頻度和用戶標識符頻度判斷兩個程序的相似性。
13．小型文本編輯器
問題描述：設計一個行編輯程序，使其具有通常行編輯器(如vi、edlin)應具備的基本功能。
基本要求：編輯器應具備對文本文件的查找、插人、刪除、修改、字符串替換、統(tǒng)計字數(shù)，統(tǒng)計行數(shù)等功能，對于超過一屏的長文件，應能夠分頁顯示，查找功能用字符串匹配算法實現(xiàn)。設計用戶接口命令，實現(xiàn)對文本的編輯。具體的編輯命令，可參考數(shù)據(jù)結構算法網(wǎng)絡教學平臺上提供的edlin、vi的命令集。
測試數(shù)據(jù)：任一文本文件。
提高要求：１.可以支持“* ”、“? ”等通配符；
２.支持復制、粘貼等功能
3.支持多文檔同時編輯；
提示：可以考慮用雙向鏈表實現(xiàn)，每一結點表示一行字符，注意每行字符不能超過255。14．小型英漢詞典
問題描述：設計一個英漢詞典，支持member(查找)、insert(插入)、delete(刪除)操作。
基本要求：實現(xiàn)字典的常用方法有：有序線性表（memeber用二分檢索實現(xiàn)）、avl樹（二叉搜索樹）、patricia trie、散列表等，任選一種方法實現(xiàn)字典的操作，查找單詞、插入單詞（插入時，先查找，找不到插入，找到提示用戶）、刪除單詞（刪除時，先查找，找到刪除，找不到提示用戶）。
測試數(shù)據(jù)：任一英文單詞。提高要求：選用兩種以上的方法實現(xiàn)字典的操作，并比較不同實現(xiàn)算法的時間復雜度和空間復雜度。
提示：字典可以自己建立，但必須按字母a~z建立26個文件，建議從網(wǎng)上下載，文件類型為txt。
備注：
1.每道題目后面的*號，表示題目的難度系數(shù)；對應的評定成績等級為及格（無*號）、中等（*號）、良好（**號）、優(yōu)秀（***號），學生完成題目的基本要求，即可得到程序設計部分的相應等級成績，完成題目提高要求，成績可以向上浮動，如果沒有完成基本要求，成績向下浮動，直至不及格。
2.所有題目均需用c++完成，不能用c或mfc。3.實驗班的學生原則上應選擇“*”號多的題目。4.每道題的選題人數(shù)不能超過3人
數(shù)據(jù)結構與算法課程設計題目答案篇三
2014/2015學年第一學期
《數(shù)據(jù)結構與算法課程設計》任務書
一、課程設計目的
數(shù)據(jù)結構與算法課程設計是《數(shù)據(jù)結構與算法》課程教學必不可缺的一個重要環(huán)節(jié)，它可加深學生對該課程所學內容的進一步的理解與鞏固，是將計算機課程與實際問題相聯(lián)接的關鍵步驟。通過課程設計，能夠提高學生分析問題、解決問題，從而運用所學知識解決實際問題的能力，因而必須給予足夠的重視。
2二、課程設計題目
2.1 棋盤覆蓋
【間題描述】
在一個2k×2k 個方格組成的棋盤中，恰有一個方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態(tài)的l型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個l型骨牌不得重疊覆蓋。
【基本要求】
（1）輸入k以及特殊方格所在的行號dr和特殊方格的列號dc。
1（2）要求輸出每一步用什么形態(tài)l型骨牌覆蓋，覆蓋后得到的棋盤圖形。（3）如果輸出的結果只是用矩陣表示則為良好，用圖形表示則為優(yōu)。【測試數(shù)據(jù)】 【實現(xiàn)提示】
使用分治策略，把棋盤劃分成4個小棋盤，然后用一個l型骨牌覆蓋將這4個小棋盤變?yōu)槎季哂刑厥夥礁竦钠灞P。
2.2 hanoi塔問題（*）
【問題描述】
設a，b，c是三個塔座。開始時，在塔座a上有一疊共n個圓盤，這些圓盤自下而上，由大到小地疊放在一起，各圓盤從小到大編號為1,2,?,n，要求將塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動圓盤時應遵守以下移動規(guī)則：
規(guī)則（1）每次只能移動一個圓盤；
規(guī)則（2）任何時刻都部允許將較大的圓盤壓在較小的圓盤之上；
規(guī)則（3）在滿足移動規(guī)則（1）和（2）的前提下，可將圓盤移至a，b，c中任一塔座上。
【基本要求】
（1）設計出hannoi塔游戲，供用戶玩；（2）提供正確的搬運方法?！緦崿F(xiàn)說明】
正確的搬運方法使用遞歸方法實現(xiàn)?！緶y試數(shù)據(jù)】
2.3 矩陣連乘問題
【問題描述】
給定n個矩陣{a1,a2,...,an},其中ai和ai?1是可乘的，i＝1,2,?,n-1?？疾爝@n個矩陣的連乘積a1a2,...,an，通過加括號方式，找出矩陣乘積所需的最少計算量的方法。
【基本要求】
輸入每個矩陣的行和列，要求輸出最少計算量的矩陣乘積方法，如(a1(a2(a3a4)))?！緦崿F(xiàn)說明】 使用動態(tài)規(guī)劃方法。
2.4 多邊形游戲（*）
【問題描述】
多邊形游戲是一個單人玩的游戲，開始時有一個由n個頂點構成的多邊形。每個頂點被賦予一個整數(shù)值，每條邊被賦予一個運算符“＋”或“*”。所有邊依次用整數(shù)從1到n編號。
游戲第1步，將一條邊刪除。隨后n-1步按以下方式操作：
選擇一條邊e及由e連接著的2個頂點v1和v2；
用一個新的頂點取代邊e及用e連接著的2個頂點v1和v2，將由頂點v1和v2的整數(shù)值通過邊e上的運算得到的結果賦予新頂點。
最后，所有邊都被刪除，游戲結束。游戲的得分就是所剩頂點上的整數(shù)值?！净疽蟆?BR> 設計該游戲供用戶玩；
對于給定的多邊形，給出最高得分計算。【實現(xiàn)說明】 使用動態(tài)規(guī)劃方法。
2.5 0-1背包問題
【問題描述】
給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為c。問應如何選擇裝入背包種的物品，使得裝入背包種物品的總價值最大。
【基本要求】
使用動態(tài)規(guī)劃、回溯法以及分支界限三種方法實現(xiàn)?！緶y試數(shù)據(jù)】 【實現(xiàn)提示】
2.6 排序方法
【問題描述】
給定n個元素，要求對這n個元素進行排序?！净疽蟆?BR> 使用多種排序方法，越多越好；
比較每種排序方法的時間復雜度和空間復雜度?！緶y試數(shù)據(jù)】 【實現(xiàn)提示】
2.7 哈夫曼編碼譯碼器
【問題描述】
設計一個哈夫曼編碼/譯碼系統(tǒng)，對一個文本文件中的字符進行哈夫曼編碼，生成編碼文件
（壓縮文件，）；反過來，可將一個壓縮文件譯碼還原為一個文本文件(.txt)。
【基本要求】
（1）輸入一個待壓縮的英文文本文件，統(tǒng)計文本文件中各字符的個數(shù)作為權值，生成哈夫曼樹；
（2）將文本文件利用哈夫曼樹進行編碼，生成壓縮文件（后綴名cod）（3）輸入一個待解壓的壓縮文件名稱,并利用相應的哈夫曼樹將編碼序列譯碼?！緦崿F(xiàn)說明】
（1）在構造哈夫曼樹時，可以利用不同的線性表存放二叉樹：用順序表、單鏈表、5 循環(huán)單鏈表、雙向鏈表、循環(huán)雙鏈表；
（2）在構造哈夫曼樹時，可以利用優(yōu)先隊列存放二叉樹：順序隊列、鏈隊列（可以是單鏈表、雙鏈表等，還可以用靜態(tài)結構去實現(xiàn)），可以分別在入隊列或出隊列時實現(xiàn)優(yōu)先級；
（3）二叉樹本身也可以用靜態(tài)數(shù)組模擬；（4）使用貪心算法
2.8 迷宮問題（*）
【問題描述】
設計一個迷宮并給出正確走法。如： *** *** *** *** *** *** *** 其中0表示可以走，1表示不能走，每一步只能向上下左右移動。【基本要求】
（1）給出迷宮的正確走法，包括沒有解的情況；（2）要求界面友好?！緶y試數(shù)據(jù)】
【實現(xiàn)提示】 使用回溯的方法。
2.9 繼續(xù)郵資問題
【問題描述】
假設某國家發(fā)行了n種不同面值的郵票，并且規(guī)定每張信封上最多只允許貼m張郵票。連續(xù)郵資問題要求對于給定的n和m的值，給出郵票面值的最佳設計，在1張信封上貼出從郵資1開始，增量為1的最大連續(xù)郵資區(qū)間。
【基本要求】
輸入任意的m和n都能設計出最佳的方案，并給出連續(xù)郵資區(qū)間?！緦崿F(xiàn)說明】 【測試數(shù)據(jù)】
2.10 圖的m著色問題
【問題描述】
給定一個地圖，要求給出該地圖的最少著色方案 【基本要求】
（1）把地圖以及最少著色的方案顯示出來則為良好。（2）有友好的界面則為優(yōu) 【實現(xiàn)說明】
2.11 猜數(shù)字游戲（*）
【問題描述】
孩子想1個由4種顏色組成的序列（4種顏色不一定完全不同）。每種顏色只能是6種顏色之一。方便起見，我們用數(shù)字1到6表示6種顏色。
計算機必須根據(jù)孩子的回答找出孩子所想的顏色序列。計算機在屏幕上顯示一個序列，孩子用鍵盤回答以下兩個問題：
猜對的顏色中位置不對的有幾個？ 猜對的顏色中位置對的有幾個？ 【基本要求】
編程使至多6次問答后猜出序列，如果辦不到，至多10次問答后猜出序列?！緦崿F(xiàn)說明】 【測試數(shù)據(jù)】
如孩子想的是4655 計算機猜想 顏色對位置錯的數(shù)目 顏色和位置都對的數(shù)目 1234 1 0 5156 2 1 6165 1 1 5625 1 2 5653 1 2 8 4655 0 4 2.12 大整數(shù)計算器
【問題描述】
設計一個計算器實現(xiàn)兩個任意長得整數(shù)的加、減、乘、除?！净疽蟆?BR> 設計一個實現(xiàn)任意長的整數(shù)進行四則運算的演示程序，要求輸入任意長的整數(shù)進行四則運算，都能得到精確的結果。
【實現(xiàn)說明】
2.13 查找搜索技術
【問題描述】
給定任意的數(shù)組，對于給定的數(shù)，查找是否在數(shù)組中，如果在，則返回給定數(shù)在數(shù)組的位置，不在則返回不在信息。
【基本要求】
（1）使用多種搜索方法，越多越好，其中二分搜索技術、線性時間選擇是必須的；（2）比較每種排序方法的時間復雜度和空間復雜度?！緦崿F(xiàn)說明】
2.14 tom,jerry和奶酪（*）
【問題描述】
貓tom和鼠jerry同住在一矩陣地窖中。貓要吃鼠，鼠要吃奶酪。地窖中有2種地磚：有洞磚與無洞磚。一個洞足以讓鼠鉆入，但貓不能。
以菜單形式完成以下任務：
隨機地生成一個地窖，并給貓、鼠和奶酪安排一個位置。如： fffffffffffffff fppppppppppppcf fhfffffffffffpf fpppjhppppppppf fpffffffpffffff fpppppppppptppf fffffffffffffff 其中c表示貓，j表示鼠，h表示洞，f表示不能通行（2）鼠先行，貓后行。兩者皆滿足以下規(guī)定： 1）必須上、下、左或右移動 2）鼠必須走1步（穿過p或h）3）貓必須走1或2步（穿過p）
（3）當鼠吃到奶酪或貓抓到鼠時，游戲結束。【基本要求】 【實現(xiàn)說明】
2.15 布線問題
【問題描述】
印刷電路板將布線區(qū)域劃分成n×m個方格陣列，精確的電路布線問題要求確定連接方格a的中點到方格b的中點的最短布線方案。在布線時，電路只能沿著直線或直角布線。為了避免線路相交，已布了線的方格做了封鎖標記，其他線路不允許穿過被封鎖的方格。
【基本要求】（1）解決題目的問題（2）提供友好的界面 【實現(xiàn)說明】 使用分支限界法。
2.16 魔方工具包（*）
【問題描述】
一個魔方是一個由3×3×3個小立方體組成的立方體。最初立方體的6個面分別涂上不同顏色，我們稱之為“最初魔方”。魔方的每一面上的3×3個小立方體組成它的一層。
魔方所能見到的每一層（6個面）都能旋轉90，180，220或360度。所有層的旋轉軸都垂直于面且通過其中心。旋轉的結果是另一個魔方，它的所有面的顏色都改變了。
現(xiàn)在我們用字符來代替顏色：u=上，d=下，f=前，b=后，l=左，r=右。任何一個序列的旋轉都能表示成{u,r,f,b,l,d}中一些字符組成的字符串，其中每個字符表示它所 11 指定的面順時針旋轉90度。
【基本要求】
（1）編程完成以下3個任務（菜單形式），你可以假設任何輸入的字串長度都<=35。你的算法能處理非法輸入的情況，如： 輸入 輸出 l l ll ll lll lll llll “”(空串 lllll l llrrrffffrlb lllb hello “error”
（2）判斷輸入的2個字串的旋轉結果是否相同。如 輸入一 輸入二 輸出 ru ur no rrffrrffrrffrrff ffrrffrr yes rrffrrffrrffrrff rrffrrff no（3）求出輸入字符串至少須使用幾次才能將魔方轉回到“最初魔方”（一定大于0）輸入 輸出 l 4 12 dd 2 bulb 36 ruf 80 bluff 180 【實現(xiàn)說明】
2.17 圖的建立與輸出
【問題描述】
建立圖的存儲結構（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學生可以任選兩種類型），能夠輸入圖的頂點和邊的信息，并存儲到相應存儲結構中，而后輸出圖的鄰接矩陣。
【基本要求】
給出圖的深度優(yōu)先和廣度優(yōu)先遍歷算法，并給出遍歷過程的動態(tài)演示效果 【實現(xiàn)說明】
無
2.18 圖的建立與輸出
【問題描述】
建立圖的存儲結構（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學生可以任選兩種類型），能夠輸入圖的頂點和邊的信息，并存儲到相應存儲結構中，而后輸出 13 圖的鄰接矩陣。
【基本要求】
給出圖的深度優(yōu)先和廣度優(yōu)先遍歷算法，并給出遍歷過程的動態(tài)演示效果?！緦崿F(xiàn)說明】
無
2.19 以隊列實現(xiàn)的仿真技術預測理發(fā)館的經(jīng)營狀況（*）
【問題描述】
理發(fā)館一天的工作過程如下：
1)理發(fā)館有n把理發(fā)椅，可同時為n位顧客進行理發(fā)。
2)理發(fā)師分三個等級（一級、二級、三級），對應不同的服務收費。3)當顧客進門時，需選擇某級別理發(fā)師，只要該級別的理發(fā)師有空椅，則可立即坐下理發(fā)，否則需排隊等候。
4)一旦該級別的理發(fā)師有顧客理發(fā)完離去，排在隊頭的顧客便可開始理發(fā)。5)若理發(fā)館每天連續(xù)營業(yè)t分鐘，求
（1）一天內顧客在理發(fā)館內的平均逗留時間；（2）顧客排隊等候理發(fā)的隊列長度平均值；
（3）營業(yè)時間到點后仍需完成服務的收尾工作時間；（4）統(tǒng)計每天的營業(yè)額；
（5）統(tǒng)計每天不同級別理發(fā)師的創(chuàng)收。
【基本要求】
1)模擬理發(fā)館一天的工作過程：必須采用事件驅動的離散模型（參考教科書3.5節(jié)離散事件模擬p65）；
2)每個顧客到達和下一顧客到達時間的間隔應是隨機的； 3)理發(fā)師編號、理發(fā)師級別和每天的營業(yè)時間由用戶輸入；
4)某顧客挑選某一個級別的理發(fā)師而不得時，選第一個隊列排隊等待 ；
5)每個顧客進門時將生成三個隨機數(shù):(1)durtime:進門顧客理發(fā)所需服務時間（簡稱：理發(fā)時間）；(2)intertime:下一顧客將到達的時間間隔（簡稱：間隔時間）；(3)select:服務選項。
6)服務收費：應包含服務時間和理發(fā)師級別兩個因素。
7)除了輸出統(tǒng)計的數(shù)據(jù)外，還需要顯示理發(fā)館的狀態(tài)，可以采用文本方式（橫向顯示每張椅編號、理發(fā)師級別。縱向表示等待該理發(fā)師理發(fā)的排隊長度）?！緦崿F(xiàn)說明】
用戶輸入每位理發(fā)師編號、級別號和營業(yè)的時間，結合隨機數(shù)進行測試。
2.20 防抄襲管理系統(tǒng)（*）
【問題描述】
對于給定的文檔，如word文檔，txt文檔等，找出文檔的相似度。【基本要求】
（1）要求找出給定的兩個文檔的相似度以及標出相似的地方（1:1）；（2）要求找出給定的一個文檔與給定的文件夾的所有文檔的相似度，以及標出相似的地方(1:n)（3）要求找出給定的文件夾下面所有文檔的相似度(n:n)?！緦崿F(xiàn)說明】
給定相似文檔進行測試。
2.21.設計一個停車場管理系統(tǒng)，模擬停車場的運作
設計要求：通過此程序具備以下功能：
1、要求以棧模擬停車場，以隊列模擬車場 15 外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進行模擬管理；
2、要求處理的數(shù)據(jù)元素包括三個數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車牌照號碼及到達或離去的時刻；
3、該系統(tǒng)完成以下功能：若是車輛到達，則輸出汽車在停車場內或便道上的停車位置；若是車離去，則輸出汽車在停車場內停留的時間和應交納的費用（在便道上停留的時間不收費）；
4、要求棧以順序結構實現(xiàn)，隊列以鏈表實現(xiàn)。
2.22． 赫夫曼編碼
設計要求：自己找一篇不少于200個單詞的英文文章，分析該文章中每一個字符的出現(xiàn)概率（包括標點符號，區(qū)分大小寫），根據(jù)分析結果對文章中每一個字符進行赫夫曼編碼，并將編碼原則儲于一個獨立的文本文件中。最后，根據(jù)這個編碼原則，將英文文章轉換為01 串存儲于一個文本文件中，再編寫一個解碼程序，將編碼解碼為原文件。如：英文文章為 aaabbc 則編碼規(guī)則為 a-----0 b-----10 c-----11 英文文章將被轉化為 000101011 2.23.并查集：檢查網(wǎng)絡
題目要求：給定一個計算機網(wǎng)絡以及機器間的雙向連線列表，每一條連線允許兩端的計算機進行直接的文件傳輸，其他計算機間若存在一條連通路徑，也可以進行間接的文件傳輸。請寫出程序判斷：任意指定兩臺計算機，它們之間是否可以進行文件傳輸？ 輸入要求：輸入若干測試數(shù)據(jù)組成。對于每一組測試，第1行包含一個整數(shù)n（≤10000），即網(wǎng)絡中計算機的總臺數(shù)，因而每臺計算機可用1到n之間的一個正整數(shù)表示。接下來的幾行輸入格式為i c1 c2或者 c或者c c1c2或者s，其中c1和c2是兩臺計算機的 16 序號，i表示在c1和c2間輸入一條連線，c表示檢查c1和c2間是否可以傳輸文件，s表示該組測試結束。
當n為0時，表示全部測試結束，不要對該數(shù)據(jù)做任何處理。
輸出要求：對每一組c開頭的測試，檢查c1和c2間是否可以傳輸文件，若可以，則在一行中輸出“yes”，否則輸出“no”。
當讀到s時，檢查整個網(wǎng)絡。若網(wǎng)絡中任意兩機器間都可以傳輸文件，則在一行中輸出“the network is connected.”，否則輸出“there are k components.”,其中k是網(wǎng)絡中連通集的個數(shù)。
兩組測試數(shù)據(jù)之間請輸出一空行分隔。
2.24.教學計劃編制問題（圖的應用）
[問題描述] 大學的每個專業(yè)都要制定教學計劃。假設任何專業(yè)都有固定的學習年限，每學年含兩學期，每學期的時間長度和學分上限值均相等。每個專業(yè)開設的課程都是確定的，而且課程在開設時間的安排必須滿足先修關系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學期。試在這樣的前提下設計一個教學計劃編制程序。[實現(xiàn)提示]
1、輸入?yún)?shù)應包括：學期總數(shù)，一學期的學分上限，每門課的課程號（可以是固定占3位的字母數(shù)字串）、學分和直接先修課的課程號。
2、應允許用戶指定下列兩種編排策略之一：一是使學生在各學期中的學習負擔盡量均勻；二是使課程盡可能地集中在前幾個學期中。
3、若根據(jù)給定的條件問題無解，則報告適當?shù)男畔ⅲ环駝t將教學計劃輸出到用戶指定的文件中。計劃的表格格式可以自己設計。
4、可設學期總數(shù)不超過12，課程總數(shù)不超過100。如果輸入的先修課程號不在該專業(yè)開設的課程序列中，則作為錯誤處理。
============================= 17 2.25.藥品銷售統(tǒng)計系統(tǒng)（排序應用）
【問題描述】
設計一系統(tǒng)，實現(xiàn)醫(yī)藥公司定期對銷售各藥品的記錄進行統(tǒng)計，可按藥品的編號、單價、銷售量或銷售額做出排名?！緦崿F(xiàn)提示】
在本設計中，首先從數(shù)據(jù)文件中讀出各藥品的信息記錄，存儲在順序表中。各藥品的信息包括：藥品編號、藥名、藥品單價、銷出數(shù)量、銷售額。藥品編號共4位，采用字母和數(shù)字混合編號，如：a125，前一位為大寫字母，后三位為數(shù)字，按藥品編號進行排序時，可采用基數(shù)排序法。對各藥品的單價、銷售量或銷售額進行排序時，可采用多種排序方法，如直接插入排序、冒泡排序、快速排序，直接選擇排序等方法。在本設計中，對單價的排序采用冒泡排序法，對銷售量的排序采用快速排序法，對銷售額的排序采用堆排序法。
藥品信息的元素類型定義： typedef struct node { char num[4];/*藥品編號*/ char name[10];/*藥品名稱*/ float price;/*藥品單價*/ int count;/*銷售數(shù)量*/ float sale;/*本藥品銷售額*/ }datatype;存儲藥品信息的順序表的定義： typedef struct { datatype r[maxsize];int length;}sequenlist;
2.26梯運行仿真程序
[問題描述] 辦公大樓有若干層（例如，十層），每層有電梯，同時有步行樓梯；
全樓有若干部（例如，不多于10部）電梯同時供使用，電梯容量為24人，速度每上下一層需5秒，在某一層停下至少15秒。其運行狀態(tài)可分：向上、向下、停止，當前乘客數(shù)，當前所在層數(shù)。它設有一個“按鈕數(shù)組”，例如第五層的按鈕按下，意味著有乘客在第5層到達目標層，等等。在樓的每一層，有電梯數(shù)，有按鈕表示有人等待向上或向下，由若干人在等待，有若干電梯在本層停下，等等。
在大樓中（包括進出）的總人數(shù)不超過500 人，每個人站在電梯前有個目標層，他有一個最大的忍受等待時間，因為他可以選擇電梯或是步行走樓梯，等等。
還有下面若干假設：在每個時間段要進大樓的人數(shù)在0～199 之間隨機取值；
用電梯的每個人的目標層在1～10 之間取值；一個人在進電梯或改走樓梯之前的等待時間在180～360 秒范圍內隨機發(fā)生；一個人到達目標層后第二次再乘電梯中間的工作時間在400～6600 秒間隨機取值。[基本要求] 編寫一個程序，模擬辦公大樓中全部電梯的工作過程。這個仿真程序可以用來監(jiān)測系統(tǒng)運行情況，改善大樓管理，它也可以看成是一種游戲程序。
2.27國交通咨詢模擬
[問題描述]
處于不同目的的旅客對交通工具有不同的要求。例如，因公出差的旅客希望在旅 途中的時間盡可能的短，出門旅游的游客則期望旅費盡可能省，而老年旅客則要求中轉次數(shù)最少。編制一個全國城市間的交通咨詢程序，為旅客提供最優(yōu)決策的交通咨詢。
[基本要求]
（1）提供對城市信息進行編輯（如：添加或刪除）的功能；
（2）城市之間有兩種交通工具：火車或飛機，提供對全國城市交通圖和列車時刻表及飛機航班表進行編輯的功能。（信息的輸入方式可以是文件輸入和鍵盤輸入兩種方式）
（3）提供兩種最優(yōu)決策：最快到達和最省錢到達。（選作：旅途中轉次數(shù)最少的最優(yōu)決策）
（4）旅途中耗費的總時間應該包括中轉站的等候時間。
（5）咨詢以用戶和計算機的對話方式進行。
a）由用戶輸入起始站、終點站、最優(yōu)決策原則和交通工具；
b）輸出信息：最快需要多長時間才能到達或者最少需要多少旅費才能到達，并詳 細說明依次于何時乘坐哪一趟列車或哪一次班機到何地。
三、課程設計的基本要求
1．問題分析和任務定義。根據(jù)設計題目的要求，充分地分析和理解問題，明確問題要求做什么？（而不是怎么做？）限制條件是什么？
2．邏輯設計。對問題描述中涉及的操作對象定義相應的數(shù)據(jù)類型，并按照以數(shù)據(jù)結構為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。邏輯設計的結果應寫出每個抽象數(shù)據(jù)類型的定義(包括數(shù)據(jù)結構的描述和每個基本操作的功能說明)，各個主要模塊的算法，并畫出模塊之間的調用關系圖。
3．詳細設計。定義相應的存儲結構并寫出各函數(shù)的偽碼算法。在這個過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結構清晰、合理、簡單和易于調試，抽象數(shù)據(jù)類型的實現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可能明確具體。詳細設計的結果是對數(shù)據(jù)結構和基本操作作出進一步的求精，20 寫出數(shù)據(jù)存儲結構的類型定義，寫出函數(shù)形式的算法框架。
4．程序編碼。把詳細設計的結果進一步求精為程序設計語言程序。同時加入一些注解和斷言，使程序中邏輯概念清楚。
5．程序調試與測試。采用自底向上，分模塊進行，即先調試低層函數(shù)。能夠熟練掌握調試工具的各種功能，設計測試數(shù)據(jù)確定疑點，通過修改程序來證實它或繞過它。調試正確后，認真整理源程序及其注釋，形成格式和風格良好的源程序清單和結果。
6．結果分析。程序運行結果包括正確的輸入及其輸出結果和含有錯誤的輸入及其輸出結果。算法的時間、空間復雜性分析。
7．編寫課程設計報告并提交相關內容
設計最終需提交的內容包括：
a）課程設計報告（1份，a4紙打印，同時包括一份電子版）報告要求版面清晰，格式規(guī)范，否則重新編寫。報告內容要求包括：
（1）問題的概述、分析及研究意義；（2）數(shù)據(jù)結構的邏輯設計和物理存儲設計；（3）重要算法的設計、流程描述或偽代碼描述；
（4）數(shù)據(jù)結構的時空復雜性分析以及重要算法的復雜性分析；
（5）程序最終實現(xiàn)結果（包括重點結果界面的抓取，能過說明問題的重要實驗結果數(shù)據(jù)的打印或其可視化結果等）。
（6）參考文獻（如果需要）。
（7）附錄部分附上關鍵數(shù)據(jù)結構的定義及關鍵算法的源代碼。
b）完整的程序系統(tǒng)（電子方式提交）
能夠對輸入產(chǎn)生相應的輸出，同時盡量的完成可視化演示。
該部分包括源代碼和可執(zhí)行文件兩個部分（提交的時候需清楚的注明個人姓名，班級）。
c）源程序文檔（電子方式提交）
源程序代碼要求結構清晰、可讀性好。應對源程序中的類說明（如果采用面向對象方法設計），函數(shù)說明，接口說明，關鍵變量說明等進行注釋；源程序要進行適當?shù)目s進編排。
d）答辯報告（編寫power point答辯報告，電子方式提交）要求突出重點，思路清晰。同時就此報告準備答辯。
e）所有以電子方式提交的文件全部存在一個目錄中，并對其進行壓縮（用winrar或winzip均 21 可），壓縮后的文件按規(guī)定格式進行命名，命名格式為：學號+（）。8．每位同學只能選擇一個題目并完成
四、評分標準
1、基本功能：
50分。
通過功能的實現(xiàn)情況、界面的完成情況、軟件的實現(xiàn)情況進行評分。
2、設計報告及使用說明書： 20分 按照報告的要求進行評分。
3、回答問題：
4、平時考勤：
5、核分標準：
15分 15分 100分
（90~100為優(yōu)、80~89為良、70~79為中、60~69為及格、，60以下為不及格）
五、參考書目
嚴蔚敏.《數(shù)據(jù)結構》（c語言版）.清華大學出版社 劉玉龍．《數(shù)據(jù)結構與算法》.電子工業(yè)出版社.嚴蔚敏等《數(shù)據(jù)結構題集》（c語言版）.清華大學出版社
徐孝凱.數(shù)據(jù)結構實用教程（c/c++描述）.北京:清華大學出版社.陳慧南.數(shù)據(jù)結構（使用c++語言描述）.南京:東南大學出版社.殷人昆, 陶永雷, 謝若陽等.數(shù)據(jù)結構（用面向對象方法與c++描述）.北京:清華大學出版社.22
數(shù)據(jù)結構與算法課程設計題目答案篇四
數(shù)據(jù)結構課程設計題目 以下8個題目任選其一。
1．排序算法比較
利用隨機函數(shù)產(chǎn)生30000個隨機整數(shù)，利用插入排序、起泡排序、選擇排序、快速排序、堆排序、歸并排序等排序方法進行排序，并且（1）統(tǒng)計每一種排序上機所花費的時間。
（2）統(tǒng)計在完全正序，完全逆序情況下記錄的比較次數(shù)和移動次數(shù)。（3）比較的指標為關鍵字的比較次數(shù)和記錄的移動次數(shù)(一次記錄交換計為3次移動)。
（4）對結果作簡單分析，包括對各組數(shù)據(jù)得出結果波動大小的解釋。2．圖的深度遍歷
對任意給定的圖（頂點數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用堆棧的五種基本運算（清空堆棧、壓棧、彈出、取棧頂元素、判棧空）實現(xiàn)圖的深度優(yōu)先搜索遍歷。畫出搜索順序示意圖。3．圖的廣度遍歷
對任意給定的圖（頂點數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用隊列的五種基本運算（置空隊列、進隊、出隊、取隊頭元素、判隊空）實現(xiàn)圖的廣度優(yōu)先搜索遍歷。畫出搜索順序示意圖。4．二叉樹的遍歷
對任意給定的二叉樹（頂點數(shù)自定）建立它的二叉鏈表存貯結構，并利用棧的五種基本運算（置空棧、進棧、出棧、取棧頂元素、判?？眨崿F(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ù)據(jù)：
（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ù)據(jù)：
（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）根據(jù)字符頻率構造哈夫曼樹，并給出每個字符的哈夫曼編碼。
（4）用哈夫曼編碼來存儲文件，并和輸入文本文件大小進行比較，計算文件壓縮率
（5）根據(jù)相應哈夫曼編碼，對編碼后的文件進行解碼，恢復成ascii編碼的英文短文后輸出。
分析及設計步驟（供參考）
1.分析問題，給出數(shù)學模型，設計相應的數(shù)據(jù)結構。
1)分析問題特點，用數(shù)學表達式或其它形式描述其數(shù)學模型。2)選擇能夠體現(xiàn)問題本身特點的一種或幾種邏輯結構。
3)依據(jù)邏輯結構和問題特點，設計并選擇相應的存儲結構（順序存儲結構和鏈式存儲結構對應的算法實現(xiàn)有區(qū)別）。
2.算法設計
1)確定所需模塊：對于復雜的程序設計，要充分利用模塊化程序設計方法和面向對象思想，自頂向下，逐步細化。
2)各子模塊功能描述：給出主要模塊的算法描述，用流程圖或偽代碼表示。3)模塊之間的調用關系：給出算法各模塊之間的關系圖示。3.上機實現(xiàn)程序
為提高工作效率，充分利用上機調試時間，在上機之前應列出程序清單。
4.用有代表性的各種測試數(shù)據(jù)去驗證算法及程序的正確性
5.算法分析及優(yōu)化
經(jīng)過上機調試，源程序運行正確，并且實現(xiàn)算法要求的功能，解決課程設計題目中給出的問題后，分析算法的時間復雜度和空間復雜度，如有可能對程序進行優(yōu)化改進。
課程設計報告范例（參考）
約瑟夫環(huán)問題。
問題描述：設編號為1,2,…,n(n>0)個人按順時針方向圍坐一圈，每人持有一個正整數(shù)密碼。開始時任意給出一個報數(shù)上限值m，從第一個人開始順時針方向自1起順序報數(shù)，報到m時停止報數(shù)，抱m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人起重新自1起順序報數(shù)；如此下去，直到所有人全部出列為止。要求設計一個程序模擬此過程，并給出出列人的編號序列?；疽螅?BR> （1）初始報數(shù)上限值m和測試數(shù)據(jù)在程序中確定；（2）用帶頭結點的單循環(huán)鏈表作數(shù)據(jù)元素的存儲結構；（3）把帶頭結點的單循環(huán)鏈表作為抽象數(shù)據(jù)類型設計。測試數(shù)據(jù)：
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ù)據(jù)類型sclinlist，其中包括基本操作的函數(shù)有：初始化操作函數(shù)、插入一個結點操作函數(shù)、刪除一個結點操作函數(shù)、取一個結點數(shù)據(jù)操作函數(shù)和判表是否非空操作函數(shù)。該抽象數(shù)據(jù)類型文件名為sclinlist.h。
（2）void sclldeleteafter(sclnode *p)，其功能是刪除帶頭結點的單循環(huán)鏈表中指針p所指結點的下一個結點。這是對帶頭結點的單循環(huán)鏈表抽象數(shù)據(jù)類型sclinlist，補充本問題需要的一個操作函數(shù)。（3）void jesephring(sclnode *head, int m)，其功能是對帶頭結點的單循環(huán)鏈表head,以m為初始報數(shù)上限值實現(xiàn)問題要求。
（4）void main(void)，主函數(shù)，功能是給出測試數(shù)據(jù)值，建立測試數(shù)據(jù)值的帶頭結點單循環(huán)鏈表，調用jesephring()函數(shù)實現(xiàn)問題要求。數(shù)據(jù)結構：
（1）數(shù)據(jù)類型datatype定義如下： typedef struct { int number;int cipher;} datatype;
（2）帶頭結點單循環(huán)鏈表抽象數(shù)據(jù)類型sclinlist。
（3）帶頭結點單循環(huán)鏈表抽象數(shù)據(jù)類型的結點結構定義如下：
typedef struct node { datatype data;struct node *next;} sclnode;源程序：
源程序存放在兩個文件中，文件sclinlist.h是帶頭結點單循環(huán)鏈表抽象數(shù)據(jù)類型，文件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ù)據(jù)元素值*/ { 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ù)據(jù)類型datatype*/ #include “sclinlist.h” /*包含sclinlist抽象數(shù)據(jù)類型*/ 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->);m = curr->;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ù)據(jù)結構與算法課程設計題目答案篇五
數(shù)據(jù)結構課程設計題目
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)可以按學校編號或名稱、學?？偡帧⒛信畧F體總分排序輸出；
4)可以按學校編號查詢學校某個項目的情況；可以按項目編號查詢取得前三或前五名的學校。5)數(shù)據(jù)存入文件并能隨時查詢
6)規(guī)定：輸入數(shù)據(jù)形式和范圍：可以輸入學校的名稱，運動項目的名稱
輸出形式：有合理的提示，各學校分數(shù)為整形
界面要求：有合理的提示，每個功能可以設立菜單，根據(jù)提示，可以完成相關的功能要求。
存儲結構：學生自己根據(jù)系統(tǒng)功能要求自己設計，但是要求運動會的相關數(shù)據(jù)要存儲在數(shù)據(jù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關內容在c語言程序設計的書上，請自學解決）請在最后的上交資料中指明你用到的存儲結構；
測試數(shù)據(jù)：要求使用
1、全部合法數(shù)據(jù)；
2、整體非法數(shù)據(jù)；
3、局部非法數(shù)據(jù)。進行程序測試，以保證程序的穩(wěn)定。測試數(shù)據(jù)及測試結果請在上交的資料中寫明；
2.飛機訂票系統(tǒng)（限1 人完成）
任務：通過此系統(tǒng)可以實現(xiàn)如下功能：
錄入：
可以錄入航班情況（數(shù)據(jù)可以存儲在一個數(shù)據(jù)文件中，數(shù)據(jù)結構、具體數(shù)據(jù)自定）
查詢：
可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛抵達城市，航班票價，票價折扣，確定航班是否滿倉）；
可以輸入起飛抵達城市，查詢飛機航班情況；
訂票：（訂票情況可以存在一個數(shù)據(jù)文件中，結構自己設定）
可以訂票，如果該航班已經(jīng)無票，可以提供相關可選擇航班；
退票： 可退票，退票后修改相關數(shù)據(jù)文件；
客戶資料有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號。
修改航班信息：
當航班信息改變可以修改航班數(shù)據(jù)文件
要求：
根據(jù)以上功能說明，設計航班信息，訂票信息的存儲結構，設計程序完成功能；
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ù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標點符號。
輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出“全部字母數(shù)”、“數(shù)字個數(shù)”、“空格個數(shù)”、“文章總字數(shù)”（3）輸出刪除某一字符串后的文章；
4.宿舍管理查詢軟件（限1 人完成）
1)任務：為宿舍管理人員編寫一個宿舍管理查詢軟件, 程序設計要求： a.采用交互工作方式
b.建立數(shù)據(jù)文件，數(shù)據(jù)文件按關鍵字（姓名、學號、房號）進行排序(冒泡、選擇、插入排序等任選一種)2)查詢菜單:(用二分查找實現(xiàn)以下操作)a.按姓名查詢
b.按學號查詢
c.按房號查詢
3)打印任一查詢結果（可以連續(xù)操作）
5.校園導航問題（限1 人完成）
設計要求：設計你的學校的平面圖，至少包括10個以上的場所，每兩個場所間可以有不同的路，且路長也可能不同，找出從任意場所到達另一場所的最佳路徑（最短路徑）。
6.教學計劃編制問題（限1 人完成）
設計要求：針對計算機系本科課程，根據(jù)課程之間的依賴關系（如離散數(shù)學應在數(shù)據(jù)結構之前開設）制定課程安排計劃，并滿足各學期課程數(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(wèi)，生成一棵二叉排 序樹t； 2)對二叉排序樹t作中序遍歷，輸出結果；
3)輸入元素x,查找二叉排序樹t,若存在含x的結點,則刪除該結點,并作中序遍歷(執(zhí)行操作2)；否則輸出信息“無x”；
12.最小生成樹問題（限1 人完成）
設計要求：在n個城市之間建設網(wǎng)絡，只需保證連通即可，求最經(jīng)濟的架設方法。存儲結構采用多種。求解算法多種。
13.通訊錄的制作（限1 人完成）
設計目的：用〈〈數(shù)據(jù)結構〉〉中的雙向鏈表作數(shù)據(jù)結構，結合c語言基本知識。編寫一個通訊錄管理系統(tǒng)。以把所學數(shù)據(jù)結構知識應用到實際軟件開發(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ù)據(jù)存放在數(shù)據(jù)文件(，位于執(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è)務?！净疽蟆?BR> 1)每種書的登記內容包括書號、書名、著作者、現(xiàn)存量和庫存量； 2)對書號建立索引表（線性表）以提高查找效率； 3)系統(tǒng)主要功能如下：
*采編入庫：新購一種書，確定書號后，登記到圖書帳目表中，如果表中已有，則只將庫存量增加； *借閱：如果一種書的現(xiàn)存量大于0，則借出一本，登記借閱者的書證號和歸還期限，改變現(xiàn)存量； *歸還：注銷對借閱者的登記，改變該書的現(xiàn)存量?！具M一步完成內容】 1)系統(tǒng)功能的進一步完善； 2)索引表采用樹表。3)設計內容 4)程序流程圖 5)源程序
6)軟件測試報告（包括所用到的數(shù)據(jù)及結果）
16.散列表的設計與實現(xiàn)（限1 人完成）【問題描述】
設計散列表實現(xiàn)電話號碼查找系統(tǒng)。【基本要求】
1)設每個記錄有下列數(shù)據(jù)項：電話號碼、用戶名、地址；
2)從鍵盤輸入各記錄，分別以電話號碼和用戶名為關鍵字建立散列表； 3)采用一定的方法解決沖突； 4)查找并顯示給定電話號碼的記錄； 5)查找并顯示給定用戶名的記錄?！具M一步完成內容】 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 人完成）
要求：建立試題庫文件，隨機產(chǎn)生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ù)據(jù)結構實現(xiàn)上述求解 2)采用鏈數(shù)據(jù)結構實現(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ù)產(chǎn)生n個隨機整數(shù)（20000以上），對這些數(shù)進行多種方法進行排序。要求：
1)至少采用三種方法實現(xiàn)上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結果保存在不同的文件中。
2)統(tǒng)計每一種排序方法的性能（以上機運行程序所花費的時間為準進行對比），找出其中兩種較快的方法。3)如果采用4種或4種以上的方法者，可適當加分。
25.學生成績管理系統(tǒng)（限1 人完成）現(xiàn)有學生成績信息文件1（），內容如下 姓名 學號 語文 數(shù)學 英語
張明明 01 67 78 82 李成友 02 78 91 88 張輝燦 03 68 82 56 王露 04 56 45 77 陳東明 05 67 38 47 ….......…
學生成績信息文件2（）,內容如下: 姓名 學號 語文 數(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ù)據(jù)進行合并, 2) 3)中的數(shù)據(jù)按總分降序排序(至少采用兩種排序方法實現(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個城市間的距離網(wǎng)，用prim算法或kruskal算法建立最小生成樹，并計算得到的最小生成樹的代價?；疽螅?BR> 1、城市間的距離網(wǎng)采用鄰接矩陣表示，鄰接矩陣的存儲結構定義采用課本中給出的定義，若兩個城市之間不存在道路，則將相應邊的權值設為自己定義的無窮大值。要求在屏幕上顯示得到的最小生成樹中包括了哪些城市間的道路，并顯示得到的最小生成樹的代價。
2、表示城市間距離網(wǎng)的鄰接矩陣（要求至少6個城市，10條邊）
3、最小生成樹中包括的邊及其權值，并顯示得到的最小生成樹的代價。
36.客戶消費積分管理系統(tǒng)（限1 人完成）
問題描述：針對客戶的消費情況，進行客戶管理，根據(jù)客戶的消費積分對客戶實行不同程度的打折優(yōu)惠?；疽螅?BR> 1.采用一定的存儲結構進行客戶信息的存儲； 2.對客戶的信息可以進行修改、刪除、添加； 3.能夠根據(jù)消費情況進行客戶積分的計算； 4.根據(jù)積分情況實行不同程度的打折優(yōu)惠；
37.產(chǎn)品進銷存管理系統(tǒng)（限1 人完成）
問題描述：針對某一種行業(yè)的庫房的產(chǎn)品進銷存情況進行管理?；疽螅?BR> 1.采用一定的存儲結構對庫房的貨品及其數(shù)量進行分類管理； 2.可以進行產(chǎn)品類的添加、產(chǎn)品的添加、產(chǎn)品數(shù)量的添加；
3.能夠查詢庫房每種產(chǎn)品的總量、進貨日期、銷出數(shù)量、銷售時間等；
38.特殊矩陣的壓縮存儲算法的實現(xiàn)（限1 人完成）問題描述：對于特殊矩陣可以通過壓縮存儲減少存儲空間?；疽螅?BR> 1.針對多種特殊矩陣進行壓縮存儲，并能顯示壓縮后的相關地址和值； 2.輸入在原來特殊矩陣中的地址，要求能從壓縮后的矩陣中讀出相應的值；
39.算術表達式的求解（限1 人完成）
問題描述：給定一個算術表達式，通過程序求出最后的結果?；疽螅?BR> 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ù)據(jù)的迷宮，輸出的一條通路為：（1，1，1），（1,2,2）,(3,2,3),(3,1,2),…。測試數(shù)據(jù)：
迷宮的測試數(shù)據(jù)如下：左下角（1，1）為入口，右下角（8，9）為出口。實現(xiàn)提示： 計算機解迷宮通常用的是“窮舉求解”方法，即從入口出發(fā)，順著某個方向進行探索，若能走通，則繼續(xù)往前進；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設的迷宮沒有通路。
可以二維數(shù)組存儲迷宮數(shù)據(jù)，通常設定入口點的下標為（1，1），出口點的下標為（n,n）。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮中任一位置，均可約定有東、南、西、北四個方向可通。選做內容：
（1）編寫遞歸形式的算法，求得迷宮中所有可能的通路；（2）以方陣形式輸出迷宮及其通路。43.迷宮問題（隊列）（同上）44二叉搜索樹：各種搜索樹效率比較 題目要求：
本題目要求對普通的二叉排序樹、avl樹分別實現(xiàn)制定操作，并分析比較這兩種不同數(shù)據(jù)結構對應的一系列插入和刪除操作的效率。要求測試對n個不同整數(shù)進行下列操作的效率：（1）按遞增順序插入n個整數(shù)，并按同樣順序刪除；（2）按遞增順序插入n個整數(shù)，并按相反順序刪除；（3）按隨機順序插入n個整數(shù)，并按隨機順序刪除；
要求n從1000到10000取值，并以數(shù)據(jù)規(guī)模n為橫軸，運行時間為縱軸，畫出3種不同數(shù)據(jù)結構對應的操作效率比較圖。
45.病毒測試程序 本題的任務是：
當整個網(wǎng)絡被感染后，計算有多少臺機器被某個特定變種所感染。輸入要求：
輸入由若干組測試數(shù)據(jù)組成。
每組數(shù)據(jù)的第1行包含2個整數(shù)m和n（1≤m,n≤500），接下來是一個m*n的矩陣表示網(wǎng)絡的初始感染狀態(tài)，其中的正、負整數(shù)的意義如題目描述中所定義。
下面一行給出一個正整數(shù)q，是將要查詢的變種的個數(shù)。接下去的q行里，每行給出一個變種的類型。當m或n為0時，表示全部測試結束，不要對該數(shù)據(jù)做任何處理。輸出要求：
對每一組測試，在一行里輸出被某個特定變種所感染的機器數(shù)量。
46關鍵路徑問題（限1 人完成）
問題描述：設計一個程序求出完成整項工程至少需要多少時間以及整項工程中的關鍵活動?；疽螅?BR> （1）對一個描述工程的aoe網(wǎng)，應判斷其是否能夠順利進行。
（2）若該工程能順利進行，輸出完成整項工程至少需要多少時間，以及每一個關鍵活動所依附的兩個頂點、最早發(fā)生時間、最遲發(fā)生時間。
47.神秘國度的愛情故事
輸入要求：輸入由若干組測試數(shù)據(jù)組成。
每組數(shù)據(jù)的第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ù)據(jù)做任何處理。
輸出要求：對每一組測試給定的a,b,c，在一行里輸出答案，即：如果c在a和b之間的路徑上，輸出yes,否則輸出no。
48.并查集：檢查網(wǎng)絡
題目要求：給定一個計算機網(wǎng)絡以及機器間的雙向連線列表，每一條連線允許兩端的計算機進行直接的文件傳輸，其他計算機間若存在一條連通路徑，也可以進行間接的文件傳輸。請寫出程序判斷：任意指定兩臺計算機，它們之間是否可以進行文件傳輸？
輸入要求：輸入若干測試數(shù)據(jù)組成。對于每一組測試，第1行包含一個整數(shù)n（≤10000），即網(wǎng)絡中計算機的總臺數(shù)，因而每臺計算機可用1到n之間的一個正整數(shù)表示。接下來的幾行輸入格式為i c1 c2或者 c或者c c1c2或者s，其中c1和c2是兩臺計算機的序號，i表示在c1和c2間輸入一條連線，c表示檢查c1和c2間是否可以傳輸文件，s表示該組測試結束。當n為0時，表示全部測試結束，不要對該數(shù)據(jù)做任何處理。
輸出要求：對每一組c開頭的測試，檢查c1和c2間是否可以傳輸文件，若可以，則在一行中輸出“yes”，否則輸出“no”。
當讀到s時，檢查整個網(wǎng)絡。若網(wǎng)絡中任意兩機器間都可以傳輸文件，則在一行中輸出“the network is connected.”，否則輸出“there are k components.”,其中k是網(wǎng)絡中連通集的個數(shù)。兩組測試數(shù)據(jù)之間請輸出一空行分隔。
49.廣義表的應用
由于廣義表在結構上較線性表復雜得多，因此，廣義表的運算也不如線性表簡單。本設計要求實現(xiàn)的廣義表的建立、查找、輸出、取表頭和取表尾以及求深度、求逆表等。本設計用一個主控菜單程序控制，共分為6個子系統(tǒng)。（1）.建立廣義表（2）輸出廣義表（3）結點的查找（4）求廣義表表頭（5）求廣義表表尾（6）求廣義表的深度
50.網(wǎng)絡流：宇宙旅行 題目要求：
在走遍了地球上的所有景點以后，旅游狂人開始計劃他的宇宙旅行項目。經(jīng)過謹慎調查，他目前掌握了一張各衛(wèi)星空間站可以臨時容納的旅客人數(shù)列表。但旅客從一個星球飛往另一個星球時，需要在若干衛(wèi)星空間站臨時?？恐修D，而這些空間站不能接待任何旅客駐留，旅客必須立刻轉乘另一艘飛船離開，所以空間站不能接待超過自己最大容量的旅客流。為了估計預算，現(xiàn)在旅游狂人需要知道終點星球的接待站應該設計多大容量，才能使得每艘飛船在到達時都可以保證讓全部旅客下船。輸入要求：
輸入若干組測試數(shù)據(jù)組成。
每組測試數(shù)據(jù)的第1行包含旅行的起點星球和終點星球的名稱和一個不超過500的正整數(shù)n（n為0標志全部測試結束，不要對該數(shù)據(jù)做任何處理）。
接下來的n行里，數(shù)據(jù)格式為：sourcei capacityi，其中sourcei和destinationi是衛(wèi)星空間站的名稱或起點、終點星球的名稱，正整數(shù)capacityi是飛船從sourcei到destinationi一次能運載的最大旅客流量。每個名稱是由a～z之間三個大寫字母組成的字符串，例如：zju。測試數(shù)據(jù)中不包含任何到達起點星球的信息以及任何從終點星球出發(fā)的信息。輸出要求：
對每一組測試，在一行里輸出終點星球接待站應具有的最小容量，使得每艘飛船在到達時都可以保證讓全部旅客下船。
數(shù)據(jù)結構與算法課程設計題目答案篇一
一、基本信息
課程編號：e1132107 課程類別：學科基礎課必修課 適用層次：本科
適用專業(yè)：計算機科學與技術、網(wǎng)絡工程、軟件工程等 開課學期：3 學 分：2學分 學 時：2周 考核方式：考查
二、教學目的
數(shù)據(jù)結構與算法課程設計不僅是數(shù)據(jù)結構與算法課程的實踐教學環(huán)節(jié)，而且是一門綜合性實驗項目。通過這個實驗，培養(yǎng)學生綜合運用數(shù)據(jù)結構基本知識和程序設計基本知識，解決實際問題，提高程序設計的能力和團隊協(xié)作精神。
本課程設計的目的就是要達到理論與實際應用相結合，使同學們能夠根據(jù)數(shù)據(jù)對象的特性，學會數(shù)據(jù)組織的方法，能把現(xiàn)實世界中的實際問題在計算機內部表示出來，并培養(yǎng)基本的、良好的程序設計技能。
1．學生通過實踐掌握線性表、樹、圖等數(shù)據(jù)結構的存儲結構及算法實現(xiàn)； 2．培養(yǎng)學生利用數(shù)據(jù)結構知識解決實際問題的能力;3．使學生初步具備查閱資料、分析設計、上機實現(xiàn)和書寫科技 報告的能力。
三、基本要求
1.指導教師要在選題、設計、上機實現(xiàn)等諸環(huán)節(jié)上投入精力，加強指導、討論和答疑的力度。尤其在選題上，要充分考慮學生目前所具有的知識水平、掌握的開發(fā)工具、以及綜合設計能力的現(xiàn)狀，使題目取材合理、大小適中、難易適度，使學生在完成設計工作后，能有所收獲。2.參加課程設計的學生要珍惜機會、勤奮工作、勇于創(chuàng)新、勇于探索、勇于實踐，虛心向指導教師請教，向同學學習，獨立完成設計任務。
3.學生需保質、保量、保時間進度地提交規(guī)范的課程設計報告，審查由指導教師負責。
四、教學內容
1.主要內容：應用所掌握的線性表、樹、圖等數(shù)據(jù)結構知識解決實際問題。2.軟件開發(fā)工具：c/c++、java。
3.課程設計題目：指導教師擬定（參考題目見附錄1）
4.具體步驟：指導教師擬定設計題目，學生研究具體問題、進行需求分析、選擇合適的數(shù)據(jù)結構、設計算法、編寫并調試代碼、書寫文檔材料、提交設計報告，最后，由指導教師驗收并評定成績。
5.設計內容及時間安排：第1-3天，選定題目，明確題目要求、確定數(shù)據(jù)結構、設計算法，并分析算法復雜度；第4-8天，編寫程序、調試程序、測試程序；第9-10天，撰寫設計報告，準備答辯（上機演示，回答教師提問）。6.設計報告書寫要求：按照軟件開發(fā)規(guī)范的要求書寫設計報告（參見附錄三報告書寫格式）；要求報告層次結構清晰、圖表完整、語言通順、字跡工整。7.驗收要求：1）運行所設計的程序；2）回答有關問題；3）提交課程設計報告（打印或手寫在實習報告冊上）；4）提交軟盤（源程序）。（鼓勵學生創(chuàng)新。對內容有創(chuàng)新者，成績評定將適當提高）。
五、考核方法
學習成績的評定方式：考查。
課程設計成績評定 =平時出勤（20%）+設計報告（40%）+答辯（40%）通過設計答辯方式，并結合學生的動手能力，獨立分析解決問題的能力和創(chuàng)新精神，總結報告和答辯水平以及學習態(tài)度綜合考評。成績分為優(yōu)、良、中、及格和不及格五等。
六、教材與參考資料 1.建議教材：
[1] 數(shù)據(jù)結構(c++)版，王紅梅、胡明、王濤編著，清華大學出版社，2005.7 [2] 自編教材
2.建議參考書目：
[1] 許卓群，楊冬青，唐世渭，張銘.數(shù)據(jù)結構與算法.高等教育出版社，2004.7 [2] 嚴蔚敏, 陳文博.數(shù)據(jù)結構及應用算法教程.清華大學出版社, 2001.2 [3] 朱晉蜀.數(shù)據(jù)結構(第一版).成都: 電子科技大學出版社, 2000.1 [4] clifford r著.張銘，劉曉丹譯.數(shù)據(jù)結構與算法分析.電子工業(yè)出版社，1998.8 [5] 殷人昆等.數(shù)據(jù)結構（用面向對象方法與c++描述）.清華大學出版社，1999.7 [6] ford w., topp structures with c++.清華大學出版社（影印版），1997.3
附錄一
參考題目（可分若干組，每個學生選擇其中一個題目）
1．商廈家電庫存管理 2.排序算法的時間比較
3．使用哈希表技術判斷兩個源程序的相似性 4．以隊列實現(xiàn)的仿真技術預測理發(fā)館的經(jīng)營狀況 5.某公園導游圖
6．用樹型結構的搜索算法模擬因特網(wǎng)域名的查詢 7．管道鋪設施工的最佳方案選擇 8．表達式分析與求值程序 9．安排教學計劃
10.設計huffman 編碼器與解碼器 11．在國際象棋盤上馬遍歷問題 12．八皇后問題 13．民航售票系統(tǒng) 14．模擬旅館管理系統(tǒng)中的床位分配和加收 15．銀行業(yè)務活動的模擬
16．文字統(tǒng)計系統(tǒng)—文字研究助手 17．修道士野人問題 18．考試問題
19．計算機輔助考核系統(tǒng) 20．學籍管理系統(tǒng)
注：學生可以自選題目或選擇指導老師擬定的題目。
附錄二
開發(fā)步驟
1.分析題目的要求、目的； 2.選擇適當?shù)臄?shù)據(jù)結構；
3.抽象數(shù)據(jù)類型的設計； 4.抽象數(shù)據(jù)類型的實現(xiàn)； 5.編寫代碼、上機調試； 6.總結驗收、評價。
附錄三 報告書寫格式
1．問題描述
題目內容、基本要求 2．需求分析
軟件的基本功能、輸入/輸出形式、測試數(shù)據(jù)要求 3．概要設計
所需的adt及作用、主程序流程及模塊調用關系 4．詳細設計
實現(xiàn)概要設計的數(shù)據(jù)類型、每個操作的偽碼算法、主程序和其它模塊的偽碼算法、函數(shù)調用關系圖 5．編碼與調試分析
編碼與調試過程中遇到的問題及解決的辦法，還存在哪些沒有解決的問題？ 6．使用說明
簡要說明程序運行操作步驟 7．測試結果
8．課程設計心得體會
數(shù)據(jù)結構與算法課程設計題目答案篇二
數(shù)據(jù)結構與算法課程設計題目
1．成績管理
問題描述：給出n個學生的考試成績表，成績表包括學生的學號、姓名、考試成績（高等數(shù)
學、英語、物理），設計一個簡單的成績管理程序。
基本要求：
（1）建立成績表，能夠插入、刪除、修改學生的成績記錄；（2）按任一單科成績排序；(3)計算每名學生的平均成績；
(4)統(tǒng)計任一單科成績不及格的學生人數(shù), 輸出不及格人數(shù)及不及格的學生名單(5)根據(jù)平均成績將成績表按由高到低的次序排列，統(tǒng)計每名學生在考試中獲得的名次，分數(shù)相同的為同一名次，按名次輸出成績表。
(6)成績表保存在文件中, 可以從文件讀取數(shù)據(jù)。
測試數(shù)據(jù)：學生可以根據(jù)自己班級的考試成績單，任意截取一部分做為測試數(shù)據(jù) 2．一元多項式簡單計算
問題描述：設計一個簡單一元多項式計算器?；疽螅?1)輸入并建立多項式；(2)輸出多項式；
(3)兩個多項式相加，輸出結果多項式；(4)兩個多項式相減，輸出結果多項式。
提高要求：可以根據(jù)輸入變量的值，計算出多項式的結果，且算法的效率高。測試數(shù)據(jù)：可任意選取兩個一元多項式，可以是一般的多項式，也可以是稀疏多項式。3．舞伴問題
問題描述：一班有m個女生、n個男生(m不等于n), 舉辦一場舞會.男女生分別編號坐在舞池兩邊的椅子上，每曲開始時, 依次從男生和女生中各出一人配對跳舞, 本曲沒成功配對者坐著等待下一曲找舞伴，設計一個程序模擬舞伴配對過程。
基本要求：輸入男、女學生的姓名、性別，由程序自動為男女生編號，可以順序編號，也可以隨機編號，輸出每曲配對情況（包括男、女生的姓名、性別和編號）。原始數(shù)據(jù)和結果數(shù)據(jù)要保存到文件中。
測試數(shù)據(jù)：分別選擇男生多于女生、女生多于男生、男女生相等的三組測試數(shù)據(jù) 提高要求：計算出任意一位男生(編號為x)和任意一位女生(編號為y), 在第k曲配對跳舞的情況。
4．文學研究助手（*）
問題描述：文學研究人員需要統(tǒng)計某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。試寫一個實現(xiàn)這一目標的文字統(tǒng)計系統(tǒng)，稱為“文學研究助手”?；疽螅河⑽男≌f存于一個文本文件中，待統(tǒng)計的詞匯集合要一次輸入完畢，即統(tǒng)計工作必須在程序的一次運行之后就全部完成。程序的輸出結果是每個詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在行的行號，格式自行設計, 結果保存到文件中。
提高要求：模式匹配選取kmp算法
測試數(shù)據(jù)：以你的c/c++/java源程序模擬英文小說，相應語言的保留字集作為待統(tǒng)計的詞匯集。
5．哈希表的設計與實現(xiàn)（*）
問題描述：針對某個單位電話號碼簿，設計一個哈希表，并完成相應的建表和查表程序?；疽螅涸O每個記錄有下列數(shù)據(jù)項：電話號碼、用戶名、住址。從鍵盤輸入各記錄，以用戶名為關鍵字建立哈希表，哈希函數(shù)用除留取余數(shù)法構造，采用線性探測法解決沖突。可以插入、查找、刪除并顯示給定用戶名的記錄，并計算查找長度, 哈希表保存到文件中。
測試數(shù)據(jù)：取某個單位電話號碼簿中的30個記錄。
提高要求：將電話號碼薄以文件形式保存到盤上，能夠按用戶名和電話號碼兩種形式建立哈希表并實現(xiàn)插入、查找、刪除表中元素的功能。
6．管道鋪設施工的最佳方案（*）
問題描述:需要在某個城市的n個小區(qū)鋪設管道，則在這n個小區(qū)之間鋪設n-1條管道即可，假設任意兩個居民區(qū)之間都可以架設管道，但由于地理環(huán)境的不同，所需經(jīng)費不同，選擇最優(yōu)的施工方案使總投資盡可能的少。
基本要求：輸入表示小區(qū)間關系的圖及每條管道的權值，選擇出n-1條管道, 使總投資最小。圖的信息輸入一次后, 保存到文件中, 選擇的n-1條管道輸出到顯示器的同時, 也保存于文件中。
測試用例：任意選擇一個圖，模擬小區(qū)間可能鋪設的管道及費用。提高要求：顯示原始圖及選擇n-1條管道后的圖。
7．安排教學計劃（**）
問題描述：大學的每個專業(yè)都要制定教學計劃。假設任何專業(yè)都有固定的學習年限，每學年含兩個學期，每學期的時間長度和學分上限值均相等。每個專業(yè)開設的課程都是確定的，而且課程在開設時間的安排上必須滿足先修關系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課程恰好占一個學期。試在這樣的前提下設計一個教學計劃編制程序。
基本要求：輸入?yún)?shù)包括學期總數(shù)，一學期的學分上限，每門課程的課程號、學分和直接先修課的課程號；允許兩種策略，一是使學生在各學期的學習負擔盡量均勻，二是使課程盡量集中在前幾個學期；若根據(jù)給定的條件問題無解，則報告適當?shù)男畔ⅲ駝t將教學計劃輸出到用戶指定的文件中。教學計劃的表格格式自行設定, 可以從鍵盤讀取數(shù)據(jù)也可以從文件讀取數(shù)據(jù), 結果保存到文件中。
測試數(shù)據(jù)：學期總數(shù)為6，學分上限為10，該專業(yè)共開設12門。以08級某專業(yè)必修課與選修課為例，選擇12門課程及相應學分，制定一個表明各門課程先后約束關系的有向圖。
提高要求：產(chǎn)生多種不同的方案，并使方案之間的差異盡可能地大。8．停車場管理程序(**)問題描述：設停車場內只有一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車在停車場內按車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先到達的第一輛車停放在車場的最北端），若車場內已停滿n輛汽車，則后來的汽車只能在門外的便道上等候，一旦有車開走，則排在便道上的第一輛車即可開入；當停車場內某輛車要離開時，在它之后開入的車輛必須先退出車場為它讓路，待該輛車開出大門外，其它車輛再按原次序進入車場，每輛停放在車場的車在它離開停車場時必須按它停留的時間長短交納費用。試為停車場編制按上述要求進行管理的模擬程序。
基本要求：每一組輸入數(shù)據(jù)包括三個數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車牌照號碼及到達或離去的時刻，對每一組輸入數(shù)據(jù)進行操作后的輸出數(shù)據(jù)為：若是車輛到達，則輸出汽車在停車場內或便道上的停車位置；若是車離去；則輸出汽車在停車場內停留的時間和應交納的費用（在便道上停留的時間不收費，單位時間的停車費用由用戶從鍵盤輸入）。
測試數(shù)據(jù)：設輸入數(shù)據(jù)為：（‘a(chǎn)’，1，5），（‘a(chǎn)’，2，10），（‘d’，1，15），（‘a(chǎn)’，3，20），（‘a(chǎn)’，4，25），（‘a(chǎn)’，5，30），（‘d’，2，35），（‘d’，4，40），（‘e’，0，0）。其中，‘a(chǎn)’表示到達；‘d’表示離去，‘e’表示輸入結束。
提高要求：設停車場有南、北兩個門，每個門都可以進、出車輛。9．計算表達式的值(**)問題描述：對于給定的一個表達式，表達式中可以包括常數(shù)、算術運行符（“+”、“-”、“*”、“/”）和括號，編寫程序計算表達式的值。
基本要求：從鍵盤輸入一個正確的中綴表達式，將中綴表達式轉換為對應的后綴表達式，計算后綴表達式的值。
測試數(shù)據(jù)：任意選取一個符合題目要求的表達式。提高要求：（1）對于表達式中的簡單錯誤，能夠給出提示；
（2）表達式中可以包括單個字母表示的變量。
10．設計huffman 編碼器與解碼器（***）
問題描述：利用哈夫曼編碼進行信息通訊可以大大提高信道的利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳輸數(shù)據(jù)預先編碼；在接受端將傳來的數(shù)據(jù)進行譯碼。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站編寫一個哈夫曼碼的編/譯碼系統(tǒng)。
基本要求：根據(jù)某字符文件統(tǒng)計字符出現(xiàn)頻度，構造huffman 樹，編制huffman編碼，并將給定字符文件編碼，生成編碼文件；再將給定編碼文件解碼，生成字符文件。（要求按二進制位表示編碼）測試數(shù)據(jù)：英文文件。
提高要求：用二進制表示編碼，生成二進制的編碼文件。11．銀行業(yè)務模擬（***）
問題描述：設銀行有四個服務窗口，一個等待隊列, 每個窗口均可以辦理存款、取款、掛失、還貸業(yè)務，每種業(yè)務所需的服務時間不同，客戶到達銀行后，先到打號機上打號，號票上包括到達時間、編號和需要辦理的業(yè)務，然后在銀行內等候, 當任一服務窗口空閑時,處理等候客戶中排在最前面的客戶的業(yè)務。寫一個上述銀行業(yè)務的模擬系統(tǒng),通過模擬方法求出客戶在銀行內逗留的平均時間和每個窗口辦理的客戶數(shù)及辦理的每種業(yè)務數(shù)。
基本要求：每個客戶到達銀行的時間和需要辦理的業(yè)務隨機產(chǎn)生，輸出一天客戶在銀行的平均逗留時間和每個窗口每天辦理的客戶數(shù)和每種業(yè)務數(shù)。
測試數(shù)據(jù)：營業(yè)時間為8小時，其他模擬量自行設定。12．程序源代碼的相似性（***）
問題描述：對于兩個c++語言的源程序代碼，用哈希表的方法分別統(tǒng)計兩個程序中使用c++語言關鍵字的情況，并最終按定量的計算結果，得出兩份程序的相似性。
基本要求：建立c++語言關鍵字的哈希表，統(tǒng)計在每個源程序中c++關鍵字出現(xiàn)的頻度, 得到兩個向量x1和x2，通過計算向量x1和x2的相對距離來判斷兩個源程序的相似性。
例如: 關鍵字 void int for char if else while do break class 程序1關鍵字頻度 4 3 0 4 3 0 7 0 0 2 程序2關鍵字頻度 4 2 0 5 4 0 5 2 0 1 x1=[4,3,0,4,3,0,7,0,0,2] x2=[4,2,0,5,4,0,5,2,0,1] 設s是向量x1和x2的相對距離，s=sqrt(∑(xi1-xi2)2)，當x1=x2時，s=0, 反映出可能是同一個程序；s值越大，則兩個程序的差別可能也越大。
測試數(shù)據(jù): 選擇若干組編譯和運行都無誤的c++程序，程序之間有相近的和差別大的，用上述方法求s, 對比兩個程序的相似性。
提高要求：建立源代碼用戶標識符表，比較兩個源代碼用戶標識符出現(xiàn)的頻度，綜合關鍵字頻度和用戶標識符頻度判斷兩個程序的相似性。
13．小型文本編輯器
問題描述：設計一個行編輯程序，使其具有通常行編輯器(如vi、edlin)應具備的基本功能。
基本要求：編輯器應具備對文本文件的查找、插人、刪除、修改、字符串替換、統(tǒng)計字數(shù)，統(tǒng)計行數(shù)等功能，對于超過一屏的長文件，應能夠分頁顯示，查找功能用字符串匹配算法實現(xiàn)。設計用戶接口命令，實現(xiàn)對文本的編輯。具體的編輯命令，可參考數(shù)據(jù)結構算法網(wǎng)絡教學平臺上提供的edlin、vi的命令集。
測試數(shù)據(jù)：任一文本文件。
提高要求：１.可以支持“* ”、“? ”等通配符；
２.支持復制、粘貼等功能
3.支持多文檔同時編輯；
提示：可以考慮用雙向鏈表實現(xiàn)，每一結點表示一行字符，注意每行字符不能超過255。14．小型英漢詞典
問題描述：設計一個英漢詞典，支持member(查找)、insert(插入)、delete(刪除)操作。
基本要求：實現(xiàn)字典的常用方法有：有序線性表（memeber用二分檢索實現(xiàn)）、avl樹（二叉搜索樹）、patricia trie、散列表等，任選一種方法實現(xiàn)字典的操作，查找單詞、插入單詞（插入時，先查找，找不到插入，找到提示用戶）、刪除單詞（刪除時，先查找，找到刪除，找不到提示用戶）。
測試數(shù)據(jù)：任一英文單詞。提高要求：選用兩種以上的方法實現(xiàn)字典的操作，并比較不同實現(xiàn)算法的時間復雜度和空間復雜度。
提示：字典可以自己建立，但必須按字母a~z建立26個文件，建議從網(wǎng)上下載，文件類型為txt。
備注：
1.每道題目后面的*號，表示題目的難度系數(shù)；對應的評定成績等級為及格（無*號）、中等（*號）、良好（**號）、優(yōu)秀（***號），學生完成題目的基本要求，即可得到程序設計部分的相應等級成績，完成題目提高要求，成績可以向上浮動，如果沒有完成基本要求，成績向下浮動，直至不及格。
2.所有題目均需用c++完成，不能用c或mfc。3.實驗班的學生原則上應選擇“*”號多的題目。4.每道題的選題人數(shù)不能超過3人
數(shù)據(jù)結構與算法課程設計題目答案篇三
2014/2015學年第一學期
《數(shù)據(jù)結構與算法課程設計》任務書
一、課程設計目的
數(shù)據(jù)結構與算法課程設計是《數(shù)據(jù)結構與算法》課程教學必不可缺的一個重要環(huán)節(jié)，它可加深學生對該課程所學內容的進一步的理解與鞏固，是將計算機課程與實際問題相聯(lián)接的關鍵步驟。通過課程設計，能夠提高學生分析問題、解決問題，從而運用所學知識解決實際問題的能力，因而必須給予足夠的重視。
2二、課程設計題目
2.1 棋盤覆蓋
【間題描述】
在一個2k×2k 個方格組成的棋盤中，恰有一個方格與其它方格不同，稱該方格為一特殊方格，且稱該棋盤為一特殊棋盤。在棋盤覆蓋問題中，要用圖示的4種不同形態(tài)的l型骨牌覆蓋給定的特殊棋盤上除特殊方格以外的所有方格，且任何2個l型骨牌不得重疊覆蓋。
【基本要求】
（1）輸入k以及特殊方格所在的行號dr和特殊方格的列號dc。
1（2）要求輸出每一步用什么形態(tài)l型骨牌覆蓋，覆蓋后得到的棋盤圖形。（3）如果輸出的結果只是用矩陣表示則為良好，用圖形表示則為優(yōu)。【測試數(shù)據(jù)】 【實現(xiàn)提示】
使用分治策略，把棋盤劃分成4個小棋盤，然后用一個l型骨牌覆蓋將這4個小棋盤變?yōu)槎季哂刑厥夥礁竦钠灞P。
2.2 hanoi塔問題（*）
【問題描述】
設a，b，c是三個塔座。開始時，在塔座a上有一疊共n個圓盤，這些圓盤自下而上，由大到小地疊放在一起，各圓盤從小到大編號為1,2,?,n，要求將塔座a上的這一疊圓盤移到塔座b上，并仍按同樣順序疊置。在移動圓盤時應遵守以下移動規(guī)則：
規(guī)則（1）每次只能移動一個圓盤；
規(guī)則（2）任何時刻都部允許將較大的圓盤壓在較小的圓盤之上；
規(guī)則（3）在滿足移動規(guī)則（1）和（2）的前提下，可將圓盤移至a，b，c中任一塔座上。
【基本要求】
（1）設計出hannoi塔游戲，供用戶玩；（2）提供正確的搬運方法?！緦崿F(xiàn)說明】
正確的搬運方法使用遞歸方法實現(xiàn)?！緶y試數(shù)據(jù)】
2.3 矩陣連乘問題
【問題描述】
給定n個矩陣{a1,a2,...,an},其中ai和ai?1是可乘的，i＝1,2,?,n-1?？疾爝@n個矩陣的連乘積a1a2,...,an，通過加括號方式，找出矩陣乘積所需的最少計算量的方法。
【基本要求】
輸入每個矩陣的行和列，要求輸出最少計算量的矩陣乘積方法，如(a1(a2(a3a4)))?！緦崿F(xiàn)說明】 使用動態(tài)規(guī)劃方法。
2.4 多邊形游戲（*）
【問題描述】
多邊形游戲是一個單人玩的游戲，開始時有一個由n個頂點構成的多邊形。每個頂點被賦予一個整數(shù)值，每條邊被賦予一個運算符“＋”或“*”。所有邊依次用整數(shù)從1到n編號。
游戲第1步，將一條邊刪除。隨后n-1步按以下方式操作：
選擇一條邊e及由e連接著的2個頂點v1和v2；
用一個新的頂點取代邊e及用e連接著的2個頂點v1和v2，將由頂點v1和v2的整數(shù)值通過邊e上的運算得到的結果賦予新頂點。
最后，所有邊都被刪除，游戲結束。游戲的得分就是所剩頂點上的整數(shù)值?！净疽蟆?BR> 設計該游戲供用戶玩；
對于給定的多邊形，給出最高得分計算。【實現(xiàn)說明】 使用動態(tài)規(guī)劃方法。
2.5 0-1背包問題
【問題描述】
給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為c。問應如何選擇裝入背包種的物品，使得裝入背包種物品的總價值最大。
【基本要求】
使用動態(tài)規(guī)劃、回溯法以及分支界限三種方法實現(xiàn)?！緶y試數(shù)據(jù)】 【實現(xiàn)提示】
2.6 排序方法
【問題描述】
給定n個元素，要求對這n個元素進行排序?！净疽蟆?BR> 使用多種排序方法，越多越好；
比較每種排序方法的時間復雜度和空間復雜度?！緶y試數(shù)據(jù)】 【實現(xiàn)提示】
2.7 哈夫曼編碼譯碼器
【問題描述】
設計一個哈夫曼編碼/譯碼系統(tǒng)，對一個文本文件中的字符進行哈夫曼編碼，生成編碼文件
（壓縮文件，）；反過來，可將一個壓縮文件譯碼還原為一個文本文件(.txt)。
【基本要求】
（1）輸入一個待壓縮的英文文本文件，統(tǒng)計文本文件中各字符的個數(shù)作為權值，生成哈夫曼樹；
（2）將文本文件利用哈夫曼樹進行編碼，生成壓縮文件（后綴名cod）（3）輸入一個待解壓的壓縮文件名稱,并利用相應的哈夫曼樹將編碼序列譯碼?！緦崿F(xiàn)說明】
（1）在構造哈夫曼樹時，可以利用不同的線性表存放二叉樹：用順序表、單鏈表、5 循環(huán)單鏈表、雙向鏈表、循環(huán)雙鏈表；
（2）在構造哈夫曼樹時，可以利用優(yōu)先隊列存放二叉樹：順序隊列、鏈隊列（可以是單鏈表、雙鏈表等，還可以用靜態(tài)結構去實現(xiàn)），可以分別在入隊列或出隊列時實現(xiàn)優(yōu)先級；
（3）二叉樹本身也可以用靜態(tài)數(shù)組模擬；（4）使用貪心算法
2.8 迷宮問題（*）
【問題描述】
設計一個迷宮并給出正確走法。如： *** *** *** *** *** *** *** 其中0表示可以走，1表示不能走，每一步只能向上下左右移動。【基本要求】
（1）給出迷宮的正確走法，包括沒有解的情況；（2）要求界面友好?！緶y試數(shù)據(jù)】
【實現(xiàn)提示】 使用回溯的方法。
2.9 繼續(xù)郵資問題
【問題描述】
假設某國家發(fā)行了n種不同面值的郵票，并且規(guī)定每張信封上最多只允許貼m張郵票。連續(xù)郵資問題要求對于給定的n和m的值，給出郵票面值的最佳設計，在1張信封上貼出從郵資1開始，增量為1的最大連續(xù)郵資區(qū)間。
【基本要求】
輸入任意的m和n都能設計出最佳的方案，并給出連續(xù)郵資區(qū)間?！緦崿F(xiàn)說明】 【測試數(shù)據(jù)】
2.10 圖的m著色問題
【問題描述】
給定一個地圖，要求給出該地圖的最少著色方案 【基本要求】
（1）把地圖以及最少著色的方案顯示出來則為良好。（2）有友好的界面則為優(yōu) 【實現(xiàn)說明】
2.11 猜數(shù)字游戲（*）
【問題描述】
孩子想1個由4種顏色組成的序列（4種顏色不一定完全不同）。每種顏色只能是6種顏色之一。方便起見，我們用數(shù)字1到6表示6種顏色。
計算機必須根據(jù)孩子的回答找出孩子所想的顏色序列。計算機在屏幕上顯示一個序列，孩子用鍵盤回答以下兩個問題：
猜對的顏色中位置不對的有幾個？ 猜對的顏色中位置對的有幾個？ 【基本要求】
編程使至多6次問答后猜出序列，如果辦不到，至多10次問答后猜出序列?！緦崿F(xiàn)說明】 【測試數(shù)據(jù)】
如孩子想的是4655 計算機猜想 顏色對位置錯的數(shù)目 顏色和位置都對的數(shù)目 1234 1 0 5156 2 1 6165 1 1 5625 1 2 5653 1 2 8 4655 0 4 2.12 大整數(shù)計算器
【問題描述】
設計一個計算器實現(xiàn)兩個任意長得整數(shù)的加、減、乘、除?！净疽蟆?BR> 設計一個實現(xiàn)任意長的整數(shù)進行四則運算的演示程序，要求輸入任意長的整數(shù)進行四則運算，都能得到精確的結果。
【實現(xiàn)說明】
2.13 查找搜索技術
【問題描述】
給定任意的數(shù)組，對于給定的數(shù)，查找是否在數(shù)組中，如果在，則返回給定數(shù)在數(shù)組的位置，不在則返回不在信息。
【基本要求】
（1）使用多種搜索方法，越多越好，其中二分搜索技術、線性時間選擇是必須的；（2）比較每種排序方法的時間復雜度和空間復雜度?！緦崿F(xiàn)說明】
2.14 tom,jerry和奶酪（*）
【問題描述】
貓tom和鼠jerry同住在一矩陣地窖中。貓要吃鼠，鼠要吃奶酪。地窖中有2種地磚：有洞磚與無洞磚。一個洞足以讓鼠鉆入，但貓不能。
以菜單形式完成以下任務：
隨機地生成一個地窖，并給貓、鼠和奶酪安排一個位置。如： fffffffffffffff fppppppppppppcf fhfffffffffffpf fpppjhppppppppf fpffffffpffffff fpppppppppptppf fffffffffffffff 其中c表示貓，j表示鼠，h表示洞，f表示不能通行（2）鼠先行，貓后行。兩者皆滿足以下規(guī)定： 1）必須上、下、左或右移動 2）鼠必須走1步（穿過p或h）3）貓必須走1或2步（穿過p）
（3）當鼠吃到奶酪或貓抓到鼠時，游戲結束。【基本要求】 【實現(xiàn)說明】
2.15 布線問題
【問題描述】
印刷電路板將布線區(qū)域劃分成n×m個方格陣列，精確的電路布線問題要求確定連接方格a的中點到方格b的中點的最短布線方案。在布線時，電路只能沿著直線或直角布線。為了避免線路相交，已布了線的方格做了封鎖標記，其他線路不允許穿過被封鎖的方格。
【基本要求】（1）解決題目的問題（2）提供友好的界面 【實現(xiàn)說明】 使用分支限界法。
2.16 魔方工具包（*）
【問題描述】
一個魔方是一個由3×3×3個小立方體組成的立方體。最初立方體的6個面分別涂上不同顏色，我們稱之為“最初魔方”。魔方的每一面上的3×3個小立方體組成它的一層。
魔方所能見到的每一層（6個面）都能旋轉90，180，220或360度。所有層的旋轉軸都垂直于面且通過其中心。旋轉的結果是另一個魔方，它的所有面的顏色都改變了。
現(xiàn)在我們用字符來代替顏色：u=上，d=下，f=前，b=后，l=左，r=右。任何一個序列的旋轉都能表示成{u,r,f,b,l,d}中一些字符組成的字符串，其中每個字符表示它所 11 指定的面順時針旋轉90度。
【基本要求】
（1）編程完成以下3個任務（菜單形式），你可以假設任何輸入的字串長度都<=35。你的算法能處理非法輸入的情況，如： 輸入 輸出 l l ll ll lll lll llll “”(空串 lllll l llrrrffffrlb lllb hello “error”
（2）判斷輸入的2個字串的旋轉結果是否相同。如 輸入一 輸入二 輸出 ru ur no rrffrrffrrffrrff ffrrffrr yes rrffrrffrrffrrff rrffrrff no（3）求出輸入字符串至少須使用幾次才能將魔方轉回到“最初魔方”（一定大于0）輸入 輸出 l 4 12 dd 2 bulb 36 ruf 80 bluff 180 【實現(xiàn)說明】
2.17 圖的建立與輸出
【問題描述】
建立圖的存儲結構（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學生可以任選兩種類型），能夠輸入圖的頂點和邊的信息，并存儲到相應存儲結構中，而后輸出圖的鄰接矩陣。
【基本要求】
給出圖的深度優(yōu)先和廣度優(yōu)先遍歷算法，并給出遍歷過程的動態(tài)演示效果 【實現(xiàn)說明】
無
2.18 圖的建立與輸出
【問題描述】
建立圖的存儲結構（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學生可以任選兩種類型），能夠輸入圖的頂點和邊的信息，并存儲到相應存儲結構中，而后輸出 13 圖的鄰接矩陣。
【基本要求】
給出圖的深度優(yōu)先和廣度優(yōu)先遍歷算法，并給出遍歷過程的動態(tài)演示效果?！緦崿F(xiàn)說明】
無
2.19 以隊列實現(xiàn)的仿真技術預測理發(fā)館的經(jīng)營狀況（*）
【問題描述】
理發(fā)館一天的工作過程如下：
1)理發(fā)館有n把理發(fā)椅，可同時為n位顧客進行理發(fā)。
2)理發(fā)師分三個等級（一級、二級、三級），對應不同的服務收費。3)當顧客進門時，需選擇某級別理發(fā)師，只要該級別的理發(fā)師有空椅，則可立即坐下理發(fā)，否則需排隊等候。
4)一旦該級別的理發(fā)師有顧客理發(fā)完離去，排在隊頭的顧客便可開始理發(fā)。5)若理發(fā)館每天連續(xù)營業(yè)t分鐘，求
（1）一天內顧客在理發(fā)館內的平均逗留時間；（2）顧客排隊等候理發(fā)的隊列長度平均值；
（3）營業(yè)時間到點后仍需完成服務的收尾工作時間；（4）統(tǒng)計每天的營業(yè)額；
（5）統(tǒng)計每天不同級別理發(fā)師的創(chuàng)收。
【基本要求】
1)模擬理發(fā)館一天的工作過程：必須采用事件驅動的離散模型（參考教科書3.5節(jié)離散事件模擬p65）；
2)每個顧客到達和下一顧客到達時間的間隔應是隨機的； 3)理發(fā)師編號、理發(fā)師級別和每天的營業(yè)時間由用戶輸入；
4)某顧客挑選某一個級別的理發(fā)師而不得時，選第一個隊列排隊等待 ；
5)每個顧客進門時將生成三個隨機數(shù):(1)durtime:進門顧客理發(fā)所需服務時間（簡稱：理發(fā)時間）；(2)intertime:下一顧客將到達的時間間隔（簡稱：間隔時間）；(3)select:服務選項。
6)服務收費：應包含服務時間和理發(fā)師級別兩個因素。
7)除了輸出統(tǒng)計的數(shù)據(jù)外，還需要顯示理發(fā)館的狀態(tài)，可以采用文本方式（橫向顯示每張椅編號、理發(fā)師級別。縱向表示等待該理發(fā)師理發(fā)的排隊長度）?！緦崿F(xiàn)說明】
用戶輸入每位理發(fā)師編號、級別號和營業(yè)的時間，結合隨機數(shù)進行測試。
2.20 防抄襲管理系統(tǒng)（*）
【問題描述】
對于給定的文檔，如word文檔，txt文檔等，找出文檔的相似度。【基本要求】
（1）要求找出給定的兩個文檔的相似度以及標出相似的地方（1:1）；（2）要求找出給定的一個文檔與給定的文件夾的所有文檔的相似度，以及標出相似的地方(1:n)（3）要求找出給定的文件夾下面所有文檔的相似度(n:n)?！緦崿F(xiàn)說明】
給定相似文檔進行測試。
2.21.設計一個停車場管理系統(tǒng)，模擬停車場的運作
設計要求：通過此程序具備以下功能：
1、要求以棧模擬停車場，以隊列模擬車場 15 外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進行模擬管理；
2、要求處理的數(shù)據(jù)元素包括三個數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車牌照號碼及到達或離去的時刻；
3、該系統(tǒng)完成以下功能：若是車輛到達，則輸出汽車在停車場內或便道上的停車位置；若是車離去，則輸出汽車在停車場內停留的時間和應交納的費用（在便道上停留的時間不收費）；
4、要求棧以順序結構實現(xiàn)，隊列以鏈表實現(xiàn)。
2.22． 赫夫曼編碼
設計要求：自己找一篇不少于200個單詞的英文文章，分析該文章中每一個字符的出現(xiàn)概率（包括標點符號，區(qū)分大小寫），根據(jù)分析結果對文章中每一個字符進行赫夫曼編碼，并將編碼原則儲于一個獨立的文本文件中。最后，根據(jù)這個編碼原則，將英文文章轉換為01 串存儲于一個文本文件中，再編寫一個解碼程序，將編碼解碼為原文件。如：英文文章為 aaabbc 則編碼規(guī)則為 a-----0 b-----10 c-----11 英文文章將被轉化為 000101011 2.23.并查集：檢查網(wǎng)絡
題目要求：給定一個計算機網(wǎng)絡以及機器間的雙向連線列表，每一條連線允許兩端的計算機進行直接的文件傳輸，其他計算機間若存在一條連通路徑，也可以進行間接的文件傳輸。請寫出程序判斷：任意指定兩臺計算機，它們之間是否可以進行文件傳輸？ 輸入要求：輸入若干測試數(shù)據(jù)組成。對于每一組測試，第1行包含一個整數(shù)n（≤10000），即網(wǎng)絡中計算機的總臺數(shù)，因而每臺計算機可用1到n之間的一個正整數(shù)表示。接下來的幾行輸入格式為i c1 c2或者 c或者c c1c2或者s，其中c1和c2是兩臺計算機的 16 序號，i表示在c1和c2間輸入一條連線，c表示檢查c1和c2間是否可以傳輸文件，s表示該組測試結束。
當n為0時，表示全部測試結束，不要對該數(shù)據(jù)做任何處理。
輸出要求：對每一組c開頭的測試，檢查c1和c2間是否可以傳輸文件，若可以，則在一行中輸出“yes”，否則輸出“no”。
當讀到s時，檢查整個網(wǎng)絡。若網(wǎng)絡中任意兩機器間都可以傳輸文件，則在一行中輸出“the network is connected.”，否則輸出“there are k components.”,其中k是網(wǎng)絡中連通集的個數(shù)。
兩組測試數(shù)據(jù)之間請輸出一空行分隔。
2.24.教學計劃編制問題（圖的應用）
[問題描述] 大學的每個專業(yè)都要制定教學計劃。假設任何專業(yè)都有固定的學習年限，每學年含兩學期，每學期的時間長度和學分上限值均相等。每個專業(yè)開設的課程都是確定的，而且課程在開設時間的安排必須滿足先修關系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學期。試在這樣的前提下設計一個教學計劃編制程序。[實現(xiàn)提示]
1、輸入?yún)?shù)應包括：學期總數(shù)，一學期的學分上限，每門課的課程號（可以是固定占3位的字母數(shù)字串）、學分和直接先修課的課程號。
2、應允許用戶指定下列兩種編排策略之一：一是使學生在各學期中的學習負擔盡量均勻；二是使課程盡可能地集中在前幾個學期中。
3、若根據(jù)給定的條件問題無解，則報告適當?shù)男畔ⅲ环駝t將教學計劃輸出到用戶指定的文件中。計劃的表格格式可以自己設計。
4、可設學期總數(shù)不超過12，課程總數(shù)不超過100。如果輸入的先修課程號不在該專業(yè)開設的課程序列中，則作為錯誤處理。
============================= 17 2.25.藥品銷售統(tǒng)計系統(tǒng)（排序應用）
【問題描述】
設計一系統(tǒng)，實現(xiàn)醫(yī)藥公司定期對銷售各藥品的記錄進行統(tǒng)計，可按藥品的編號、單價、銷售量或銷售額做出排名?！緦崿F(xiàn)提示】
在本設計中，首先從數(shù)據(jù)文件中讀出各藥品的信息記錄，存儲在順序表中。各藥品的信息包括：藥品編號、藥名、藥品單價、銷出數(shù)量、銷售額。藥品編號共4位，采用字母和數(shù)字混合編號，如：a125，前一位為大寫字母，后三位為數(shù)字，按藥品編號進行排序時，可采用基數(shù)排序法。對各藥品的單價、銷售量或銷售額進行排序時，可采用多種排序方法，如直接插入排序、冒泡排序、快速排序，直接選擇排序等方法。在本設計中，對單價的排序采用冒泡排序法，對銷售量的排序采用快速排序法，對銷售額的排序采用堆排序法。
藥品信息的元素類型定義： typedef struct node { char num[4];/*藥品編號*/ char name[10];/*藥品名稱*/ float price;/*藥品單價*/ int count;/*銷售數(shù)量*/ float sale;/*本藥品銷售額*/ }datatype;存儲藥品信息的順序表的定義： typedef struct { datatype r[maxsize];int length;}sequenlist;
2.26梯運行仿真程序
[問題描述] 辦公大樓有若干層（例如，十層），每層有電梯，同時有步行樓梯；
全樓有若干部（例如，不多于10部）電梯同時供使用，電梯容量為24人，速度每上下一層需5秒，在某一層停下至少15秒。其運行狀態(tài)可分：向上、向下、停止，當前乘客數(shù)，當前所在層數(shù)。它設有一個“按鈕數(shù)組”，例如第五層的按鈕按下，意味著有乘客在第5層到達目標層，等等。在樓的每一層，有電梯數(shù)，有按鈕表示有人等待向上或向下，由若干人在等待，有若干電梯在本層停下，等等。
在大樓中（包括進出）的總人數(shù)不超過500 人，每個人站在電梯前有個目標層，他有一個最大的忍受等待時間，因為他可以選擇電梯或是步行走樓梯，等等。
還有下面若干假設：在每個時間段要進大樓的人數(shù)在0～199 之間隨機取值；
用電梯的每個人的目標層在1～10 之間取值；一個人在進電梯或改走樓梯之前的等待時間在180～360 秒范圍內隨機發(fā)生；一個人到達目標層后第二次再乘電梯中間的工作時間在400～6600 秒間隨機取值。[基本要求] 編寫一個程序，模擬辦公大樓中全部電梯的工作過程。這個仿真程序可以用來監(jiān)測系統(tǒng)運行情況，改善大樓管理，它也可以看成是一種游戲程序。
2.27國交通咨詢模擬
[問題描述]
處于不同目的的旅客對交通工具有不同的要求。例如，因公出差的旅客希望在旅 途中的時間盡可能的短，出門旅游的游客則期望旅費盡可能省，而老年旅客則要求中轉次數(shù)最少。編制一個全國城市間的交通咨詢程序，為旅客提供最優(yōu)決策的交通咨詢。
[基本要求]
（1）提供對城市信息進行編輯（如：添加或刪除）的功能；
（2）城市之間有兩種交通工具：火車或飛機，提供對全國城市交通圖和列車時刻表及飛機航班表進行編輯的功能。（信息的輸入方式可以是文件輸入和鍵盤輸入兩種方式）
（3）提供兩種最優(yōu)決策：最快到達和最省錢到達。（選作：旅途中轉次數(shù)最少的最優(yōu)決策）
（4）旅途中耗費的總時間應該包括中轉站的等候時間。
（5）咨詢以用戶和計算機的對話方式進行。
a）由用戶輸入起始站、終點站、最優(yōu)決策原則和交通工具；
b）輸出信息：最快需要多長時間才能到達或者最少需要多少旅費才能到達，并詳 細說明依次于何時乘坐哪一趟列車或哪一次班機到何地。
三、課程設計的基本要求
1．問題分析和任務定義。根據(jù)設計題目的要求，充分地分析和理解問題，明確問題要求做什么？（而不是怎么做？）限制條件是什么？
2．邏輯設計。對問題描述中涉及的操作對象定義相應的數(shù)據(jù)類型，并按照以數(shù)據(jù)結構為中心的原則劃分模塊，定義主程序模塊和各抽象數(shù)據(jù)類型。邏輯設計的結果應寫出每個抽象數(shù)據(jù)類型的定義(包括數(shù)據(jù)結構的描述和每個基本操作的功能說明)，各個主要模塊的算法，并畫出模塊之間的調用關系圖。
3．詳細設計。定義相應的存儲結構并寫出各函數(shù)的偽碼算法。在這個過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結構清晰、合理、簡單和易于調試，抽象數(shù)據(jù)類型的實現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可能明確具體。詳細設計的結果是對數(shù)據(jù)結構和基本操作作出進一步的求精，20 寫出數(shù)據(jù)存儲結構的類型定義，寫出函數(shù)形式的算法框架。
4．程序編碼。把詳細設計的結果進一步求精為程序設計語言程序。同時加入一些注解和斷言，使程序中邏輯概念清楚。
5．程序調試與測試。采用自底向上，分模塊進行，即先調試低層函數(shù)。能夠熟練掌握調試工具的各種功能，設計測試數(shù)據(jù)確定疑點，通過修改程序來證實它或繞過它。調試正確后，認真整理源程序及其注釋，形成格式和風格良好的源程序清單和結果。
6．結果分析。程序運行結果包括正確的輸入及其輸出結果和含有錯誤的輸入及其輸出結果。算法的時間、空間復雜性分析。
7．編寫課程設計報告并提交相關內容
設計最終需提交的內容包括：
a）課程設計報告（1份，a4紙打印，同時包括一份電子版）報告要求版面清晰，格式規(guī)范，否則重新編寫。報告內容要求包括：
（1）問題的概述、分析及研究意義；（2）數(shù)據(jù)結構的邏輯設計和物理存儲設計；（3）重要算法的設計、流程描述或偽代碼描述；
（4）數(shù)據(jù)結構的時空復雜性分析以及重要算法的復雜性分析；
（5）程序最終實現(xiàn)結果（包括重點結果界面的抓取，能過說明問題的重要實驗結果數(shù)據(jù)的打印或其可視化結果等）。
（6）參考文獻（如果需要）。
（7）附錄部分附上關鍵數(shù)據(jù)結構的定義及關鍵算法的源代碼。
b）完整的程序系統(tǒng)（電子方式提交）
能夠對輸入產(chǎn)生相應的輸出，同時盡量的完成可視化演示。
該部分包括源代碼和可執(zhí)行文件兩個部分（提交的時候需清楚的注明個人姓名，班級）。
c）源程序文檔（電子方式提交）
源程序代碼要求結構清晰、可讀性好。應對源程序中的類說明（如果采用面向對象方法設計），函數(shù)說明，接口說明，關鍵變量說明等進行注釋；源程序要進行適當?shù)目s進編排。
d）答辯報告（編寫power point答辯報告，電子方式提交）要求突出重點，思路清晰。同時就此報告準備答辯。
e）所有以電子方式提交的文件全部存在一個目錄中，并對其進行壓縮（用winrar或winzip均 21 可），壓縮后的文件按規(guī)定格式進行命名，命名格式為：學號+（）。8．每位同學只能選擇一個題目并完成
四、評分標準
1、基本功能：
50分。
通過功能的實現(xiàn)情況、界面的完成情況、軟件的實現(xiàn)情況進行評分。
2、設計報告及使用說明書： 20分 按照報告的要求進行評分。
3、回答問題：
4、平時考勤：
5、核分標準：
15分 15分 100分
（90~100為優(yōu)、80~89為良、70~79為中、60~69為及格、，60以下為不及格）
五、參考書目
嚴蔚敏.《數(shù)據(jù)結構》（c語言版）.清華大學出版社 劉玉龍．《數(shù)據(jù)結構與算法》.電子工業(yè)出版社.嚴蔚敏等《數(shù)據(jù)結構題集》（c語言版）.清華大學出版社
徐孝凱.數(shù)據(jù)結構實用教程（c/c++描述）.北京:清華大學出版社.陳慧南.數(shù)據(jù)結構（使用c++語言描述）.南京:東南大學出版社.殷人昆, 陶永雷, 謝若陽等.數(shù)據(jù)結構（用面向對象方法與c++描述）.北京:清華大學出版社.22
數(shù)據(jù)結構與算法課程設計題目答案篇四
數(shù)據(jù)結構課程設計題目 以下8個題目任選其一。
1．排序算法比較
利用隨機函數(shù)產(chǎn)生30000個隨機整數(shù)，利用插入排序、起泡排序、選擇排序、快速排序、堆排序、歸并排序等排序方法進行排序，并且（1）統(tǒng)計每一種排序上機所花費的時間。
（2）統(tǒng)計在完全正序，完全逆序情況下記錄的比較次數(shù)和移動次數(shù)。（3）比較的指標為關鍵字的比較次數(shù)和記錄的移動次數(shù)(一次記錄交換計為3次移動)。
（4）對結果作簡單分析，包括對各組數(shù)據(jù)得出結果波動大小的解釋。2．圖的深度遍歷
對任意給定的圖（頂點數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用堆棧的五種基本運算（清空堆棧、壓棧、彈出、取棧頂元素、判棧空）實現(xiàn)圖的深度優(yōu)先搜索遍歷。畫出搜索順序示意圖。3．圖的廣度遍歷
對任意給定的圖（頂點數(shù)和邊數(shù)自定），建立它的鄰接表并輸出，然后利用隊列的五種基本運算（置空隊列、進隊、出隊、取隊頭元素、判隊空）實現(xiàn)圖的廣度優(yōu)先搜索遍歷。畫出搜索順序示意圖。4．二叉樹的遍歷
對任意給定的二叉樹（頂點數(shù)自定）建立它的二叉鏈表存貯結構，并利用棧的五種基本運算（置空棧、進棧、出棧、取棧頂元素、判?？眨崿F(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ù)據(jù)：
（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ù)據(jù)：
（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）根據(jù)字符頻率構造哈夫曼樹，并給出每個字符的哈夫曼編碼。
（4）用哈夫曼編碼來存儲文件，并和輸入文本文件大小進行比較，計算文件壓縮率
（5）根據(jù)相應哈夫曼編碼，對編碼后的文件進行解碼，恢復成ascii編碼的英文短文后輸出。
分析及設計步驟（供參考）
1.分析問題，給出數(shù)學模型，設計相應的數(shù)據(jù)結構。
1)分析問題特點，用數(shù)學表達式或其它形式描述其數(shù)學模型。2)選擇能夠體現(xiàn)問題本身特點的一種或幾種邏輯結構。
3)依據(jù)邏輯結構和問題特點，設計并選擇相應的存儲結構（順序存儲結構和鏈式存儲結構對應的算法實現(xiàn)有區(qū)別）。
2.算法設計
1)確定所需模塊：對于復雜的程序設計，要充分利用模塊化程序設計方法和面向對象思想，自頂向下，逐步細化。
2)各子模塊功能描述：給出主要模塊的算法描述，用流程圖或偽代碼表示。3)模塊之間的調用關系：給出算法各模塊之間的關系圖示。3.上機實現(xiàn)程序
為提高工作效率，充分利用上機調試時間，在上機之前應列出程序清單。
4.用有代表性的各種測試數(shù)據(jù)去驗證算法及程序的正確性
5.算法分析及優(yōu)化
經(jīng)過上機調試，源程序運行正確，并且實現(xiàn)算法要求的功能，解決課程設計題目中給出的問題后，分析算法的時間復雜度和空間復雜度，如有可能對程序進行優(yōu)化改進。
課程設計報告范例（參考）
約瑟夫環(huán)問題。
問題描述：設編號為1,2,…,n(n>0)個人按順時針方向圍坐一圈，每人持有一個正整數(shù)密碼。開始時任意給出一個報數(shù)上限值m，從第一個人開始順時針方向自1起順序報數(shù)，報到m時停止報數(shù)，抱m的人出列，將他的密碼作為新的m值，從他在順時針方向上的下一個人起重新自1起順序報數(shù)；如此下去，直到所有人全部出列為止。要求設計一個程序模擬此過程，并給出出列人的編號序列?；疽螅?BR> （1）初始報數(shù)上限值m和測試數(shù)據(jù)在程序中確定；（2）用帶頭結點的單循環(huán)鏈表作數(shù)據(jù)元素的存儲結構；（3）把帶頭結點的單循環(huán)鏈表作為抽象數(shù)據(jù)類型設計。測試數(shù)據(jù)：
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ù)據(jù)類型sclinlist，其中包括基本操作的函數(shù)有：初始化操作函數(shù)、插入一個結點操作函數(shù)、刪除一個結點操作函數(shù)、取一個結點數(shù)據(jù)操作函數(shù)和判表是否非空操作函數(shù)。該抽象數(shù)據(jù)類型文件名為sclinlist.h。
（2）void sclldeleteafter(sclnode *p)，其功能是刪除帶頭結點的單循環(huán)鏈表中指針p所指結點的下一個結點。這是對帶頭結點的單循環(huán)鏈表抽象數(shù)據(jù)類型sclinlist，補充本問題需要的一個操作函數(shù)。（3）void jesephring(sclnode *head, int m)，其功能是對帶頭結點的單循環(huán)鏈表head,以m為初始報數(shù)上限值實現(xiàn)問題要求。
（4）void main(void)，主函數(shù)，功能是給出測試數(shù)據(jù)值，建立測試數(shù)據(jù)值的帶頭結點單循環(huán)鏈表，調用jesephring()函數(shù)實現(xiàn)問題要求。數(shù)據(jù)結構：
（1）數(shù)據(jù)類型datatype定義如下： typedef struct { int number;int cipher;} datatype;
（2）帶頭結點單循環(huán)鏈表抽象數(shù)據(jù)類型sclinlist。
（3）帶頭結點單循環(huán)鏈表抽象數(shù)據(jù)類型的結點結構定義如下：
typedef struct node { datatype data;struct node *next;} sclnode;源程序：
源程序存放在兩個文件中，文件sclinlist.h是帶頭結點單循環(huán)鏈表抽象數(shù)據(jù)類型，文件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ù)據(jù)元素值*/ { 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ù)據(jù)類型datatype*/ #include “sclinlist.h” /*包含sclinlist抽象數(shù)據(jù)類型*/ 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->);m = curr->;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ù)據(jù)結構與算法課程設計題目答案篇五
數(shù)據(jù)結構課程設計題目
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)可以按學校編號或名稱、學?？偡帧⒛信畧F體總分排序輸出；
4)可以按學校編號查詢學校某個項目的情況；可以按項目編號查詢取得前三或前五名的學校。5)數(shù)據(jù)存入文件并能隨時查詢
6)規(guī)定：輸入數(shù)據(jù)形式和范圍：可以輸入學校的名稱，運動項目的名稱
輸出形式：有合理的提示，各學校分數(shù)為整形
界面要求：有合理的提示，每個功能可以設立菜單，根據(jù)提示，可以完成相關的功能要求。
存儲結構：學生自己根據(jù)系統(tǒng)功能要求自己設計，但是要求運動會的相關數(shù)據(jù)要存儲在數(shù)據(jù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關內容在c語言程序設計的書上，請自學解決）請在最后的上交資料中指明你用到的存儲結構；
測試數(shù)據(jù)：要求使用
1、全部合法數(shù)據(jù)；
2、整體非法數(shù)據(jù)；
3、局部非法數(shù)據(jù)。進行程序測試，以保證程序的穩(wěn)定。測試數(shù)據(jù)及測試結果請在上交的資料中寫明；
2.飛機訂票系統(tǒng)（限1 人完成）
任務：通過此系統(tǒng)可以實現(xiàn)如下功能：
錄入：
可以錄入航班情況（數(shù)據(jù)可以存儲在一個數(shù)據(jù)文件中，數(shù)據(jù)結構、具體數(shù)據(jù)自定）
查詢：
可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛抵達城市，航班票價，票價折扣，確定航班是否滿倉）；
可以輸入起飛抵達城市，查詢飛機航班情況；
訂票：（訂票情況可以存在一個數(shù)據(jù)文件中，結構自己設定）
可以訂票，如果該航班已經(jīng)無票，可以提供相關可選擇航班；
退票： 可退票，退票后修改相關數(shù)據(jù)文件；
客戶資料有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號。
修改航班信息：
當航班信息改變可以修改航班數(shù)據(jù)文件
要求：
根據(jù)以上功能說明，設計航班信息，訂票信息的存儲結構，設計程序完成功能；
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ù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標點符號。
輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出“全部字母數(shù)”、“數(shù)字個數(shù)”、“空格個數(shù)”、“文章總字數(shù)”（3）輸出刪除某一字符串后的文章；
4.宿舍管理查詢軟件（限1 人完成）
1)任務：為宿舍管理人員編寫一個宿舍管理查詢軟件, 程序設計要求： a.采用交互工作方式
b.建立數(shù)據(jù)文件，數(shù)據(jù)文件按關鍵字（姓名、學號、房號）進行排序(冒泡、選擇、插入排序等任選一種)2)查詢菜單:(用二分查找實現(xiàn)以下操作)a.按姓名查詢
b.按學號查詢
c.按房號查詢
3)打印任一查詢結果（可以連續(xù)操作）
5.校園導航問題（限1 人完成）
設計要求：設計你的學校的平面圖，至少包括10個以上的場所，每兩個場所間可以有不同的路，且路長也可能不同，找出從任意場所到達另一場所的最佳路徑（最短路徑）。
6.教學計劃編制問題（限1 人完成）
設計要求：針對計算機系本科課程，根據(jù)課程之間的依賴關系（如離散數(shù)學應在數(shù)據(jù)結構之前開設）制定課程安排計劃，并滿足各學期課程數(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(wèi)，生成一棵二叉排 序樹t； 2)對二叉排序樹t作中序遍歷，輸出結果；
3)輸入元素x,查找二叉排序樹t,若存在含x的結點,則刪除該結點,并作中序遍歷(執(zhí)行操作2)；否則輸出信息“無x”；
12.最小生成樹問題（限1 人完成）
設計要求：在n個城市之間建設網(wǎng)絡，只需保證連通即可，求最經(jīng)濟的架設方法。存儲結構采用多種。求解算法多種。
13.通訊錄的制作（限1 人完成）
設計目的：用〈〈數(shù)據(jù)結構〉〉中的雙向鏈表作數(shù)據(jù)結構，結合c語言基本知識。編寫一個通訊錄管理系統(tǒng)。以把所學數(shù)據(jù)結構知識應用到實際軟件開發(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ù)據(jù)存放在數(shù)據(jù)文件(，位于執(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è)務?！净疽蟆?BR> 1)每種書的登記內容包括書號、書名、著作者、現(xiàn)存量和庫存量； 2)對書號建立索引表（線性表）以提高查找效率； 3)系統(tǒng)主要功能如下：
*采編入庫：新購一種書，確定書號后，登記到圖書帳目表中，如果表中已有，則只將庫存量增加； *借閱：如果一種書的現(xiàn)存量大于0，則借出一本，登記借閱者的書證號和歸還期限，改變現(xiàn)存量； *歸還：注銷對借閱者的登記，改變該書的現(xiàn)存量?！具M一步完成內容】 1)系統(tǒng)功能的進一步完善； 2)索引表采用樹表。3)設計內容 4)程序流程圖 5)源程序
6)軟件測試報告（包括所用到的數(shù)據(jù)及結果）
16.散列表的設計與實現(xiàn)（限1 人完成）【問題描述】
設計散列表實現(xiàn)電話號碼查找系統(tǒng)。【基本要求】
1)設每個記錄有下列數(shù)據(jù)項：電話號碼、用戶名、地址；
2)從鍵盤輸入各記錄，分別以電話號碼和用戶名為關鍵字建立散列表； 3)采用一定的方法解決沖突； 4)查找并顯示給定電話號碼的記錄； 5)查找并顯示給定用戶名的記錄?！具M一步完成內容】 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 人完成）
要求：建立試題庫文件，隨機產(chǎn)生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ù)據(jù)結構實現(xiàn)上述求解 2)采用鏈數(shù)據(jù)結構實現(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ù)產(chǎn)生n個隨機整數(shù)（20000以上），對這些數(shù)進行多種方法進行排序。要求：
1)至少采用三種方法實現(xiàn)上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結果保存在不同的文件中。
2)統(tǒng)計每一種排序方法的性能（以上機運行程序所花費的時間為準進行對比），找出其中兩種較快的方法。3)如果采用4種或4種以上的方法者，可適當加分。
25.學生成績管理系統(tǒng)（限1 人完成）現(xiàn)有學生成績信息文件1（），內容如下 姓名 學號 語文 數(shù)學 英語
張明明 01 67 78 82 李成友 02 78 91 88 張輝燦 03 68 82 56 王露 04 56 45 77 陳東明 05 67 38 47 ….......…
學生成績信息文件2（）,內容如下: 姓名 學號 語文 數(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ù)據(jù)進行合并, 2) 3)中的數(shù)據(jù)按總分降序排序(至少采用兩種排序方法實現(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個城市間的距離網(wǎng)，用prim算法或kruskal算法建立最小生成樹，并計算得到的最小生成樹的代價?；疽螅?BR> 1、城市間的距離網(wǎng)采用鄰接矩陣表示，鄰接矩陣的存儲結構定義采用課本中給出的定義，若兩個城市之間不存在道路，則將相應邊的權值設為自己定義的無窮大值。要求在屏幕上顯示得到的最小生成樹中包括了哪些城市間的道路，并顯示得到的最小生成樹的代價。
2、表示城市間距離網(wǎng)的鄰接矩陣（要求至少6個城市，10條邊）
3、最小生成樹中包括的邊及其權值，并顯示得到的最小生成樹的代價。
36.客戶消費積分管理系統(tǒng)（限1 人完成）
問題描述：針對客戶的消費情況，進行客戶管理，根據(jù)客戶的消費積分對客戶實行不同程度的打折優(yōu)惠?；疽螅?BR> 1.采用一定的存儲結構進行客戶信息的存儲； 2.對客戶的信息可以進行修改、刪除、添加； 3.能夠根據(jù)消費情況進行客戶積分的計算； 4.根據(jù)積分情況實行不同程度的打折優(yōu)惠；
37.產(chǎn)品進銷存管理系統(tǒng)（限1 人完成）
問題描述：針對某一種行業(yè)的庫房的產(chǎn)品進銷存情況進行管理?；疽螅?BR> 1.采用一定的存儲結構對庫房的貨品及其數(shù)量進行分類管理； 2.可以進行產(chǎn)品類的添加、產(chǎn)品的添加、產(chǎn)品數(shù)量的添加；
3.能夠查詢庫房每種產(chǎn)品的總量、進貨日期、銷出數(shù)量、銷售時間等；
38.特殊矩陣的壓縮存儲算法的實現(xiàn)（限1 人完成）問題描述：對于特殊矩陣可以通過壓縮存儲減少存儲空間?；疽螅?BR> 1.針對多種特殊矩陣進行壓縮存儲，并能顯示壓縮后的相關地址和值； 2.輸入在原來特殊矩陣中的地址，要求能從壓縮后的矩陣中讀出相應的值；
39.算術表達式的求解（限1 人完成）
問題描述：給定一個算術表達式，通過程序求出最后的結果?；疽螅?BR> 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ù)據(jù)的迷宮，輸出的一條通路為：（1，1，1），（1,2,2）,(3,2,3),(3,1,2),…。測試數(shù)據(jù)：
迷宮的測試數(shù)據(jù)如下：左下角（1，1）為入口，右下角（8，9）為出口。實現(xiàn)提示： 計算機解迷宮通常用的是“窮舉求解”方法，即從入口出發(fā)，順著某個方向進行探索，若能走通，則繼續(xù)往前進；否則沿著原路退回，換一個方向繼續(xù)探索，直至出口位置，求得一條通路。假如所有可能的通路都探索到而未能到達出口，則所設的迷宮沒有通路。
可以二維數(shù)組存儲迷宮數(shù)據(jù)，通常設定入口點的下標為（1，1），出口點的下標為（n,n）。為處理方便起見，可在迷宮的四周加一圈障礙。對于迷宮中任一位置，均可約定有東、南、西、北四個方向可通。選做內容：
（1）編寫遞歸形式的算法，求得迷宮中所有可能的通路；（2）以方陣形式輸出迷宮及其通路。43.迷宮問題（隊列）（同上）44二叉搜索樹：各種搜索樹效率比較 題目要求：
本題目要求對普通的二叉排序樹、avl樹分別實現(xiàn)制定操作，并分析比較這兩種不同數(shù)據(jù)結構對應的一系列插入和刪除操作的效率。要求測試對n個不同整數(shù)進行下列操作的效率：（1）按遞增順序插入n個整數(shù)，并按同樣順序刪除；（2）按遞增順序插入n個整數(shù)，并按相反順序刪除；（3）按隨機順序插入n個整數(shù)，并按隨機順序刪除；
要求n從1000到10000取值，并以數(shù)據(jù)規(guī)模n為橫軸，運行時間為縱軸，畫出3種不同數(shù)據(jù)結構對應的操作效率比較圖。
45.病毒測試程序 本題的任務是：
當整個網(wǎng)絡被感染后，計算有多少臺機器被某個特定變種所感染。輸入要求：
輸入由若干組測試數(shù)據(jù)組成。
每組數(shù)據(jù)的第1行包含2個整數(shù)m和n（1≤m,n≤500），接下來是一個m*n的矩陣表示網(wǎng)絡的初始感染狀態(tài)，其中的正、負整數(shù)的意義如題目描述中所定義。
下面一行給出一個正整數(shù)q，是將要查詢的變種的個數(shù)。接下去的q行里，每行給出一個變種的類型。當m或n為0時，表示全部測試結束，不要對該數(shù)據(jù)做任何處理。輸出要求：
對每一組測試，在一行里輸出被某個特定變種所感染的機器數(shù)量。
46關鍵路徑問題（限1 人完成）
問題描述：設計一個程序求出完成整項工程至少需要多少時間以及整項工程中的關鍵活動?；疽螅?BR> （1）對一個描述工程的aoe網(wǎng)，應判斷其是否能夠順利進行。
（2）若該工程能順利進行，輸出完成整項工程至少需要多少時間，以及每一個關鍵活動所依附的兩個頂點、最早發(fā)生時間、最遲發(fā)生時間。
47.神秘國度的愛情故事
輸入要求：輸入由若干組測試數(shù)據(jù)組成。
每組數(shù)據(jù)的第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ù)據(jù)做任何處理。
輸出要求：對每一組測試給定的a,b,c，在一行里輸出答案，即：如果c在a和b之間的路徑上，輸出yes,否則輸出no。
48.并查集：檢查網(wǎng)絡
題目要求：給定一個計算機網(wǎng)絡以及機器間的雙向連線列表，每一條連線允許兩端的計算機進行直接的文件傳輸，其他計算機間若存在一條連通路徑，也可以進行間接的文件傳輸。請寫出程序判斷：任意指定兩臺計算機，它們之間是否可以進行文件傳輸？
輸入要求：輸入若干測試數(shù)據(jù)組成。對于每一組測試，第1行包含一個整數(shù)n（≤10000），即網(wǎng)絡中計算機的總臺數(shù)，因而每臺計算機可用1到n之間的一個正整數(shù)表示。接下來的幾行輸入格式為i c1 c2或者 c或者c c1c2或者s，其中c1和c2是兩臺計算機的序號，i表示在c1和c2間輸入一條連線，c表示檢查c1和c2間是否可以傳輸文件，s表示該組測試結束。當n為0時，表示全部測試結束，不要對該數(shù)據(jù)做任何處理。
輸出要求：對每一組c開頭的測試，檢查c1和c2間是否可以傳輸文件，若可以，則在一行中輸出“yes”，否則輸出“no”。
當讀到s時，檢查整個網(wǎng)絡。若網(wǎng)絡中任意兩機器間都可以傳輸文件，則在一行中輸出“the network is connected.”，否則輸出“there are k components.”,其中k是網(wǎng)絡中連通集的個數(shù)。兩組測試數(shù)據(jù)之間請輸出一空行分隔。
49.廣義表的應用
由于廣義表在結構上較線性表復雜得多，因此，廣義表的運算也不如線性表簡單。本設計要求實現(xiàn)的廣義表的建立、查找、輸出、取表頭和取表尾以及求深度、求逆表等。本設計用一個主控菜單程序控制，共分為6個子系統(tǒng)。（1）.建立廣義表（2）輸出廣義表（3）結點的查找（4）求廣義表表頭（5）求廣義表表尾（6）求廣義表的深度
50.網(wǎng)絡流：宇宙旅行 題目要求：
在走遍了地球上的所有景點以后，旅游狂人開始計劃他的宇宙旅行項目。經(jīng)過謹慎調查，他目前掌握了一張各衛(wèi)星空間站可以臨時容納的旅客人數(shù)列表。但旅客從一個星球飛往另一個星球時，需要在若干衛(wèi)星空間站臨時?？恐修D，而這些空間站不能接待任何旅客駐留，旅客必須立刻轉乘另一艘飛船離開，所以空間站不能接待超過自己最大容量的旅客流。為了估計預算，現(xiàn)在旅游狂人需要知道終點星球的接待站應該設計多大容量，才能使得每艘飛船在到達時都可以保證讓全部旅客下船。輸入要求：
輸入若干組測試數(shù)據(jù)組成。
每組測試數(shù)據(jù)的第1行包含旅行的起點星球和終點星球的名稱和一個不超過500的正整數(shù)n（n為0標志全部測試結束，不要對該數(shù)據(jù)做任何處理）。
接下來的n行里，數(shù)據(jù)格式為：sourcei capacityi，其中sourcei和destinationi是衛(wèi)星空間站的名稱或起點、終點星球的名稱，正整數(shù)capacityi是飛船從sourcei到destinationi一次能運載的最大旅客流量。每個名稱是由a～z之間三個大寫字母組成的字符串，例如：zju。測試數(shù)據(jù)中不包含任何到達起點星球的信息以及任何從終點星球出發(fā)的信息。輸出要求：
對每一組測試，在一行里輸出終點星球接待站應具有的最小容量，使得每艘飛船在到達時都可以保證讓全部旅客下船。