數(shù)據(jù)結(jié)構(gòu)課程設(shè)計學(xué)生21個題目

1/1數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-學(xué)生-21個題目選題一：迷宮與棧問題

【問題描述】

以一個mXn的長方陣表示迷宮，0和1分別表示迷宮中的通路和障礙。設(shè)計一個程序，對任意設(shè)定的迷宮，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。

【任務(wù)要求】

1)首先實現(xiàn)一個以鏈表作存儲結(jié)構(gòu)的棧類型，然后編寫一個求解迷宮的非遞歸程序。

求得的通路以三元組（i，j，d）的形式輸出。其中：（i，j）指示迷宮中的一個坐標(biāo)，

d表示走到下一坐標(biāo)的方向。如，對于下列數(shù)據(jù)的迷宮，輸出一條通路為：（1，1，

1），（1，2，2），（2，2，2），（3，2，3），（3，1，2），…。

2)編寫遞歸形式的算法，求得迷宮中全部可能的通路。

3)以方陣形式輸出迷宮及其通路。

【測試數(shù)據(jù)】

迷宮的測試數(shù)據(jù)如下：左上角（0，1）為入口，右下角（8，9）為出口。

出口

出口

選題二：算術(shù)表達式與二叉樹

【問題描述】

一個表達式和一棵二叉樹之間，存在著自然的對應(yīng)關(guān)系。寫一個程序，實現(xiàn)基于二叉樹表示的算術(shù)表達式的操作。

【任務(wù)要求】

假設(shè)算術(shù)表達式Expression內(nèi)可以含有變量（a～z）、常量（0～9）和二元運算符（+，-，*，/，^(乘冪)）。實現(xiàn)以下操作：

1)ReadExpre(E)—以字符序列的形式輸入語法正確的前綴表達式并構(gòu)造表達式E。

2)WriteExpre(E)—用帶括弧的中綴表達式輸出表達式E。

3)Assign(V,c)—實現(xiàn)對變量V的賦值（V=c），變量的初值為0。

4)Value(E)—對算術(shù)表達式E求值。

5)CompoundExpr（P，E1，E2）--構(gòu)造一個新的復(fù)合表達式（E1）P（E2）

【測試數(shù)據(jù)】

1)分別輸入0；a；-91；+a*bc；+*5^x2*8x；+++*3^x3*2^x2x6并輸出。

2)每當(dāng)輸入一個表達式后，對其中的變量賦值，然后對表達式求值。

選題三：銀行業(yè)務(wù)模擬與離散大事模擬

【問題描述】

假設(shè)某銀行有4個窗口對外接待客戶，從早晨銀行開門（開門9：00am，關(guān)門5：00pm）起不斷有客戶進入銀行。由于每個窗口在某個時刻只能接待一個客戶，因此在客戶人數(shù)眾多時需要在每個窗口前順次排隊，對于剛進入銀行的客戶（建議：客戶進入時間使用隨機函數(shù)產(chǎn)生），假如某個窗口的業(yè)務(wù)員正空閑，則可上前辦理業(yè)務(wù)；反之，若4個窗口均有窗戶所占，他便會排在人數(shù)最少的隊伍后面。

【任務(wù)要求】

1)編制一個程序以模擬銀行的這種業(yè)務(wù)活動并計算一天中客戶在銀行逗留的平均時

間。

2)建議有如下設(shè)置：

a)客戶到達時間隨機產(chǎn)生，一天客戶的人數(shù)設(shè)定為100人。

b)銀行業(yè)務(wù)員處理時間隨機產(chǎn)生，平均處理時間10分鐘。

3)將一天的數(shù)據(jù)（包括業(yè)務(wù)員和客戶）以文件方式輸出。

【測試數(shù)據(jù)】

由隨機數(shù)產(chǎn)生器生成

選題四：文學(xué)討論助手與模式匹配算法KMP

【問題描述】

文學(xué)討論人員需要統(tǒng)計某篇英文小說中某些形容詞的消失次數(shù)和位置。試寫一個實現(xiàn)這一目標(biāo)的文字統(tǒng)計系統(tǒng)

【任務(wù)要求】

1)英文小說存于一個文本文件中。待統(tǒng)計的詞匯合合要一次輸入完畢，即統(tǒng)計工作必

須在程序的一次運行之后就全部完成。程序的輸出結(jié)果是每個詞的消失次數(shù)和消失

位置所在的行的行號，格式自行設(shè)計。待統(tǒng)計的“單詞”在文本串中不跨行消失，它或者從行首開頭，或者前置以一個空格符。

2)模式匹配要基于KMP算法。

3)推廣到更一般的模式集匹配問題，并設(shè)待查模式串可以跨行（提示：定義操作

GetAChar）。

【測試數(shù)據(jù)】

1)文本文件為testword.c

2)待統(tǒng)計的詞集：if、else、for、while、return、void、int、char、typedef、struct

選題五：北理珠校內(nèi)導(dǎo)游詢問與最短路徑

【問題描述】

1)從北京理工高校珠海學(xué)院的平面圖中選取有代表性景點（10-15個），抽象成一個

無向帶權(quán)圖。以圖中頂點表示景點，邊上的權(quán)值表示兩地之間距離。

2)本程序的目的是為用戶供應(yīng)路徑詢問。依據(jù)用戶指定的始點和終點輸出相應(yīng)路徑，

或者依據(jù)用戶指定的景點輸出景點的信息。

【任務(wù)要求】

1)從北京理工高校珠海學(xué)院的平面圖中選取有代表性景點（10-15個），抽象成一個

無向帶權(quán)圖。以圖中頂點表示校內(nèi)各景點，存放景點名稱、、簡介等信息；以

邊表示路徑，存放路徑長度等信息。

2)為來訪客人供應(yīng)圖中任意景點相關(guān)信息的查詢。

3)為來訪客人供應(yīng)圖中任意景點的問路查詢，即查詢?nèi)我鈨蓚€景點之間的一條最短的

簡潔路徑。

4)區(qū)分汽車線路與步行線路。

【測試數(shù)據(jù)】

北理珠校內(nèi)導(dǎo)游圖（距離可估量）。

選題六：B-樹與B+樹及其操作

【問題描述】

學(xué)習(xí)并討論B-樹與B+樹，并編寫演示它們操作的程序。

【任務(wù)要求】

1)B-樹構(gòu)建、查找、插入和刪除操作程序。

2)B+樹構(gòu)建、查找、插入和刪除操作程序。

【測試數(shù)據(jù)】

選題七：哈夫曼(Huffman)編/譯碼器

【問題描述】

利用哈夫曼編碼進行通信可以大大提高信道利用率，縮短信息傳輸時間，降低傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼碼的編/譯碼系統(tǒng)。

【任務(wù)要求】

一個完整的系統(tǒng)應(yīng)具有以下功能：

1)I：初始化（Initialization）。從終端讀入字符集大小n，以及n個字符和n個權(quán)值，

建立哈夫曼樹，并將它存于文件hfmTree中。

2)E：編碼（Encoding）。利用以建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmTree中

讀入），對文件ToBeTran中的正文進行編碼，然后將結(jié)果存入文件CodeFile中。

3)D：譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進行譯碼，

結(jié)果存入文件TextFile中。

4)P：印代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個代

碼。同時將此字符形式的編碼文件寫入文件CodePrin中。

5)T：印哈夫曼樹（TreePrinting）。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹

入表形式）顯示在終端上，同時將此字符形式的哈夫曼樹寫入文件TreePrint中?！緶y試數(shù)據(jù)】

1)利用教科書例6-2（嚴(yán)蔚敏《數(shù)據(jù)結(jié)構(gòu)》P148）中的數(shù)據(jù)調(diào)試程序。

2)用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹，并實現(xiàn)以下報文的編碼

選題八：內(nèi)部排序算法比較

【問題描述】

在教科書中，各種內(nèi)部排序算法的時間簡單度分析結(jié)果只給出了算法執(zhí)行時間的階，或也許執(zhí)行時間。試通過隨機數(shù)據(jù)比較各種算法的關(guān)鍵字比較次數(shù)和關(guān)鍵字移動次數(shù)，以取得直觀感受。

【任務(wù)要求】

1)對以下7種常用的內(nèi)部排序算法進行比較：冒泡排序、直接插入排序、簡潔選擇排

序、希爾排序、堆排序、歸并排序、快速排序。

2)待排序表的表長不小于100；其中的數(shù)據(jù)要用偽隨機數(shù)程序產(chǎn)生；至少要用5組不

同的輸入數(shù)據(jù)作比較；比較的指標(biāo)為有關(guān)鍵字參與的比較次數(shù)和關(guān)鍵字的移動次數(shù)

（關(guān)鍵字交換計為3次移動）。

3)最終要對結(jié)果作出簡潔分析，包括對各組數(shù)據(jù)得出結(jié)果波動大小的解釋。

【測試數(shù)據(jù)】

由隨機數(shù)產(chǎn)生器生成

選題九：簡潔行編輯程序

【問題描述】

文本編輯器程序是利用計算機進行文字加工的基本軟件工具，實現(xiàn)對文本文件的插入、刪除等修改操作。限制這些操作以行為單位進行的編輯程序稱為行編輯程序。

被編輯的文本文件可能很大，全部讀入編輯程序的數(shù)據(jù)空間（內(nèi)存）的作法既不經(jīng)濟，也不總能實現(xiàn)。一種解決方法是逐段地編輯。任何時刻只把待編輯文件的一段放在內(nèi)存，利為活區(qū)。試根據(jù)這種方法實現(xiàn)一個簡潔的行編輯程序。設(shè)文件每行不超過320個字符，很少超過80個字符。

【任務(wù)要求】

實現(xiàn)以下4條基本編輯命令：

1)行插入：格式：i

●將插入活區(qū)中第行之后。

2)行刪除。格式：d

●刪除活區(qū)中第(到第行)。例如“d10”和“d1014”

3)活區(qū)切換。格式：n

●將活區(qū)寫入輸出文件，并從輸入文件中讀入下一段，作為新的活區(qū)。

4)活區(qū)顯示。模式：p

●逐頁地（每頁20行）顯示活區(qū)內(nèi)容，每顯示一頁之后請用戶打算是連續(xù)顯示

以后各頁（假如存在）。印出的每一行要前置行號和一個空格符，行號固定占

4位，增量為1。

各條命令中的行號均須在活區(qū)中各行行號范圍之內(nèi)，只有插入命令的行號可以等于活區(qū)第一行行號減1，表示插入當(dāng)前屏幕中第一行之前，否則命令參數(shù)非法。

【測試數(shù)據(jù)】

自行設(shè)定，留意測試將活區(qū)刪空等特別狀況。

選題十：一元多項式計算

【問題描述】

1.能夠根據(jù)指數(shù)降序排列建立并輸出多項式；

2.能夠完成兩個多項式的相加、相減，并將結(jié)果輸入；

【任務(wù)要求】

1.存儲結(jié)構(gòu);

2.多項式相加的基本過程的算法（可以使用程序流程圖）

3.可以提出算法的改進方法；

【測試數(shù)據(jù)】

自行設(shè)定，留意邊界等特別狀況。

選題十一：集合的交、并、差運算

【問題描述】

編制一個能演示執(zhí)行集合的交、并和差運算的程序。

【任務(wù)要求】

1)集合元素用小寫英文字母，執(zhí)行各種操作應(yīng)以對話方式執(zhí)行。

2)算法要點：利用單鏈表表示集合；理解好三種運算的含

【測試數(shù)據(jù)】

自行設(shè)定，留意邊界等特別狀況。

選題十二：動態(tài)查找表

【問題描述】

利用二叉排序樹完成動態(tài)查找表的建立、指定關(guān)鍵字的查找、插入與刪除指定關(guān)鍵字結(jié)點。

【任務(wù)要求】

算法輸入：指定一組數(shù)據(jù)。

算法輸出：顯示二叉排序樹的中序遍歷結(jié)果、查找勝利與否的信息、插入和刪除后的中序遍歷結(jié)果(排序結(jié)果)。

算法要點：二叉排序樹建立方法、動態(tài)查找方法,對樹進行中序遍歷。

【測試數(shù)據(jù)】

自行設(shè)定，留意邊界等特別狀況。

選題十三：同學(xué)成果管理

【問題描述】

本例對同學(xué)的成果管理做一個簡潔的模擬，用菜單選擇方式完成下列功能：登記

同學(xué)成果；查詢同學(xué)成果；插入同學(xué)成果；刪除同學(xué)成果。

【任務(wù)要求】

算法輸入：操作要求，同學(xué)信息

算法輸出：操作結(jié)果

算法要點：把問題看成是對線性表的操作。將同學(xué)成果組織成挨次表，則登記同學(xué)成果即是建立挨次表操作；查詢同學(xué)成果、插入同學(xué)成果、刪除同學(xué)成果即是在挨次表中進行查找、插入和刪除操作。

【測試數(shù)據(jù)】

自行設(shè)定，留意邊界等特別狀況。

選題十四：馬踏棋盤

【問題描述】

將馬隨機放在國際象棋的8*8棋盤Bord[8Ⅱ8]的某個方格中，馬按走棋規(guī)章進行移動。要求每個方格上只進入一次，走遍棋盤上全部64個方格。

【任務(wù)要求】

編制非遞歸程序，求出馬的行走路線，并按求出的行走路線，將數(shù)字1，2，…，64依次填入一個8*8的方陣，輸出之。

測試數(shù)據(jù)：由讀者指定,可自行指定一個馬的初始位置。

實現(xiàn)提示：每次在多個可走位置中選擇一個進行摸索，其余未曾摸索過的可走位置必需用適當(dāng)結(jié)構(gòu)妥當(dāng)管理，以備摸索失敗時的“回溯”(悔棋)使用。

【測試數(shù)據(jù)】

自行設(shè)定，留意邊界等特別狀況。

選題十五：joseph環(huán)

【問題描述】

編號是1，2，……,n的n個人根據(jù)順時針方向圍坐一圈，每個人只有一個密碼（正整數(shù)）。一開頭任選一個正整數(shù)作為報數(shù)上限值m,從第一個仍開頭順時針方向自1開頭挨次報數(shù)，報到m時停止報數(shù)。報m的人出列，將他的密碼作為新的m值，從他在順時針方向的下一個人開頭重新從1報數(shù)，如此下去，直到全部人全部出列為止。設(shè)計一個程序來求出出列挨次。

【任務(wù)要求】

利用單向循環(huán)鏈表存儲結(jié)構(gòu)模擬此過程，根據(jù)出列的挨次輸出各個人的編號。

測試數(shù)據(jù)：m的初值為20，n=7,7個人的密碼依次為3，1，7，2，4，7，4，首先m=6,則正確的輸出是什么？

要求：

輸入數(shù)據(jù)：建立輸入處理輸入數(shù)據(jù)，輸入m的初值，n，輸入每個人的密碼，建立單循環(huán)鏈表。

輸出形式：建立一個輸出函數(shù)，將正確的輸出序列

【測試數(shù)據(jù)】

自行設(shè)定，留意邊界等特別狀況。

選題十六：最小生成樹

【問題描述】

在n個城市之間建設(shè)網(wǎng)絡(luò)，只需保證連通即可，求最經(jīng)濟的架設(shè)方法。

對于圖，其生成樹中的邊也帶權(quán)，將生成樹各邊的權(quán)值總和稱為生成樹的權(quán)，并將權(quán)值最小的生成樹稱為最小生成樹（MinimunSpanningTree），簡稱為MST。有兩種特別典型的算法：Prim算法和kruskal算法。

【任務(wù)要求】

設(shè)計程序完成如下功能：對給定的網(wǎng)和起點，用PRIM算法和kruskal算法的基本思想求解出全部的最小生成樹。存儲結(jié)構(gòu)可自行選擇。

【測試數(shù)據(jù)】

自行設(shè)定，留意邊界等特別狀況。

選題十七：通訊錄管理

【問題描述】

該設(shè)計采納菜單作為應(yīng)用程序的主要界面，用掌握語句來轉(zhuǎn)變程序執(zhí)行的挨次，掌握語句是實現(xiàn)結(jié)構(gòu)化程序設(shè)計的基礎(chǔ)。該設(shè)計的任務(wù)是利用一個簡潔有用的菜單，通過菜單單項進行選擇，實現(xiàn)和完成通訊錄管理中常用的幾個不同的功能。

【任務(wù)要求】

（1）菜單內(nèi)容

1、通訊錄鏈表的建立

2、通訊者結(jié)點的插入

3、通訊者結(jié)點的查詢

4、通訊者結(jié)點的刪除

5、通訊錄鏈表的輸出

0、退出管理系統(tǒng)

請選擇0~5：

（2）設(shè)計要求

使用0~5來選擇菜單項，其他輸入則不起作用。

（3）功能函數(shù)設(shè)計

5個不同功能的算法實現(xiàn)編程題，目的是練習(xí)利用鏈表結(jié)構(gòu)來解決實際應(yīng)用問題的力量，進一步理解和熟識線形表的鏈?zhǔn)酱鎯Y(jié)構(gòu)。

【測試數(shù)據(jù)】

自行設(shè)定，留意邊界等特別狀況。

選題十八：運動會分?jǐn)?shù)統(tǒng)計

【問題描述】

參與運動會有n個學(xué)校，學(xué)校編號為1……n。競賽分成m個男子項目，和w個女子項目。項目編號為男子1……m，女子m+1……m+w。不同的項目取前五名或前三名積分；取前五名的積分分別為：7、5、3、2、1，前三名的積分分別為：5、3、2；哪些取前五名或前三名由同學(xué)自己設(shè)定。（m<=20,n<=20）

【任務(wù)要求】

功能要求：1).可以輸入各個項目的前三名或前五名的成果；

2)．能統(tǒng)計各學(xué)?？偡?，

3)．可以按學(xué)校編號、學(xué)?？偡帧⒛信畧F體總分排序輸出；

4).可以按學(xué)校編號查詢學(xué)校某個項目的狀況；可以按項目編號查詢?nèi)〉们叭蚯拔迕膶W(xué)校。

規(guī)定：輸入數(shù)據(jù)形式和范圍：20以內(nèi)的整數(shù)（假如做得更好可以輸入學(xué)校的名稱，運動項目的名稱）

輸出形式：有中文提示，各學(xué)校分?jǐn)?shù)為整形

界面要求：有合理的提示，每個功能可以設(shè)立菜單，依據(jù)提示，可以完成相關(guān)的功能要求。

存儲結(jié)構(gòu)：同學(xué)自己依據(jù)系統(tǒng)功能要求自己設(shè)計，但是要求運動會的相關(guān)數(shù)據(jù)要存儲在數(shù)據(jù)文件中。（數(shù)據(jù)文件的數(shù)據(jù)讀寫方法等相關(guān)內(nèi)容在c語言程序設(shè)計的書上，請自學(xué)解決）請在最終的上交資料中指明你用到的存儲結(jié)構(gòu)；

測試數(shù)據(jù)：要求使用1、全部合法數(shù)據(jù)；2、整體非法數(shù)據(jù)；3、局部非法數(shù)據(jù)。進行程序測試，以保證程序的穩(wěn)定。測試數(shù)據(jù)及測試結(jié)果請在上交的資料中寫明；

【測試數(shù)據(jù)】

自行設(shè)定，留意邊界等特別狀況。

選題十九：航班信息的查詢與檢索

【問題描述】

該設(shè)計要求對飛機航班信息進行排序和查找?？砂春桨嗟暮桨嗵?、起點站、到達站、起飛時間以及到達時間等信息進行查詢。

【任務(wù)要求】

對于本設(shè)計，可采納基數(shù)排序法對一組具有結(jié)構(gòu)特點的飛機航班號進行排序，利用二分查找法對排好序的航班記錄按航班號實現(xiàn)快速查找，按其他次關(guān)鍵字的查找可采納最簡潔的挨次查找方法進行，因此他們用得較少。

每個航班記錄包括八項，分別是：航班號、起點站、終點站、班期、起飛時間、到達時間、飛機型號以及票價等