【正文】 第一篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目一、表達(dá)式求值（23人）l 問(wèn)題描述：從鍵盤上輸入中綴算數(shù)表達(dá)式，計(jì)算出表達(dá)式的值。l 基本要求：，如果表達(dá)式有錯(cuò)，能給出適當(dāng)?shù)奶崾尽?、－、247。這四種基本的算術(shù)運(yùn)算符。二、停車場(chǎng)管理（34人）l 問(wèn)題描述：假設(shè)停車場(chǎng)只有一個(gè)可停放n輛汽車的狹長(zhǎng)通道，且只有一個(gè)大門可供汽車進(jìn)出。汽車在停車場(chǎng)內(nèi)按車輛到達(dá)的先后順序依次排列，如果車場(chǎng)內(nèi)已經(jīng)停滿了汽車，則后來(lái)的汽車只能在門外的便道上等候。一旦停車場(chǎng)內(nèi)某輛車要離開(kāi)時(shí)，在它之后開(kāi)入的車輛必須先退出車場(chǎng)為它讓路，待該車輛開(kāi)出大門后，為它讓路的車輛再按原次序進(jìn)入停車場(chǎng)。每輛汽車在離開(kāi)時(shí)都要依據(jù)停留時(shí)間交費(fèi)（在便道上停留的時(shí)間不計(jì)費(fèi)）。l 基本要求：：到達(dá)/離去的標(biāo)識(shí)，汽車牌照號(hào)碼，到達(dá)/離去的時(shí)間。，例如要求離開(kāi)的汽車沒(méi)在停車場(chǎng)或便道時(shí)有相應(yīng)的提示。l 提示：以棧模擬停車場(chǎng)，用隊(duì)列模擬便道，另設(shè)一個(gè)棧臨時(shí)停放為讓路而從車場(chǎng)退出的車。三、約瑟夫環(huán)問(wèn)題（2人）問(wèn)題描述：設(shè)編號(hào)為1，2，3，……，n的n(n0)個(gè)人按順時(shí)針?lè)较驀蝗?，每個(gè)人持有一個(gè)正整數(shù)密碼。開(kāi)始時(shí)任選一個(gè)正整數(shù)作為報(bào)數(shù)上限m，從第一個(gè)人開(kāi)始順時(shí)針?lè)较蜃?起順序報(bào)數(shù)，報(bào)到m是停止報(bào)數(shù)，報(bào)m的人出列，將他的密碼作為新的m值，從他的下一個(gè)人開(kāi)始重新從1報(bào)數(shù)。如此下去，直到所有人全部出列為止。令n最大值取30。要求設(shè)計(jì)一個(gè)程序模擬此過(guò)程，求出出列編號(hào)序列。四、航空客運(yùn)訂票系統(tǒng)（45人）l 問(wèn)題描述：業(yè)務(wù)主要包括查詢航線和客票預(yù)訂的信息、客票預(yù)訂和辦理退票等。l 基本要求：：航班信息：飛機(jī)抵達(dá)城市、航班號(hào)、飛機(jī)號(hào)、起降時(shí)間、票價(jià)、總座位數(shù)和剩余座位數(shù)、已訂票的客戶名單?？蛻粜畔ⅲ嚎蛻粜彰⒆C件號(hào)、座位號(hào)。：承辦訂票業(yè)務(wù)：根據(jù)客戶提出的要求查詢?cè)摵桨嘈畔?，若滿足要求，則為客戶辦理訂票手續(xù)，輸出座位號(hào)。退票業(yè)務(wù)：根據(jù)客戶提供的航班號(hào)和訂票數(shù)量辦理退票手續(xù)。查詢功能：查詢航線信息（根據(jù)飛機(jī)的降落地點(diǎn)輸出航班號(hào)、飛機(jī)好、起降時(shí)間、票價(jià)和剩余座位數(shù)）和客戶預(yù)訂信息（根據(jù)客戶證件號(hào)輸出航班號(hào)、飛機(jī)號(hào)和座位號(hào)）五、漢諾塔游戲程序（23人）l 問(wèn)題描述：在平面上有三個(gè)位置A、B、C，在A位置上有n個(gè)大小不等的圓盤、小盤壓在大盤上形成圓盤堆。要求將A位置的N個(gè)圓盤通過(guò)B位置移動(dòng)到C位置上，并按同樣的順序疊放。移動(dòng)圓盤時(shí)必須遵循以下規(guī)則：、B、C任何一個(gè)塔座上 l 基本要求：圓盤的個(gè)數(shù)從鍵盤輸入（如364等）；用動(dòng)畫的形式在屏幕上顯示盤的移動(dòng)。六、八皇后問(wèn)題（2人）l 問(wèn)題描述：八皇后問(wèn)題，是一個(gè)古老而著名的問(wèn)題，是回溯算法的典型例題。該問(wèn)題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在88格的國(guó)際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上。l 基本要求：統(tǒng)計(jì)總共有多少種擺法，并以一定方式輸出擺好的格局。七、簡(jiǎn)單個(gè)人圖書管理系統(tǒng)（34人）l 問(wèn)題描述：學(xué)生在學(xué)習(xí)過(guò)程中擁有很多書籍，對(duì)購(gòu)買的書籍進(jìn)行分類和統(tǒng)計(jì)是一種良好的習(xí)慣。如果用文件來(lái)存儲(chǔ)相關(guān)書籍的各種信息，包括書號(hào)、書名、作者名、價(jià)格和購(gòu)買日期，輔之以程序?qū)畔⑦M(jìn)行統(tǒng)計(jì)和查詢會(huì)使書籍管理工作輕松有趣。l 基本要求： 、刪除、插入、更新八、雙端隊(duì)列（2人）l 問(wèn)題描述：雙端隊(duì)列是插入和刪除操作可以在兩端進(jìn)行的線性表，表的兩端分別稱作端點(diǎn)1和端點(diǎn)2。設(shè)計(jì)雙端隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)入隊(duì)、出隊(duì)等基本操作。提示：為便于操作，采用帶頭結(jié)點(diǎn)的雙鏈表存儲(chǔ)雙端隊(duì)列九、迷宮問(wèn)題（2人）l 問(wèn)題描述：迷宮實(shí)驗(yàn)是取自心理學(xué)的一個(gè)古典實(shí)驗(yàn)。在該實(shí)驗(yàn)中，把一只老鼠從一個(gè)無(wú)頂大盒子的門放入，在盒中設(shè)置了許多墻，對(duì)行進(jìn)方向形成了多處阻擋。盒子僅有一個(gè)出口，在出口處放置一塊奶酪，吸引老鼠在迷宮中尋找道路以到達(dá)出口。在給出入口和出口的前提下，給出動(dòng)態(tài)的迷宮行走路線 l 基本要求：提示：用二維數(shù)組表示迷宮，1代表有障礙，0代表無(wú)障礙 十、火車車廂重排問(wèn)題（45人）l 問(wèn)題描述：一列貨運(yùn)列車共有n節(jié)車廂，每節(jié)車廂將停放在不同的車站。假定n個(gè)車站的編號(hào)分別為1n，即貨運(yùn)列車按照第n站到第1站的次序經(jīng)過(guò)車站。為了便于從列車上卸掉相應(yīng)的車廂，車廂的編號(hào)應(yīng)與車站的編號(hào)相同，這樣，在每個(gè)車站只要卸掉最后一節(jié)車廂。所以，給定任意次序的車廂，必須重新排列它們。車廂的重排工作可以通過(guò)轉(zhuǎn)軌站完成。在轉(zhuǎn)軌站中有一個(gè)出軌、一個(gè)入軌和一個(gè)緩沖軌，緩沖軌位于入軌和出軌之間。設(shè)緩沖軌按先進(jìn)先出的方式運(yùn)作，設(shè)計(jì)算法解決火車車廂重排問(wèn)題。l 基本要求：設(shè)計(jì)存儲(chǔ)結(jié)構(gòu)表示n個(gè)車廂、k個(gè)緩沖軌以及入軌、出軌。假設(shè)k=3。十一、魔方陣（2人）l 問(wèn)題描述： 在一個(gè)nn的矩陣中填入一個(gè)1到n2的數(shù)字（n為奇數(shù)），使得每一行、每一列、每條對(duì)角線的累加和都相等。十二、簡(jiǎn)單個(gè)人電話號(hào)碼查詢系統(tǒng)（34人）l 問(wèn)題描述：人們?cè)谌粘Ｉ钪薪?jīng)常要查找某個(gè)人或某個(gè)單位的電話號(hào)碼，要求實(shí)現(xiàn)一個(gè)簡(jiǎn)單的個(gè)人電話號(hào)碼查詢系統(tǒng)，根據(jù)用戶輸入的信息（例如姓名等）進(jìn)行快速查詢。l 基本要求：，以提高查找效率 、刪除、修改等維護(hù)功能。十三、直接插入排序基于單鏈表的實(shí)現(xiàn)（1人）l 問(wèn)題描述：采用單鏈表存儲(chǔ)待排序數(shù)據(jù)，在其上實(shí)現(xiàn)直接插入排序算法。l 基本要求：排序的數(shù)據(jù)的個(gè)數(shù)及其內(nèi)容由用戶從鍵盤上輸入。十四、患者看病過(guò)程模擬（2人）l 問(wèn)題描述：患者到醫(yī)院看病的過(guò)程為先排隊(duì)等候再看病治療。在排隊(duì)的過(guò)程中主要重復(fù)做兩件事：一是患者到達(dá)診室，將病歷交給護(hù)士，排到等候隊(duì)列中候診；二是護(hù)士從等候隊(duì)列中取出下一個(gè)患者的病歷，該患者進(jìn)入診室看病。設(shè)計(jì)算法模擬該過(guò)程。l 基本要求： 十五、汽車牌照數(shù)據(jù)的排序與快速查找（3人）l 問(wèn)題描述：在汽車數(shù)據(jù)的信息模型中，汽車牌照是關(guān)鍵字，而且是具有結(jié)構(gòu)特點(diǎn)的一類關(guān)鍵字。因?yàn)槠嚺普仗?hào)是數(shù)字和字母混編的，例如01B7328，這種記錄集合是一個(gè)適用于多關(guān)鍵字進(jìn)行排序的典型例子。l 基本要求：，然后利用折半查找方法實(shí)現(xiàn)對(duì)汽車記錄按關(guān)鍵字查找，也可以按自動(dòng)方式隨機(jī)生成十六、求圖的中心點(diǎn)（2人）l 問(wèn)題描述：假設(shè)有一個(gè)公司在某個(gè)地區(qū)有n個(gè)產(chǎn)品銷售點(diǎn)，現(xiàn)根據(jù)業(yè)務(wù)需要打算在其中某個(gè)銷售點(diǎn)上建立一個(gè)中心倉(cāng)庫(kù)負(fù)責(zé)向其他銷售點(diǎn)提供產(chǎn)品。由于運(yùn)輸路線不同，運(yùn)輸費(fèi)用也不同。假定每天需要向每個(gè)銷售點(diǎn)運(yùn)輸一次產(chǎn)品，那么應(yīng)將中心倉(cāng)庫(kù)建在哪個(gè)銷售點(diǎn)上才能使運(yùn)輸費(fèi)用最低。十七、集合的交、并和差運(yùn)算的實(shí)現(xiàn)（12人）l 問(wèn)題描述：用有序單鏈表表示集合，實(shí)現(xiàn)集合的交、并、差運(yùn)算 l 基本要求： 空間復(fù)雜度為O(1)十八、單鏈表實(shí)現(xiàn)十進(jìn)制大整數(shù)運(yùn)算（12人）l 問(wèn)題描述：使用單鏈表實(shí)現(xiàn)不限大小的整數(shù)，每個(gè)結(jié)點(diǎn)存儲(chǔ)一位數(shù)字，要求實(shí)現(xiàn)加、減運(yùn)算。即能從鍵盤上輸入兩個(gè)大整數(shù)，比如：***12345和***11111，則加的結(jié)果應(yīng)為：***01234；減的結(jié)果應(yīng)為：***23456。l 基本要求： 從鍵盤上輸入運(yùn)算數(shù)和運(yùn)算符，輸出結(jié)果。十九、哈夫曼編碼（45人）l 問(wèn)題描述：利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。這就要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼,在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼。對(duì)于雙工信道(即可以雙向傳輸信息的信道)，每端都需要一個(gè)完成的編譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個(gè)哈夫曼的編譯碼系統(tǒng)。l基本要求：。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)。利用已建好的哈夫曼樹(shù),對(duì)正文進(jìn)行編碼。對(duì)編碼好的內(nèi)容進(jìn)行譯碼。二十、商品貨架管理（2人）l 問(wèn)題描述：商品貨架可以看成一個(gè)棧，棧頂商品的生產(chǎn)日期最早，棧底商品的生產(chǎn)日期最近。上貨時(shí)需要倒貨架，以保證生產(chǎn)商品較近的商品在較下的位置。用棧和隊(duì)列作為周轉(zhuǎn)，實(shí)現(xiàn)上述管理過(guò)程。二十一、稀疏矩陣運(yùn)算器（3人）l 問(wèn)題描述：實(shí)現(xiàn)兩個(gè)稀疏矩陣的加、減、乘運(yùn)算。l 基本要求：可用三元組順序表存儲(chǔ)稀疏矩陣，矩陣的運(yùn)算結(jié)果以通常的陣列形式輸出。二十二、校園導(dǎo)游程序（34人）l 問(wèn)題描述：用無(wú)向圖表示你所在學(xué)校的景點(diǎn)平面圖，圖中頂點(diǎn)表示主要景點(diǎn)，存放景點(diǎn)的編號(hào)、名稱、簡(jiǎn)介等信息，圖中的邊表示景點(diǎn)間的道路，存放路徑長(zhǎng)度等消息。l 基本要求：，即已知一個(gè)景點(diǎn)，查詢到某景點(diǎn)之間的一條最短路徑及長(zhǎng)度。二十三、排序綜合（23人）l 問(wèn)題描述：利用隨機(jī)函數(shù)產(chǎn)生N個(gè)隨機(jī)整數(shù)（20000以上），對(duì)這些數(shù)使用多種方法進(jìn)行排序。l 基本要求： （希爾排序、快速排序、堆排序）實(shí)現(xiàn)上述問(wèn)題求解（以上機(jī)運(yùn)行程序所花費(fèi)的時(shí)間為準(zhǔn)進(jìn)行對(duì)比），找出其中兩種較快的方法，最后列表顯示二十四、線索二叉樹(shù)（1人）l 問(wèn)題描述：建立一個(gè)中序線索二叉樹(shù)，并且完成中序遍歷。求該中序線索二叉樹(shù)上已知結(jié)點(diǎn)在中序的前驅(qū)和后繼；第二篇：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目.數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目（限1 人完成）任務(wù)：參加運(yùn)動(dòng)會(huì)有n個(gè)學(xué)校，學(xué)校編號(hào)為1……n。比賽分成m個(gè)男子項(xiàng)目，和w個(gè)女子項(xiàng)目。項(xiàng)目編號(hào)為男子1……m，女子m+1……m+w。不同的項(xiàng)目取前五名或前三名積分；取前五名的積分分別為：1，前三名的積分分別為：2；哪些取前五名或前三名由學(xué)生自己設(shè)定。（m功能要求：1)可以輸入各個(gè)項(xiàng)目的前三名或前五名的成績(jī)； 2)能統(tǒng)計(jì)各學(xué)?？偡郑?)可以按學(xué)校編號(hào)或名稱、學(xué)?？偡?、男女團(tuán)體總分排序輸出；4)可以按學(xué)校編號(hào)查詢學(xué)校某個(gè)項(xiàng)目的情況；可以按項(xiàng)目編號(hào)查詢?nèi)〉们叭蚯拔迕膶W(xué)校。5)數(shù)據(jù)存入文件并能隨時(shí)查詢6)規(guī)定：輸入數(shù)據(jù)形式和范圍：可以輸入學(xué)校的名稱，運(yùn)動(dòng)項(xiàng)目的名稱輸出形式：有合理的提示，各學(xué)校分?jǐn)?shù)為整形界面要求：有合理的提示，每個(gè)功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān)的功能要求。存儲(chǔ)結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計(jì)，但是要求運(yùn)動(dòng)會(huì)的相關(guān)數(shù)據(jù)要存儲(chǔ)在數(shù)據(jù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關(guān)內(nèi)容在c語(yǔ)言程序設(shè)計(jì)的書上，請(qǐng)自學(xué)解決）請(qǐng)?jiān)谧詈蟮纳辖毁Y料中指明你用到的存儲(chǔ)結(jié)構(gòu)；測(cè)試數(shù)據(jù)：要求使用全部合法數(shù)據(jù)；整體非法數(shù)據(jù)；局部非法數(shù)據(jù)。進(jìn)行程序測(cè)試，以保證程序的穩(wěn)定。測(cè)試數(shù)據(jù)及測(cè)試結(jié)果請(qǐng)?jiān)谏辖坏馁Y料中寫明；（限1 人完成）任務(wù)：通過(guò)此系統(tǒng)可以實(shí)現(xiàn)如下功能：錄入：可以錄入航班情況（數(shù)據(jù)可以存儲(chǔ)在一個(gè)數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）查詢：可以查詢某個(gè)航線的情況（如，輸入航班號(hào)，查詢起降時(shí)間，起飛抵達(dá)城市，航班票價(jià)，票價(jià)折扣，確定航班是否滿倉(cāng)）；可以輸入起飛抵達(dá)城市，查詢飛機(jī)航班情況；訂票：（訂票情況可以存在一個(gè)數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定）可以訂票，如果該航班已經(jīng)無(wú)票，可以提供相關(guān)可選擇航班；退票： 可退票，退票后修改相關(guān)數(shù)據(jù)文件；客戶資料有姓名，證件號(hào)，訂票數(shù)量及航班情況，訂單要有編號(hào)。修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件要求：根據(jù)以上功能說(shuō)明，設(shè)計(jì)航班信息，訂票信息的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)程序完成功能；（限1 人完成）功能：輸入一頁(yè)文字，程序可以統(tǒng)計(jì)出文字、數(shù)字、空格的個(gè)數(shù)。靜態(tài)存儲(chǔ)一頁(yè)文章，每行最多不超過(guò)80個(gè)字符，共N行；要求（1）分別統(tǒng)計(jì)出其中英文字母數(shù)和空格數(shù)及整篇文章總字?jǐn)?shù)；（2）統(tǒng)計(jì)某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。存儲(chǔ)結(jié)構(gòu)使用線性表，分別用幾個(gè)子函數(shù)實(shí)現(xiàn)相應(yīng)的功能；輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號(hào)。輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出“全部字母數(shù)”、“數(shù)字個(gè)數(shù)”、“空格個(gè)數(shù)”、“文章總字?jǐn)?shù)”（3）輸出刪除某一字符串后的文章；（限1 人完成）1)任務(wù)：為宿舍管理人員編寫一個(gè)宿舍管理查詢軟件, 程序設(shè)計(jì)要求： ，數(shù)據(jù)文件按關(guān)鍵字（姓名、學(xué)號(hào)、房號(hào)）進(jìn)行排序(冒泡、選擇、插入排序等任選一種)2)查詢菜單:(用二分查找實(shí)現(xiàn)以下操作)3)打印任一查詢結(jié)果（可以連續(xù)操作）（限1 人完成）設(shè)計(jì)要求：設(shè)計(jì)你的學(xué)校的平面圖，至少包括10個(gè)以上的場(chǎng)所，每?jī)蓚€(gè)場(chǎng)所間可以有不同的路，且路長(zhǎng)也可能不同，找出從任意場(chǎng)所到達(dá)另一場(chǎng)所的最佳路徑（最短路徑）。（限1 人完成）設(shè)計(jì)要求：針對(duì)計(jì)算機(jī)系本科課程，根據(jù)課程之間的依賴關(guān)系（如離散數(shù)學(xué)應(yīng)在數(shù)據(jù)結(jié)構(gòu)之前開(kāi)設(shè)）制定課程安排計(jì)劃，并滿足各學(xué)期課程數(shù)目大致相同。（限1 人完成）散列法中，散列函數(shù)構(gòu)造方法多種多樣，同時(shí)對(duì)于同一散列函數(shù)解決沖突的方法也可以不同。兩者是影響查詢算法性能的關(guān)鍵因素。對(duì)于幾種典型的散列函數(shù)構(gòu)造方法，做實(shí)驗(yàn)觀察，不同的解決沖突方法對(duì)查詢性能的影響。（限1 人完成）主要分為兩大功能：1)圖書管理(增加圖書、查詢圖書、刪除圖書、圖書借閱、還書)； 2)會(huì)員管理(增加會(huì)員、查詢會(huì)員、刪除會(huì)員、借書信息)；（限1 人完成）實(shí)現(xiàn)功能：輸入、輸出、插入、刪除、查找、追加、讀入、顯示、保存、拷貝、排序、索引、分類合計(jì)、退出。（限1 人完成）活期儲(chǔ)蓄處理中，儲(chǔ)戶開(kāi)戶、銷戶、存入、支出活動(dòng)頻繁，系統(tǒng)設(shè)計(jì)要求： 1)能比較迅速地找到儲(chǔ)戶的帳戶，以實(shí)現(xiàn)存款、取款記賬； 2)能比較簡(jiǎn)單，迅速地實(shí)現(xiàn)插入和刪除，以實(shí)現(xiàn)開(kāi)戶和銷戶的需要。（限1 人完成）用順序和二叉鏈表作存儲(chǔ)結(jié)構(gòu)1)以回車(39。n39。)為輸入結(jié)束標(biāo)志,輸入數(shù)列L，生成一棵二叉排 序樹(shù)T； 2)對(duì)二叉排序樹(shù)T作中序遍歷，輸出結(jié)果；3)輸入元素x,查找二叉排序樹(shù)T,若存在含x的結(jié)點(diǎn),則刪除該結(jié)點(diǎn),并作中序遍歷(執(zhí)行操作2)；否則輸出信息“無(wú)x”；（限1 人完成）設(shè)計(jì)要求：在n個(gè)城市之間建設(shè)網(wǎng)絡(luò)，只需保證連通即可，求最經(jīng)濟(jì)的架設(shè)方法。存儲(chǔ)結(jié)構(gòu)采用多種。求解算法多種。（限1 人完成）設(shè)計(jì)目的：用〈〈數(shù)據(jù)結(jié)構(gòu)〉〉中的雙向鏈表作數(shù)據(jù)結(jié)構(gòu)，結(jié)合C語(yǔ)言基本知識(shí)。編寫一個(gè)通訊錄管理系統(tǒng)。以把所學(xué)數(shù)據(jù)結(jié)構(gòu)知識(shí)應(yīng)用到實(shí)際軟件開(kāi)發(fā)中去。設(shè)計(jì)內(nèi)容：本系統(tǒng)應(yīng)完成一下幾方面的功能： 1)輸入信息——enter()。2)顯示信息———display()