數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)任務(wù)書(shū)班題目

1、130校園導(dǎo)游咨詢*問(wèn)題描述：（1） 設(shè)計(jì)你的學(xué)校的校園平面圖，所含景點(diǎn)不少于10個(gè)。以圖中頂點(diǎn)表示學(xué)校各景點(diǎn)，存 放景點(diǎn)名稱、代號(hào)、簡(jiǎn)介等信息；以邊表示路徑，存放路徑長(zhǎng)度等相關(guān)信息。（2）為來(lái)訪客人提供圖中任意景點(diǎn)的問(wèn)路查詢，即查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的一條最短的簡(jiǎn) 單路徑。（3）為來(lái)訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。*測(cè)試數(shù)據(jù)：由讀者根據(jù)實(shí)際情況指定。*實(shí)現(xiàn)提示：一般情況下，校園的道路是雙向通行的，可設(shè)校園平面圖是一個(gè)無(wú)向網(wǎng)。頂點(diǎn) 和邊均含有相關(guān)信息。131長(zhǎng)整數(shù)四則運(yùn)算*問(wèn)題描述：設(shè)計(jì)一個(gè)實(shí)現(xiàn)任意長(zhǎng)的整數(shù)進(jìn)行加法運(yùn)算的演示程序。*基本要求：利用雙向循環(huán)鏈表實(shí)現(xiàn)長(zhǎng)整數(shù)的存儲(chǔ)，每個(gè)結(jié)點(diǎn)含一個(gè)

2、整形變量。任何整形變量的范圍是-（2A15 - 1）（2A15 - 1）。輸入和輸出形式：按中國(guó)對(duì)于長(zhǎng)整數(shù)的表示習(xí)慣，每四位一組，組間用逗號(hào)隔開(kāi)。*測(cè)試數(shù)據(jù)：（1）0； 0;應(yīng)輸出“ 0”。（2）-2345,6789 ； -7654,3211 ;應(yīng)輸出“ -1,0000,0000 ”。（3）-9999,9999 ； 1,0000,0000,0000 ;應(yīng)輸出“ 999（4）1,0001,0001 ； -1,0001,0001 ;應(yīng)輸出“ 0”。（5）1,0001,0001 ； -1,0001,0000 ;應(yīng)輸出“ 1”。（6）-9999,9999,9999 ; -9999,9999,9999

3、;應(yīng)輸出“ 1,9999,9999,9998”。（7）1,0000,9999,9999; 1;應(yīng)輸出“ 1,0001,0000,0000 ”。*實(shí)現(xiàn)提示：（1） 每個(gè)結(jié)點(diǎn)中可以存放的最大整數(shù)為32767，才能保證兩數(shù)相加不會(huì)溢出，但若這樣存放，即相當(dāng)于按32768進(jìn)制存放，在十進(jìn)制與32768進(jìn)制數(shù)之間的轉(zhuǎn)換十分不方便，故可以在每個(gè)結(jié)點(diǎn)中僅存十進(jìn)制的4位，即不超過(guò)9999的非負(fù)整數(shù)，整個(gè)鏈表表示為萬(wàn)進(jìn)制。（2）可以利用頭結(jié)點(diǎn)數(shù)據(jù)域的符號(hào)代表長(zhǎng)整數(shù)的符號(hào)。用其絕對(duì)值表示元素結(jié)點(diǎn)數(shù)目。相加過(guò)程中不要破壞兩個(gè)操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡(jiǎn)化程序結(jié)構(gòu)的一 種方法。不能給長(zhǎng)整數(shù)位數(shù)規(guī)定上

4、限。132紙牌游戲*問(wèn)題描述：編號(hào)為1-52張牌，正面向上，從第 2張開(kāi)始，以2為基數(shù)，是2的倍數(shù)的牌翻 一次，直到最后一張牌；然后，從第 3張開(kāi)始，以3為基數(shù)，是3的倍數(shù)的牌翻一次，直到 最后一張牌；然后從第 4張開(kāi)始，以4為基數(shù)，是4的倍數(shù)的牌翻一次，直到最后一張牌；再依次5的倍數(shù)的牌翻一次，6的，7的 直到 以52為基數(shù)的 翻過(guò)。輸出：這時(shí)正 面向上的牌有哪些？133 一元多項(xiàng)式計(jì)算*問(wèn)題描述：能夠按照指數(shù)降序排列建立并輸出多項(xiàng)式； 能夠完成兩個(gè)多項(xiàng)式的相加、相減，并將結(jié)果輸入； 在上交資料中請(qǐng)寫(xiě)明：存儲(chǔ)結(jié)構(gòu)、多項(xiàng)式相加的基本過(guò)程的算法（可以使用程序流程圖） 源程序、測(cè)試數(shù)據(jù)和結(jié)果、算法

5、的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；3、 訂票系統(tǒng) *問(wèn)題描述：通過(guò)此系統(tǒng)可以實(shí)現(xiàn)如下功能：1）錄入： 可以錄入航班情況（數(shù)據(jù)可以存儲(chǔ)在一個(gè)數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定）2）查詢： 可以查詢某個(gè)航線的情況（如，輸入航班號(hào)，查詢起降時(shí)間，起飛抵達(dá)城市，航班票價(jià)，票 價(jià)折扣，確定航班是否滿倉(cāng)） ； 可以輸入起飛抵達(dá)城市，查詢飛機(jī)航班情況；3）訂票：（訂票情況可以存在一個(gè)數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定） 可以訂票，如果該航班已經(jīng)無(wú)票，可以提供相關(guān)可選擇航班；4）退票： 可退票，退票后修改相關(guān)數(shù)據(jù)文件； 客戶資料有姓名，證件號(hào)，訂票數(shù)量及航班情況，訂單要有編號(hào)。5）修改航班信息：當(dāng)航班信息改變可

6、以修改航班數(shù)據(jù)文件*要求： 根據(jù)以上功能說(shuō)明，設(shè)計(jì)航班信息，訂票信息的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)程序完成功能；134 、 迷宮求解* 問(wèn)題描述： 可以輸入一個(gè)任意大小的迷宮數(shù)據(jù)， 用非遞歸的方法求出一條走出迷宮的路徑， 并將路徑輸出；*要求：在上交資料中請(qǐng)寫(xiě)明：存儲(chǔ)結(jié)構(gòu)、基本算法（可以使用程序流程圖） 、源程序、測(cè)試數(shù)據(jù)和 結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；135 、 文章編輯*問(wèn)題描述：輸入一頁(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ì)某一字符串在文章中

7、出現(xiàn)的次數(shù)，并輸出該次數(shù)； （ 3）刪除某一子串，并將后面的字符前移。 *存儲(chǔ)結(jié)構(gòu)使用線性表，分別用幾個(gè)子函數(shù)實(shí)現(xiàn)相應(yīng)的功能； *輸入數(shù)據(jù)的形式和范圍：可以輸入大寫(xiě)、小寫(xiě)的英文字母、任何數(shù)字及標(biāo)點(diǎn)符號(hào)。*輸出形式：（1）分行輸出用戶輸入的各行字符； （2）分 4 行輸出 全部字母數(shù) 、數(shù)字個(gè)數(shù) 、空格個(gè)數(shù) 、文章總字?jǐn)?shù) （ 3）輸出刪除某一字符串后的文章；136 、 joseph 環(huán)*問(wèn)題描述：編號(hào)是1, 2,n的n個(gè)人按照順時(shí)針?lè)较驀蝗Γ總€(gè)人只有一個(gè)密碼（正整數(shù)）。一開(kāi)始任選一個(gè)正整數(shù)作為報(bào)數(shù)上限值 m,從第一個(gè)仍開(kāi)始順時(shí)針?lè)较蜃?1開(kāi)始 順序報(bào)數(shù),報(bào)到 m 時(shí)停止報(bào)數(shù)。報(bào) m 的人出

8、列,將他的密碼作為新的 m 值,從他在順時(shí)針 方向的下一個(gè)人開(kāi)始重新從 1 報(bào)數(shù), 如此下去, 直到所有人全部出列為止。 設(shè)計(jì)一個(gè)程序來(lái) 求出出列順序。*要求：利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過(guò)程,按照出列的順序輸出各個(gè)人的編號(hào)。* 測(cè)試數(shù)據(jù)：m的初值為20，n=7 ,7個(gè)人的密碼依次為 3，1，7，2，4，7，4，首先m=6,則正確的輸出 是什么？*輸入數(shù)據(jù)：建立輸入處理輸入數(shù)據(jù)，輸入 m 的初值， n ，輸入每個(gè)人的密碼，建立單循環(huán) 鏈表。*輸出形式：建立一個(gè)輸出函數(shù)，將正確的輸出序列137 、 猴子選大王*問(wèn)題描述：一堆猴子都有編號(hào)，編號(hào)是 1, 2，3m ,這群猴子（m個(gè)）按照1-m的順

9、序圍 坐一圈，從第 1 開(kāi)始數(shù)，每數(shù)到第 N 個(gè)，該猴子就要離開(kāi)此圈，這樣依次下來(lái)，直到圈中 只剩下最后一只猴子，則該猴子為大王。*輸入數(shù)據(jù)：輸入 m,n m,n 為整數(shù)， nm*輸出形式：中文提示按照 m 個(gè)猴子，數(shù) n 個(gè)數(shù)的方法，輸出為大王的猴子是幾號(hào) ，建立 一個(gè)函數(shù)來(lái)實(shí)現(xiàn)此功能138 、 建立二叉樹(shù)，層序、先序遍歷（ 用遞歸或非遞歸的 方法都可以）*問(wèn)題描述： 要求能夠輸入樹(shù)的各個(gè)結(jié)點(diǎn)， 并能夠輸出用不同方法遍歷的遍歷序列； 分別建立建立二叉樹(shù) 存儲(chǔ)結(jié)構(gòu)的的輸入函數(shù)、輸出層序遍歷序列的函數(shù)、輸出先序遍歷序列的函數(shù)；139 、 赫夫曼樹(shù)的建立*問(wèn)題描述：建立建立最優(yōu)二叉樹(shù)函數(shù) *要求：

10、可以建立函數(shù)輸入二叉樹(shù)，并輸出其赫夫曼樹(shù) 在上交資料中請(qǐng)寫(xiě)明： 存儲(chǔ)結(jié)構(gòu)、 基本算法 （可以使用程序流程圖） 、輸入輸出、 源程序、 測(cè)試數(shù)據(jù)和結(jié)果、算法的時(shí)間復(fù)雜度、另外可以提出算法的改進(jìn)方法；140八皇后問(wèn)題【問(wèn)題描述】皇后”的所有布局。8個(gè)方向相互捕捉。如圖所的位置上的皇后就能與這求出在一個(gè)nXn的棋盤(pán)上，放置 n個(gè)不能互相捕捉的國(guó)際象棋 這是來(lái)源于國(guó)際象棋的一個(gè)問(wèn)題?；屎罂梢匝刂v橫和兩條斜線 示，一個(gè)皇后放在棋盤(pán)的第 4行第3列位置上，則棋盤(pán)上凡打個(gè)皇后相互捕捉，也就是下一個(gè)皇后不能放的位置。12345678XXXXXXXXXXQXXXXXXXXXXXXXXX從圖中可以得到以下啟示：

11、 一個(gè)合適的解應(yīng)是在每列、 每行上只有一個(gè)皇后， 且一條斜線上也只有一個(gè)皇后?！緦?shí)現(xiàn)提示】 求解過(guò)程從空配置開(kāi)始。在第 1列至第m列為合理配置的基礎(chǔ)上，再配置第 m+1列，直至 第n列配置也是合理時(shí)，就找到了一個(gè)解。接著改變第n列配置，希望獲得下一個(gè)解。另外， 在任一列上，可能有 n種配置。開(kāi)始時(shí)配置在第 1行，以后改變時(shí)，順次選擇第 2行、第3 行、直到第n行。當(dāng)?shù)趎行配置也找不到一個(gè)合理的配置時(shí)，就要回溯，去改變前一列 的配置。141停車場(chǎng)管理【問(wèn)題描述】設(shè)停車場(chǎng)是一個(gè)可停放 n輛汽車的狹長(zhǎng)通道，且只有一個(gè)大門可供汽車進(jìn)出。汽車在停車場(chǎng) 內(nèi)按車輛到達(dá)時(shí)間的先后順序，依次由北向南排列（大門在

12、最南端，最先到達(dá)的第一輛車停放在車場(chǎng)的最北端），若車場(chǎng)內(nèi)已停滿 n輛汽車，則后來(lái)的汽車只能在門外的便道上等待， 一旦有車開(kāi)走，則排在便道上的第一輛車即可開(kāi)入；當(dāng)停車場(chǎng)內(nèi)某輛車要離開(kāi)時(shí)，在它之后進(jìn)入的車輛必須先退出車場(chǎng)為它讓路，待該輛車開(kāi)出大門外，其他車輛再按原次序進(jìn)入車場(chǎng)，每輛停放在車場(chǎng)的車在它離開(kāi)停車場(chǎng)時(shí)必須按它停留的時(shí)間長(zhǎng)短交納費(fèi)用。試為停車場(chǎng)編制按上述要求進(jìn)行管理的模擬程序?！净疽蟆恳詶ＤM停車場(chǎng)，以隊(duì)列模擬車場(chǎng)外的便道，按照從終端讀入的輸入數(shù)據(jù)序列進(jìn)行模擬管理。每一組輸入數(shù)據(jù)包括三個(gè)數(shù)據(jù)項(xiàng)：汽車“到達(dá)”或“離去”信息、汽車牌照號(hào)碼以及到達(dá)或 離去的時(shí)刻。對(duì)每一組輸入數(shù)據(jù)進(jìn)行操作后的

13、輸出信息為：若是車輛到達(dá)，則輸出汽車在停車場(chǎng)內(nèi)或便道上的停車位置； 若是車輛離去，則輸出汽車在停車場(chǎng)內(nèi)停留的時(shí)間和應(yīng)交納的 費(fèi)用（在便道上停留的時(shí)間不收費(fèi)）。棧以順序結(jié)構(gòu)實(shí)現(xiàn)，隊(duì)列以鏈表結(jié)構(gòu)實(shí)現(xiàn)。【測(cè)試數(shù)據(jù)】設(shè) n=2,輸入數(shù)據(jù)為：( A ,1,5),( A ,2,10),( D ,1,15),( A ,3,20),( A ,4,25),( A ,5,30),( D ,2,35),( D ,4,40),( E ,0,0)。其中： A 表示到達(dá)(Arrival ) ; D 表示(Departure); E表示輸入結(jié)束(End)?！緦?shí)現(xiàn)提示】需另設(shè)一個(gè)棧， 臨時(shí)停放為給要離去的汽車讓路而從停車場(chǎng)退

14、出來(lái)的汽車，也用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。 輸入數(shù)據(jù)按到達(dá)或離去的時(shí)刻有序。 棧中每個(gè)元素表示一輛汽車， 包含兩個(gè)數(shù)據(jù)項(xiàng)： 汽車的牌照號(hào)碼和進(jìn)入停車場(chǎng)的時(shí)刻。142 作業(yè)評(píng)分系統(tǒng)【問(wèn)題描述】 設(shè)計(jì)一個(gè)可以給小學(xué)生出題并且可以給出分?jǐn)?shù)的系統(tǒng)軟件?！净疽蟆?利用棧求表達(dá)式的值，可供小學(xué)生作業(yè)，并能給出分?jǐn)?shù)。 建立試題庫(kù)文件，隨機(jī)產(chǎn)生 n 個(gè)題目; 題目涉及加減乘除，帶括弧的混合運(yùn)算;隨時(shí)可以退出;給出作業(yè)分?jǐn)?shù)。 【進(jìn)一步完成內(nèi)容】1 )保留歷史分?jǐn)?shù)，能回顧歷史，給出與歷史分?jǐn)?shù)比較后的評(píng)價(jià)。2) 界面設(shè)計(jì)的優(yōu)化。143 哈夫曼編碼 /譯碼器【問(wèn)題描述】設(shè)計(jì)一個(gè)利用哈夫曼算法的編碼和譯碼系統(tǒng)， 重復(fù)地顯示

15、并處理以下項(xiàng)目， 直到選擇退出為 止?！净疽蟆繉?quán)值數(shù)據(jù)存放在數(shù)據(jù)文件 (文件名為data.txt，位于執(zhí)行程序的當(dāng)前目錄中 )分別采用動(dòng)態(tài) 和靜態(tài)存儲(chǔ)結(jié)構(gòu)。初始化：鍵盤(pán)輸入字符集大小n、 n 個(gè)字符和 n 個(gè)權(quán)值，建立哈夫曼樹(shù);編碼：利用建好的哈夫曼樹(shù)生成哈夫曼編碼;輸出編碼;設(shè)字符集及頻度如下表：字符 空格 A B C D E F G H I J K L M頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20字符 N O P Q R S T U V W X Y Z頻度 57 63 15 1 48 51 80 23 8 18 1 16 1【進(jìn)一步完成內(nèi)

16、容】譯碼功能;顯示哈夫曼樹(shù);界面設(shè)計(jì)的優(yōu)化。144 全國(guó)交通咨詢模擬【問(wèn)題描述】 處于不同目的的旅客對(duì)交通工具有不同的要求。 例如， 因公出差的旅客希望在旅途中的時(shí)間 盡可能的短， 出門旅游的游客則期望旅費(fèi)盡可能省， 而老年旅客則要求中轉(zhuǎn)次數(shù)最少。 編制 一個(gè)全國(guó)城市間的交通咨詢程序，為旅客提供兩種或三種最優(yōu)決策的交通咨詢?！驹O(shè)計(jì)要求】1）提供對(duì)城市信息進(jìn)行編輯（如：添加或刪除）的功能。2）提供對(duì)列車時(shí)刻表進(jìn)行編輯（增設(shè)或刪除）的功能。3）提供兩種最優(yōu)決策：最快到達(dá)和最省錢到達(dá)。4）旅途中耗費(fèi)的總時(shí)間應(yīng)該包括中轉(zhuǎn)站的等候時(shí)間。5）咨詢以用戶和計(jì)算機(jī)的對(duì)話方式進(jìn)行。由用戶輸入起始站、終點(diǎn)站、最優(yōu)

17、決策原則，輸出 信息：最快需要多長(zhǎng)時(shí)間才能到達(dá)或者最少需要多少旅費(fèi)才能到達(dá)， 并詳細(xì)說(shuō)明于何時(shí)乘坐 哪一趟列車到何地。測(cè)試數(shù)據(jù)：參考全國(guó)交通圖，自行設(shè)計(jì)列車時(shí)刻表?！緦?shí)現(xiàn)提示】1）對(duì)全國(guó)城市交通圖和列車時(shí)刻表進(jìn)行編輯， 應(yīng)該提供文件形式輸入和鍵盤(pán)輸入兩種方式。 列車時(shí)刻表則需根據(jù)交通圖給出各個(gè)路段的詳細(xì)信息， 例如： 對(duì)從北京到上海的火車， 需給 出北京至天津、天津至徐州及徐州至上海各段的出發(fā)時(shí)間、到達(dá)時(shí)間及票價(jià)等信息。2）以鄰接表作交通圖的存儲(chǔ)結(jié)構(gòu)，表示邊的結(jié)構(gòu)內(nèi)除含有鄰接點(diǎn)的信息外，還應(yīng)包括交通 工具、路程中耗費(fèi)的時(shí)間和花費(fèi)以及出發(fā)和到達(dá)的時(shí)間等多種屬性。145 宿舍管理查詢軟件【問(wèn)題描述

18、】 為宿舍管理人員編寫(xiě)一個(gè)宿舍管理查詢軟件?！净疽蟆?）程序設(shè)計(jì)要求 采用交互工作方式 建立數(shù)據(jù)文件 ，數(shù)據(jù)文件按關(guān)鍵字（姓名、學(xué)號(hào)、房號(hào)）進(jìn)行排序（冒泡、選擇、插入排序等任選一種 ）2）查詢菜單 （用二分查找實(shí)現(xiàn)以下操作 ） 按姓名查詢 按學(xué)號(hào)查詢 按房號(hào)查詢3）輸出任一查詢結(jié)果（可以連續(xù)操作）146 飛機(jī)訂票系統(tǒng)【問(wèn)題描述】 設(shè)計(jì)一個(gè)飛機(jī)訂票系統(tǒng)，可以模擬處理飛機(jī)訂票過(guò)程中的各種操作?！净疽蟆客ㄟ^(guò)此系統(tǒng)可以實(shí)現(xiàn)如下功能：1）錄入 可以錄入航班情況（數(shù)據(jù)可以存儲(chǔ)在一個(gè)數(shù)據(jù)文件中，數(shù)據(jù)結(jié)構(gòu)、具體數(shù)據(jù)自定） 。2）查詢 可以查詢某個(gè)航線的情況（如輸入航班號(hào)，查詢起降時(shí)間，起飛抵達(dá)城市，航

19、班票價(jià)，票價(jià) 折扣，確定航班是否滿倉(cāng)） ?？梢暂斎肫痫w抵達(dá)城市，查詢飛機(jī)航班情況。3）訂票（訂票情況可以存在一個(gè)數(shù)據(jù)文件中，結(jié)構(gòu)自己設(shè)定） 可以訂票，如果該航班已經(jīng)無(wú)票，可以提供相關(guān)可選擇航班。4）退票可退票，退票后修改相關(guān)數(shù)據(jù)文件。 客戶資料有姓名，證件號(hào)，訂票數(shù)量及航班情況，訂單要有編號(hào)。5）修改航班信息 當(dāng)航班信息改變可以修改航班數(shù)據(jù)文件 根據(jù)以上功能說(shuō)明，設(shè)計(jì)航班信息，訂票信息的存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)程序完成功能。147 客戶消費(fèi)積分管理系統(tǒng)問(wèn)題描述： 針對(duì)客戶的消費(fèi)情況， 進(jìn)行客戶管理， 根據(jù)客戶的消費(fèi)積分對(duì)客戶實(shí)行不同程度 的打折優(yōu)惠?；疽螅翰捎靡欢ǖ拇鎯?chǔ)結(jié)構(gòu)進(jìn)行客戶信息的存儲(chǔ)；對(duì)客戶

20、的信息可以進(jìn)行修改、刪除、添加； 能夠根據(jù)消費(fèi)情況進(jìn)行客戶積分的計(jì)算； 根據(jù)積分情況實(shí)行不同程度的打折優(yōu)惠；148 排序綜合利用隨機(jī)函數(shù)產(chǎn)生 N 個(gè)隨機(jī)整數(shù)（ 20000 以上），對(duì)這些數(shù)進(jìn)行多種方法進(jìn)行排序。 要求： 1）至少采用三種方法實(shí)現(xiàn)上述問(wèn)題求解（提示，可采用的方法有插入排序、希爾排序、起泡 排序、快速排序、選擇排序、堆排序、歸并排序） 。并把排序后的結(jié)果保存在不同的文件中。 2）統(tǒng)計(jì)每一種排序方法的性能（以上機(jī)運(yùn)行程序所花費(fèi)的時(shí)間為準(zhǔn)進(jìn)行對(duì)比），找出其中兩種較快的方法。149 學(xué)生搭配問(wèn)題一班有m個(gè)女生,有n個(gè)男生（m不等于n）,現(xiàn)要開(kāi)一個(gè)舞會(huì).男女生分別編號(hào)坐在舞池的兩邊 的椅子

21、上 .每曲開(kāi)始時(shí) ,依次從男生和女生中各出一人配對(duì)跳舞 , 本曲沒(méi)成功配對(duì)者坐著等待 下一曲找舞伴 .請(qǐng)?jiān)O(shè)計(jì)一系統(tǒng)模擬動(dòng)態(tài)地顯示出上述過(guò)程,要求如下 :1）輸出每曲配對(duì)情況2）計(jì)算出任何一個(gè)男生（編號(hào)為X）和任意女生（編號(hào)為Y）,在第K曲配對(duì)跳舞的情況至少求出 K 的兩個(gè)值 .3）盡量設(shè)計(jì)出多種算法及程序 ,可視情況適當(dāng)加分提示 :用隊(duì)列來(lái)解決比較方便 150.猴子吃桃子問(wèn)題有一群猴子摘了一堆桃子， 他們每天都吃當(dāng)前桃子的一半且再多吃一個(gè)， 到了第 10 天就只 余下一個(gè)桃子。用多種方法實(shí)現(xiàn)求出原來(lái)這群猴子共摘了多少個(gè)桃子。要求：1）采用數(shù)組數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)上述求解2）采用鏈數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)上述求解3

22、）采用遞歸實(shí)現(xiàn)上述求解151 三元組表相加設(shè)計(jì)目的1 掌握數(shù)組的定義及數(shù)組的順序存儲(chǔ)結(jié)構(gòu)2 掌握特殊矩陣的壓縮存儲(chǔ)和稀疏矩陣的三元組存儲(chǔ)設(shè)計(jì)內(nèi)容和要求 利用稀疏矩陣的三元組存儲(chǔ)，來(lái)實(shí)現(xiàn)兩矩陣相加。152 哈希表設(shè)計(jì)【問(wèn)題描述】針對(duì)某個(gè)集體 （比如你所在的班級(jí) ）中的 人名設(shè)計(jì)一個(gè)哈希表， 使得平均查找長(zhǎng)度不超過(guò) R， 完成相應(yīng)的建表和查表程序。【基本要求】 假設(shè)人名為中國(guó)人姓名的漢語(yǔ)拼音形式。待填入哈希表的人名共有30 個(gè)，取平均查找長(zhǎng)度的上限為 2。哈希函數(shù)用除留余數(shù)法構(gòu)造，用偽隨機(jī)探測(cè)再散列法處理沖突?！緶y(cè)試數(shù)據(jù)】 取讀者周圍較熟悉的 30 個(gè)人的姓名。【實(shí)現(xiàn)提示】 如果隨機(jī)函數(shù)自行構(gòu)造，

23、則應(yīng)首先調(diào)整好隨機(jī)函數(shù)，使其分布均勻。人名的長(zhǎng)度均不超過(guò)19個(gè)字符（最長(zhǎng)的人名如z莊雙雙（ZhangStmarlgShang。字符的取碼方法可直接利用 C語(yǔ)言 中的 toascii 函數(shù)，并可對(duì)過(guò)長(zhǎng)的人名先作折疊處理?！具x作內(nèi)容】（1）從教科書(shū)上介紹的幾種晗希函數(shù)構(gòu)造方法中選出適用者并設(shè)計(jì)幾個(gè)不同的哈希函數(shù)，比 較它們的地址沖突率 （可以用更大的名字集合作試驗(yàn) 。（2）研究這 30 個(gè)人名的特點(diǎn)，努力找一個(gè)晗希函數(shù)，使得對(duì)于不同的拼音名一定不發(fā)生地址 沖突。（3）在哈希函數(shù)確定的前提下嘗試各種不同處理沖突的方法，考查平均查找長(zhǎng)度的變化和造好的晗希表中關(guān)鍵字的聚簇性。153. 圖書(shū)管理【問(wèn)題描述

24、】 圖書(shū)管理基本業(yè)務(wù)活動(dòng)包括 :對(duì)一本書(shū)的采編入庫(kù)、清除庫(kù)存、借閱和歸還等等。試設(shè)計(jì)一 個(gè)圖書(shū)管理系統(tǒng)，將上述業(yè)務(wù)活動(dòng)借助于計(jì)算機(jī)系統(tǒng)完成?！净疽蟆?1每種書(shū)的登記內(nèi)容至少包括書(shū)號(hào)、書(shū)名、著者、現(xiàn)存量和總庫(kù)存量等五項(xiàng)。2作為演示系統(tǒng)，不必使用文件，全部數(shù)據(jù)可以都在內(nèi)存存放。但是由于上述四項(xiàng)基本 業(yè)務(wù)活動(dòng)都是通過(guò)書(shū)號(hào) (即關(guān)鍵字進(jìn)行的，所以要用 B 樹(shù)24 樹(shù)對(duì)書(shū)號(hào)建立索引，以獲 得高效率。3系統(tǒng)應(yīng)實(shí)現(xiàn)的操作及其功能定義如下 :采編入庫(kù) z 新購(gòu)入一種書(shū)， 經(jīng)分類和確定書(shū)號(hào)之后登記到圖書(shū)賬目中去。 如果這種書(shū)在賬中 已有，則只將總庫(kù)存量增加。 清除庫(kù)存 : 某種書(shū)已無(wú)保留價(jià)值，將它從圖書(shū)賬目

25、中注銷。 借閱 : 如果一種書(shū)的現(xiàn)存量大于零，則借出一本，登記借閱者的圖書(shū)證號(hào)和歸還期限。 歸還 z 注銷對(duì)借閱者的登記，改變?cè)摃?shū)的現(xiàn)存量。 顯示 : 以凹入表的形式顯示 B 樹(shù)。這個(gè)操作是為了調(diào)試和維護(hù)的目的而設(shè)置的。 【測(cè)試數(shù)據(jù)】入庫(kù)書(shū)號(hào) :35，16，18，70，5，50，22，60，13，17，12，45，25，氈， 15， 90， 30， 7 然 后清除 :45， 90，50， 22，42 其余數(shù)據(jù)自行設(shè)計(jì)。由空樹(shù)開(kāi)始，每插入刪除一個(gè)關(guān)鍵字后就顯示 B 樹(shù)的狀態(tài)。【實(shí)現(xiàn)提示】(1) 24 樹(shù)的查找算法是基礎(chǔ)，入庫(kù)和清除操作都要調(diào)用。難點(diǎn)在于刪除關(guān)鍵字的算法，因而 只要算法對(duì) 2-3

26、樹(shù)適用就可以了，暫時(shí)不必追求高階 B 樹(shù)也適用的刪除算法。(2) 每種書(shū)的記錄可以用動(dòng) (或靜 )態(tài)鏈?zhǔn)浇Y(jié)構(gòu)。 借閱登記信息可以鏈接在相應(yīng)的那種書(shū)的記錄 之后?！具x作內(nèi)容】(1) 將一次會(huì)話過(guò)程(即程序一次運(yùn)行)中的全部人機(jī)對(duì)話記入一個(gè)日志文件 log中去。(2) 增加列出某著者全部著作名的操作。思考如何提高這一操作的效率，參閱教科書(shū) 12.6.2 節(jié)。(3增加列出某種書(shū)狀態(tài)的操作。 狀態(tài)信息除了包括這種書(shū)記錄的全部信息外還包括最 早到期 (包括已逾期 )的借閱者證號(hào)，日期可用整數(shù)實(shí)現(xiàn)，以求簡(jiǎn)化。(4) 增加預(yù)約借書(shū)功能。154. 平衡二叉樹(shù)操作的演示【問(wèn)題描述】 利用平衡二叉樹(shù)實(shí)現(xiàn)一個(gè)動(dòng)態(tài)查

27、找表。【基本要求】 實(shí)現(xiàn)動(dòng)態(tài)查找表的三種基本功能 :查找、插入和刪除?！緶y(cè)試數(shù)據(jù)】由讀者自行設(shè)定?！緦?shí)現(xiàn)提示】(1)初始，平衡二叉樹(shù)為空樹(shù)，操作界面給出查找、插入和刪除三種操作供選擇。每種 操作均要提示輸入關(guān)鍵字。每次插入或刪除一個(gè)結(jié)點(diǎn)后，應(yīng)更新平衡二叉樹(shù)的顯示。(2)平衡二叉樹(shù)的顯示可采用凹入表形式，也可以采用圖形界面畫(huà)出樹(shù)形。(3) 教科書(shū)已給出查找和插入算法，本題重點(diǎn)在于對(duì)刪除算法的設(shè)計(jì)和實(shí)現(xiàn)。假設(shè)要?jiǎng)h除關(guān) 鍵字為 x 的結(jié)點(diǎn)。如果 x 不在葉子結(jié)點(diǎn)上， 則用它左子樹(shù)中的最大值或右子樹(shù)中的最小值取 代 x 。如此反復(fù)取代，直到刪除動(dòng)作傳遞到某個(gè)葉子結(jié)點(diǎn)。刪除葉子結(jié)點(diǎn)時(shí)，若需要進(jìn)行平 衡變

28、換，可采用插入的平衡變換的反變換(如，左子樹(shù)變矮對(duì)應(yīng)于右子樹(shù)長(zhǎng)高 )?！具x作內(nèi)容】(1)合并兩棵平衡二叉樹(shù)。 (2)把一棵平衡二叉樹(shù)分裂為兩棵平衡二叉樹(shù)，使得在一棵樹(shù)中的所有關(guān)鍵字都小于或等于 工，另一棵樹(shù)中的任一關(guān)鍵字都大于幾155. 英語(yǔ)詞典的維護(hù)和識(shí)別【問(wèn)題描述】Trie 樹(shù)通常作為一種索引樹(shù)， 這種結(jié)構(gòu)對(duì)于大小變化很大的關(guān)鍵字特別有用。利用 Trie 樹(shù)實(shí)現(xiàn)一個(gè)英語(yǔ)單詞輔助記憶系統(tǒng)，完成相應(yīng)的建表和查表程序?！净疽蟆坎幌薅?Trie 樹(shù)的層次，每個(gè)葉子結(jié)點(diǎn)只含一個(gè)關(guān)鍵字，采用單字符逐層分割的策略，實(shí)現(xiàn)Trie 樹(shù)的插入、刪除和查詢的算法，查詢可以有兩種方式:查詢一個(gè)完整的單詞或者查

29、詢以某幾個(gè)字母開(kāi)頭的單詞?！緶y(cè)試數(shù)據(jù)】自行設(shè)定?！緦?shí)現(xiàn)提示】以實(shí)習(xí)三中已實(shí)現(xiàn)的串類型或 C 語(yǔ)言中提供的長(zhǎng)度不限的串類型表示關(guān)鍵字，葉子結(jié)點(diǎn)內(nèi) 應(yīng)包括英語(yǔ)單詞及其注音、釋義等信息?！具x作內(nèi)容】限定 Trie 樹(shù)的層次，每個(gè)葉子結(jié)點(diǎn)可以包含多個(gè)關(guān)鍵字。156. 內(nèi)部排序算法比較【問(wèn)題描述】在教科書(shū)中， 各種內(nèi)部排序算法的時(shí)間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時(shí)間的階， 或大概 執(zhí)行時(shí)間。 試通過(guò)隨機(jī)數(shù)據(jù)比較各算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù)， 以取得直觀感 受?！净疽蟆?1) 對(duì)以下 6 種常用的內(nèi)部排序算法進(jìn)行比較 z 起泡排序、直接插入排序、簡(jiǎn)單選擇排序、 快速排序、希爾排序、堆排序。(

30、2)待排序表的表長(zhǎng)不小于 1005 其中的數(shù)據(jù)要用偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生： 至少要用 5 組不同 的輸入數(shù)據(jù)作比較：比較的指標(biāo)為有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動(dòng)次數(shù)(關(guān)鍵字交換計(jì)為 3 次移動(dòng) )。(3) 最后要對(duì)結(jié)果作出簡(jiǎn)單分析，包括對(duì)各組數(shù)據(jù)得出結(jié)果波動(dòng)大小的解釋。 【測(cè)試數(shù)據(jù)】由隨機(jī)數(shù)產(chǎn)生器生成?！緦?shí)現(xiàn)提示】 主要工作是設(shè)法在已知算法中的適當(dāng)位置插入對(duì)關(guān)鍵字的比較次數(shù)和移動(dòng)次數(shù)的計(jì)數(shù)操作。 程序還可以考慮幾組數(shù)據(jù)的典型性， 如，正序、 逆序和不同程度的亂序。 注意采用分塊調(diào)試 的方法?！具x作內(nèi)容】 (1)增加折半插入排序、二路插入排序、歸并排序、基數(shù)排序等。(2)對(duì)不同的輸入表長(zhǎng)作試驗(yàn)，觀察檢查兩個(gè)指標(biāo)相對(duì)于表長(zhǎng)的變化關(guān)系。還可以對(duì)穩(wěn)定性 作驗(yàn)證。157. 多關(guān)鍵字排序【問(wèn)題描述】多關(guān)鍵字的排序有其一定的實(shí)用范圍。例如:在進(jìn)行高考分?jǐn)?shù)處理時(shí)，除了需對(duì)總分進(jìn)行排序外， 不同的專業(yè)對(duì)單科分?jǐn)?shù)的要求不同， 因此尚需在總分相同的情況下， 按用戶提出的單 科分?jǐn)?shù)的次序要求排出考生錄取的次序?！净疽蟆?1) 假設(shè)待排序的記錄數(shù)不超過(guò) 10000，表中記錄的關(guān)鍵字?jǐn)?shù)不超過(guò) 5，各個(gè)關(guān)鍵字的范圍均 為 0 至 100 。按用戶給定的進(jìn)行排序的關(guān)鍵字的優(yōu)先關(guān)系，輸出排序結(jié)果。(2) 約定按 LSD 法進(jìn)行多關(guān)鍵字的排序。 在對(duì)各個(gè)關(guān)鍵字進(jìn)行排序時(shí)采用兩種策略:其