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