選題一：迷宮與棧問題【問題描繪】以一個mXn的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論。【任務要求】首先實現一個以鏈表作存儲構造的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組〔i，j，d〕的形式輸出。其中：〔i，j〕指示迷宮中的一個坐標，d表示走到下一坐標的方向。如，對于以下數據的迷宮，輸出一條通路為：〔1，1，1〕，〔1，2，2〕，〔2，2，2〕，〔3，2，3〕，〔3，1，2〕，…。編寫遞歸形式的算法，求得迷宮中所有可能的通路。以方陣形式輸出迷宮及其通路。【測試數據】迷宮的測試數據如下：左上角〔0，1〕為入口，右下角〔8，9〕為出口。

選題二：算術表達式與二叉樹【問題描繪】一個表達式和一棵二叉樹之間，存在著自然的對應關系。寫一個程序，實現基于二叉樹表示的算術表達式的操作。【任務要求】假設算術表達式Expression內可以含有變量〔a～z〕、常量〔0～9〕和二元運算符〔+，-，*，/，^(乘冪)〕。實現以下操作：ReadExpre(E)—以字符序列的形式輸入語法正確的前綴表達式并構造表達式E。WriteExpre(E)—用帶括弧的中綴表達式輸出表達式E。Assign(V,c)—實現對變量V的賦值〔V=c〕，變量的初值為0。Value(E)—對算術表達式E求值。CompoundExpr〔P，E1，E2〕--構造一個新的復合表達式〔E1〕P〔E2〕【測試數據】分別輸入0；a；-91；+a*bc；+*5^x2*8x；+++*3^x3*2^x2x6并輸出。每當輸入一個表達式后，對其中的變量賦值，然后對表達式求值。

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

選題四：文學研究助手與形式匹配算法KMP【問題描繪】文學研究人員需要統計某篇英文小說中某些形容詞的出現次數和位置。試寫一個實現這一目的的文字統計系統【任務要求】英文小說存于一個文本文件中。待統計的詞聚集合要一次輸入完畢，即統計工作必須在程序的一次運行之后就全部完成。程序的輸出結果是每個詞的出現次數和出現位置所在的行的行號，格式自行設計。待統計的“單詞〞在文本串中不跨行出現，它或者從行首開始，或者前置以一個空格符。形式匹配要基于KMP算法。推廣到更一般的形式集匹配問題，并設待查形式串可以跨行〔提示：定義操作GetAChar〕。【測試數據】文本文件為testword.c待統計的詞集：if、else、for、while、return、void、int、char、typedef、struct

選題五：北理珠校園導游咨詢與最短途徑【問題描繪】從北京理工大學珠海學院的平面圖中選取有代表性景點〔10-15個〕，抽象成一個無向帶權圖。以圖中頂點表示景點，邊上的權值表示兩地之間間隔。本程序的目的是為用戶提供途徑咨詢。根據用戶指定的始點和終點輸出相應途徑，或者根據用戶指定的景點輸出景點的信息。【任務要求】從北京理工大學珠海學院的平面圖中選取有代表性景點〔10-15個〕，抽象成一個無向帶權圖。以圖中頂點表示校內各景點，存放景點名稱、代號、簡介等信息；以邊表示途徑，存放途徑長度等信息。為來訪客人提供圖中任意景點相關信息的查詢。為來訪客人提供圖中任意景點的問路查詢，即查詢任意兩個景點之間的一條最短的簡單途徑。區分汽車線路與步行線路。【測試數據】北理珠校園導游圖〔間隔可估計〕。

選題六：B-樹與B+樹及其操作【問題描繪】學習并研究B-樹與B+樹，并編寫演示它們操作的程序。【任務要求】B-樹構建、查找、插入和刪除操作程序。B+樹構建、查找、插入和刪除操作程序。【測試數據】

選題七：哈夫曼(Huffman)編/譯碼器【問題描繪】利用哈夫曼編碼進展通信可以大大進步信道利用率，縮短信息傳輸時間，降低傳輸本錢。但是，這要求在發送端通過一個編碼系統對待傳數據預先編碼，在接收端將傳來的數據進展譯碼〔復原〕。對于雙工信道〔即可以雙向傳輸信息的信道〕，每端都需要一個完好的編/譯碼系統。試為這樣的信息收發站寫一個哈夫曼碼的編/譯碼系統。【任務要求】一個完好的系統應具有以下功能：I：初始化〔Initialization〕。從終端讀入字符集大小n，以及n個字符和n個權值，建立哈夫曼樹，并將它存于文件hfmTree中。E：編碼〔Encoding〕。利用以建好的哈夫曼樹〔如不在內存，那么從文件hfmTree中讀入〕，對文件ToBeTran中的正文進展編碼，然后將結果存入文件CodeFile中。D：譯碼〔Decoding〕。利用已建好的哈夫曼樹將文件CodeFile中的代碼進展譯碼，結果存入文件TextFile中。P：印代碼文件〔Print〕。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrin中。T：印哈夫曼樹〔TreePrinting〕。將已在內存中的哈夫曼樹以直觀的方式〔樹或凹入表形式〕顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。【測試數據】利用教科書例6-2〔嚴蔚敏?數據構造?P148〕中的數據調試程序。用下表給出的字符集和頻度的實際統計數據建立哈夫曼樹，并實現以下報文的編碼和譯碼：“THISPROGRAMISMYFAVORITE〞。字符空格ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度5763151485180238181161

選題八：內部排序算法比較【問題描繪】在教科書中，各種內部排序算法的時間復雜度分析結果只給出了算法執行時間的階，或大概執行時間。試通過隨機數據比較各種算法的關鍵字比較次數和關鍵字挪動次數，以獲得直觀感受。【任務要求】對以下7種常用的內部排序算法進展比較：冒泡排序、直接插入排序、簡單項選擇擇排序、希爾排序、堆排序、歸并排序、快速排序。待排序表的表長不小于100；其中的數據要用偽隨機數程序產生；至少要用5組不同的輸入數據作比較；比較的指標為有關鍵字參加的比較次數和關鍵字的挪動次數〔關鍵字交換計為3次挪動〕。最后要對結果作出簡單分析，包括對各組數據得出結果波動大小的解釋。【測試數據】由隨機數產生器生成

選題九：簡單行編輯程序【問題描繪】文本編輯器程序是利用計算機進展文字加工的根本軟件工具，實現對文本文件的插入、刪除等修改操作。限制這些操作以行為單位進展的編輯程序稱為行編輯程序。被編輯的文本文件可能很大，全部讀入編輯程序的數據空間〔內存〕的作法既不經濟，也不總能實現。一種解決方法是逐段地編輯。任何時刻只把待編輯文件的一段放在內存，利為活區。試按照這種方法實現一個簡單的行編輯程序。設文件每行不超過320個字符，很少超過80個字符。【任務要求】實現以下4條根本編輯命令：行插入：格式：i<行號><回車><文本><回車>將<文本>插入活區中第<行號>行之后。行刪除。格式：d<行號1>[<空格><行號2>]<回車>刪除活區中第<行號1>(到第<行號2>行)。例如“d10〞和“d1014活區切換。格式：n<回車>將活區寫入輸出文件，并從輸入文件中讀入下一段，作為新的活區。活區顯示。形式：p<回車>逐頁地〔每頁20行〕顯示活區內容，每顯示一頁之后請用戶決定是繼續顯示以后各頁〔假設存在〕。印出的每一行要前置行號和一個空格符，行號固定占4位，增量為1。各條命令中的行號均須在活區中各行行號范圍之內，只有插入命令的行號可以等于活區第一行行號減1，表示插入當前屏幕中第一行之前，否那么命令參數非法。【測試數據】自行設定，注意測試將活區刪空等特殊情況。選題十：一元多項式計算【問題描繪】1.可以按照指數降序排列建立并輸出多項式；2.可以完成兩個多項式的相加、相減，并將結果輸入；

【任務要求】1.存儲構造;2.多項式相加的根本過程的算法〔可以使用程序流程圖〕3.可以提出算法的改進方法；【測試數據】自行設定，注意邊界等特殊情況。選題十一：集合的交、并、差運算【問題描繪】編制一個能演示執行集合的交、并和差運算的程序。【任務要求】集合元素用小寫英文字母，執行各種操作應以對話方式執行。算法要點：利用單鏈表表示集合；理解好三種運算的含【測試數據】自行設定，注意邊界等特殊情況。選題十二：動態查找表【問題描繪】利用二叉排序樹完成動態查找表的建立、指定關鍵字的查找、插入與刪除指定關鍵字結點。【任務要求】算法輸入：指定一組數據。算法輸出：顯示二叉排序樹的中序遍歷結果、查找成功與否的信息、插入和刪除后的中序遍歷結果(排序結果)。算法要點：二叉排序樹建立方法、動態查找方法,對樹進展中序遍歷。【測試數據】自行設定，注意邊界等特殊情況。選題十三：學生成績管理【問題描繪】本例對學生的成績管理做一個簡單的模擬，用菜單項選擇擇方式完成以下功能：登記學生成績；查詢學生成績；插入學生成績；刪除學生成績。【任務要求】算法輸入：操作要求，學生信息算法輸出：操作結果算法要點：把問題看成是對線性表的操作。將學生成績組織成順序表，那么登記學生成績即是建立順序表操作；查詢學生成績、插入學生成績、刪除學生成績即是在順序表中進展查找、插入和刪除操作。【測試數據】自行設定，注意邊界等特殊情況。選題十四：馬踏棋盤【問題描繪】將馬隨機放在國際象棋的8*8棋盤Bord[8Ⅱ8]的某個方格中，馬按走棋規那么進展挪動。要求每個方格上只進入一次，走遍棋盤上全部64個方格。【任務要求】編制非遞歸程序，求出馬的行走道路，并按求出的行走道路，將數字1，2，…，64依次填入一個8*8的方陣，輸出之。測試數據：由讀者指定,可自行指定一個馬的初始位置。實現提示：每次在多個可走位置中選擇一個進展試探，其余未曾試探過的可走位置必須用適當構造妥善管理，以備試探失敗時的“回溯〞(悔棋)使用。【測試數據】自行設定，注意邊界等特殊情況。選題十五：joseph環【問題描繪】編號是1，2，……,n的n個人按照順時針方向圍坐一圈，每個人只有一個密碼〔正整數〕。一開始任選一個正整數作為報數上限值m,從第一個仍開始順時針方向自1開始順序報數，報到m時停頓報數。報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下一個人開始重新從1報數，如此下去，直到所有人全部出列為止。設計一個程序來求出出列順序。【任務要求】利用單向循環鏈表存儲構造模擬此過程，按照出列的順序輸出各個人的編號。測試數據：m的初值為20，n=7,7個人的密碼依次為3，1，7，2，4，7，4，首先m=6,那么正確的輸出是什么？

要求：

輸入數據：建立輸入處理輸入數據，輸入m的初值，n，輸入每個人的密碼，建立單循環鏈表。

輸出形式：建立一個輸出函數，將正確的輸出序列【測試數據】自行設定，注意邊界等特殊情況。選題十六：最小生成樹【問題描繪】在n個城市之間建立網絡，只需保證連通即可，求最經濟的架設方法。對于圖，其生成樹中的邊也帶權，將生成樹各邊的權值總和稱為生成樹的權，并將權值最小的生成樹稱為最小生成樹〔MinimunSpanningTree〕，簡稱為MST。有兩種非常典型的算法：Prim算法和kruskal算法。【任務要求】設計程序完成如下功能：對給定的網和起點，用PRIM算法和kruskal算法的根本思想求解出所有的最小生成樹。存儲構造可自行選擇。【測試數據】自行設定，注意邊界等特殊情況。選題十七：通訊錄管理【問題描繪】該設計采用菜單作為應用程序的主要界面，用控制語句來改變程序執行的順序，控制語句是實現構造化程序設計的根底。該設計的任務是利用一個簡單實用的菜單，通過菜單單項進展選擇，實現和完成通訊錄管理中常用的幾個不同的功能。【任務要求】菜單內容通訊錄鏈表的建立通訊者結點的插入通訊者結點的查詢通訊者結點的刪除通訊錄鏈表的輸出退出管理系統請選擇0~5：設計要求使用0~5來選擇菜單項，其他輸入那么不起作用。功能函數設計5個不同功能的算法實現編程題，目的是練習利用鏈表構造來解決實際應用問題的才能，進一步理解和熟悉線形表的鏈式存儲構造。【測試數據】自行設定，注意邊界等特殊情況。選題十八：運動會分數統計【問題描繪】參加運動會有n個學校，學校編號為1……n。比賽分成m個男子工程，和w個女子工程。工程編號為男子1……m，女子m+1……m+w。不同的工程取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前三名由學生自己設定。〔m<=20,n<=20〕【任務要求】功能要求：1).可以輸入各個工程的前三名或前五名的成績；

2)．能統計各學校總分，

3)．可以按學校編號、學校總分、男女團體總分排序輸出；

4).可以按學校編號查詢學校某個工程的情況；可以按工程編號查詢獲得前三或前五名的學校。

規定：輸入數據形式和范圍：20以內的整數〔假設做得更好可以輸入學校的名稱，運開工程的名稱〕

輸出形式：有中文提示，各學校分數為整形

界面要求：有合理的提示，每個功能可以設立菜單，根據提示，可以完成相關的功能要求。

存儲構造：學生自己根據系統功能要求自己設計，但是要求運動會的相關數據要存儲在數據文件中。〔數據文件的數據讀寫方法等相關內容在c語言程序設計的書上，請自學解決〕請在最后的上交資料中指明你用到的存儲構造；

測試數據：要求使用1、全部合法數據；2、整體非法數據；3、局部非法數據。進展程序測試，以保證程序的穩定。測試數據及測試結果請在上交的資料中寫明；【測試數據】自行設定，注意邊界等特殊情況。選題十九：航班信息的查詢與檢索【問題描繪】該設計要求對飛機航班信息進展排序和查找。可按航班的航班號、起點站、到達站、起飛時間以及到達時間等信息進展查詢。【任務要求】對于本設計，可采用基數排序法對一組具有構造特點的飛機航班號進展排序，利用二分查找法對排好序的航班記錄按航班號實現快速查找，按其他次關鍵字的查找可采用最簡單的順序查找方法進展，因此他們用得較少。每個航班記錄包括八項，分別是：航班號、起點站、終點站、班期、起飛時間、到達時間、飛機型號以及票價等，假設航班信息表〔8條記錄〕航班號起點站終點站班期起飛時間到達時間機型票價CA1544合肥北京1.2.4.510551240733960MU5341上海廣州每日14201615M901280CZ3869重慶深圳2.4.6085510357331010MU3682桂林南京2.3.4.6.720502215M901380HU1836上海北京每日094011207381250CZ3528成都廈門1.3.4.5.715101650CRJ1060MU4594昆明西安1.3.5.6101511403281160SC7425青島海口1.3.619202120DH41630其中航班號一項的格式