個題目“數據結構”課程設計方案指導書

1、選題一：迷宮與棧問題【問題描述】以一個 mXn 的長方陣表示迷宮， 0 和 1 分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論?！救蝿找蟆?) 首先實現一個以鏈表作存儲結構的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（ i， j，d ）的形式輸出。其中：（ i， j）指示迷宮中的一個坐標， d 表示走到下一坐標的方向。如，對于下列數據的迷宮，輸出一條通路為：（ 1， 1， 1），（ 1， 2， 2），（ 2， 2， 2），（ 3，2， 3），（ 3， 1， 2）， 。2) 編寫遞歸形式的算法，求得迷宮中所有可能的

2、通路。3) 以方陣形式輸出迷宮及其通路?！緶y試數據】迷宮的測試數據如下：左上角（0， 1）為入口，右下角（8， 9）為出口。入口入口012345678901234567890010111111111110010001012210010001013310000110014410111000015510001000016610100010017710111011018811000000009出口91111111111出口【成績評定】1. 完成“任務要求”第 1 項成績評定為“及格” -“中”。2. 完成“任務要求”第 2 項和第 3 項成績評定為“良”或以上。選題二：算術表達式與二叉樹【問題描述】

3、一個表達式和一棵二叉樹之間，存在著自然的對應關系。寫一個程序，實現基于二叉樹表示的算術表達式的操作?！救蝿找蟆考僭O算術表達式 Expression 內可以含有變量（ a z）、常量（ 0 9）和二元運算符（+， -，* ， / ， ( 乘冪 )）。實現以下操作：1) ReadExpre(E)以字符序列的形式輸入語法正確的前綴表達式并構造表達式E。2) WriteExpre(E)用帶括弧的中綴表達式輸出表達式E。3) Assign(V,c)實現對變量V 的賦值（ V=c），變量的初值為0。4) Value(E)對算術表達式E 求值。5) CompoundExpr （ P，E1， E2） -構造

4、一個新的復合表達式（E1） P（ E2）【測試數據】1) 分別輸入 0 ；a； -91； +a*bc ； +*5x2*8x ； +*3x3*2x2x6 并輸出。2) 每當輸入一個表達式后，對其中的變量賦值，然后對表達式求值?！境煽冊u定】1. 完成“任務要求”第 1 項和第 2 項成績評定為“及格” -“中”。2. 完成“任務要求”第 3 項至第 5 項成績評定為“良”及以上。選題三：銀行業(yè)務模擬與離散事件模擬【問題描述】假設某銀行有4 個窗口對外接待客戶，從早晨銀行開門（開門9： 00am ，關門5：00pm）起不斷有客戶進入銀行。由于每個窗口在某個時刻只能接待一個客戶，因此在客戶人數眾多時需

5、要在每個窗口前順次排隊，對于剛進入銀行的客戶（建議：客戶進入時間使用隨機函數產生），如果某個窗口的業(yè)務員正空閑，則可上前辦理業(yè)務；反之，若 4 個窗口均有窗戶所占，他便會排在人數最少的隊伍后面?！救蝿找蟆?) 編制一個程序以模擬銀行的這種業(yè)務活動并計算一天中客戶在銀行逗留的平均時間。2) 建議有如下設置：a)客戶到達時間隨機產生，一天客戶的人數設定為b)銀行業(yè)務員處理時間隨機產生，平均處理時間100 人。10 分鐘。3) 將一天的數據（包括業(yè)務員和客戶）以文件方式輸出?！緶y試數據】由隨機數產生器生成【成績評定】1) 能按教材要求完成“任務要求”第1 項成績評定為“及格”-“中”。2) 完成“

6、任務要求”第 2 項至第 3 項成績評定為“良”及以上。選題四：文學研究助手與模式匹配算法KMP【問題描述】文學研究人員需要統(tǒng)計某篇英文小說中某些形容詞的出現次數和位置。試寫一個實現這一目標的文字統(tǒng)計系統(tǒng)【任務要求】1) 英文小說存于一個文本文件中。待統(tǒng)計的詞匯集合要一次輸入完畢，即統(tǒng)計工作必須在程序的一次運行之后就全部完成。程序的輸出結果是每個詞的出現次數和出現位置所在的行的行號，格式自行設計。待統(tǒng)計的“單詞”在文本串中不跨行出現，它或者從行首開始，或者前置以一個空格符。2) 模式匹配要基于 KMP 算法。3) 推廣到更一般的模式集匹配問題，并設待查模式串可以跨行（提示：定義操作GetACh

7、ar）?！緶y試數據】1) 文本文件為 testword.c2) 待統(tǒng)計的詞集： if、 else、for 、while 、 return 、 void、 int 、 char、 typedef 、struct【成績評定】1) 完成“任務要求”第 1 項成績評定為“及格” -“中”。2) 完成“任務要求”第 2 項至第 3 項成績評定為“良”及以上。選題五：北理珠校園導游咨詢與最短路徑【問題描述】1) 從北京理工大學珠海學院的平面圖中選取有代表性景點（ 10-15 個），抽象成一個無向帶權圖。以圖中頂點表示景點，邊上的權值表示兩地之間距離。2) 本程序的目的是為用戶提供路徑咨詢。根據用戶指定的始

8、點和終點輸出相應路徑，或者根據用戶指定的景點輸出景點的信息?！救蝿找蟆?) 從北京理工大學珠海學院的平面圖中選取有代表性景點（10-15 個），抽象成一個無向帶權圖。以圖中頂點表示校內各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等信息。2) 為來訪客人提供圖中任意景點相關信息的查詢。3) 為來訪客人提供圖中任意景點的問路查詢，即查詢任意兩個景點之間的一條最短的簡單路徑。4) 區(qū)分汽車線路與步行線路?！緶y試數據】北理珠校園導游圖（距離可估計）?！境煽冊u定】1) 完成“任務要求”第 3 項成績評定為“及格”。2) 完成“任務要求”第 1-3 項成績評定為“中”以上。3) 完

9、成“任務要求”第 1-4 項成績評定為“良”以上。選題六： B- 樹與 B+ 樹及其操作【問題描述】學習并研究B-樹與 B+樹，并編寫演示它們操作的程序?！救蝿找蟆?) B-樹構建、查找、插入和刪除操作程序。2) B+樹構建、查找、插入和刪除操作程序?！緶y試數據】【成績評定】1) 完成“任務要求”第 1 項成績評定為“及格” -“中”。2) 完成“任務要求”第 1-2 項成績評定為“良”以上。選題七：哈夫曼(Huffman)編 / 譯碼器【問題描述】利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數據預先編碼，在接收端將

10、傳來的數據進行譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編 / 譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼碼的編/ 譯碼系統(tǒng)?！救蝿找蟆恳粋€完整的系統(tǒng)應具有以下功能：1)I：初始化（ Initialization ）。從終端讀入字符集大小n，以及 n 個字符和 n 個權值，建立哈夫曼樹，并將它存于文件hfmTree 中。2)E：編碼（ Encoding）。利用以建好的哈夫曼樹（如不在內存，則從文件hfmTree 中讀入），對文件 ToBeTran中的正文進行編碼，然后將結果存入文件CodeFile 中。3)D：譯碼（ Decoding ）。利用已建好的哈夫曼

11、樹將文件CodeFile中的代碼進行譯碼，結果存入文件 TextFile 中。4)P：印代碼文件（ Print ）。將文件 CodeFile 以緊湊格式顯示在終端上，每行50 個代碼。同時將此字符形式的編碼文件寫入文件CodePrin 中。5) T：印哈夫曼樹（ Tree Printing ）。將已在內存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint 中?！緶y試數據】1) 利用教科書例 6-2（嚴蔚敏數據結構 P148）中的數據調試程序。2) 用下表給出的字符集和頻度的實際統(tǒng)計數據建立哈夫曼樹，并實現以下報文的編碼和譯碼：“ THI

12、S PROGRAM IS MY FAVORITE”。字符 空格ABCDEFGHIJKLM頻度1866413223210321154757153220字符NO PQRSTUVWXYZ頻度5763151485180238181161【成績評定】1) 完成“任務要求”第 1 項成績評定為“及格” -“中”。2) 完成“任務要求”第 1-2 項成績評定為“良”以上。選題八：內部排序算法比較【問題描述】在教科書中，各種內部排序算法的時間復雜度分析結果只給出了算法執(zhí)行時間的階，或大概執(zhí)行時間。試通過隨機數據比較各種算法的關鍵字比較次數和關鍵字移動次數，以取得直觀感受。【任務要求】1) 對以下 7 種常用的

13、內部排序算法進行比較：冒泡排序、直接插入排序、簡單選擇排序、希爾排序、堆排序、歸并排序、快速排序。2) 待排序表的表長不小于100；其中的數據要用偽隨機數程序產生；至少要用同的輸入數據作比較；比較的指標為有關鍵字參加的比較次數和關鍵字的移動次數（關鍵字交換計為3 次移動）。5 組不3) 最后要對結果作出簡單分析，包括對各組數據得出結果波動大小的解釋。【測試數據】由隨機數產生器生成【成績評定】1) 完成“任務要求” 4 個排序算法及比較評定為“及格”-“中”。2) 完成“任務要求”所有排序算法及比較成績評定為“良”以上。選題九：簡單行編輯程序【問題描述】文本編輯器程序是利用計算機進行文字加工的基

14、本軟件工具，實現對文本文件的插入、刪除等修改操作。限制這些操作以行為單位進行的編輯程序稱為行編輯程序。被編輯的文本文件可能很大，全部讀入編輯程序的數據空間（內存）的作法既不經濟，也不總能實現。一種解決辦法是逐段地編輯。任何時刻只把待編輯文件的一段放在內存，利為活區(qū)。試按照這種方法實現一個簡單的行編輯程序。設文件每行不超過320 個字符，很少超過 80個字符?！救蝿找蟆繉崿F以下 4條基本編輯命令：1) 行插入：格式： i<行號 ><回車 ><文本 ><回車 > 將 <文本 >插入活區(qū)中第 <行號 >行之后。2) 行刪除。格

15、式： d<行號 1><空格 ><行號 2><回車 >刪除活區(qū)中第<行號 1>(到第 <行號 2>行 )。例如“ d10”和“ d10 14”3) 活區(qū)切換。格式： n<回車 >將活區(qū)寫入輸出文件，并從輸入文件中讀入下一段，作為新的活區(qū)。4) 活區(qū)顯示。模式： p<回車 >逐頁地（每頁 20 行）顯示活區(qū)內容，每顯示一頁之后請用戶決定是繼續(xù)顯示以后各頁（如果存在）。印出的每一行要前置行號和一個空格符，行號固定占 4 位，增量為 1。各條命令中的行號均須在活區(qū)中各行行號范圍之內，只有插入命令的行號可以等

16、于活區(qū)第一行行號減 1，表示插入當前屏幕中第一行之前，否則命令參數非法?！緶y試數據】自行設定，注意測試將活區(qū)刪空等特殊情況?！境煽冊u定】1) 完成“插入”與“刪除”功能評定為“及格”；2) 完成全部功能評定為“良”以上。選題十：一元多項式計算【問題描述】1.能夠按照指數降序排列建立并輸出多項式；2.能夠完成兩個多項式的相加、相減，并將結果輸入；【任務要求】1.存儲結構。2.多項式相加的基本過程的算法（可以使用程序流程圖）3.可以提出算法的改進方法；【測試數據】自行設定，注意測試將活區(qū)刪空等特殊情況?！境煽冊u定】3) 完成“相加”與“相減”功能評定為“及格”或“中等”；4) 對算法有所改進和優(yōu)化

17、評定為“良好”。選題十一：集合的交、并、差運算【問題描述】編制一個能演示執(zhí)行集合的交、并和差運算的程序?！救蝿找蟆?) 集合元素用小寫英文字母，執(zhí)行各種操作應以對話方式執(zhí)行。2) 算法要點：利用單鏈表表示集合；理解好三種運算的含【測試數據】自行設定，注意測試將活區(qū)刪空等特殊情況?！境煽冊u定】1) 基本完成交、并和差功能評定為“及格”或“中等”；2) 對算法有所改進和優(yōu)化評定為“良好”。選題十二：動態(tài)查找表【問題描述】利用二叉排序樹完成動態(tài)查找表的建立、指定關鍵字的查找、插入與刪除指定關鍵字結點?！救蝿找蟆克惴ㄝ斎耄褐付ㄒ唤M數據。算法輸出：顯示二叉排序樹的中序遍歷結果、查找成功與否的信息、插

18、入和刪除后的中序遍歷結果 (排序結果 )。算法要點：二叉排序樹建立方法、動態(tài)查找方法,對樹進行中序遍歷?！緶y試數據】自行設定，注意測試將活區(qū)刪空等特殊情況?！境煽冊u定】1) 基本完成相應功能評定為“及格”或“中等”；2) 對算法有所改進和優(yōu)化評定為“良好”。選題十三：學生成績管理【問題描述】本例對學生的成績管理做一個簡單的模擬，用菜單選擇方式完成下列功能： 登記學生成績；查詢學生成績；插入學生成績；刪除學生成績?！救蝿找蟆克惴ㄝ斎耄翰僮饕螅瑢W生信息算法輸出：操作結果算法要點：把問題看成是對線性表的操作。將學生成績組織成順序表，則登記學生成績即是建立順序表操作；查詢學生成績、插入學生成績、刪

19、除學生成績即是在順序表中進行查找、插入和刪除操作?！緶y試數據】自行設定，注意測試將活區(qū)刪空等特殊情況?！境煽冊u定】1) 基本完成相應功能評定為“及格”或“中等”；2) 對算法有所改進和優(yōu)化評定為“良好”。選題十四：馬踏棋盤【問題描述】將馬隨機放在國際象棋的8*8 棋盤 Bord8 8的某個方格中，馬按走棋規(guī)則進行移動。要求每個方格上只進入一次，走遍棋盤上全部64 個方格?！救蝿找蟆烤幹品沁f歸程序，求出馬的行走路線，并按求出的行走路線，將數字1， 2， ， 64 依次填入一個 8* 8 的方陣，輸出之。測試數據：由讀者指定, 可自行指定一個馬的初始位置。實現提示：每次在多個可走位置中選擇一個進

20、行試探，其余未曾試探過的可走位置必須用適當結構妥善管理，以備試探失敗時的“回溯”(悔棋)使用?！緶y試數據】自行設定，注意測試將活區(qū)刪空等特殊情況?！境煽冊u定】1) 基本完成相應功能評定為“及格”或“中等”；2) 對算法有所改進和優(yōu)化評定為“良好”。選題十五：joseph環(huán)【問題描述】編號是1 ， 2，,n的 n 個人按照順時針方向圍坐一圈，每個人只有一個密碼（正整數）。一開始任選一個正整數作為報數上限值m,從第一個仍開始順時針方向自1 開始順序報數，報到m 時停止報數。報m 的人出列，將他的密碼作為新的m 值，從他在順時針方向的下一個人開始重新從1 報數，如此下去，直到所有人全部出列為止。設計

21、一個程序來求出出列順序。【任務要求】利用單向循環(huán)鏈表存儲結構模擬此過程，按照出列的順序輸出各個人的編號。測試數據：m 的初值為20， n=7 ,7 個人的密碼依次為3， 1， 7， 2， 4，7， 4，首先m=6,則正確的輸出是什么？要求：輸入數據：建立輸入處理輸入數據，輸入m 的初值， n ，輸入每個人的密碼，建立單循環(huán)鏈表。輸出形式：建立一個輸出函數，將正確的輸出序列【測試數據】自行設定，注意測試將活區(qū)刪空等特殊情況?！境煽冊u定】1) 基本完成相應功能評定為“及格”或“中等”；2) 對算法有所改進和優(yōu)化評定為“良好”。選題十六：最小生成樹【問題描述】在 n 個城市之間建設網絡，只需保證連通

22、即可，求最經濟的架設方法。對于圖，其生成樹中的邊也帶權，將生成樹各邊的權值總和稱為生成樹的權，并將權值最小的生成樹稱為最小生成樹（Minimun Spanning Tree ），簡稱為MST。有兩種非常典型的算法： Prim 算法和 kruskal 算法。【任務要求】設計程序完成如下功能：對給定的網和起點，用 PRIM 算法和 kruskal 算法的基本思想求解出所有的最小生成樹。存儲結構可自行選擇。【測試數據】自行設定，注意測試將活區(qū)刪空等特殊情況?！境煽冊u定】1) 基本完成其中一個算法相應功能評定為“及格”或“中等”；2) 完成兩個算法并對算法有所改進和優(yōu)化評定為“良好”。選題十七：通訊錄

23、管理【問題描述】該設計采用菜單作為應用程序的主要界面，用控制語句來改變程序執(zhí)行的順序，控制語句是實現結構化程序設計的基礎。該設計的任務是利用一個簡單實用的菜單，通過菜單單項進行選擇，實現和完成通訊錄管理中常用的幾個不同的功能。【任務要求】（ 1）菜單內容1、 通訊錄鏈表的建立2、 通訊者結點的插入3、 通訊者結點的查詢4、 通訊者結點的刪除5、 通訊錄鏈表的輸出0、 退出管理系統(tǒng)請選擇 05：（ 2）設計要求使用 05 來選擇菜單項，其他輸入則不起作用。（ 3）功能函數設計5 個不同功能的算法實現編程題，目的是練習利用鏈表結構來解決實際應用問題的能力，進一步理解和熟悉線形表的鏈式存儲結構。【測

24、試數據】自行設定，注意測試將活區(qū)刪空等特殊情況?！境煽冊u定】1) 基本完成相應功能評定為“及格”或“中等”；2) 對算法有所改進和優(yōu)化評定為“良好”。選題十八：運動會分數統(tǒng)計【問題描述】參加運動會有n 個學校，學校編號為1 n。比賽分成m 個男子工程，和w 個女子工程。工程編號為男子1 m，女子m+1m+w。不同的工程取前五名或前三名積分；取前五名的積分分別為：7、 5 、3 、 2、 1，前三名的積分分別為：5、 3、2 ；哪些取前五名或前三名由學生自己設定。（m<=20,n<=20）【任務要求】功能要求：1).可以輸入各個工程的前三名或前五名的成績；2)能統(tǒng)計各學?？偡?，3)

25、可以按學校編號、學?？偡帧⒛信畧F體總分排序輸出；的動要4).可以按學校編號查詢學校某個工程的情況；可以按工程編號查詢取得前三或前五名學校。規(guī)定：輸入數據形式和范圍：20 以內的整數（如果做得更好可以輸入學校的名稱，運工程的名稱）輸出形式：有中文提示，各學校分數為整形界面要求：有合理的提示，每個功能可以設立菜單，根據提示，可以完成相關的功能求。存儲結構：學生自己根據系統(tǒng)功能要求自己設計，但是要求運動會的相關數據要存儲在數據文件中。（數據文件的數據讀寫方法等相關內容在 c 語言程序設計的書上，請自學解決）請在最后的上交資料中指明你用到的存儲結構；測試數據：要求使用 1、全部合法數據； 2、整體非法

26、數據； 3、局部非法數據。進行程序測試，以保證程序的穩(wěn)定。測試數據及測試結果請在上交的資料中寫明；【測試數據】自行設定，注意測試將活區(qū)刪空等特殊情況?！境煽冊u定】1) 基本完成相應功能評定為“及格”或“中等”；2) 對算法有所改進和優(yōu)化評定為“良好”。選題十九：航班信息的查詢與檢索【問題描述】該設計要求對飛機航班信息進行排序和查找?？砂春桨嗟暮桨嗵?、起點站、到達站、起飛時間以及到達時間等信息進行查詢?！救蝿找蟆繉τ诒驹O計，可采用基數排序法對一組具有結構特點的飛機航班號進行排序，利用二分查找法對排好序的航班記錄按航班號實現快速查找，按其他次關鍵字的查找可采用最簡單的順序查找方法進行，因此他們用得較少。每個航班記錄包括八項，分別是：航班號、起點站、終點站、班期、起飛時間、到達時間、飛機型號以及票價等，假設航班信息表（8 條記錄）航班號起點站終點站班期起飛時間到達時間機型票價CA1544合肥北京1.2.4.510551240733960MU5341上海廣州每日14201615M901280CZ3869重慶深圳2.4.6085510357331010MU3682桂林南京2.3.4.6.720502215M901380HU1836上海北京每日094011207381250CZ3528成都廈門1.3.4.5.715101650CRJ1060MU4594昆明西安1.3.