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

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計備選題目64441.運動會分數(shù)統(tǒng)計 230632.飛機訂票系統(tǒng) 369453.文章編輯 5182934.地圖著色問題 5173265.宿舍管理查詢軟件 6244076.校園導(dǎo)航問題 6244647.學(xué)校超市選址問題（帶權(quán)有向圖的中心點） 763238.教學(xué)計劃編制問題 7260019.活期儲蓄帳目管理 102587510.二叉排序樹的實現(xiàn) 10190111.最小生成樹問題 11107412通訊錄的制作 112024913.哈夫曼編碼/譯碼器 12939514.圖書管理系統(tǒng) 152128715.散列表的設(shè)計與實現(xiàn) 1687916.走迷宮游戲 17904817.銀行業(yè)務(wù)模擬與離散事件模擬 181799618.航班信息的查詢與檢索 192216519.藥店的藥品銷售統(tǒng)計系統(tǒng)（排序應(yīng)用） 213039820.二叉樹的遍歷 231175421、樹的應(yīng)用 232492722.排序綜合 23723423.學(xué)生成績管理系統(tǒng) 24288624.圖的遍歷和生成樹求解 251661125.線索二叉樹的應(yīng)用 261305426.稀疏矩陣實現(xiàn)與應(yīng)用 26487227.簡單的職工管理系統(tǒng) 261697328.全國鐵路運輸網(wǎng)最佳經(jīng)由問題 281203831.平衡二叉樹操作演示 303256032.全國交通咨詢模擬 313120033.表達式類型的實現(xiàn) 333218234.關(guān)鍵路徑的實現(xiàn) 341388035.求復(fù)雜表達式的值 35859936.分析二分查找成功時的平均查找長度 351.運動會分數(shù)統(tǒng)計任務(wù)：參加運動會有n個學(xué)校，學(xué)校編號為1……n。比賽分成m個男子項目，和w個女子項目。項目編號為男子1……m，女子m+1……m+w。不同的項目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前三名由學(xué)生自己設(shè)定。（m<=20,n<=20）功能要求：1)可以輸入各個項目的前三名或前五名的成績；2)能統(tǒng)計各學(xué)?？偡郑?)可以按學(xué)校編號或名稱、學(xué)校總分、男女團體總分排序輸出；4)可以按學(xué)校編號查詢學(xué)校某個項目的情況；可以按項目編號查詢?nèi)〉们叭蚯拔迕膶W(xué)校。5)數(shù)據(jù)存入文件并能隨時查詢6)規(guī)定：輸入數(shù)據(jù)形式和范圍：可以輸入學(xué)校的名稱，運動項目的名稱輸出形式：有中文提示，各學(xué)校分數(shù)為整形界面要求：有合理的提示，每個功能可以設(shè)立菜單，根據(jù)提示，可以完成相關(guān)的功能要求。存儲結(jié)構(gòu)：學(xué)生自己根據(jù)系統(tǒng)功能要求自己設(shè)計，但是要求運動會的相關(guān)數(shù)據(jù)要存儲在數(shù)據(jù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關(guān)內(nèi)容在c語言程序設(shè)計的書上，請自學(xué)解決）請在最后的上交資料中指明你用到的存儲結(jié)構(gòu)；測試數(shù)據(jù)：要求使用1、全部合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù)據(jù)。進行程序測試，以保證程序的穩(wěn)定。測試數(shù)據(jù)及測試結(jié)果請在上交的資料中寫明；

2.飛機訂票系統(tǒng)任務(wù)：通過此系統(tǒng)可以實現(xiàn)如下功能：錄入：可以錄入航班情況（數(shù)據(jù)可以存儲在一個數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）查詢：可以查詢某個航線的情況（如，輸入航班號，查詢起降時間，起飛抵達城市，航班票價，票價折扣，確定航班是否滿倉）；可以輸入起飛抵達城市，查詢飛機航班情況；訂票：（訂票情況可以存在一個數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定）可以訂票，如果該航班已經(jīng)無票，可以提供相關(guān)可選擇航班；退票：可退票，退票后修改相關(guān)數(shù)據(jù)文件；e客戶資料有姓名，證件號，訂票數(shù)量及航班情況，訂單要有編號。修改航班信息：當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件要求：根據(jù)以上功能說明，設(shè)計航班信息，訂票信息的存儲結(jié)構(gòu)，設(shè)計程序完成功能；

3.文章編輯功能：輸入一頁文字，程序可以統(tǒng)計出文字、數(shù)字、空格的個數(shù)。靜態(tài)存儲一頁文章，每行最多不超過80個字符，共；要求（1）分別統(tǒng)計出其中英文字母數(shù)和空格數(shù)及整篇文章總字數(shù)；（2）統(tǒng)計某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；（3）刪除某一子串，并將后面的字符前移。存儲結(jié)構(gòu)使用線性表，分別用幾個子函數(shù)實現(xiàn)相應(yīng)的功能；輸入數(shù)據(jù)的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標點符號。輸出形式：（1）分行輸出用戶輸入的各行字符；（2）分4行輸出"全部字母數(shù)"、"數(shù)字個數(shù)"、"空格個數(shù)"、"文章總字數(shù)"（3）輸出刪除某一字符串后的文章；4.地圖著色問題設(shè)計要求：已知中國地圖，對各省進行著色，要求相鄰省所使用的顏色不同，并保證使用的顏色總數(shù)最少。5.宿舍管理查詢軟件1)任務(wù)：為宿舍管理人員編寫一個宿舍管理查詢軟件,程序設(shè)計要求：A.采用交互工作方式B.建立數(shù)據(jù)文件，數(shù)據(jù)文件按關(guān)鍵字（姓名、學(xué)號、房號）進行排序(冒泡、選擇、插入排序等任選一種)2)查詢菜單:(用二分查找實現(xiàn)以下操作)A.按姓名查詢B.按學(xué)號查詢C.按房號查詢3)打印任一查詢結(jié)果（可以連續(xù)操作）

6.校園導(dǎo)航問題設(shè)計要求：設(shè)計你的學(xué)校的平面圖，至少包括10個以上的場所，每兩個場所間可以有不同的路，且路長也可能不同，找出從任意場所到達另一場所的最佳路徑（最短路徑）。1、

基本要求：1）

設(shè)計校園平面圖，在校園景點選10個左右景點。以圖中頂點表示校園內(nèi)各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等有關(guān)信息。2）

為來訪客人提供圖中任意景點相關(guān)信息的查詢。3）

為來訪客人提供任意景點的問路查詢，即查詢?nèi)我鈨蓚€景點之間的一條最短路徑。2、

實現(xiàn)提示：一般情況下，校園的道路是雙向通行的，可設(shè)計校園平面圖是一個無向網(wǎng)。頂點和邊均含有相關(guān)信息。

7.學(xué)校超市選址問題（帶權(quán)有向圖的中心點）設(shè)計要求：對于某一學(xué)校超市，其他各單位到其的距離不同，同時各單位人員去超市的頻度也不同。請為超市選址，要求實現(xiàn)總體最優(yōu)。8.教學(xué)計劃編制問題[問題描述]

大學(xué)的每個專業(yè)都要制定教學(xué)計劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時間長度和學(xué)分上限值均相等，每個專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學(xué)期。試在這樣的前提下設(shè)計一個教學(xué)計劃編制程序。[基本要求]（1）輸入?yún)?shù)包括：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門課的課程號(固定占3位的字母數(shù)字串)、學(xué)分和直接先修課的課程號。（2）允許用戶指定下列兩種編排策略之一：一是使學(xué)生在各學(xué)期中的學(xué)習(xí)負擔(dān)盡量均勻；二是使課程盡可能地集中在前幾個學(xué)期中。（3）若根據(jù)給定的條件問題無解，則報告適當(dāng)?shù)男畔ⅲ环駝t將教學(xué)計劃輸出到用戶指定的文件中。計劃的表格格式自行設(shè)計。[測試數(shù)據(jù)]學(xué)期總數(shù)：6；學(xué)分上限：10；該專業(yè)共開設(shè)12門課，課程號從C01到C12，學(xué)分順序為2,3,4,3,2,3,4,4,7,5,2,3。先修關(guān)系如下：課程編號課程名稱先決條件C1程序設(shè)計基礎(chǔ)無C2離散數(shù)學(xué)C1C3數(shù)據(jù)結(jié)構(gòu)C1，C2C4匯編語言C1C5語言的設(shè)計和分析C3，C4C6計算機原理C11C7編譯原理C5，C3C8操作系統(tǒng)C3，C6C9高等數(shù)學(xué)無C10線性代數(shù)C9C11普通物理C9C12數(shù)值分析C9，C10，C1[實現(xiàn)提示]可設(shè)學(xué)期總數(shù)不超過12，課程總數(shù)不超過100。如果輸入的先修課程號不在該專業(yè)開設(shè)的課程序列中，則作為錯誤處理。應(yīng)建立內(nèi)部課程序號與課程號之間的對應(yīng)關(guān)系。

9.活期儲蓄帳目管理

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

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

用順序和二叉鏈表作存儲結(jié)構(gòu)

1)以回車('\n')為輸入結(jié)束標志,輸入數(shù)列L，生成一棵二叉排

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

11.最小生成樹問題設(shè)計要求：在n個城市之間建設(shè)網(wǎng)絡(luò)，只需保證連通即可，求最經(jīng)濟的架設(shè)方法。存儲結(jié)構(gòu)采用多種。求解算法多種。

12通訊錄的制作模塊要求：第一個模塊——主函數(shù)main()的功能是：根據(jù)選單的選項調(diào)用各函數(shù)，并完成相應(yīng)的功能。第二個模塊——Menu()的功能是：顯示英文提示選單。第三個模塊——Quit()的功能是：退出選單。第四個模塊——Create()的功能是：創(chuàng)建新的通訊錄。第五個模塊——Add()的功能是：在通訊錄的末尾，寫入新的信息，并返回選單。第六個模塊——Find()的功能是：查詢某人的信息，如果找到了，則顯示該人的信息，如果未找到，則提示通訊錄中沒有此人的信息，并返回選單。第七個模塊——Alter()的功能是：修改某人的信息，如果未找到要修改的人，則提示通訊錄中沒有此人的信息，并返回選單。第八個模塊——Delete()的功能是：刪除某人的信息，如果未找到要刪除的人，則提示通訊錄中沒有此人的信息，并返回選單。第九個模塊——List()的功能是：顯示通訊錄中的所有記錄。;設(shè)計要求：1)每條信息至包含：姓名（NAME）、性別(GENDER)、電話（TEL）、城市（CITY）郵編（EIP）幾項。2)作為一個完整的系統(tǒng)，應(yīng)具有友好的界面和較強的容錯能力13.哈夫曼編碼/譯碼器[問題描述]利用哈夫曼編碼進行信息通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼編/譯碼系統(tǒng)。[基本要求]一個完整的系統(tǒng)應(yīng)具有以下功能：（1）I：初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。（2）E：編碼（Encoding）。利用已建好的哈夫曼樹（如不在內(nèi)存，則從文件htmTree中讀入），對文件ToBeTran中的正文進行編碼，然后將結(jié)果存入文件CodeFile中。（3）D：譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進行譯碼，結(jié)果存入文件TextFile中。（4）P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼寫入文件CodePrint中。（5）T：印哈夫曼樹（TreePrinting）。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。[測試數(shù)據(jù)]（1）數(shù)據(jù)一：已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)8種字符，其概率分別為0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,以此設(shè)計哈夫曼編碼。利用此數(shù)據(jù)對程序進行調(diào)試。（2）用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹，并實現(xiàn)以下報文的編碼和譯碼：“THISPROGRAMISMYFAVORITE”。字符MABCDEFGHIJKLM頻度206413223210321154757153220字符NOPQRSTUVWXYZ

頻度5763151485180238181161

[實現(xiàn)提示]（1）文件CodeFile的基類型可以設(shè)為子界型bit=0..1。（2）用戶界面可以設(shè)計為“菜單”方式：顯示上述功能符號，再加上“Q”，表示運行Quit。請用戶鍵入一個先把功能符，些功能執(zhí)行完畢后再經(jīng)菜單，直至某次用戶先把了“E”為止。（3）在程序的一次執(zhí)行過程中，第一次執(zhí)行I、D或C命令之后，哈夫曼樹已經(jīng)在內(nèi)存了，不必再讀入。每次執(zhí)行中不一定執(zhí)行I命令，因為文件hfmTree可能早已建好。

14.圖書管理系統(tǒng)【問題描述】設(shè)計一個計算機管理系統(tǒng)完成圖書管理基本業(yè)務(wù)?！净疽蟆?)每種書的登記內(nèi)容包括書號、書名、著作者、現(xiàn)存量和庫存量；2)對書號建立索引表（線性表）以提高查找效率；3)系統(tǒng)主要功能如下：*采編入庫：新購一種書，確定書號后，登記到圖書帳目表中，如果表中已有，則只將庫存量增加；*借閱：如果一種書的現(xiàn)存量大于0，則借出一本，登記借閱者的書證號和歸還期限，改變現(xiàn)存量；*歸還：注銷對借閱者的登記，改變該書的現(xiàn)存量。【進一步完成內(nèi)容】1)系統(tǒng)功能的進一步完善；2)索引表采用樹表。3)設(shè)計內(nèi)容4)程序流程圖5)源程序6)軟件測試報告（包括所用到的數(shù)據(jù)及結(jié)果）

15.散列表的設(shè)計與實現(xiàn)【問題描述】設(shè)計散列表實現(xiàn)電話號碼查找系統(tǒng)?！净疽蟆?)設(shè)每個記錄有下列數(shù)據(jù)項：電話號碼、用戶名、地址；2)從鍵盤輸入各記錄，分別以電話號碼和用戶名為關(guān)鍵字建立散列表；3)采用一定的方法解決沖突；4)查找并顯示給定電話號碼的記錄；5)查找并顯示給定用戶名的記錄。【進一步完成內(nèi)容】1)系統(tǒng)功能的完善；2)設(shè)計不同的散列函數(shù)，比較沖突率；3)在散列函數(shù)確定的前提下，嘗試各種不同類型處理沖突的方法，考察平均查找長度的變化。

16.走迷宮游戲程序開始運行時顯示一個迷宮地圖，迷宮中央有一只老鼠，迷宮的右下方有一個糧倉。游戲的任務(wù)是使用鍵盤上的方向鍵操縱老鼠在規(guī)定的時間內(nèi)走到糧倉處。要求：1)老鼠形象可辨認，可用鍵盤操縱老鼠上下左右移動；2)迷宮的墻足夠結(jié)實，老鼠不能穿墻而過；3)正確檢測結(jié)果，若老鼠在規(guī)定時間內(nèi)走到糧倉處，提示成功，否則提示失?。?)添加編輯迷宮功能，可修改當(dāng)前迷宮，修改內(nèi)容：墻變路、路變墻；5)找出走出迷宮的所有路徑，以及最短路徑。利用序列化功能實現(xiàn)迷宮地圖文件的存盤和讀出等功能

17.銀行業(yè)務(wù)模擬與離散事件模擬【問題描述】假設(shè)某銀行有4個窗口對外接待客戶，從早晨銀行開門（開門9：00am，關(guān)門5：00pm）起不斷有客戶進入銀行。由于每個窗口在某個時刻只能接待一個客戶，因此在客戶人數(shù)眾多時需要在每個窗口前順次排隊，對于剛進入銀行的客戶（建議：客戶進入時間使用隨機函數(shù)產(chǎn)生），如果某個窗口的業(yè)務(wù)員正空閑，則可上前辦理業(yè)務(wù)；反之，若4個窗口均有窗戶所占，他便會排在人數(shù)最少的隊伍后面。【任務(wù)要求】（1）編制一個程序以模擬銀行的這種業(yè)務(wù)活動并計算一天中客戶在銀行逗留的平均時間。（2）建議有如下設(shè)置：a.客戶到達時間隨機產(chǎn)生，一天客戶的人數(shù)設(shè)定為100人。b.銀行業(yè)務(wù)員處理時間隨機產(chǎn)生，平均處理時間10分鐘。（3）將一天的數(shù)據(jù)（包括業(yè)務(wù)員和客戶）以文件方式輸出?！緶y試數(shù)據(jù)】由隨機數(shù)產(chǎn)生器生成

18.航班信息的查詢與檢索【問題描述】該設(shè)計要求對飛機航班信息進行排序和查找?？砂春桨嗟暮桨嗵枴⑵瘘c站、到達站、起飛時間以及到達時間等信息進行查詢。【任務(wù)要求】對于本設(shè)計，可采用基數(shù)排序法對一組具有結(jié)構(gòu)特點的飛機航班號進行排序，利用二分查找法對排好序的航班記錄按航班號實現(xiàn)快速查找，按其他次關(guān)鍵字的查找可采用最簡單的順序查找方法進行，因此他們用得較少。每個航班記錄包括八項，分別是：航班號、起點站、終點站、班期、起飛時間、到達時間、飛機型號以及票價等，假設(shè)航班信息表（8條記錄）航班號起點站終點站班期起飛時間到達時間機型票價CA1544合肥北京10551240733960MU5341上海廣州每日14201615M901280CZ3869重慶深圳2.4.6085510357331010MU3682桂林南京.720502215M901380HU1836上海北京每日094011207381250CZ3528成都廈門.715101650CRJ1060MU4594昆明西安101511403281160SC7425青島?？?.3.619202120DH41630其中航班號一項的格式為：K0K1K2K3K4K5CZ3869其中K0和K1的輸入值是航空公司的別稱，用兩個大寫字母標示，后4位為航班號，這種航班號關(guān)鍵字可分成兩段，即字母和數(shù)字。其余七項輸入內(nèi)容因為不涉及本設(shè)計的核心，因此除了票價為數(shù)值型外，均定義為字符串即可?！緶y試數(shù)據(jù)】自行設(shè)定，注意邊界等特殊情況。19.藥店的藥品銷售統(tǒng)計系統(tǒng)（排序應(yīng)用）【問題描述】設(shè)計一系統(tǒng)，實現(xiàn)醫(yī)藥公司定期對銷售各藥品的記錄進行統(tǒng)計，可按藥品的編號、單價、銷售量或銷售額做出排名?！緦崿F(xiàn)提示】在本設(shè)計中，首先從數(shù)據(jù)文件中讀出各藥品的信息記錄，存儲在順序表中。各藥品的信息包括：藥品編號、藥名、藥品單價、銷出數(shù)量、銷售額。藥品編號共4位，采用字母和數(shù)字混合編號，如：A125，前一位為大寫字母，后三位為數(shù)字，按藥品編號進行排序時，可采用基數(shù)排序法。對各藥品的單價、銷售量或銷售額進行排序時，可采用多種排序方法，如直接插入排序、冒泡排序、快速排序，直接選擇排序等方法。在本設(shè)計中，對單價的排序采用冒泡排序法，對銷售量的排序采用快速排序法，對銷售額的排序采用堆排序法。藥品信息的元素類型定義：typedefstructnode{charnum[4];/*藥品編號*/charname[10];/*藥品名稱*/floatprice;/*藥品單價*/intcount;/*銷售數(shù)量*/floatsale;/*本藥品銷售額*/}DataType;存儲藥品信息的順序表的定義：typedefstruct{DataTyper[MaxSize];intlength;}SequenList;20.二叉樹的遍歷要求實現(xiàn)二叉樹的中序、前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法，應(yīng)包含建樹的實現(xiàn)。要求：遍歷內(nèi)容可以是數(shù)值可以是字符或者記錄等等。21、樹的應(yīng)用要求實現(xiàn)樹與二叉樹的轉(zhuǎn)換的以及樹的前序、后序的遞歸、非遞歸算法，層次序的非遞歸算法的實現(xiàn)，應(yīng)包含建樹的實現(xiàn)。遍歷內(nèi)容可以是數(shù)值可以是字符或者記錄等等。

22.排序綜合

利用隨機函數(shù)產(chǎn)生N個隨機整數(shù)（20000以上），對這些數(shù)進行多種方法進行排序。要求：1)至少采用三種方法實現(xiàn)上述問題求解（提示，可采用的方法有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結(jié)果保存在不同的文件中。2)統(tǒng)計每一種排序方法的性能（以上機運行程序所花費的時間為準進行對比），找出其中兩種較快的方法。3)如果采用4種或4種以上的方法者，可適當(dāng)加分。

23.學(xué)生成績管理系統(tǒng)現(xiàn)有學(xué)生成績信息文件1（1.txt），內(nèi)容如下姓名

學(xué)號

語文

數(shù)學(xué)

英語

張明明

01

67

78

82李成友

02

78

91

88張輝燦

03

68

82

56王露

04

56

45

77陳東明

05

67

38

47….

..

..

..

…學(xué)生成績信息文件2（2.txt）,內(nèi)容如下:姓名

學(xué)號

語文

數(shù)學(xué)

英語

陳果

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ù)進行合并,生成新文件3.txt2)抽取出三科成績中有補考的學(xué)生并保存在一個新文件4.txt3)對合并后的文件3.txt中的數(shù)據(jù)按總分降序排序(至少采用兩種排序方法實現(xiàn))4)輸入一個學(xué)生姓名后,能查找到此學(xué)生的信息并輸出結(jié)果(至少采用兩種查找方法實現(xiàn))5)要求使用結(jié)構(gòu)體,鏈或數(shù)組等實現(xiàn)上述要求.6)采用多種方法且算法正確者,可適當(dāng)加分.24.圖的遍歷和生成樹求解【基本要求】1)先任意創(chuàng)建一個圖；2)圖的DFS,BFS的遞歸和非遞歸算法的實現(xiàn)3)最小生成樹（兩個算法）的實現(xiàn)，求連通分量的實現(xiàn)4)要求用鄰接矩陣、鄰接表、十字鏈表多種結(jié)構(gòu)存儲實現(xiàn)25.線索二叉樹的應(yīng)用要求：實現(xiàn)線索樹建立、插入、刪除、恢復(fù)線索的實現(xiàn)。26.稀疏矩陣實現(xiàn)與應(yīng)用要求：實現(xiàn)三元組，十字鏈表下的稀疏矩陣的加、轉(zhuǎn)、乘的實現(xiàn)。

27.簡單的職工管理系統(tǒng)【問題描述】對單位的職工進行管理，包括插入、刪除、查找、排序等功能?！净疽蟆柯毠ο蟀ㄐ彰⑿詣e、出生年月、工作年月、學(xué)歷、職務(wù)、住址、電話等信息。（1）新增一名職工：將新增職工對象按姓名以字典方式職工管理文件中。（2）刪除一名職工：從職工管理文件中刪除一名職工對象。（3）查詢：從職工管理文件中查詢符合某些條件的職工。（4）修改：檢索某個職工對象，對其某些屬性進行修改。（5）排序：按某種需要對職工對象文件進行排序?！緦崿F(xiàn)提示】職工對象數(shù)不必很多，便于一次讀入內(nèi)存，所有操作不經(jīng)過內(nèi)外存交換。（1）由鍵盤輸入職工對象，以文件方式保存。程序執(zhí)行時先將文件讀入內(nèi)存。（2）對職工對象中的"姓名"按字典順序進行排序。（3）對排序后的職工對象進行增、刪、查詢、修改、排序等操作?！具x做內(nèi)容】將職工對象按散列法存儲，并設(shè)計解決沖突的方法。在此基礎(chǔ)上實現(xiàn)增、刪、查詢、修改、排序等操作。

28.全國鐵路運輸網(wǎng)最佳經(jīng)由問題【問題描述】這是上海鐵路局目前仍在使用的行包托運軟件中的一部分內(nèi)部算法。該題目采用1995年年底我國鐵路運輸網(wǎng)的真實數(shù)據(jù)進行編程和運行驗證。鐵路運輸網(wǎng)絡(luò)中由鐵路線和火車站的兩個主要概念，譬如：1號鐵路線表示京廣線，2號鐵路線表示京滬線等。鐵路線對象包括鐵路線編號,鐵路線名稱，起始站編號,終點站編號,該鐵路線長度，通行標志(00B客貨運禁行,01B貨運通行專線，10B客運通行專線，11B客貨運通行)。火車站對象包括所屬鐵路線編號，車站代碼，車站名，車站簡稱，離該鐵路線起點站路程及終點站路程。【基本要求】（1）

查詢某站所屬的鐵路線（2）

要求具備新增鐵路線的管理功能（3）

要求具備新增車站的管理功能（4）

針對客運，貨運情況能計算任何一個起始車站到任何一個終點站之間的最短路徑。并且要求能夠顯示出該最短路徑的各個火車站的經(jīng)由順序29.模擬電梯工作【問題描述】設(shè)計一個模擬電梯工作過程的圖形演示系統(tǒng)，要求所設(shè)計的電梯能符合市場上大多數(shù)系統(tǒng)的要求。30.停車場管理【問題描述】設(shè)有一個可以停放n輛汽車的狹長停車場，它只有一個大門可以供車輛進出。車輛按到達停車場時間的早晚依次從停車場最里面向大門口處停放(最先到達的第一輛車放在停車場的最里面)。如果停車場已放滿n輛車，則后來的車輛只能在停車場大門外的便道上等待，一旦停車場內(nèi)有車開走，則排在便道上的第一輛車就進入停車場。停車場內(nèi)如有某輛車要開走，在它之后進入停車場的車都必須先退出停車場為它讓路，待其開出停車場后，這些車輛再依原來的次序進場。每輛車在離開停車場時，都應(yīng)根據(jù)它在停車場內(nèi)停留的時間長短交費。如果停留在便道上的車未進停車場就要離去，允許其離去，不收停車費，并且仍然保持在便道上等待的車輛的次序。編制一程序模擬該停車場的管理?！緦崿F(xiàn)要求】要求程序輸出每輛車到達后的停車位置(停車場或便道上)，以及某輛車離開停車場時應(yīng)交納的費用和它在停車場內(nèi)停留的時間?！緦崿F(xiàn)提示】汽車的模擬輸入信息格式可以是：(到達／離去，汽車牌照號碼，到達／離去的時刻)。例如，(‘A’，，1，5)表示1號牌照車在5這個時刻到達，而(‘D’，，5，20)表示5號牌照車在20這個時刻離去。整個程序可以在輸入信息為(‘E’，0，0)時結(jié)束。本題可用棧和隊列來實現(xiàn)。31.平衡二叉樹操作演示【問題描述】利用平衡二叉樹實現(xiàn)一個動態(tài)查找表【基本要求】實現(xiàn)動態(tài)查找表的三種基本功能：查找、插入和刪除。【測試數(shù)據(jù)】自行設(shè)定【實現(xiàn)提示】（1）初始，平衡二叉樹為空樹，操作界面給出查找、插入和刪除三種操作供選擇。每種操作均要提示輸入關(guān)鍵字。每次插入或刪除一個結(jié)點后應(yīng)更新平衡二叉樹的顯示。（2）平衡二叉樹的顯示可以采用凹入表形式，也可以采用圖形界面畫出樹形。（3）教科書已給出查找和插入的算法，本題重點在于對刪除算法的設(shè)計和實現(xiàn)。假設(shè)要刪除關(guān)鍵字為x的結(jié)點。如果x不在葉子結(jié)點上，則用它左子樹中的最大值或右子樹中的最小值取代x。如此反復(fù)取代，指導(dǎo)刪除動作傳遞到某個葉子結(jié)點。刪除葉子結(jié)點時，若需要進行平衡變換，則可采用插入平衡變換的反變換（如，左子樹變矮對應(yīng)于右子樹長高）32.全國交通咨詢模擬【問題描述】出于不同目的的旅客對交通工具有不同的要求。例如，因公出差的旅客希望在旅途中的時間盡可能短，出門旅游的游客則期望旅費盡可能省，而老年旅客則要求中轉(zhuǎn)次數(shù)最少。編制一個全國城市間的交通咨詢程序，為旅客提供兩種或三種最優(yōu)決策的交通咨詢?！净疽蟆浚?）提供對城市信息進行編輯（如：添加或刪除）的功能。（2）城市之間有兩種交通工具：火車和飛機。提供對列車時刻表和飛機航班進行編輯（增設(shè)或刪除）的功能。（3）提供兩種最優(yōu)決策：最快到達或最省錢到達。全程只考慮一種交通工具。（4）旅途中耗費的總時間應(yīng)該包括中轉(zhuǎn)站的等候時間。（5）咨詢以用戶和計算機的對話方式進行。由用戶輸入起始站、終點站、最優(yōu)決策原則和交通工具，輸出信息：最快需要多長時間才能到達或者最少需要多少旅費才能到達，并詳細說明依次于何時乘坐哪一趟列車或哪一次班機到何地。【測試數(shù)據(jù)】參考教科書7.6節(jié)圖7.33的全國交通圖，自行設(shè)計列出時刻表和飛機航班【實現(xiàn)提示】（1）對全國城市交通圖和列出時刻表及飛機航班的編輯，應(yīng)該提供文件