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

吉林師范大學計算機學院

數(shù)據(jù)結(jié)構(gòu)課程設計題目1.計算器功能描述：編寫功能類似于Windows計算器的程序，不要求實現(xiàn)用戶界面。當用戶輸入第一個數(shù)值后，輸入的運算符號，再輸入另外一個數(shù)值，計算并保存兩個數(shù)值進行該運算的結(jié)果；可以進行連續(xù)計算，當輸入的運算符是“=”時，輸出計算結(jié)果。（要求程序能夠處理負數(shù)，小數(shù);并對輸入錯誤給出提示；運算類型包括+-*〃）算法知識：數(shù)據(jù)結(jié)構(gòu)中棧相關(guān)的知識輸入測試數(shù)據(jù)：3人4+9-=輸出結(jié)果：88教學計劃編制問題功能描述：針對計算機系本科課程，根據(jù)課程之間的依賴關(guān)系（如離散數(shù)學應在數(shù)據(jù)結(jié)構(gòu)之前開設）制定課程安排計劃，并滿足各學期課程數(shù)目大致相同。算法知識:拓撲排序AOV-網(wǎng)的應用，拓撲排序（需利用棧）輸入數(shù)據(jù):學期數(shù)、課程數(shù)、課程的代表值、課程間的先后關(guān)系數(shù)、每條?。ㄟ叄┑幕∥埠突☆^輸出數(shù)據(jù):排序結(jié)果選班長功能描述：設編號為1，2，3，，n的n（n>0）個人按順時針方向圍坐一圈，每個人持有一個正整數(shù)密碼。開始時任選一個正整數(shù)做為報數(shù)上限m,從第一個人開始順時針方向自1起順序報數(shù)，報到m是停止報數(shù)，報m的人出列，將他的密碼作為新的m值，從他的下一個人開始重新從1報數(shù)。如此下去，直到最后只有一人時，此人即為班長。令n最大值取30。要求實現(xiàn)每個人的密碼隨機產(chǎn)生，初始密碼隨機。算法知識：數(shù)據(jù)結(jié)構(gòu)中隊列的知識，及隨機數(shù)產(chǎn)生算法輸入數(shù)據(jù)：n（即參選人數(shù)）輸出數(shù)據(jù)：淘汰人選的序列，班長的序號進一步要求：有興趣的同學可以自己擴充系統(tǒng)功能，實現(xiàn)編號+姓名矩陣的連乘運算功能描述：現(xiàn)有N個矩陣，求這N個矩陣的乘積。若矩陣可以相乘，則求出乘積；否則給出提示信息。算法知識：矩陣乘法及存儲結(jié)構(gòu)輸入數(shù)據(jù)：矩陣個數(shù)，各矩陣的行數(shù)、列數(shù)及矩陣中的各個元素輸出數(shù)據(jù)：乘積或提示信息哈夫曼樹應用（編碼及譯碼）功能要求：根據(jù)給定的字符集和其中每個字符的頻度，構(gòu)造哈夫曼樹，并輸出字符集中每個字符的哈夫曼編碼。將給定的字符串根據(jù)其哈夫曼編碼進行編碼，并進行相應的譯碼。算法知識：哈夫曼樹及哈夫曼編碼輸入數(shù)據(jù)：字符集和權(quán)值數(shù)據(jù)存放在數(shù)據(jù)文件設字符集及頻度如下表：字符空格ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度5763151485180238181161輸出數(shù)據(jù)：哈夫曼編碼6.文本編輯器功能描述：輸入一頁文字，設計一個可以統(tǒng)計出文字、數(shù)字、空格的個數(shù)的程序?；疽螅红o態(tài)存儲一頁文章，每行最多不超過80個字符，共N行；要求（1） 分別統(tǒng)計出其中英文字母數(shù)和空格數(shù)及整篇文章總字數(shù)；（2） 統(tǒng)計某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3） 刪除某一子串，并將后面的字符前移。算法知識：串及其模式匹配輸入數(shù)據(jù)：可以輸入大寫、小寫的英文字母、任何數(shù)字及標點符號。輸出數(shù)據(jù)：（1） 分行輸出用戶輸入的各行字符；（2） 分4行輸出"全部字母數(shù)"、"數(shù)字個數(shù)"、"空格個數(shù)"、"文章總字數(shù)"（3） 輸出刪除某一字符串后的文章；利用棧求表達式的值功能描述：對于正確輸入的數(shù)學四則運算表達式（運算符同C語言），計算并輸出表達式計算的結(jié)果，錯誤時給出提示。算法知識：棧輸入數(shù)據(jù)：（3+2）*7/9輸出數(shù)據(jù)：表達式正確則給出結(jié)果，錯誤給出提示校園導航功能描述：校園中有各個教學樓和宿舍樓，各樓之間有道路連通，每條道路都有一定長度。求出從任一樓房出發(fā)到達指定位置的最短的距離。算法知識：最短路徑輸入數(shù)據(jù)：樓的個數(shù)，各樓之間的路及距離，以構(gòu)成有向圖輸出數(shù)據(jù)：最短距離及路徑9.打字程序功能描述：制作類似金山打字的打字程序，要求能統(tǒng)計打字速度，正確、錯誤率。算法知識：C語言作圖及鍵盤事件處理輸入數(shù)據(jù)：輸出數(shù)據(jù)：10.工程工期管理功能描述：一個工程由若干個活動構(gòu)成，每個活動有一個持續(xù)時間。有的活動只有當多個前期活動的結(jié)束才能開始。給出工程的各個活動及持續(xù)時間，形成其對應的AOE網(wǎng)，找出可以縮短工程工期的活動并輸出。算法知識：AOE網(wǎng)及最短路徑輸入數(shù)據(jù)：各個活動及持續(xù)時間輸出數(shù)據(jù)：可縮短工期的活動軍事打擊的原則功能描述：一個地區(qū)的若干個城市之間可能有多條道路相通，在進行軍事部署時要考慮打擊那些關(guān)鍵的城市，一旦該城被摧毀，就會有一些城市失去與其他城市的聯(lián)系，陷入孤立的狀態(tài)。找出這樣的城市對其進行重點保護。算法知識：關(guān)節(jié)點輸入數(shù)據(jù)：各城市及其連接線輸出數(shù)據(jù)：關(guān)節(jié)城市紙牌游戲21點功能描述：21點游戲的規(guī)則是：游戲的兩人分為莊和閑家。莊先抓牌，每次最少三張，最多不超過5張牌，按每張撲克的點數(shù)算，21點最大，超過21點時算0點。若莊家和閑家同點，則莊家贏，若莊家0點則閑家贏。其他情況依點數(shù)大小，大者贏。輪流執(zhí)莊算法知識：牌面生成及存儲輸入數(shù)據(jù)：電腦和人對弈，生成每張抽取的牌面輸出數(shù)據(jù)：電腦和人的每張牌，點數(shù)及勝負情況。13.題目：學生運動會成績數(shù)據(jù)庫功能描述：學生運動會成績數(shù)據(jù)庫系統(tǒng)記錄某校運動會上全部運動項目，各系獲得的分數(shù)及排名的情況，包括50、100、200，400，1500米，跳高，跳遠，標槍，鉛球鐵餅等。進入系統(tǒng)后可以輸入和修改某個項目的結(jié)果情況，可以按各系院編號輸出總分；按總分排序；按男團體總分排序；按系院編號查詢；按項目編號查詢；按女團體總分排序。分步實施：1） 初步完成總體設計，搭好框架，確定人機對話的界面，確定函數(shù)個數(shù)；2） 完成最低要求：建立一個文件，包括某個系，5個項目的得分情況，能對文件中的信息進行擴充（追加），修改和刪除；3）進一步要求：完成對多個系，多個項目的得分排序，以及完成系統(tǒng)查詢功能。有興趣的同學可以自己擴充系統(tǒng)功能。算法知識：排序輸入數(shù)據(jù)：系院數(shù)目，男子項目數(shù)女子項目數(shù)，（每項目取前三名，分別為10，5，2分）輸出數(shù)據(jù)：可以按各系院編號輸出總分；按總分排序；按男團體總分排序；按系院編號查詢；按項目編號查詢；按女團體總分排序。要求：1）界面友好，函數(shù)功能要劃分好2）總體設計應畫一流程圖3）程序要加必要的注釋4）要提供程序測試方案5）程序一定要經(jīng)得起測試，寧可功能少一些，也要能運行起來，不能運行的程序是沒有價值的14.運動會分數(shù)統(tǒng)計功能描述：參加運動會有n個學校，學校編號為1……n。比賽分成m個男子項目，和w個女子項目。項目編號為男子1m,女子m+1m+w。不同的項目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前三名由學生自己設定。（mv=20,nv=20）功能要求：1） 可以輸入各個項目的前三名或前五名的成績；2） 能統(tǒng)計各學?？偡郑?） 可以按學校編號或名稱、學?？偡帧⒛信畧F體總分排序輸出；4） 可以按學校編號查詢學校某個項目的情況；可以按項目編號查詢?nèi)〉们叭蚯拔迕膶W校。5） 數(shù)據(jù)存入文件并能隨時查詢6） 規(guī)定：輸入數(shù)據(jù)形式和范圍：可以輸入學校的名稱，運動項目的名稱輸出形式：有中文提示，各學校分數(shù)為整形界面要求：有合理的提示，每個功能可以設立菜單，根據(jù)提示，可以完成相關(guān)的功能要求。算法知識：排序，文件的讀寫存儲結(jié)構(gòu)：學生自己根據(jù)系統(tǒng)功能要求自己設計，但是要求運動會的相關(guān)數(shù)據(jù)要存儲在數(shù)據(jù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關(guān)內(nèi)容在c語言程序設計的書上，請自學解決）請在最后的上交資料中指明你用到的存儲結(jié)構(gòu)；測試數(shù)據(jù)：要求使用1、全部合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù)據(jù)。進行程序測試，以保證程序的穩(wěn)定。測試數(shù)據(jù)及測試結(jié)果請在上交的資料中寫明；15.飛機訂票系統(tǒng)功能描述：錄入：可以錄入航班情況（數(shù)據(jù)可以存儲在一個數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）查詢：可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛抵達城市，航班票價，票價折扣，確定航班是否滿倉）；可以輸入起飛抵達城市，查詢飛機航班情況；訂票：（訂票情況可以存在一個數(shù)據(jù)文件中，結(jié)構(gòu)自己設定）可以訂票，如果該航班已經(jīng)無票，可以提供相關(guān)可選擇航班；退票：可退票，退票后修改相關(guān)數(shù)據(jù)文件；客戶資料有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號。修改航班信息：當航班信息改變可以修改航班數(shù)據(jù)文件要求：根據(jù)以上功能說明，設計航班信息，訂票信息的存儲結(jié)構(gòu)，設計程序完成功能；16.圖的遍歷功能描述：實現(xiàn)圖的深度優(yōu)先,廣度優(yōu)先遍歷算法，并輸出原圖及遍歷結(jié)果。分步實施：1） 初步完成總體設計，搭好框架；2）完成最低要求：兩種必須都要實現(xiàn)，寫出畫圖的思路；3）進一步要求：畫出圖的結(jié)構(gòu)，有興趣的同學可以進一步改進圖的效果。要求：1）界面友好，函數(shù)功能要劃分好2）總體設計應畫一流程圖3）程序要加必要的注釋4）要提供程序測試方案5）程序一定要經(jīng)得起測試，寧可功能少一些，也要能運行起來，不能運行的程序是沒有價值的。17.多項式乘法功能描述：完成兩個n元多項式作乘法，給出明確的等式形式。分步實施：1）初步完成總體設計，搭好框架，確定人機對話的界面，確定函數(shù)個數(shù)；2）完成最低要求：建立一個文件，實現(xiàn)兩個一元二次多項式作乘法。3）進一步要求：實現(xiàn)三元二次多項式的乘法。有興趣的同學可以自己擴充系統(tǒng)功能。要求：1）界面友好，函數(shù)功能要劃分好2）總體設計應畫一流程圖3）程序要加必要的注釋4）要提供程序測試方案5）程序一定要經(jīng)得起測試，寧可功能少一些，也要能運行起來，不能運行的程序是沒有價值的。18.集合運算功能描述：使用鏈表來表示集合，完成集合的合并，求交集等操作。分步實施：1）初步完成總體設計，搭好框架，確定人機對話的界面，確定函數(shù)個數(shù)；2）完成最低要求：3）進一步要求：要求：1）界面友好，函數(shù)功能要劃分好2）總體設計應畫一流程圖3）程序要加必要的注釋4）要提供程序測試方案5）程序一定要經(jīng)得起測試，寧可功能少一些，也要能運行起來，不能運行的程序是沒有價值的。漢諾塔非遞歸實現(xiàn)功能描述：編程序顯示n（n<=9）層漢諾威塔的調(diào)整過程。分步實施：1） 初步完成總體設計，搭好框架，確定人機對話的界面，確定函數(shù)個數(shù)；2） 完成最低要求：實現(xiàn)5層漢諾威塔的調(diào)整過程；3） 進一步要求：直至實現(xiàn)n=9時的情況。有興趣的同學可以自己擴充系統(tǒng)功能。要求：1） 界面友好，函數(shù)功能要劃分好2） 總體設計應畫一流程圖3） 程序要加必要的注釋4） 要提供程序測試方案5） 程序一定要經(jīng)得起測試，寧可功能少一些，也要能運行起來，不能運行的程序是沒有價值的。銀行業(yè)務的模擬系統(tǒng)問題描述：設計一個銀行業(yè)務模擬系統(tǒng)，模擬銀行的業(yè)務運行并計算一天中客戶在銀行逗留的平均時間。銀行有N（N的取值自己定義）個窗口對外接待客戶，從早晨銀行開門起不斷有客戶進入銀行。由于每個窗口在某個時刻只能接待一個客戶，因此在客戶人數(shù)眾多時需在每個窗口前順次排隊，對于剛進入銀行的客戶，如果某個窗口的業(yè)務員正空閑，則可上前辦理業(yè)務；反之，若N個窗口均有客戶所占，他便會排在人數(shù)最少的隊伍后面?；疽螅?） 在界面上可以設定銀行的對外營業(yè)時間（銀行的開門時間以及銀行的關(guān)門時間）。2） 用人機交互的方式來輸入客戶的到達時間以及客戶的離開時間，用隊列來存儲客戶的到達事件和客戶的離開事件。3） 可以友好的顯示出在某一天中整個銀行系統(tǒng)中客戶在銀行逗留的平均時間。停車場管理系統(tǒng)問題描述：設計一個停車場管理系統(tǒng)，模擬停車場的運作。基本要求：1） 要求以棧模擬停車場，以隊列模擬車場外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進行模擬管理；2） 要求處理的數(shù)據(jù)元素包括如下數(shù)據(jù)項：汽車“到達”或“離去”信息、汽車牌照及“到達”或“離去”的時刻；3）若是車輛到達，就輸出汽車在停車場內(nèi)或便道上的停車位置；若是車離去，就輸出汽車在停車場內(nèi)停留的時間和應交納的費用（在便道上停留的時間不收費）。4）完成該停車場的一些信息統(tǒng)計功能（如每天到達/離開的車次，停車總時數(shù)、每天的停車費用等）。22.迷宮問題問題描述：用一個字符類型的二維數(shù)組表示迷宮，數(shù)組中的每個元素表示一個小方格，取值“0”（通道）或“1”（阻塞物）。設計一個模擬小老鼠走迷宮的程序，為小老鼠尋找一條從迷宮入口到迷宮出口的途徑小方格最少的最短通路。基本要求：1）用隨機函數(shù)設置迷宮；2）選擇合適的數(shù)據(jù)結(jié)構(gòu)表示迷宮。3） 迷宮入口處的下標是（xO,yO）,出口處的下標是（xl,yl）,由鍵盤輸入。4） 輸出從入口到出口的最短通路（如存在）或不存在通路的信息。5） 設計出友好的圖形化界面,做到很好的人機交互。文件目錄管理系統(tǒng)問題描述：文件是管理用戶信息和應用程序的一種工具。每個文件有唯一的文件名,可以通過文件名訪問文件,同時可對文件進行生成、刪除及文件名修改等操作。文件系統(tǒng)對若干文件進行管理時將所有的文件目錄組合在一起構(gòu)成一個目錄文件。通過對目錄文件的管理達到“按名存取”的目的,目錄文件常采用的組織結(jié)構(gòu)是樹型目錄結(jié)構(gòu)?；疽螅汉瘮?shù)功能要劃分好,程序要有必要的注釋。用戶通過界面菜單選擇以下操作：l）生成文件,選擇路徑和文件名,實現(xiàn)對文件的生成。設定系統(tǒng)的關(guān)鍵字如createfile,makedir2）刪除文件,對指定文件進行刪除操作。3） 修改文件,對指定文件進行內(nèi)容修改或者文件名修改。4） 輸出該目錄結(jié)構(gòu)。大整數(shù)的加減乘除功能描述：在實際應用中往往要使用一些很大的整數(shù)進行四則運算,這些整數(shù)在計算機中無法用程序設計語言默認的類型表示出來,請設計相應的存儲結(jié)構(gòu)實現(xiàn)大整數(shù)的四則運算。基本要求：最少要實現(xiàn)大整數(shù)及其加減法進一步擴充至乘除法及四則運算二叉樹的層序遍歷編寫算法將通常輸入四則運算表達式轉(zhuǎn)化為逆波蘭表達式（后綴表達式）利用前中或中后序遍歷結(jié)果還原二叉樹二叉樹三種遍歷的非遞歸實現(xiàn)求出二叉樹中葉子結(jié)點，度為1的結(jié)點，度為2的結(jié)點的個數(shù)并輸出馬踏棋盤問題問題描述：設計一個國際象棋的馬踏棋盤的演示程序基本要求：將馬隨機放在國際象棋的8X8棋盤的某個方格中，馬按照走棋的規(guī)則進行移動。要求每個方格只進入一次，走遍棋盤的全部64個方格。編制非遞歸程序，求出馬的行走路線，并按求出的行走路線，將1,2,?,64依次填入一個8X8的方陣，并輸出。n階魔陣問題任務：給定一奇數(shù)n構(gòu)造一個n