數(shù)據(jù)結(jié)構(gòu)題目匯總

1、序號(hào)題目?jī)?nèi)容難度1飛機(jī)訂票系統(tǒng)設(shè)計(jì)一小型飛機(jī)訂票系統(tǒng)，系統(tǒng)主要功能如下：1. 錄入航班情況，修改航班信息；2. 查詢：查詢航線情況（如，輸入航班號(hào)，起降時(shí)間，起飛抵達(dá)城市，航班票價(jià)，票價(jià)折扣，確定航班是否滿倉等）；3訂票：實(shí)現(xiàn)訂票功能，如果該航班已經(jīng)無票，可以提供相關(guān)可選擇航班；4退票：可退票，退票后修改相關(guān)數(shù)據(jù)文件；根據(jù)以上功能說明，自己設(shè)計(jì)航班信息，訂票信息的存儲(chǔ)結(jié)構(gòu)。B-2宿舍管理軟件采用簡(jiǎn)單交互方式設(shè)計(jì)一小型宿舍管理軟件，系統(tǒng)主要功能如下：1. 錄入及修改學(xué)生信息；2. 查詢：按照姓名、學(xué)號(hào)和房間號(hào)等查詢；3刪除：可按照某條件實(shí)現(xiàn)批量刪除功能。注：學(xué)生基本信息：姓名，學(xué)生證件號(hào)，房間號(hào)

2、，專業(yè)，班級(jí)和性別等。存儲(chǔ)結(jié)構(gòu)可以選用單鏈表或循環(huán)鏈表，也可根據(jù)功能需要自己設(shè)計(jì)。B-3圖書借閱管理軟件設(shè)計(jì)一小型圖書借閱管理軟件，系統(tǒng)主要功能如下：1. 錄入新到圖書的基本信息；2. 查詢：按照作者、書名和出版社等查詢，查找算法要求使用折半查找算法；3借閱：借閱人，借閱數(shù)量，期限等。對(duì)書號(hào)建立索引表（線性表）以提高查找效率，存儲(chǔ)結(jié)構(gòu)自定。B-4學(xué)生成績(jī)管理設(shè)計(jì)一小型成績(jī)管理軟件，系統(tǒng)主要功能如下：1. 錄入、修改和刪除學(xué)生信息；2. 查詢：按照姓名或?qū)W號(hào)查詢，查找算法要求使用折半查找算法；3學(xué)生成績(jī)排序、分類，平均成績(jī)計(jì)算等。 注：學(xué)生基本信息：姓名，學(xué)生證件號(hào)，專業(yè)，班級(jí)和性別等。B-5同

3、學(xué)通訊錄設(shè)計(jì)一小型同學(xué)通訊錄，系統(tǒng)主要功能如下：1. 錄入、修改及刪除同學(xué)信息；2. 查詢：按照姓名、城市等查詢，查找算法可以使用折半查找；3排序：按照同學(xué)姓名排序，排序方法不唯一。 注：同學(xué)基本信息：姓名，性別，電話，E-MAIL和城市等。存儲(chǔ)結(jié)構(gòu)可以選用單鏈表或循環(huán)鏈表，也可根據(jù)功能需要自己設(shè)計(jì)。B-6工資管理軟件設(shè)計(jì)一個(gè)職工工資管理軟件，存儲(chǔ)結(jié)構(gòu)自定。系統(tǒng)主要功能如下：1. 新職工信息的錄入;2調(diào)離和死亡等職工信息的刪除；2. 職工某些信息的修改；3. 職工信息的查找。B-7航班信息的查詢與檢索1. 建立：建立一個(gè)線性表的存儲(chǔ)結(jié)構(gòu)。2. 錄入功能：輸入航班信息。3. 排序：按航班號(hào)進(jìn)行排

4、序。3. 查詢功能：輸入航班號(hào)顯示相應(yīng)數(shù)據(jù)元素。輸入起點(diǎn)站顯示相應(yīng)數(shù)據(jù)元素。輸入終點(diǎn)站顯示相應(yīng)數(shù)據(jù)元素。輸入起飛時(shí)間顯示相應(yīng)數(shù)據(jù)元素。輸入到達(dá)時(shí)間顯示相應(yīng)數(shù)據(jù)元素。B-8火車售票系統(tǒng)1. 列車基本信息管理：輸入所有列班信息。每條路線所涉及的信息有：終點(diǎn)站名、車次號(hào)、車廂號(hào)、開車周日（星期幾）、乘員定額、余票量、已訂票的客戶名單（包括姓名、訂票量、座位等級(jí)1，2或3）以及等候替補(bǔ)的客戶名單（包括姓名、所需的票量）。2列車基本信息查詢：按車次號(hào)查找，按抵達(dá)站查找，按路線查找三種查找方式進(jìn)行查找。3. 訂票管理：客戶對(duì)想要購買的票進(jìn)行訂票。3. 退票管理：將不想要的票進(jìn)行退票。B-9小型學(xué)生運(yùn)動(dòng)會(huì)成

5、績(jī)管理軟件設(shè)計(jì)一款小型學(xué)生運(yùn)動(dòng)會(huì)成績(jī)管理軟件，記錄某校運(yùn)動(dòng)會(huì)上全部運(yùn)動(dòng)項(xiàng)目，各系獲得的分?jǐn)?shù)及排名的情況，包括50、100、200，400，1500米，跳高，跳遠(yuǎn)，標(biāo)槍，鉛球鐵餅等。進(jìn)入系統(tǒng)后可以輸入和修改某個(gè)項(xiàng)目的結(jié)果情況，可以按各系院編號(hào)輸出總分；按總分排序；按男團(tuán)體總分排序 ；按系院編號(hào)查詢；按項(xiàng)目編號(hào)查詢；按女團(tuán)體總分排序。B-10個(gè)人帳簿管理系統(tǒng)設(shè)計(jì)個(gè)人帳簿管理系統(tǒng)記錄某人每月的全部收入及各項(xiàng)開支情況，包括食品消費(fèi)，房租，子女教育費(fèi)用，水電費(fèi)，醫(yī)療費(fèi)，儲(chǔ)蓄等。進(jìn)入系統(tǒng)后可以輸入和修改某月的收支情況，可以對(duì)每月的開支從小到大進(jìn)行排序，可以根據(jù)輸入的月份查詢每月的收支情況。B-11一元多項(xiàng)

6、式加（減）法計(jì)算設(shè)計(jì)一個(gè)一元多項(xiàng)式簡(jiǎn)單的加(減)法計(jì)算器，系統(tǒng)主要功能如下：1. 從鍵盤輸入多項(xiàng)式，并以文件形式存儲(chǔ)；2. 實(shí)現(xiàn)兩個(gè)多項(xiàng)式相加,并建立輸出多項(xiàng)式；3實(shí)現(xiàn)兩個(gè)多項(xiàng)式相減,并建立輸出多項(xiàng)式。注：可選擇帶頭結(jié)點(diǎn)的單循環(huán)鏈表或單向鏈表存儲(chǔ)多項(xiàng)式。B-12看 病 排 隊(duì)用隊(duì)列模擬上述看病排隊(duì)候診的問題，建立兩個(gè)隊(duì)列分別對(duì)應(yīng)兩個(gè)不同的優(yōu)先級(jí)別，按照從終端讀入的輸入數(shù)據(jù)的方式進(jìn)行模擬管理。（1）新的病人掛號(hào)然后加入隊(duì)列候診，護(hù)士根據(jù)病情指定其優(yōu)先級(jí)。（2）醫(yī)生根據(jù)優(yōu)先級(jí)別為病人進(jìn)行診治。（3）病人出隊(duì)。B-13自動(dòng)括號(hào)匹配器的設(shè)計(jì)假設(shè)一個(gè)算術(shù)表達(dá)式中可包含三種括號(hào)：圓括號(hào)，方括號(hào)和花括號(hào)且這

7、三種括號(hào)可按任意次序嵌套使用。試?yán)脳５倪\(yùn)算，編寫判別給定表達(dá)式中所含括號(hào)是否正確配對(duì)出現(xiàn)的算法。B-14約瑟夫環(huán)編號(hào)為1，2 n的n個(gè)人按順時(shí)針方向圍坐一圈，每人持有一個(gè)密碼（正整數(shù)）。一開始任選一個(gè)正整數(shù)作為報(bào)數(shù)的上限值m，從第一個(gè)人開始按順時(shí)針方向自1開始順序報(bào)數(shù)，報(bào)到m時(shí)停止報(bào)數(shù)，報(bào)m的人出列，將他的密碼作為新的m值，從他的順時(shí)針方向上的下一個(gè)開始重新從1報(bào)數(shù)，如此下去，直至所有人全部出列為止，設(shè)計(jì)一個(gè)程序求出出列順序。B-15串的查找和替換打開一篇英文文章，在該文章中找出所有給定的單詞，然后對(duì)所有給定的單詞替換為另外一個(gè)單詞，再存盤。B-16紙牌游戲編號(hào)為1-52張牌，正面向上，從第

8、2張開始，以2為基數(shù)，是2的倍數(shù)的牌翻一次，直到最后一張牌；然后，從第3張開始，以3為基數(shù)，是3的倍數(shù)的牌翻一次，直到最后一張牌；然后從第4張開始，以4為基數(shù)，是4的倍數(shù)的牌翻一次， 直到最后一張牌；.再依次5的倍數(shù)的牌翻一次，1的，1的直到 以52為基數(shù)的 翻過，輸出：這時(shí)正面向上的牌有哪些？B-17專利信息檢索系統(tǒng)專利信息的數(shù)據(jù)量很大，為了提高檢索速度，對(duì)專利題目建立關(guān)鍵詞索引表,并能根據(jù)關(guān)鍵詞進(jìn)行快速檢索。指定一個(gè)文本文件, 文件中按行存放著若干專利的題目，對(duì)這些專利題目建立關(guān)鍵字索引, 并能夠根據(jù)關(guān)鍵字進(jìn)行快速檢索。自擬定提取關(guān)鍵字的算法,要有一定的合理性。B-18舞伴配對(duì)程序假設(shè)在某

9、場(chǎng)舞會(huì)上，男士和女士進(jìn)入舞廳時(shí)分別排成兩隊(duì)。跳舞開始時(shí)，依次從男隊(duì)和女隊(duì)的開始位置各出一個(gè)配成舞伴。若兩初始人數(shù)不相同，則較長(zhǎng)的那一隊(duì)中未配對(duì)者等待下一輪舞曲。編寫程序模擬上述舞伴配對(duì)程序。B-19撲克牌的排序編寫算法能夠用基數(shù)排序算法對(duì)撲克牌進(jìn)行排序。應(yīng)能夠選擇按花色優(yōu)先或按面值優(yōu)先，初始撲克牌牌序要求能自動(dòng)的生成（隨機(jī)生成）。B-20離散事件的模擬假設(shè)某銀行有四個(gè)窗口對(duì)外接待客戶，從早晨銀行開門起不斷有客戶進(jìn)入銀行。由于每個(gè)窗口在某個(gè)時(shí)刻只能接待一個(gè)客戶，因此在客戶人數(shù)眾多時(shí)需在每個(gè)窗口前順次排隊(duì)，對(duì)于剛進(jìn)入銀行的客戶，如果某個(gè)窗口的業(yè)務(wù)員正空閑，則可上前辦理業(yè)務(wù)，反之，若四個(gè)窗口均有客戶

10、所占，他便會(huì)排在人數(shù)最少的隊(duì)伍后面。這個(gè)程序以模擬銀行的這種業(yè)務(wù)活動(dòng)并計(jì)算一天中客戶在銀行逗留的平均時(shí)間。B-21實(shí)現(xiàn)并演示堆排序的排序算法和排序過程從鍵盤輸入以整數(shù)序列, 可以動(dòng)態(tài)演示堆排序算法對(duì)該整數(shù)序列進(jìn)行排序的過程,并輸出排序后的結(jié)果。B-22實(shí)現(xiàn)并演示快速排序的排序算法和排序過程從鍵盤輸入以整數(shù)序列,可以動(dòng)態(tài)演示快速排序算法對(duì)該整數(shù)序列進(jìn)行排序的過程,并輸出排序后的結(jié)果。B-23實(shí)現(xiàn)并演示希爾排序的排序算法和排序過程從鍵盤輸入以整數(shù)序列,可以動(dòng)態(tài)演示希爾排序算法對(duì)該整數(shù)序列進(jìn)行排序的過程,并輸出排序后的結(jié)果。B-24實(shí)現(xiàn)并演示歸并排序的排序算法和排序過程從鍵盤輸入以整數(shù)序列,可以動(dòng)態(tài)

11、演示歸并排序算法對(duì)該整數(shù)序列進(jìn)行排序的過程,并輸出排序后的結(jié)果。B-25英文詞頻統(tǒng)計(jì)程序設(shè)計(jì)一個(gè)程序，統(tǒng)計(jì)一篇英文文章中每個(gè)單詞出現(xiàn)頻率，然后根據(jù)用戶輸入的兩個(gè)閾值a和b，將詞頻大于a的和詞頻小于b的所有單詞輸出。B-26排序綜合利用隨機(jī)函數(shù)產(chǎn)生N個(gè)隨機(jī)整數(shù)（N2000000），對(duì)這些數(shù)進(jìn)行多種方法進(jìn)行排序。要求：1.要求采用所學(xué)的全部七種排序方法實(shí)現(xiàn)上述問題求解（具體有插入排序、希爾排序、起泡排序、快速排序、選擇排序、堆排序、歸并排序）。并把排序后的結(jié)果保存在不同的文件中。2.統(tǒng)計(jì)每一種排序方法的性能（以上機(jī)運(yùn)行程序所花費(fèi)的時(shí)間為準(zhǔn)進(jìn)行對(duì)比），找出其中兩種較快的方法。B-27基于雙向循環(huán)鏈表

12、的通訊錄的設(shè)計(jì)利用雙向循環(huán)鏈表作為存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)并實(shí)現(xiàn)一個(gè)通訊錄程序。可以實(shí)現(xiàn)信息的添加、插入、刪除、查詢和統(tǒng)計(jì)等功能B-1大整數(shù)計(jì)算器由于整形數(shù)據(jù)存儲(chǔ)位數(shù)有限，因此引入串的概念，將整型數(shù)據(jù)用字符串進(jìn)行存儲(chǔ)，利用字符串的一個(gè)字符存儲(chǔ)大整數(shù)的一位數(shù)值，然后根據(jù)四則運(yùn)算規(guī)則對(duì)相應(yīng)位依次進(jìn)行運(yùn)算，同時(shí)保存進(jìn)位，從而實(shí)現(xiàn)大整數(shù)精確的運(yùn)算。B2關(guān)鍵詞提取程序設(shè)計(jì)一個(gè)簡(jiǎn)單的英文關(guān)鍵詞提取程序，可實(shí)現(xiàn)對(duì)一段英文短文中出現(xiàn)的頻率最高的三個(gè)到五個(gè)詞或短語進(jìn)行提取。要求：1.從文件中讀取一篇英文短文（300詞以內(nèi)），并顯示在屏幕上。2.按照出現(xiàn)頻率順序顯示三個(gè)到五個(gè)詞語，并注明出現(xiàn)的次數(shù)。B3停車場(chǎng)管理程序設(shè)停車場(chǎng)

13、內(nèi)只有一個(gè)可停入n輛汽車的狹長(zhǎng)通道，且只有一個(gè)大門可供汽車進(jìn)出。汽車在停車場(chǎng)內(nèi)按車輛到達(dá)時(shí)的先后順序，依次由北向南排列（大門在最南端，最先到達(dá)的第一輛車停放在最北端），若停車場(chǎng)內(nèi)已停滿n輛汽車，則后來的汽車只能停在門外的過道止等候，一旦停車場(chǎng)內(nèi)有車開走，則排在過道上的第一輛車即可開入；當(dāng)停車場(chǎng)內(nèi)某車輛要離開時(shí)，由于停車場(chǎng)是狹長(zhǎng)的通道，在它之后開入車輛必須先退出停車場(chǎng)為它讓路，待該輛車開出大門外后，為它讓路的車輛再按原次序進(jìn)入停車場(chǎng)。每輛車按其在停車場(chǎng)停留的時(shí)間付費(fèi)，車輛停在停車場(chǎng)內(nèi)時(shí)需要計(jì)時(shí)收費(fèi)，而停在過道上不收費(fèi)。按這個(gè)要求，設(shè)計(jì)一個(gè)停車場(chǎng)管理程序。B4求解馬踏棋盤問題國際象棋共有8行8列，

14、共64個(gè)單元格，無論將馬放于棋盤的哪個(gè)單元格，都可以讓馬踏遍棋盤的每個(gè)單元格。馬只能走日字，當(dāng)馬位于棋盤中間位置時(shí)，馬可以向8個(gè)方向跳動(dòng)，當(dāng)馬位于棋盤的邊或角時(shí)，馬可以跳動(dòng)的方向?qū)⑸儆?個(gè)。另外，當(dāng)馬所跳向的8 個(gè)方向中的某一個(gè)或幾個(gè)方向若已經(jīng)被馬走過，也將跳至馬下一步要走的位置。B5黑白棋游戲程序黑白棋，又叫翻轉(zhuǎn)棋、蘋果棋或奧賽羅棋。棋盤共有8行8列共64格。開局時(shí)棋盤正中央的4格先放黑白相隔的4枚棋子，黑白子為交叉放置。通常黑子先行。雙方輪流落子。只要落子和棋盤上任一枚己方的棋子在一條線上（橫、直、斜線皆可）夾著對(duì)方棋子，就能將對(duì)方的這些棋子轉(zhuǎn)變?yōu)榧悍降钠遄樱ǚ婕纯桑?。如果在任一位置落?/p>

15、都不能夾住對(duì)手的任一顆棋子，就要讓對(duì)手下棋。當(dāng)雙方皆不能下子時(shí)，或者64個(gè)方格全部占滿后，游戲就結(jié)束，子多一方獲勝。B6文字編輯軟件設(shè)計(jì)一小型文字編輯軟件，系統(tǒng)主要功能如下：1. 從鍵盤輸入文字，以文本文件形式存儲(chǔ)；2. 統(tǒng)計(jì)該文本文件中英文字母數(shù)、空格數(shù)及整篇文章總字?jǐn)?shù)；3統(tǒng)計(jì)某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)；4刪除某一子串，并將后面的字符前移。注：存儲(chǔ)結(jié)構(gòu)使用線性表，分別用幾個(gè)子函數(shù)實(shí)現(xiàn)相應(yīng)的功能。B7字符串的排序與查找生成一個(gè)百萬級(jí)的字符串集合，在該集合上演示快速排序，并計(jì)算集合規(guī)模對(duì)排序效率的影響。然后在生成的有序集上進(jìn)行快速字符串查找，要求采用字符串分段hash算法實(shí)現(xiàn)。B

16、8最小矩形面積問題在一個(gè)二維平面中有N個(gè)點(diǎn)（點(diǎn)的數(shù)量不超過50個(gè)），每個(gè)點(diǎn)用二維坐標(biāo)表示，例如，有4個(gè)點(diǎn)，且這4個(gè)點(diǎn)的坐標(biāo)分別為：P1（1，1），P2（2，2），P3（3，6），P4（0，7）可以在二維平面中繪制一個(gè)矩形，使所有N個(gè)點(diǎn)都落在該矩形中。若要使用N個(gè)點(diǎn)都落在繪制的矩形中，則繪制一個(gè)非常大的矩形即可。也可以繪制多個(gè)矩形來覆蓋所有點(diǎn)?，F(xiàn)在要求在輸入文件中給出N個(gè)點(diǎn)的坐標(biāo)和繪制矩形數(shù)量K（1K3），請(qǐng)編程進(jìn)行計(jì)算，怎么才能使得覆蓋所有點(diǎn)的K個(gè)矩形的面積和最小B9應(yīng)用堆實(shí)現(xiàn)一個(gè)優(yōu)先隊(duì)列優(yōu)先隊(duì)列priority queue 是一種可以用于很多場(chǎng)合的數(shù)據(jù)結(jié)構(gòu)，該結(jié)構(gòu)支持如下基本操作：Inser

17、t (S, x) 將元素x 插入集合SMinimum (S) 返回S 中最小的關(guān)鍵字Extract Min (S) 刪除S 中的最小關(guān)鍵字可設(shè)計(jì)要求以堆作為輔助結(jié)構(gòu)實(shí)現(xiàn)一個(gè)優(yōu)先隊(duì)列。要將堆結(jié)構(gòu)嵌入到隊(duì)列結(jié)構(gòu)中，以作為其數(shù)據(jù)組織的一部分。此處由于要用堆實(shí)現(xiàn)隊(duì)列，所以堆結(jié)構(gòu)的存儲(chǔ)表示要求用數(shù)組。B10醫(yī)院選址問題n個(gè)村莊之間的交通圖可以用有向網(wǎng)圖來表示，圖中邊<vi, vj>上的權(quán)值表示從村莊i到村莊j的道路長(zhǎng)度?，F(xiàn)在要從這n個(gè)村莊中選擇一個(gè)村莊新建一所醫(yī)院，問這所醫(yī)院應(yīng)建在哪個(gè)村莊，才能使所有的村莊離醫(yī)院都比較近？B11行編輯程序設(shè)計(jì)一個(gè)簡(jiǎn)單的行編輯程序。程序包括5個(gè)基本命令：E（行

18、編輯）, W（寫入文件），#（退格）, （清除整行）和Q（存盤退出）。程序運(yùn)行后提示用戶輸入命令：當(dāng)用戶輸入“E”命令，開始編輯一行文本，程序?yàn)橛脩羯暾?qǐng)一個(gè)臨時(shí)存放空間（棧），存儲(chǔ)用戶當(dāng)前輸入字符；當(dāng)用戶輸入一個(gè)退格命令“#”，以表示當(dāng)前棧頂字符無效；如果錯(cuò)誤較多，可以鍵入退行符“”，清除棧中整行；當(dāng)行輸入完畢后，輸入“W”命令，則將該行寫入文件中。文件編輯結(jié)束后，輸入“Q”命令，存盤退出。B12迷宮的生成與路由設(shè)計(jì)算法生成一個(gè)N×M(N 行M 列)的迷宮，并完成迷宮的組織和存儲(chǔ)。實(shí)現(xiàn)兩種不同的迷宮路由算法：廣度優(yōu)先，深度優(yōu)先算法。要求：1N 和M 是用戶可配置的，缺省值為50 和5

19、0。2迷宮的入口和出口分別在第0 行和第N-1 行上，隨機(jī)選擇。3生成的迷宮要求是連通的。B13集合運(yùn)算求解設(shè)全集為字母集合，以鏈表代表一個(gè)子集，設(shè)計(jì)一組函數(shù)完成兩個(gè)集合的并、交、差、異或和補(bǔ)五種運(yùn)算，并演示其使用效果。B14索引順序表表創(chuàng)建設(shè)計(jì)一個(gè)索引順序表并給出查找算法。要求：索引表和數(shù)據(jù)表必須采用順序存儲(chǔ)存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)；B15圖的建立及輸出建立圖的存儲(chǔ)結(jié)構(gòu)（圖的類型可以是有向圖、無向圖、有向網(wǎng)、無向網(wǎng)，學(xué)生可以任選兩種類型），能夠輸入圖的頂點(diǎn)和邊的信息，并存儲(chǔ)到相應(yīng)存儲(chǔ)結(jié)構(gòu)中，而后輸出圖的鄰接矩陣。B1二叉排序樹的實(shí)現(xiàn)用順序和二叉鏈表做存儲(chǔ)結(jié)構(gòu)，以回車('n')為輸入結(jié)束標(biāo)

20、志,輸入數(shù)列L，生成一棵二叉排序樹T。對(duì)二叉排序樹T作中序遍歷，輸出結(jié)果；對(duì)二叉排序樹T作先序遍歷，輸出結(jié)果；輸入元素x,查找二叉排序樹T，若存在含x的結(jié)點(diǎn),則刪除該結(jié)點(diǎn)，并作中序遍歷；A-2哈夫曼編碼/譯碼器設(shè)計(jì)一個(gè)利用哈夫曼算法的編碼和譯碼系統(tǒng)，通過鍵盤輸入權(quán)值數(shù)據(jù)，并以文件形式存儲(chǔ)，從屏幕輸出相應(yīng)的哈夫曼樹。利用建好的哈夫曼樹生成哈夫曼編碼，并通過屏幕輸出相應(yīng)的編碼。A-3二叉排序樹的插入、刪除算法1. 給定一組關(guān)鍵字，生成一棵二叉排序樹2. 刪除該二叉排序樹中的指定節(jié)點(diǎn)，刪除后二叉排序樹性質(zhì)不發(fā)生變化3. 用直觀、易于理解的形式來演示二叉排序樹的插入、刪除過程A-4二叉樹遍歷程序設(shè)計(jì)一

21、個(gè)程序：輸入一個(gè)二叉樹,對(duì)該樹分別以先序、中序和后序三種方式進(jìn)行遍歷每個(gè)節(jié)點(diǎn)，并輸出遍歷結(jié)果，要求采用非遞歸算法。A-5樹與二叉樹轉(zhuǎn)換利用雙親表示法創(chuàng)建一棵樹，將該樹轉(zhuǎn)換為二叉鏈表表示，并給出轉(zhuǎn)換后的二叉樹的先序、中序和后序遍歷結(jié)果以及對(duì)該二叉樹進(jìn)行中序遍歷線索化。要求：給出樹的雙親表示和二叉鏈表表示的存儲(chǔ)結(jié)構(gòu)；要求二叉樹三種遍歷要采用非遞歸算法；A-6圖的基本操作編寫算法能夠建立帶權(quán)圖，輸出該帶權(quán)圖各頂點(diǎn)的度，關(guān)聯(lián)的所有邊和邊上的權(quán)值。輸出該帶權(quán)圖的深度、廣度優(yōu)先遍歷序列，并能夠刪除該帶權(quán)圖的任一頂點(diǎn)和該頂點(diǎn)關(guān)聯(lián)的所有邊。A-1Prim算法生成最小生成樹在n個(gè)城市之間建設(shè)網(wǎng)絡(luò)，只需保證連通即

22、可，求最經(jīng)濟(jì)的架設(shè)方法。利用Prim算法輸出n個(gè)城市之間網(wǎng)絡(luò)圖，輸出n個(gè)節(jié)點(diǎn)的最小生成樹。其中，n個(gè)城市表示n個(gè)節(jié)點(diǎn)，兩個(gè)城市間如果有路則用邊連接，生成一個(gè)n個(gè)節(jié)點(diǎn)的邊權(quán)圖，要求鍵盤輸入。A2最短路徑求解從鍵盤輸入一個(gè)圖，節(jié)點(diǎn)代表城市，節(jié)點(diǎn)間的邊代表城市間距離，現(xiàn)指定圖中任意兩個(gè)城市，求出連接這兩個(gè)城市的最短行走路線。A3連通圖著色求解從鍵盤輸入一個(gè)無向圖，給圖上的每一個(gè)節(jié)點(diǎn)標(biāo)記一種顏色，在保證任何相鄰節(jié)點(diǎn)顏色不同的同時(shí)，求解出該圖所需要的最少顏色數(shù)，并給出每個(gè)節(jié)點(diǎn)的具體顏色。A4哈斯圖中特殊元素求解給定一個(gè)有向圖，代表一個(gè)由特定偏序關(guān)系的導(dǎo)出的哈斯圖，指定一個(gè)節(jié)點(diǎn)子集，求解該子集對(duì)應(yīng)的極大元

23、、極小元、最大元、最小元、上界、下界、上確界、下確界八種特殊元素。A5實(shí)現(xiàn)求關(guān)鍵路徑的算法自擬定合適的方式從鍵盤上輸入一個(gè)AOE網(wǎng), 并用合適的存儲(chǔ)結(jié)構(gòu)存儲(chǔ)該AOE網(wǎng). 然后求出該AOE網(wǎng)的關(guān)鍵路徑。A6實(shí)現(xiàn)求有向圖強(qiáng)連通分量的算法以合適方便的方式輸入一有向圖,并建立有向圖的合適的存儲(chǔ)結(jié)構(gòu). 判斷該有向圖是否強(qiáng)連通,如果是強(qiáng)連通圖,則求出該圖的所有的強(qiáng)連通分量并輸出字符。A7二叉排序樹的平衡化從鍵盤輸入一個(gè)整數(shù)序列,根據(jù)該整數(shù)序列構(gòu)造一棵平衡的二叉排序樹。注意在構(gòu)造二叉排序樹時(shí),要按照整數(shù)序列中整數(shù)的輸入順序插入節(jié)點(diǎn)。利用中序遍歷算法輸出經(jīng)過平衡化的二叉排序樹，輸出時(shí)，輸出每個(gè)節(jié)點(diǎn)的平衡因子。

24、A8KRUSKAL算法求最小生成樹以合適方便的方式輸入一個(gè)邊帶權(quán)值的無向圖，采用鄰接表存儲(chǔ)結(jié)構(gòu)存儲(chǔ)該無向圖，然后根據(jù)KRUSKAL算法求該無向圖的最小生成樹并輸出A9求有向圖中所有簡(jiǎn)單回路以合適方便的方式輸入一有向圖，并建立有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)，然后求該有向圖中所有的簡(jiǎn)單回路。輸入有向圖的方式要盡量簡(jiǎn)單方便，要能夠形象方便地觀察有向圖的圖形結(jié)構(gòu)。A10有向圖的拓?fù)渑判蛞院线m方便的方式輸入一個(gè)有向圖，采用鄰接表存儲(chǔ)結(jié)構(gòu)存儲(chǔ)該有向圖，然后對(duì)該有向圖進(jìn)行拓?fù)渑判?，如果該有向圖有環(huán)存在，程序需要給出圖中有環(huán)的輸出結(jié)果，否則輸出對(duì)圖進(jìn)行拓?fù)渑判虻慕Y(jié)果。A11稀疏矩陣運(yùn)算稀疏矩陣是指那些多數(shù)元素為零的矩

25、陣。利用“稀疏”特點(diǎn)進(jìn)行存儲(chǔ)和計(jì)算可以大大的節(jié)省存儲(chǔ)空間，提高計(jì)算效率。寫一個(gè)以十字鏈表為存儲(chǔ)結(jié)構(gòu)的稀疏矩陣相加的程序。兩個(gè)稀疏矩陣以元素值三元組的形式從終端讀入，結(jié)果矩陣則以通常的陣列形輸出。A12偏序關(guān)系中特殊元素判定給定一個(gè)有向圖，代表一個(gè)由特定偏序關(guān)系的導(dǎo)出的哈斯圖，指定一個(gè)節(jié)點(diǎn)子集，求解該子集對(duì)應(yīng)的極大元、極小元、最大元、最小元、上界、下界、上確界、下確界八種特殊元素。A13利用弗洛伊德(Floyd)算法求解最短路徑給出一張無向圖，圖上的每個(gè)頂點(diǎn)表示一個(gè)城市，頂點(diǎn)之間的邊表示城市間存在路徑，邊上的權(quán)值表示城市間的路徑長(zhǎng)度。利用弗洛伊德(Floyd)算法求解最短路徑求解任意兩個(gè)城市之間

26、的最短路徑問題。A14檢測(cè)數(shù)據(jù)庫死鎖的等待圖法事務(wù)等待圖是一個(gè)有向圖G=(T,U)。 T為結(jié)點(diǎn)的集合，每個(gè)結(jié)點(diǎn)表示正運(yùn)行的事務(wù)；U為邊的集合，每條邊表示事務(wù)等待的情況。若T1等待T2,則T1、T2之間劃一條有向邊，從T1指向T2。事務(wù)等待圖動(dòng)態(tài)地反映了所有事務(wù)的等待情況，如果發(fā)現(xiàn)圖中存在回路，則表示系統(tǒng)中出現(xiàn)了死鎖。A15識(shí)別廣義表頭、尾演示寫一個(gè)程序，建立廣義表的存儲(chǔ)結(jié)構(gòu)，演示在此存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)的廣義表求頭/求尾操作序列的結(jié)果。廣義表允許多行輸入，其中可以任意輸入空格符；廣義表存儲(chǔ)結(jié)構(gòu)自定；對(duì)廣義表的操作為一個(gè)由t和h組成的字符串；A16二叉排序Hash樹的建立隨機(jī)生成一整數(shù)作為樹的結(jié)點(diǎn)關(guān)鍵字，建立一棵二叉排序Hash樹，其中樹中結(jié)點(diǎn)的Hash值計(jì)算方法為：(1)左右孩子都存在時(shí)，HashHash(H