數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用

《數(shù)據(jù)結(jié)構(gòu)與算法應(yīng)用》上機試驗題目

題目1（線性表）

［問題描述］

采用帶頭結(jié)點的單鏈表實現(xiàn)兩個集合的并、交、差運算。（難易程度：低）

［試驗?zāi)康模?/p>

1、把握線性表的鏈表存儲結(jié)構(gòu)。

2、把握在單鏈表上基本操作的實現(xiàn)。

3、在把握單鏈表的基本操作上進行綜合題的實現(xiàn)。

［試驗內(nèi)容及要求］

1、要求用帶頭結(jié)點的單鏈表存儲兩個集合中的元素和最終的結(jié)果。

2、集合的元素限定為十進制數(shù)，程序應(yīng)對消失重復(fù)的數(shù)據(jù)進行過濾，即使得鏈

表中沒有重復(fù)數(shù)據(jù)。

3、顯示兩個集合的內(nèi)容及其并集、交集和差集的內(nèi)容。

4、要求不轉(zhuǎn)變原來的集合，并集、交集和差集分別此外存放。

［測試數(shù)據(jù)］

1、setl={3,8,5,8,11},set2={22,6,8,3,15,11,20）

setlUset2=

setlAset2=

setl-set2=

2、其中一個集合為空集

3、兩個集合都是空集

4、創(chuàng)建集合時有重復(fù)數(shù)據(jù)的狀況

題目2（棧、串）

［問題描述］

采用棧實現(xiàn)算術(shù)表達式的求值?？梢院啙嵰恍?，假設(shè)表達式中含有一位整數(shù),

以及+、-、*、/、（、）。但不受此限制。（難易程度：中）

［試驗?zāi)康模?/p>

1、把握棧的應(yīng)用。

2、把握算符優(yōu)先表達式求值的算法。

3、把握字符串處理和數(shù)值的轉(zhuǎn)換。

［試驗內(nèi)容及要求］

1、表達式以字符串形式輸入，并以'#‘開頭和結(jié)束（'#'也作為算法來處理）。

如輸入:#6+3*（9-7）-8/2#

2、能夠有效判別表達式的輸入格式是否有誤（如缺失操作數(shù)、非法算符、括

號不匹配等錯誤），若輸入格式錯誤，輸出錯誤提示。

［測試數(shù)據(jù)］

1、#6+3*（9-7）-8/2#

2、#（8-2）/（3-1）*（9-6）#

3、#5+a*（8-4）/2#

4、#5+（7-3）*6#

題目3（二叉排序樹）

［問題描述］

采用二叉查找樹（又稱為二叉排序樹、二叉搜尋樹）實現(xiàn)對輸入的英文單詞進

行搜尋，同時可給出單詞消失的次數(shù)。（難易程度：高）

［試驗?zāi)康模?/p>

1、把握二叉鏈表的存儲結(jié)構(gòu)。

2、把握搜尋和過濾的方法。

3、把握二叉排序樹的插入和刪除操作。

［試驗內(nèi)容及要求］

1、構(gòu)造二叉查找樹

（1）從文本文件中讀入文本內(nèi)容，能夠分別出單詞，過濾掉阿拉伯?dāng)?shù)字和標(biāo)點

符號，并將英文字母的大寫形式全部轉(zhuǎn)換成小寫形式。

（2）依據(jù)英文字母表的挨次構(gòu)造英文單詞的二叉查找樹、當(dāng)兩個英文單詞的首

字母相同時，按其次個字母進行排序，依次類推。

（3）當(dāng)待插入的單詞已在二叉查找樹中，則將該單詞的消失次數(shù)增1。

2、遍歷二叉查找樹

（1）搜尋：輸入一個待檢索單詞，在二叉查找樹中進行查找，假如能找到該

單詞，則輸出該單詞及其消失次數(shù)；

（2）實現(xiàn)二叉查找樹的中序遍歷，并將遍歷結(jié)果輸出到屏幕上，包括單詞和

單詞消失的位置。

3、刪除結(jié)點：給定一個停用詞列表（停用詞是指對搜尋沒有作用的詞，如:

of,and,a,an,the等等），將二叉查找樹中的屬于停用詞表中的單詞依次刪除。

4、可以顯示菜單，在菜單中可以進行如下四項操作（但并不局限這些操作）：

（1）讀入文本內(nèi)容，包含若干英文單詞、標(biāo)點符號以及阿拉伯?dāng)?shù)字，用于構(gòu)

建二叉查找樹。

（2）輸入停用詞，每個停用詞占一行。對于每個停用詞，都需要刪除二叉查

找樹中的相應(yīng)結(jié)點，即：每輸入一個停用詞，執(zhí)行一次刪除結(jié)點的操作。

（3）中序遍歷二叉查找樹，遍歷結(jié)果中的每個單詞占一行，先輸出該單詞，

然后輸出一個空格，再輸出該單詞消失的次數(shù)。

（4）輸入查詢詞。對每個查詢詞，都需要在二叉查找樹中的搜尋相應(yīng)結(jié)點，

假如找到，則輸出該單詞及其消失次數(shù)；假如未找到，則輸出相應(yīng)的信息。

每個查詢詞的查詢結(jié)果占一行，先輸出該單詞，然后輸出一個空格，再輸出

該單詞消失的次數(shù)。

［測試數(shù)據(jù)］

1、輸入的文本含有大小寫字母、阿拉伯?dāng)?shù)字、標(biāo)點符號及其它字符。

2、單詞的數(shù)量應(yīng)足夠多，并有肯定量的相同單詞。、

題目4（隊列）

［問題描述］

實現(xiàn)一個簡潔銀行叫號模擬系統(tǒng)。銀行有三個窗口可以同時辦理業(yè)務(wù)，當(dāng)有用

戶到達銀行時，首先選擇自己要辦理的業(yè)務(wù)，可以選擇一種或多種。系統(tǒng)計算辦理

此業(yè)務(wù)所需的時間并顯示給用戶，然后系統(tǒng)查看有無空閑的窗口，假如有，通知用

戶到一個空閑窗口辦理，假如沒有空閑窗口，則需支配用戶到某個窗口等候，系統(tǒng)

先計算每個隊列中用戶辦理業(yè)務(wù)的總時間，將用戶支配到時間最短的隊列等候。模

擬輸出多個用戶辦理業(yè)務(wù)的過程。（難易程度：高）

［試驗?zāi)康模?/p>

1、深化理解隊列的特性。

2、把握使用隊列實現(xiàn)某些問題。

［試驗內(nèi)容及要求］

1、建立3個隊列存放在三個窗口等待的用戶。

2、建立業(yè)務(wù)表，描述銀行能夠辦理的各項業(yè)務(wù)，以及辦理業(yè)務(wù)所需時間。

3、建立用戶表，描述用戶辦理的業(yè)務(wù)，用戶的狀態(tài)等

4、可以隨機產(chǎn)生用戶進入銀行的時間，讓用戶輸入所需辦理的業(yè)務(wù)。

5、由于輸入的數(shù)據(jù)量較大，可以采納文本文件存放需要輸入的數(shù)據(jù)。

［測試數(shù)據(jù)］

以下數(shù)據(jù)供參考：

用戶1在時間1到達銀行，在1號窗口辦理業(yè)務(wù)，需要1分鐘

用戶1在時間2結(jié)束,離開

用戶2在時間3達到。在1號窗口開頭辦理，辦理業(yè)務(wù)需要4分鐘

用戶3在時間3到達,在2號窗口開頭辦理，辦理業(yè)務(wù)需要5分鐘

用戶4在時間5到達,在3號窗口開頭辦理，辦理需要8分鐘

用戶5在時間6到達,在1號窗口等待，辦理業(yè)務(wù)需要4分鐘

用戶2在時間8辦理完業(yè)務(wù)，離開

用戶5在時間8在1號窗口，辦理業(yè)務(wù)需要4分鐘

用戶6在時間8到達，在1號窗口等待，辦理業(yè)務(wù)需要6分鐘

用戶7在時間8到達，在2號窗口等待，辦理業(yè)務(wù)需要10分鐘

題目5（二叉樹）

［問題描述］

樹和二叉樹是最常用的非線性結(jié)構(gòu)（樹型結(jié)構(gòu)），其中以二叉樹最為常見。遍歷

二叉樹是二叉樹各種操作的基礎(chǔ)，它分為先序、中序和后序。（難易程度：中）

［試驗?zāi)康模?/p>

1、嫻熟把握二叉樹的結(jié)構(gòu)特性。

2、把握二叉樹的各種存儲結(jié)構(gòu)的特點及使用范圍。

3、通過二叉樹的基本操作的實現(xiàn)，從而思索一般樹的基本操作的實現(xiàn)。

4、嫻熟把握各種遍歷二叉樹的遞歸和非遞歸算法。

［試驗內(nèi)容及要求］

1、創(chuàng)建二叉樹時可以依據(jù)前序遍歷序列進行創(chuàng)建，或者以其他方式創(chuàng)建二叉

樹。創(chuàng)建好之后將結(jié)點的值寫入文本文件。

2、創(chuàng)建好二叉鏈表之后實現(xiàn)以下功能：

（1）結(jié)點的值從文本文件讀出，在屏幕上以樹的形式或?qū)哟蔚男问斤@示。

（2）輸入一個結(jié)點值，輸出其雙親及其全部子女，以及兄弟結(jié)點值。

3、對二叉樹進行遞歸和非遞歸遍歷（先序、中序、后序）…

［測試數(shù)據(jù)］

1、用二叉鏈表表示一個大家族的家譜，即采納孩子兄弟表示法存儲數(shù)。根為

祖先結(jié)點，每個結(jié)點的左子樹是其第一個孩子，右子樹是其下一個兄弟。

2、輸入的結(jié)點值最好能夠體現(xiàn)結(jié)點之間的雙親、孩子、兄弟之間的關(guān)系，以

便于測試。

題目6（哈夫曼樹的編/譯碼器）

［問題描述】

采用哈夫曼編碼進行通訊可以大大提高信道采用率，縮短信息傳輸時間，降低

傳輸成本。但是，這要求在發(fā)送端通過一個編碼系統(tǒng)將待傳數(shù)據(jù)進行預(yù)先編碼；在

接受端將傳來的數(shù)據(jù)進行解碼（復(fù)原）。對于可以雙向傳輸?shù)男诺?，每端都要有?/p>

個完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個哈夫曼的編譯碼系統(tǒng)。（難易

程度：高）

［試驗?zāi)康模?/p>

1、通過哈夫曼樹的定義，把握構(gòu)造哈夫曼樹的意義。

2、把握構(gòu)造哈夫曼樹的算法思想。

3、通過具體構(gòu)造哈夫曼樹，進一步理解構(gòu)造哈夫曼樹編碼的意義。

［試驗內(nèi)容及要求］

1、從終端讀入字符集大小為n（即字符的個數(shù)），逐一輸入n個字符和相應(yīng)的

n個權(quán)值（即字符消失的頻度），建立哈夫曼樹，將它存于文件hfmtree中。并將

建立好的哈夫曼樹以樹或凹入法形式輸出;對每個字符進行編碼并且輸出。

2、采用已建好的哈夫曼編碼文件hfmtree,對已編碼的正文進行譯碼，輸出

譯碼后的正文。

3、采納文本文件存放文本，先統(tǒng)計文本中的每個字符消失的頻率，然后再建

立哈夫曼樹，并進行編碼和譯碼。

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

1、用下表給出的字符集和頻度的實際統(tǒng)計數(shù)據(jù)建立哈夫曼樹。

字符ABCDEFGHIJKLMN

頻度641322321032115475715322057

字符0PQRSTUVWXYZ空格

頻度63151485180238181161168

并實現(xiàn)以下報文的譯碼和輸出：THISPROGRAMISMYFAVORITE

2、采納文本文件存放文本，測試試驗內(nèi)容及要求的第3項。

題目7（圖）

［問題描述］

給定一個無向圖或有向圖，采用深度優(yōu)先遍歷和廣度優(yōu)先遍歷對給定圖進行遍

歷。（難易程度：低）

［試驗?zāi)康模?/p>

1、熟識圖的兩種常用的存儲結(jié)構(gòu)。

2、把握對圖的兩種遍歷方法，即深度優(yōu)先遍歷和廣度優(yōu)先遍歷。

3、進一步把握采用遞歸或隊列結(jié)構(gòu)進行算法設(shè)計方法。

［試驗內(nèi)容及要求］

1、構(gòu)造一個具有n個頂點的無向圖或有向圖。

2、輸出以深度優(yōu)先遍歷和廣度優(yōu)先遍歷圖的頂點序列。

3、考慮如何把遞歸實現(xiàn)的深度優(yōu)先遍歷算法改為非遞歸算法。

［測試數(shù)據(jù)］

以下圖作為測試數(shù)據(jù):

題目8(采用Prim算法求無向網(wǎng)的最小生成樹)

［問題描述］

假如要在n個城市之間建設(shè)通信網(wǎng)絡(luò)，只需架設(shè)n-1條線路即可。如何以最低

的經(jīng)濟代價建設(shè)這個通信網(wǎng)，是求一個無向網(wǎng)的最小生成樹問題。(難易程度：低)

［試驗?zāi)康模?/p>

1、把握圖的各種存儲結(jié)構(gòu)和基本操作。

2、對于實際問題的求解能夠選用合適的存儲結(jié)構(gòu)。

3、通過Prim算法理解如何求無向網(wǎng)的最小生成樹。

［試驗內(nèi)容及要求］

1、構(gòu)造具有n個頂點的無向網(wǎng)，并采用Prim算法求網(wǎng)的最小生成樹。

2、以文本形式輸出所求得的最小生成樹中各條邊以及它們的權(quán)值。

［測試數(shù)據(jù)］以下圖作為測試數(shù)據(jù):

題目9(圖，最短路徑)

［問題描述］

某旅行團要從南寧坐飛機周游東南亞7國，假如八地之間都有直飛航班，已知

南寧坐標(biāo)(378,78),河內(nèi)(327,119),曼谷(232,266),金邊(314,311),吉隆坡

(255,477),新加坡(296,513),文萊(510,438),馬尼拉(628,246),編程查找最

短周游路徑，并顯示出來。(例如：南寧-河內(nèi)-曼谷……)(難易程度：高)

［試驗?zāi)康模?/p>

1、把握圖的各種存儲結(jié)構(gòu)和基本操作。

2、對于實際問題的求解會選用合適的存儲結(jié)構(gòu)。

3、通過Dijkstra算法求有向網(wǎng)的最短路徑。

［試驗內(nèi)容及要求］

1、構(gòu)造具有8個頂點的有向網(wǎng)，并采用Dijkstra或Floyd算法求最短路徑。

2、以文本形式輸出所求得的最短路徑中各條邊以及它們的權(quán)值。

［測試數(shù)據(jù)］

依據(jù)題目的問題描述給出完全有向網(wǎng)，并作為測試數(shù)據(jù)。

題目10（串、模式匹配）

［問題描述］

統(tǒng)計英文文章中單詞個數(shù)、空格個數(shù)和標(biāo)點符號的個數(shù)，同時還能夠查找指定

的單詞，并替換為新的單詞。（難易程度：中）

［試驗?zāi)康模?/p>

1、把握串的各種存儲結(jié)構(gòu)。

2、依據(jù)實際問題選用合適的存儲結(jié)構(gòu)。

3、把握串的運算和模式匹配算法。

［試驗內(nèi)容及要求］

1、通過模式匹配算法及串的運算完成單詞的查找和替換。

2、以文本文件的形式存放英文文章，現(xiàn)將文章讀入到串中，讀入時需使用

EOF函數(shù)推斷文件結(jié)束標(biāo)記。

［測試數(shù)據(jù)］

英文文章的長度不能過短，必需能夠說明問題。

題目11（散列表）

［問題描述］

實現(xiàn)Hash表的建立、刪除、插入以及查找操作，對同學(xué)信息（如學(xué)號、姓名、

性別）進行管理。（難易程度：高）

［試驗?zāi)康模?/p>

1、把握散列函數(shù)及解決沖突的方法。

2、對于實際問題能夠選用合適的散列函數(shù)。

3、能夠選擇適當(dāng)?shù)慕鉀Q沖突的方法。

［試驗內(nèi)容及要求］

1、以學(xué)號的全部位或者部分位作為散列函數(shù)的自變量，學(xué)號的位數(shù)應(yīng)符合

實際，并且學(xué)號不肯定連續(xù)。

2、設(shè)計散列函數(shù)，要求計算出的散列地址應(yīng)分布勻稱，并且散列函數(shù)易于

實現(xiàn)。

3、可以采納閉散列表（開放地址法）或者開散列表（拉鏈法）解決沖突。

4、從文本文件讀取同學(xué)信息建立散列表。

［測試數(shù)據(jù)］

文本文件中的同學(xué)人數(shù)必需足夠多，能夠說明問題。

題目12（排序）

［問題描述］

排序是對一組紀(jì)錄依據(jù)紀(jì)錄的關(guān)鍵字有序進行重新排列，通過幾種典型的排序

算法，并對各種算法的特點、使用范圍和效率進一步地了解。（難易程度：低）

［試驗?zāi)康模?/p>

1、深刻理解排序的定義和各類排序的算法思想，并能夠依據(jù)實際狀況敏捷應(yīng)

用。

2、把握各類排序的時間簡單度的分析方法，能從“關(guān)鍵字間的比較次數(shù)”分

析算法的平均狀況、最好狀況和最壞狀況。

3、把握不同排序方法的空間簡單度的計算。

4、理解排序方法“穩(wěn)定”和“不穩(wěn)定”的含義。

5、對結(jié)果做出簡潔的分析，諸如穩(wěn)定性、最好狀況、最壞狀況、平均狀況等。

［試驗內(nèi)容及要求］

1、實現(xiàn)直接插入排序、希爾排序、快速排序、歸并排序