真誠為您提供優(yōu)質參考資料，若有不當之處，請指正。 數(shù)據結構課程設計選題題目 選題一：迷宮與棧問題 【問題描述】 以一個mXn的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設計一個程序，對任意設定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結論。 【任務要求】 1) 首先實現(xiàn)一個以鏈表作存儲結構的棧類型，然后編寫一個求解迷宮的非遞歸程序。求得的通路以三元組（i，j，d）的形式輸出。其中：（i，j）指示迷宮中的一個坐標，d表示走到下一坐標的方向。如，對于下列數(shù)據的迷宮，輸出一條通路為：（1，1，1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），…。 2) 編寫遞歸形式的算法，求得迷宮中所有可能的通路。 3) 以方陣形式輸出迷宮及其通路。 【測試數(shù)據】 迷宮的測試數(shù)據如下：左上角（0，1）為入口，右下角（8，9）為出口。 選題二：算術表達式與二叉樹 【問題描述】 一個表達式和一棵二叉樹之間，存在著自然的對應關系。寫一個程序，實現(xiàn)基于二叉樹表示的算術表達式的操作。 【任務要求】 假設算術表達式Expression內可以含有變量（a～z）、常量（0～9）和二元運算符（+，-，*，/，^(乘冪)）。實現(xiàn)以下操作： 1) ReadExpre(E)—以字符序列的形式輸入語法正確的前綴表達式并構造表達式E。 2) WriteExpre(E)—用帶括弧的中綴表達式輸出表達式E。 3) Assign(V,c)—實現(xiàn)對變量V的賦值（V=c），變量的初值為0。 4) Value(E)—對算術表達式E求值。 5) CompoundExpr（P，E1，E2）--構造一個新的復合表達式（E1）P（E2） 【測試數(shù)據】 1) 分別輸入0；a；-91；+a*bc；+*5^x2*8x；+++*3^x3*2^x2x6并輸出。 2) 每當輸入一個表達式后，對其中的變量賦值，然后對表達式求值。 選題三：銀行業(yè)務模擬與離散事件模擬 【問題描述】 假設某銀行有4個窗口對外接待客戶，從早晨銀行開門（開門9：00am，關門5：00pm）起不斷有客戶進入銀行。由于每個窗口在某個時刻只能接待一個客戶，因此在客戶人數(shù)眾多時需要在每個窗口前順次排隊，對于剛進入銀行的客戶（建議：客戶進入時間使用隨機函數(shù)產生），如果某個窗口的業(yè)務員正空閑，則可上前辦理業(yè)務；反之，若4個窗口均有窗戶所占，他便會排在人數(shù)最少的隊伍后面。 【任務要求】 1) 編制一個程序以模擬銀行的這種業(yè)務活動并計算一天中客戶在銀行逗留的平均時間。 2) 建議有如下設置： a) 客戶到達時間隨機產生，一天客戶的人數(shù)設定為100人。 b) 銀行業(yè)務員處理時間隨機產生，平均處理時間10分鐘。 3) 將一天的數(shù)據（包括業(yè)務員和客戶）以文件方式輸出。 【測試數(shù)據】 由隨機數(shù)產生器生成 選題四：文學研究助手與模式匹配算法KMP 【問題描述】 文學研究人員需要統(tǒng)計某篇英文小說中某些形容詞的出現(xiàn)次數(shù)和位置。試寫一個實現(xiàn)這一目標的文字統(tǒng)計系統(tǒng) 【任務要求】 1) 英文小說存于一個文本文件中。待統(tǒng)計的詞匯集合要一次輸入完畢，即統(tǒng)計工作必須在程序的一次運行之后就全部完成。程序的輸出結果是每個詞的出現(xiàn)次數(shù)和出現(xiàn)位置所在的行的行號，格式自行設計。待統(tǒng)計的“單詞”在文本串中不跨行出現(xiàn)，它或者從行首開始，或者前置以一個空格符。 2) 模式匹配要基于KMP算法。 3) 推廣到更一般的模式集匹配問題，并設待查模式串可以跨行（提示：定義操作GetAChar）。 【測試數(shù)據】 1) 文本文件為testword.c 2) 待統(tǒng)計的詞集：if、else、for、while、return、void、int、char、typedef、struct 選題五：隴橋校園導游咨詢與最短路徑 【問題描述】 1) 從隴橋校園的平面圖中選取有代表性景點（7-10個），抽象成一個無向帶權圖。以圖中頂點表示景點，邊上的權值表示兩地之間距離。 2) 本程序的目的是為用戶提供路徑咨詢。根據用戶指定的始點和終點輸出相應路徑，或者根據用戶指定的景點輸出景點的信息。 【任務要求】 1) 從隴橋校園的平面圖中選取有代表性景點（7-10個），抽象成一個無向帶權圖。以圖中頂點表示校內各景點，存放景點名稱、代號、簡介等信息；以邊表示路徑，存放路徑長度等信息。 2) 為來訪客人提供圖中任意景點相關信息的查詢。 3) 為來訪客人提供圖中任意景點的問路查詢，即查詢任意兩個景點之間的一條最短的簡單路徑。 4) 區(qū)分汽車線路與步行線路。 【測試數(shù)據】 隴橋校園校園導游圖（距離可估計）。 選題六：哈夫曼(Huffman)編/譯碼器 【問題描述】 利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據預先編碼，在接收端將傳來的數(shù)據進行譯碼（復原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼碼的編/譯碼系統(tǒng)。 【任務要求】 一個完整的系統(tǒng)應具有以下功能： 1) I：初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權值，建立哈夫曼樹，并將它存于文件hfmTree中。 2) E：編碼（Encoding）。利用以建好的哈夫曼樹（如不在內存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進行編碼，然后將結果存入文件CodeFile中。 3) D：譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進行譯碼，結果存入文件TextFile中。 4) P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代碼。同時將此字符形式的編碼文件寫入文件CodePrin中。 5) T：印哈夫曼樹（Tree Printing）。將已在內存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中。 【測試數(shù)據】 1) 利用教科書中的數(shù)據調試程序。 2) 用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據建立哈夫曼樹，并實現(xiàn)以下報文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE”。 字符 空格 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 　 選題七：內部排序算法比較 【問題描述】 在教科書中，各種內部排序算法的時間復雜度分析結果只給出了算法執(zhí)行時間的階，或大概執(zhí)行時間。試通過隨機數(shù)據比較各種算法的關鍵字比較次數(shù)和關鍵字移動次數(shù)，以取得直觀感受。 【任務要求】 1) 對以下4種常用的內部排序算法進行比較：冒泡排序、直接插入排序、選擇排序、快速排序。 2) 待排序表的表長不小于100；其中的數(shù)據要用偽隨機數(shù)程序產生；至少要用5組不同的輸入數(shù)據作比較；比較的指標為有關鍵字參加的比較次數(shù)和關鍵字的移動次數(shù)（關鍵字交換計為3次移動）。 3) 最后要對結果作出簡單分析，包括對各組數(shù)據得出結果波動大小的解釋。 選題八：文章編輯 【問題描述】 輸入一頁文字，程序可以統(tǒng)計出文字、數(shù)字、空格的個數(shù)。靜態(tài)存儲一頁文章，每行最多不超過80個字符，共20行。 【任務要求】 1) 分別統(tǒng)計出其中英文字母數(shù)和空格數(shù)及整篇文章總字數(shù)。 2) 統(tǒng)計某一字符串在文章中出現(xiàn)的次數(shù)，并輸出該次數(shù)。 3) 刪除某一子串，并將后面的字符前移。 【測試數(shù)據】 輸入數(shù)據的形式和范圍：可以輸入大寫、小寫的英文字母、任何數(shù)字及標點符號。 選題九：停車場管理系統(tǒng) 【問題描述】 1) 以棧模擬停車場,以隊列模擬車場外的便道,按照從終端讀入的輸入數(shù)據序列進行模擬管理。 2) 每一組輸入數(shù)據包括三個數(shù)據項：汽車“到達”或“離去”信息、汽車牌照號碼以及到達或離去的時刻。 3) 對每一組輸入數(shù)據進行操作后的輸出信息為：若是車輛到達,則輸出汽車在停車場或便道上的停車位置；若是車輛離去,則輸出汽車在停車場內停留的時間和應交納的費用(在便道上停留的時間不收費，功能可自己添加)。 【任務要求】 1) 掌握棧和隊列的建立及基本操作。 2) 深入了解棧和隊列的特性,以便在解決實際問題中靈活運用它們。 選題十：集合的交、并、差運算 【問題描述】 編制一個能演示執(zhí)行集合的交、并和差運算的程序。 【任務要求】 1) 集合元素用小寫英文字母，執(zhí)行各種操作應以對話方式執(zhí)行。 2) 算法要點：利用單鏈表表示集合；理解好三種運算的含義。 選題十一：學生成績管理系統(tǒng)　 【問題描述】 本例對學生的成績管理做一個簡單的模擬，用菜單選擇方式完成下列功能： 登記學生成績；查詢學生成績；插入學生成績；刪除學生成績。 【任務要求】 1) 算法輸入：操作要求，學生信息 2) 算法輸出：操作結果 3) 算法要點：把問題看成是對線性表的操作。將學生成績組織成順序表，則登記學生成績即是建立順序表操作；查詢學生成績、插入學生成績、刪除學生成績即是在順序表中進行查找、插入和刪除操作。 【測試數(shù)據】 自行設定(測試數(shù)據不少于5人)。 選題十二：馬踏棋盤 【問題描述】 將馬隨機放在國際象棋的8* 8棋盤Bord[8Ⅱ8]的某個方格中，馬按走棋規(guī)則進行移動。要求每個方格上只進入一次，走遍棋盤上全部64個方格。 【任務要求】 1) 編制非遞歸程序，求出馬的行走路線 ，并按求出的行走路線，將數(shù)字1，2，…，64依次填入一個8* 8的方陣，輸出之。 2) 測試數(shù)據：由讀者指定,可自行指定一個馬的初始位置。 3) 實現(xiàn)提示：每次在多個可走位置中選擇一個進行試探，其余未曾試探過的可走位置必須用適當結構妥善管理，以備試探失敗時的“回溯”(悔棋)使用。 選題十三： joseph環(huán) 【問題描述】 編號是1，2，……,n的n個人按照順時針方向圍坐一圈，每個人只有一個密碼（正整數(shù)）。一開始任選一個正整數(shù)作為報數(shù)上限值m,從第一個仍開始順時針方向自1開始順序報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下一個人開始重新從1報數(shù)，如此下去，直到所有人全部出列為止。設計一個程序來求出出列順序。 【任務要求】 1) 利用單向循環(huán)鏈表存儲結構模擬此過程，按照出列的順序輸出各個人的編號。 2) 測試數(shù)據：　　m的初值為20，n=7 ,7個人的密碼依次為3，1，7，2，4，7，4，首先m=6,則正確的輸出是什么？ 3) 要求： 輸入數(shù)據：建立輸入處理輸入數(shù)據，輸入m的初值，n ，輸入每個人的密碼，建立單循環(huán)鏈表。 輸出形式：建立一個輸出函數(shù)，將正確的輸出序列 【測試數(shù)據】 自行設定。 選題十四： 最小生成樹 【問題描述】 在n個城市之間建設網絡，只需保證連通即可，求最經濟的架設方法。 對于圖，其生成樹中的邊也帶權，將生成樹各邊的權值總和稱為生成樹的權，并將權值最小的生成樹稱為最小生成樹（Minimun Spanning Tree），簡稱為MST。有兩種非常典型的算法：Prim算法和kruskal算法。 【任務要求】 設計程序完成如下功能：對給定的網和起點，用PRIM算法和kruskal算法的基本思想求解出所有的最小生成樹。存儲結構可自行選擇。 【測試數(shù)據】 自行設定(城市數(shù)不少于15個，權值參考距離)。 選題十五：通訊錄管理系統(tǒng) 【問題描述】 該設計采用菜單作為應用程序的主要界面，用控制語句來改變程序執(zhí)行的順序，控制語句是實現(xiàn)結構化程序設計的基礎。該設計的任務是利用一個簡單實用的菜單，通過菜單單項進行選擇，實現(xiàn)和完成通訊錄管理中常用的幾個不同的功能。 【任務要求】 （1） 菜單內容 1、 通訊錄鏈表的建立 2、 通訊者結點的插入 3、 通訊者結點的查詢 4、 通訊者結點的刪除 5、 通訊錄鏈表的輸出 0、 退出管理系統(tǒng) 請選擇0~5： (2 ) 設計要求 1、使用0~5來選擇菜單項，其他輸入則不起作用。 2、功能函數(shù)設計 3、5個不同功能的算法實現(xiàn)編程題，目的是練習利用鏈表結構來解決實際應用問題的能力，進一步理解和熟悉線形表的鏈式存儲結構。 【測試數(shù)據】 自行設定(測試數(shù)據不少于10人，通訊錄項目不少于3個)。 選題十六：運動會分數(shù)統(tǒng)計系統(tǒng) 【問題描述】 參加運動會有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)．能統(tǒng)計各學?？偡?，　　 3)．可以按學校編號、學?？偡帧⒛信畧F體總分排序輸出；　　 4).可以按學校編號查詢學校某個項目的情況；可以按項目編號查詢取得前三或前五名的學校。 　　 規(guī)定：輸入數(shù)據形式和范圍：20以內的整數(shù)（如果做得更好可以輸入學校的名稱，運動項目的名稱）　　 輸出形式：有中文提示，各學校分數(shù)為整形　　 界面要求：有合理的提示，每個功能可以設立菜單，根據提示，可以完成相關的功能要求?！　? 存儲結構：學生自己根據系統(tǒng)功能要求自己設計，但是要求運動會的相關數(shù)據要存儲在數(shù)據文件中。（數(shù)據文件的數(shù)據讀寫方法等相關內容在c語言程序設計的書上，請自學解決）請在最后的上交資料中指明你用到的存儲結構； 測試數(shù)據：要求使用1、全部合法數(shù)據；2、整體非法數(shù)據；3、局部非法數(shù)據。進行程序測試，以保證程序的穩(wěn)定。測試數(shù)據及測試結果請在上交的資料中寫明； 【測試數(shù)據】 自行設定(男女運動員分別不少于5人，學校不少于10個)。 選題十七：航班信息的查詢系統(tǒng) 【問題描述】 該設計要求對飛機航班信息進行排序和查找。可按航班的航班號、起點站、到達站、起飛時間以及到達時間等信息進行查詢。 【任務要求】 對于本設計，可采用基數(shù)排序法對一組具有結構特點的飛機航班號進行排序，利用二分查找法對排好序的航班記錄按航班號實現(xiàn)快速查找，按其他次關鍵字的查找可采用最簡單的順序查找方法進行，因此他們用得較少。 每個航班記錄包括八項，分別是：航班號、起點站、終點站、班期、起飛時間、到達時間、飛機型號以及票價等，假設航班信息表（8條記錄） 航班號 起點站 終點站 班期 起飛時間 到達時間 機型 票價 CA1544 合肥 北京 1.2.4.5 1055 1240 733 960 MU5341 上海 廣州 每日 1420 1615 M90 1280 CZ3869 重慶 深圳 2.4.6 0855 1035 733 1010 MU3682 桂林 南京 2.3.4.6.7 2050 2215 M90 1380 HU1836 上海 北京 每日 0940 1120 738 1250 CZ3528 成都 廈門 1.3.4.5.7 1510 1650 CRJ 1060 MU4594 昆明 西安 1.3.5.6 1015 1140 328 1160 SC7425 青島 ?？? 1.3.6 1920 2120 DH4 1630 其中航班號一項的格式為： K0 K1 K2 K3 K4 K5 C Z 3 8 6 9 其中K0和K1的輸入值是航空公司的別稱，用兩個大寫字母標示，后4位為航班號，這種航班號關鍵字可分成兩段，即字母和數(shù)字。其余七項輸入內容因為不涉及本設計的核心，因此除了票價為數(shù)值型外，均定義為字符串即可。 【測試數(shù)據】 自行設定(航班號不少于20個)。 選題十八：哈希表應用 【問題描述】 利用哈希表進行存儲。 【任務要求】 1) 任務要求：針對一組數(shù)據進行初始化哈希表，可以進行顯示哈希表，查找元素，插入元素，刪除元素，退出程序操作。 2) 設計思想：哈希函數(shù)用除留余數(shù)法構造，用線性探測再散列處理沖突。 3) 設計目的：實現(xiàn)哈希表的綜合操作 4) 簡體中文控制臺界面：用戶可以進行創(chuàng)建哈希表，顯示哈希表，查找元素，插入元素，刪除元素。 5) 顯示元素：顯示已經創(chuàng)建的哈希表。 6) 查找元素：查找哈希表中的元素，分為查找成功和查找不成功。 7) 插入元素：在哈希表中，插入一個元素，分為插入成功和失敗。 8) 刪除元素：在已有的數(shù)據中，刪除一個元素。 9) 退出系統(tǒng)：退出程序。 【測試數(shù)據】 自行設定(測試數(shù)據不少于3組，每組數(shù)據不少于12個)。 選題十九：拓撲排序 【問題描述】 拓撲排序可判斷AOV網絡中是否存在回路，使的所有活動可排成一個線性序列，使用每個活動的所有前驅活動都排在該活動的前面。 關鍵路徑的工期決定了整個項目的工期。任何關鍵路徑上的終端元素的延遲將直接影響項目的預期完成時間（例如在關鍵路徑上沒有浮動時間）。 【任務要求】 構建AOV網絡，并輸出其拓撲序列結果，輸出該圖的關鍵路徑和關鍵活動，存儲結構自行選擇。 【測試數(shù)據】 自行設定(結點數(shù)不少于10個)。 選題二十：自擬題目 【要求】 1. 學生原則上可以結合個人愛好自選課題。 2. 自選課題必須覆蓋數(shù)據結構的主要內容，有一定的深度與難度，有一定的算法復雜性，能明確體現(xiàn)數(shù)據抽象與組織、算法設計與性能分析以及編碼實現(xiàn)等過程。 3. 學生自選課題需提前報課程設計指導教師批準方可生效。 10 / 10