數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)(15級(jí))

1、“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計(jì)-指導(dǎo)書 2014-4-5選題一：迷宮與棧問題【問題描述】以一個(gè)mXn的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計(jì)一個(gè)程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論?！緦?shí)現(xiàn)提示】1) 首先實(shí)現(xiàn)一個(gè)以鏈表作存儲(chǔ)結(jié)構(gòu)的棧類型，然后編寫一個(gè)求解迷宮的非遞歸程序。求得的通路以三元組（i，j，d）的形式輸出。其中：（i，j）指示迷宮中的一個(gè)坐標(biāo)，d表示走到下一坐標(biāo)的方向。如，對于下列數(shù)據(jù)的迷宮，輸出一條通路為：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），。2) 編寫遞歸形式的算法，求得迷宮中所有可能的通路。3)

2、 以方陣形式輸出迷宮及其通路?！緶y試數(shù)據(jù)】迷宮的測試數(shù)據(jù)如下：左上角（0，1）為入口，右下角（8，9）為出口。選題二：算術(shù)表達(dá)式與二叉樹【問題描述】一個(gè)表達(dá)式和一棵二叉樹之間，存在著自然的對應(yīng)關(guān)系。寫一個(gè)程序，實(shí)現(xiàn)基于二叉樹表示的算術(shù)表達(dá)式的操作?！緦?shí)現(xiàn)提示】假設(shè)算術(shù)表達(dá)式Expression內(nèi)可以含有變量（az）、常量（09）和二元運(yùn)算符（+，-，*，/，(乘冪)）。實(shí)現(xiàn)以下操作：1) ReadExpre(E)以字符序列的形式輸入語法正確的前綴表達(dá)式并構(gòu)造表達(dá)式E。2) WriteExpre(E)用帶括弧的中綴表達(dá)式輸出表達(dá)式E。3) Assign(V,c)實(shí)現(xiàn)對變量V的賦值（V=c），變量

3、的初值為0。4) Value(E)對算術(shù)表達(dá)式E求值。5) CompoundExpr（P，E1，E2）-構(gòu)造一個(gè)新的復(fù)合表達(dá)式（E1）P（E2）【測試數(shù)據(jù)】1) 分別輸入0；a；-91；+a*bc；+*5x2*8x；+*3x3*2x2x6并輸出。2) 每當(dāng)輸入一個(gè)表達(dá)式后，對其中的變量賦值，然后對表達(dá)式求值。選題三：銀行業(yè)務(wù)模擬與離散事件模擬【問題描述】假設(shè)某銀行有4個(gè)窗口對外接待客戶，從早晨銀行開門（開門9：00am，關(guān)門5：00pm）起不斷有客戶進(jìn)入銀行。由于每個(gè)窗口在某個(gè)時(shí)刻只能接待一個(gè)客戶，因此在客戶人數(shù)眾多時(shí)需要在每個(gè)窗口前順次排隊(duì)，對于剛進(jìn)入銀行的客戶（建議：客戶進(jìn)入時(shí)間使用隨機(jī)函

4、數(shù)產(chǎn)生），如果某個(gè)窗口的業(yè)務(wù)員正空閑，則可上前辦理業(yè)務(wù)；反之，若4個(gè)窗口均有窗戶所占，他便會(huì)排在人數(shù)最少的隊(duì)伍后面。【實(shí)現(xiàn)提示】1) 編制一個(gè)程序以模擬銀行的這種業(yè)務(wù)活動(dòng)并計(jì)算一天中客戶在銀行逗留的平均時(shí)間。2) 建議有如下設(shè)置：a) 客戶到達(dá)時(shí)間隨機(jī)產(chǎn)生，一天客戶的人數(shù)設(shè)定為100人。b) 銀行業(yè)務(wù)員處理時(shí)間隨機(jī)產(chǎn)生，平均處理時(shí)間10分鐘。3) 將一天的數(shù)據(jù)（包括業(yè)務(wù)員和客戶）以文件方式輸出?！緶y試數(shù)據(jù)】由隨機(jī)數(shù)產(chǎn)生器生成選題四：文學(xué)研究助手與模式匹配算法KMP【問題描述】文學(xué)研究人員需要統(tǒng)計(jì)某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。試寫一個(gè)實(shí)現(xiàn)這一目標(biāo)的文字統(tǒng)計(jì)系統(tǒng)【實(shí)現(xiàn)提示】1) 英文小

5、說存于一個(gè)文本文件中。待統(tǒng)計(jì)的詞匯集合要一次輸入完畢，即統(tǒng)計(jì)工作必須在程序的一次運(yùn)行之后就全部完成。程序的輸出結(jié)果是每個(gè)詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在的行的行號(hào)，格式自行設(shè)計(jì)。待統(tǒng)計(jì)的“單詞”在文本串中不跨行出現(xiàn)，它或者從行首開始，或者前置以一個(gè)空格符。2) 模式匹配要基于KMP算法。3) 推廣到更一般的模式集匹配問題，并設(shè)待查模式串可以跨行（提示：定義操作GetAChar）?！緶y試數(shù)據(jù)】1) 文本文件為testword.c2) 待統(tǒng)計(jì)的詞集：if、else、for、while、return、void、int、char、typedef、struct選題五：瓊州學(xué)院校園導(dǎo)游咨詢與最短路徑【問題描述】

6、1) 從瓊州學(xué)院的平面圖中選取有代表性景點(diǎn)（10-15個(gè)），抽象成一個(gè)無向帶權(quán)圖。以圖中頂點(diǎn)表示景點(diǎn)，邊上的權(quán)值表示兩地之間距離。2) 本程序的目的是為用戶提供路徑咨詢。根據(jù)用戶指定的始點(diǎn)和終點(diǎn)輸出相應(yīng)路徑，或者根據(jù)用戶指定的景點(diǎn)輸出景點(diǎn)的信息?！緦?shí)現(xiàn)提示】1) 從瓊州學(xué)院的平面圖中選取有代表性景點(diǎn)（10-15個(gè)），抽象成一個(gè)無向帶權(quán)圖。以圖中頂點(diǎn)表示校內(nèi)各景點(diǎn)，存放景點(diǎn)名稱、代號(hào)、簡介等信息；以邊表示路徑，存放路徑長度等信息。2) 為來訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。3) 為來訪客人提供圖中任意景點(diǎn)的問路查詢，即查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的一條最短的簡單路徑。4) 區(qū)分汽車線路與步行線路?！?/p>

7、測試數(shù)據(jù)】瓊州學(xué)院導(dǎo)游圖（距離可估計(jì)）。選題六：設(shè)計(jì)一個(gè)計(jì)算機(jī)管理系統(tǒng)完成圖書管理基本業(yè)務(wù) 【實(shí)現(xiàn)提示】 1)每種書的登記內(nèi)容包括書號(hào)、書名、著作者、現(xiàn)存量和庫存量； 2)對書號(hào)建立索引表（線性表）以提高查找效率（索引表采用樹表）； 3)系統(tǒng)主要功能如下： *采編入庫：新購一種書，確定書號(hào)后，登記到圖書帳目表中，如果表中已有，則只將庫存量增加； *借閱：如果一種書的現(xiàn)存量大于0，則借出一本，登記借閱者的書證號(hào)和歸還期限，改變現(xiàn)存量； *歸還：注銷對借閱者的登記，改變該書的現(xiàn)存量。選題七：哈夫曼(Huffman)編/譯碼器【問

8、題描述】利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個(gè)哈夫曼碼的編/譯碼系統(tǒng)?！緦?shí)現(xiàn)提示】一個(gè)完整的系統(tǒng)應(yīng)具有以下功能：1) I：初始化（Initialization）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。2) E：編碼（Encoding）。利用以建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對文件

9、ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。3) D：譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。4) P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件CodePrin中。5) T：印哈夫曼樹（Tree Printing）。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件TreePrint中?！緶y試數(shù)據(jù)】1) 利用教科書例6-2（嚴(yán)蔚敏數(shù)據(jù)結(jié)構(gòu)P148）中的數(shù)據(jù)調(diào)試

10、程序。2) 用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”。字符空格ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度5763151485180238181161選題八：內(nèi)部排序算法比較【問題描述】在教科書中，各種內(nèi)部排序算法的時(shí)間復(fù)雜度分析結(jié)果只給出了算法執(zhí)行時(shí)間的階，或大概執(zhí)行時(shí)間。試通過隨機(jī)數(shù)據(jù)比較各種算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動(dòng)次數(shù)，以取得直觀感受?！緦?shí)現(xiàn)提示】1) 對以下7種常用的內(nèi)部排序算法進(jìn)行比較：冒泡排序、直接插入

11、排序、簡單選擇排序、希爾排序、堆排序、歸并排序、快速排序。2) 待排序表的表長不小于100；其中的數(shù)據(jù)要用偽隨機(jī)數(shù)程序產(chǎn)生；至少要用5組不同的輸入數(shù)據(jù)作比較；比較的指標(biāo)為有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動(dòng)次數(shù)（關(guān)鍵字交換計(jì)為3次移動(dòng)）。3) 最后要對結(jié)果作出簡單分析，包括對各組數(shù)據(jù)得出結(jié)果波動(dòng)大小的解釋?！緶y試數(shù)據(jù)】由隨機(jī)數(shù)產(chǎn)生器生成選題九：簡單行編輯程序【問題描述】文本編輯器程序是利用計(jì)算機(jī)進(jìn)行文字加工的基本軟件工具，實(shí)現(xiàn)對文本文件的插入、刪除等修改操作。限制這些操作以行為單位進(jìn)行的編輯程序稱為行編輯程序。被編輯的文本文件可能很大，全部讀入編輯程序的數(shù)據(jù)空間（內(nèi)存）的作法既不經(jīng)濟(jì)，也不總能

12、實(shí)現(xiàn)。一種解決辦法是逐段地編輯。任何時(shí)刻只把待編輯文件的一段放在內(nèi)存，利為活區(qū)。試按照這種方法實(shí)現(xiàn)一個(gè)簡單的行編輯程序。設(shè)文件每行不超過320個(gè)字符，很少超過80個(gè)字符?！緦?shí)現(xiàn)提示】實(shí)現(xiàn)以下4條基本編輯命令：1) 行插入：格式：i<行號(hào)><回車><文本><回車>l 將<文本>插入活區(qū)中第<行號(hào)>行之后。2) 行刪除。格式：d<行號(hào)1><空格><行號(hào)2><回車>l 刪除活區(qū)中第<行號(hào)1>(到第<行號(hào)2>行)。例如“d10”和“d10 14”3) 活區(qū)切換

13、。格式：n<回車>l 將活區(qū)寫入輸出文件，并從輸入文件中讀入下一段，作為新的活區(qū)。4) 活區(qū)顯示。模式：p<回車>l 逐頁地（每頁20行）顯示活區(qū)內(nèi)容，每顯示一頁之后請用戶決定是繼續(xù)顯示以后各頁（如果存在）。印出的每一行要前置行號(hào)和一個(gè)空格符，行號(hào)固定占4位，增量為1。各條命令中的行號(hào)均須在活區(qū)中各行行號(hào)范圍之內(nèi)，只有插入命令的行號(hào)可以等于活區(qū)第一行行號(hào)減1，表示插入當(dāng)前屏幕中第一行之前，否則命令參數(shù)非法?！緶y試數(shù)據(jù)】自行設(shè)定，注意測試將活區(qū)刪空等特殊情況。選題十：一元多項(xiàng)式計(jì)算【問題描述】1.能夠按照指數(shù)降序排列建立并輸出多項(xiàng)式；2.能夠完成兩個(gè)多項(xiàng)式的相加、相減，并

14、將結(jié)果輸入；【實(shí)現(xiàn)提示】1.存儲(chǔ)結(jié)構(gòu);2.多項(xiàng)式相加的基本過程的算法（可以使用程序流程圖）3.可以提出算法的改進(jìn)方法；【測試數(shù)據(jù)】自行設(shè)定，注意邊界等特殊情況。選題十一：集合的交、并、差運(yùn)算【問題描述】 編制一個(gè)能演示執(zhí)行集合的交、并和差運(yùn)算的程序?！緦?shí)現(xiàn)提示】1) 集合元素用小寫英文字母，執(zhí)行各種操作應(yīng)以對話方式執(zhí)行。2) 算法要點(diǎn)：利用單鏈表表示集合；理解好三種運(yùn)算的含【測試數(shù)據(jù)】自行設(shè)定，注意邊界等特殊情況。選題十二：動(dòng)態(tài)查找表【問題描述】 利用二叉排序樹完成動(dòng)態(tài)查找表的建立、指定關(guān)鍵字的查找、插入與刪除指定關(guān)鍵字結(jié)點(diǎn)。【實(shí)現(xiàn)提示】 算法輸入：指定一組數(shù)據(jù)。算法輸出：顯示二叉排序樹的中序

15、遍歷結(jié)果、查找成功與否的信息、插入和刪除后的中序遍歷結(jié)果(排序結(jié)果)。算法要點(diǎn)：二叉排序樹建立方法、動(dòng)態(tài)查找方法,對樹進(jìn)行中序遍歷?！緶y試數(shù)據(jù)】自行設(shè)定，注意邊界等特殊情況。選題十三：學(xué)生成績管理【問題描述】 本例對學(xué)生的成績管理做一個(gè)簡單的模擬，用菜單選擇方式完成下列功能： 登記學(xué)生成績；查詢學(xué)生成績；插入學(xué)生成績；刪除學(xué)生成績?！緦?shí)現(xiàn)提示】 算法輸入：操作要求，學(xué)生信息算法輸出：操作結(jié)果算法要點(diǎn)：把問題看成是對線性表的操作。將學(xué)生成績組織成順序表，則登記學(xué)生成績即是建立順序表操作；查詢學(xué)生成績、插入學(xué)生成績、刪除學(xué)生成績即是在順序表中進(jìn)行查找、插入和刪除操作?！緶y試數(shù)據(jù)】自行設(shè)定，注意邊界

16、等特殊情況。選題十四：馬踏棋盤【問題描述】 將馬隨機(jī)放在國際象棋的8* 8棋盤Bord88的某個(gè)方格中，馬按走棋規(guī)則進(jìn)行移動(dòng)。要求每個(gè)方格上只進(jìn)入一次，走遍棋盤上全部64個(gè)方格。【實(shí)現(xiàn)提示】 編制非遞歸程序，求出馬的行走路線 ，并按求出的行走路線，將數(shù)字1，2，64依次填入一個(gè)8* 8的方陣，輸出之。測試數(shù)據(jù)：由讀者指定,可自行指定一個(gè)馬的初始位置。實(shí)現(xiàn)提示：每次在多個(gè)可走位置中選擇一個(gè)進(jìn)行試探，其余未曾試探過的可走位置必須用適當(dāng)結(jié)構(gòu)妥善管理，以備試探失敗時(shí)的“回溯”(悔棋)使用?！緶y試數(shù)據(jù)】自行設(shè)定，注意邊界等特殊情況。選題十五： joseph環(huán)【問題描述】 編號(hào)是1，2，,n的n個(gè)人按照順

17、時(shí)針方向圍坐一圈，每個(gè)人只有一個(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è)程序來求出出列順序?！緦?shí)現(xiàn)提示】 利用單向循環(huán)鏈表存儲(chǔ)結(jié)構(gòu)模擬此過程，按照出列的順序輸出各個(gè)人的編號(hào)。測試數(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)鏈表。 輸出形式：建立一

18、個(gè)輸出函數(shù)，將正確的輸出序列【測試數(shù)據(jù)】自行設(shè)定，注意邊界等特殊情況。選題十六： 最小生成樹【問題描述】在n個(gè)城市之間建設(shè)網(wǎng)絡(luò)，只需保證連通即可，求最經(jīng)濟(jì)的架設(shè)方法。對于圖，其生成樹中的邊也帶權(quán)，將生成樹各邊的權(quán)值總和稱為生成樹的權(quán)，并將權(quán)值最小的生成樹稱為最小生成樹（Minimun Spanning Tree），簡稱為MST。有兩種非常典型的算法：Prim算法和kruskal算法?！緦?shí)現(xiàn)提示】 設(shè)計(jì)程序完成如下功能：對給定的網(wǎng)和起點(diǎn)，用PRIM算法和kruskal算法的基本思想求解出所有的最小生成樹。存儲(chǔ)結(jié)構(gòu)可自行選擇?！緶y試數(shù)據(jù)】自行設(shè)定，注意邊界等特殊情況。選題十七：通訊錄管理【問題描述

19、】 該設(shè)計(jì)采用菜單作為應(yīng)用程序的主要界面，用控制語句來改變程序執(zhí)行的順序，控制語句是實(shí)現(xiàn)結(jié)構(gòu)化程序設(shè)計(jì)的基礎(chǔ)。該設(shè)計(jì)的任務(wù)是利用一個(gè)簡單實(shí)用的菜單，通過菜單單項(xiàng)進(jìn)行選擇，實(shí)現(xiàn)和完成通訊錄管理中常用的幾個(gè)不同的功能?！緦?shí)現(xiàn)提示】 （1） 菜單內(nèi)容1、 通訊錄鏈表的建立2、 通訊者結(jié)點(diǎn)的插入3、 通訊者結(jié)點(diǎn)的查詢4、 通訊者結(jié)點(diǎn)的刪除5、 通訊錄鏈表的輸出0、 退出管理系統(tǒng)請選擇05：（2） 設(shè)計(jì)要求使用05來選擇菜單項(xiàng)，其他輸入則不起作用。（3） 功能函數(shù)設(shè)計(jì)5個(gè)不同功能的算法實(shí)現(xiàn)編程題，目的是練習(xí)利用鏈表結(jié)構(gòu)來解決實(shí)際應(yīng)用問題的能力，進(jìn)一步理解和熟悉線形表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)?！緶y試數(shù)據(jù)】自行設(shè)定，

20、注意邊界等特殊情況。選題十八：運(yùn)動(dòng)會(huì)分?jǐn)?shù)統(tǒng)計(jì)【問題描述】 參加運(yùn)動(dòng)會(huì)有n個(gè)學(xué)校，學(xué)校編號(hào)為1n。比賽分成m個(gè)男子項(xiàng)目，和w個(gè)女子項(xiàng)目。項(xiàng)目編號(hào)為男子1m，女子m+1m+w。不同的項(xiàng)目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前三名由學(xué)生自己設(shè)定。（m<=20,n<=20）【實(shí)現(xiàn)提示】 功能要求：1).可以輸入各個(gè)項(xiàng)目的前三名或前五名的成績；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é)校。 規(guī)定：輸入數(shù)據(jù)形

21、式和范圍：20以內(nèi)的整數(shù)（如果做得更好可以輸入學(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語言程序設(shè)計(jì)的書上，請自學(xué)解決）請?jiān)谧詈蟮纳辖毁Y料中指明你用到的存儲(chǔ)結(jié)構(gòu)；測試數(shù)據(jù)：要求使用1、全部合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù)據(jù)。進(jìn)行程序測試，以保證程序的穩(wěn)定。測試數(shù)據(jù)及測試結(jié)果請?jiān)谏辖坏馁Y料中寫明；【測試數(shù)據(jù)】自行設(shè)定，注意邊界等特殊情況。選題十九：航班信息的查

22、詢與檢索【問題描述】 該設(shè)計(jì)要求對飛機(jī)航班信息進(jìn)行排序和查找?？砂春桨嗟暮桨嗵?hào)、起點(diǎn)站、到達(dá)站、起飛時(shí)間以及到達(dá)時(shí)間等信息進(jìn)行查詢?！緦?shí)現(xiàn)提示】對于本設(shè)計(jì)，可采用基數(shù)排序法對一組具有結(jié)構(gòu)特點(diǎn)的飛機(jī)航班號(hào)進(jìn)行排序，利用二分查找法對排好序的航班記錄按航班號(hào)實(shí)現(xiàn)快速查找，按其他次關(guān)鍵字的查找可采用最簡單的順序查找方法進(jìn)行，因此他們用得較少。每個(gè)航班記錄包括八項(xiàng)，分別是：航班號(hào)、起點(diǎn)站、終點(diǎn)站、班期、起飛時(shí)間、到達(dá)時(shí)間、飛機(jī)型號(hào)以及票價(jià)等，假設(shè)航班信息表（8條記錄）航班號(hào)起點(diǎn)站終點(diǎn)站班期起飛時(shí)間到達(dá)時(shí)間機(jī)型票價(jià)CA1544合肥北京1.2.4.510551240733960MU5341上海廣州每日142

23、01615M901280CZ3869重慶深圳2.4.6085510357331010MU3682桂林南京2.3.4.6.720502215M901380HU1836上海北京每日094011207381250CZ3528成都廈門1.3.4.5.715101650CRJ1060MU4594昆明西安1.3.5.6101511403281160SC7425青島?？?.3.619202120DH41630其中航班號(hào)一項(xiàng)的格式為：K0 K1 K2 K3 K4 K5CZ3869其中K0和K1的輸入值是航空公司的別稱，用兩個(gè)大寫字母標(biāo)示，后4位為航班號(hào)，這種航班號(hào)關(guān)鍵字可分成兩段，即字母和數(shù)字。其余七項(xiàng)輸入內(nèi)

24、容因?yàn)椴簧婕氨驹O(shè)計(jì)的核心，因此除了票價(jià)為數(shù)值型外，均定義為字符串即可?！緶y試數(shù)據(jù)】自行設(shè)定，注意邊界等特殊情況。選題二十：哈希表應(yīng)用【問題描述】 利用哈希表進(jìn)行存儲(chǔ)?！緦?shí)現(xiàn)提示】 任務(wù)要求：針對一組數(shù)據(jù)進(jìn)行初始化哈希表，可以進(jìn)行顯示哈希表，查找元素，插入元素，刪除元素，退出程序操作。設(shè)計(jì)思想：哈希函數(shù)用除留余數(shù)法構(gòu)造，用線性探測再散列處理沖突。設(shè)計(jì)目的：實(shí)現(xiàn)哈希表的綜合操作簡體中文控制臺(tái)界面：用戶可以進(jìn)行創(chuàng)建哈希表，顯示哈希表，查找元素，插入元素，刪除元素。顯示元素：顯示已經(jīng)創(chuàng)建的哈希表。查找元素：查找哈希表中的元素，分為查找成功和查找不成功。插入元素：在哈希表中，插入一個(gè)元素，分為插入成功和

25、失敗。刪除元素：在已有的數(shù)據(jù)中，刪除一個(gè)元素。退出系統(tǒng)：退出程序?！緶y試數(shù)據(jù)】自行設(shè)定，注意邊界等特殊情況。選題二十一：拓?fù)渑判蚝完P(guān)鍵路徑【問題描述】拓?fù)渑判蚩膳袛郃OV網(wǎng)絡(luò)中是否存在回路，使的所有活動(dòng)可排成一個(gè)線性序列，使用每個(gè)活動(dòng)的所有前驅(qū)活動(dòng)都排在該活動(dòng)的前面。關(guān)鍵路徑的工期決定了整個(gè)項(xiàng)目的工期。任何關(guān)鍵路徑上的終端元素的延遲將直接影響項(xiàng)目的預(yù)期完成時(shí)間（例如在關(guān)鍵路徑上沒有浮動(dòng)時(shí)間）?！緦?shí)現(xiàn)提示】 構(gòu)建AOV網(wǎng)絡(luò)，并輸出其拓?fù)湫蛄薪Y(jié)果，輸出該圖的關(guān)鍵路徑和關(guān)鍵活動(dòng)，存儲(chǔ)結(jié)構(gòu)自行選擇?！緶y試數(shù)據(jù)】自行設(shè)定，注意邊界等特殊情況。選題二十二：倉庫管理系統(tǒng)【問題描述】建立一個(gè)倉庫管理程序，可以

26、按順序和貨物名稱查詢倉庫存儲(chǔ)情況，也可以增加或刪除貨物以及建立新的倉庫存儲(chǔ)系統(tǒng)?！緦?shí)現(xiàn)提示】可以采用雙向鏈表的存儲(chǔ)結(jié)構(gòu)，如可定義如下的存儲(chǔ)結(jié)構(gòu)：typedef struct dnode /*定義雙向鏈表結(jié)構(gòu)體*/ int number; /*貨物編號(hào)*/ char namemax; /*貨物名稱*/ int counter; /*貨物數(shù)量*/ struct dnode *prior,*next; /*定義兩指針，分別指向其前驅(qū)和后繼*/ dlnode;選題二十三：單位員工通訊錄管理系統(tǒng)【問題描述】為某個(gè)單位建立一個(gè)員工通訊錄管理系統(tǒng)，可以方便查詢每一個(gè)員工的辦公室電話、手機(jī)號(hào)、及電子郵箱。其功

27、能包括通訊錄鏈表的建立、員工通訊信息的查詢、修改、插入與刪除、以及整個(gè)通訊錄表的輸出?！緦?shí)現(xiàn)提示】可以采用單鏈表的存儲(chǔ)結(jié)構(gòu)，如可定義如下的存儲(chǔ)結(jié)構(gòu)：typedef struct /*員工通訊信息的結(jié)構(gòu)類型定義*/ char num5; /*員工編號(hào)*/ char name10; /*員工姓名*/ char phone15; /*辦公室電話號(hào)碼*/ char call15; /*手機(jī)號(hào)碼*/DataType;/*通訊錄單鏈表的結(jié)點(diǎn)類型*/typedef struct node DataType data; /*結(jié)點(diǎn)的數(shù)據(jù)域*/ struct node *next; /*結(jié)點(diǎn)的指針域*/ListN

28、ode,*LinkList;選題二十四: 哈夫曼編碼/譯碼系統(tǒng)【問題描述】利用哈夫曼編碼進(jìn)行通信，可以壓縮通信的數(shù)據(jù)量，提高傳輸效率，縮短信息的傳輸時(shí)間，還有一定的保密性。現(xiàn)在要求編寫一程序模擬傳輸過程，實(shí)現(xiàn)在發(fā)送前將要發(fā)送的字符信息進(jìn)行編碼，然后進(jìn)行發(fā)送，接收后將傳來的數(shù)據(jù)進(jìn)行譯碼，即將信息還原成發(fā)送前的字符信息?！緦?shí)現(xiàn)提示】在本例中設(shè)置發(fā)送者和接受者兩個(gè)功能，發(fā)送者的功能包括：輸入待傳送的字符信息；統(tǒng)計(jì)字符信息中出現(xiàn)的字符種類數(shù)和各字符出現(xiàn)的次數(shù)（頻率）；根據(jù)字符的種類數(shù)和各自出現(xiàn)的次數(shù)建立哈夫曼樹；利用以上哈夫曼樹求出各字符的哈夫曼編碼；將字符信息轉(zhuǎn)換成對應(yīng)的編碼信息進(jìn)行傳送。接受者的功

29、能包括：接收發(fā)送者傳送來的編碼信息；利用上述哈夫曼樹對編碼信息進(jìn)行翻譯，即將編碼信息還原成發(fā)送前的字符信息。從以上分析可發(fā)現(xiàn)，在本例中的主要算法有三個(gè)：（1）哈夫曼樹的建立；（2）哈夫曼編碼的生成；（3）對編碼信息的翻譯。選題二十五:教學(xué)計(jì)劃編制問題【問題描述】大學(xué)的每個(gè)專業(yè)都要制定教學(xué)計(jì)劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時(shí)間長度和學(xué)分上限值均相等。每個(gè)專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時(shí)間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個(gè)學(xué)期。試在這樣的前提下設(shè)計(jì)一個(gè)教學(xué)計(jì)劃編制程序?！緦?shí)現(xiàn)提示】1、 輸入?yún)?shù)

30、應(yīng)包括：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門課的課程號(hào)（可以是固定占3位的字母數(shù)字串）、學(xué)分和直接先修課的課程號(hào)。2、 應(yīng)允許用戶指定下列兩種編排策略之一：一是使學(xué)生在各學(xué)期中的學(xué)習(xí)負(fù)擔(dān)盡量均勻；二是使課程盡可能地集中在前幾個(gè)學(xué)期中。3、 若根據(jù)給定的條件問題無解，則報(bào)告適當(dāng)?shù)男畔ⅲ环駝t將教學(xué)計(jì)劃輸出到用戶指定的文件中。計(jì)劃的表格格式可以自己設(shè)計(jì)。4、 可設(shè)學(xué)期總數(shù)不超過12，課程總數(shù)不超過100。如果輸入的先修課程號(hào)不在該專業(yè)開設(shè)的課程序列中，則作為錯(cuò)誤處理。選題二十六：圖書管理系統(tǒng)【問題描述】圖書管理基本業(yè)務(wù)活動(dòng)包括：對一本書的采編入庫、清除庫存、借閱和歸還等等。試設(shè)計(jì)一個(gè)圖書管理系統(tǒng)，將上述

31、業(yè)務(wù)活動(dòng)借助于計(jì)算機(jī)系統(tǒng)完成。【實(shí)現(xiàn)提示】1、 每種書的登記內(nèi)容至少包括書號(hào)、書名、著者、現(xiàn)存量和總庫存量等五項(xiàng)。2、 由于圖書管理的基本業(yè)務(wù)活動(dòng)都是通過書號(hào)（即關(guān)鍵字）進(jìn)行的，所以要用對書號(hào) 索引，以獲得高效率。3、 系統(tǒng)應(yīng)實(shí)現(xiàn)的基本功能有：l 采編入庫：新購入一種書，經(jīng)分類和確定書號(hào)之后登記到圖書帳目中去。如果這兩種書在帳中已有，則只將總庫存量增加。l 清除庫存：某種書已無保留價(jià)值，將它從圖書帳目中注銷。l 借閱：如果一種書的現(xiàn)存量大于零，則借出一本，登記借閱者的圖書證號(hào)和歸還期限。l 歸還：注銷對借閱者的登記，改變該書的現(xiàn)存量。l 顯示：以凹入表的形式顯示B樹。這個(gè)操作是為了調(diào)試和維護(hù)的

32、目的而設(shè)置的。選題二十七： 通信錄查詢系統(tǒng)【問題描述】設(shè)計(jì)散列表實(shí)現(xiàn)通訊錄查找系統(tǒng)。(1) 設(shè)每個(gè)記錄有下列數(shù)據(jù)項(xiàng)：電話號(hào)碼、用戶名、地址；(2) 從鍵盤輸入各記錄，分別以電話號(hào)碼為關(guān)鍵字建立散列表；(3) 采用二次探測再散列法解決沖突；(4) 查找并顯示給定電話號(hào)碼的記錄；(5) 通訊錄信息文件保存；(6) 要求人機(jī)界面友好，使用圖形化界面；【實(shí)現(xiàn)提示】主函數(shù)：根據(jù)選單的選項(xiàng)調(diào)用各函數(shù)，并完成相應(yīng)的功能。Menu()的功能：顯示英文提示選單。Quit()的功能：退出選單。Create()的功能：創(chuàng)建新的通訊錄。Append()的功能：在通訊錄的末尾寫入新的信息，并返回選單。Find()：查詢某人的信息，如果找到了，則顯示該人的信息，如果沒有則提示通訊錄中沒有此人的信息，并返回選單。Alter()的功能：修改某人的信息，如果未找到要修改的人，則提示通訊錄中沒有此人的信息，并返回選單。Delete()的功能：刪除