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

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

題目1（線性表）

［問(wèn)題描述］

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

［試驗(yàn)?zāi)康模?/p>

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

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

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

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

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

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

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

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

4、要求不轉(zhuǎn)變?cè)瓉?lái)的集合，并集、交集和差集分別此外存放。

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

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

setlUset2=

setlAset2=

setl-set2=

2、其中一個(gè)集合為空集

3、兩個(gè)集合都是空集

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

題目2（棧、串）

［問(wèn)題描述］

采用棧實(shí)現(xiàn)算術(shù)表達(dá)式的求值?？梢院?jiǎn)潔一些，假設(shè)表達(dá)式中含有一位整數(shù),

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

［試驗(yàn)?zāi)康模?/p>

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

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

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

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

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

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

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

號(hào)不匹配等錯(cuò)誤），若輸入格式錯(cuò)誤，輸出錯(cuò)誤提示。

［測(cè)試數(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（二叉排序樹(shù)）

［問(wèn)題描述］

采用二叉查找樹(shù)（又稱(chēng)為二叉排序樹(shù)、二叉搜尋樹(shù)）實(shí)現(xiàn)對(duì)輸入的英文單詞進(jìn)

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

［試驗(yàn)?zāi)康模?/p>

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

2、把握搜尋和過(guò)濾的方法。

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

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

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

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

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

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

字母相同時(shí)，按其次個(gè)字母進(jìn)行排序，依次類(lèi)推。

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

2、遍歷二叉查找樹(shù)

（1）搜尋：輸入一個(gè)待檢索單詞，在二叉查找樹(shù)中進(jìn)行查找，假如能找到該

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

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

單詞消失的位置。

3、刪除結(jié)點(diǎn)：給定一個(gè)停用詞列表（停用詞是指對(duì)搜尋沒(méi)有作用的詞，如:

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

4、可以顯示菜單，在菜單中可以進(jìn)行如下四項(xiàng)操作（但并不局限這些操作）：

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

建二叉查找樹(shù)。

（2）輸入停用詞，每個(gè)停用詞占一行。對(duì)于每個(gè)停用詞，都需要?jiǎng)h除二叉查

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

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

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

（4）輸入查詢(xún)?cè)~。對(duì)每個(gè)查詢(xún)?cè)~，都需要在二叉查找樹(shù)中的搜尋相應(yīng)結(jié)點(diǎn)，

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

每個(gè)查詢(xún)?cè)~的查詢(xún)結(jié)果占一行，先輸出該單詞，然后輸出一個(gè)空格，再輸出

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

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

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

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

題目4（隊(duì)列）

［問(wèn)題描述］

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

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

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

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

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

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

［試驗(yàn)?zāi)康模?/p>

1、深化理解隊(duì)列的特性。

2、把握使用隊(duì)列實(shí)現(xiàn)某些問(wèn)題。

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

1、建立3個(gè)隊(duì)列存放在三個(gè)窗口等待的用戶(hù)。

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

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

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

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

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

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

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

用戶(hù)1在時(shí)間2結(jié)束,離開(kāi)

用戶(hù)2在時(shí)間3達(dá)到。在1號(hào)窗口開(kāi)頭辦理，辦理業(yè)務(wù)需要4分鐘

用戶(hù)3在時(shí)間3到達(dá),在2號(hào)窗口開(kāi)頭辦理，辦理業(yè)務(wù)需要5分鐘

用戶(hù)4在時(shí)間5到達(dá),在3號(hào)窗口開(kāi)頭辦理，辦理需要8分鐘

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

用戶(hù)2在時(shí)間8辦理完業(yè)務(wù)，離開(kāi)

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

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

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

題目5（二叉樹(shù)）

［問(wèn)題描述］

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

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

［試驗(yàn)?zāi)康模?/p>

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

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

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

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

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

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

樹(shù)。創(chuàng)建好之后將結(jié)點(diǎn)的值寫(xiě)入文本文件。

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

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

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

3、對(duì)二叉樹(shù)進(jìn)行遞歸和非遞歸遍歷（先序、中序、后序）…

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

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

祖先結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)的左子樹(shù)是其第一個(gè)孩子，右子樹(shù)是其下一個(gè)兄弟。

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

便于測(cè)試。

題目6（哈夫曼樹(shù)的編/譯碼器）

［問(wèn)題描述】

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

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

接受端將傳來(lái)的數(shù)據(jù)進(jìn)行解碼（復(fù)原）。對(duì)于可以雙向傳輸?shù)男诺溃慷硕家幸?/p>

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

程度：高）

［試驗(yàn)?zāi)康模?/p>

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

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

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

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

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

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

建立好的哈夫曼樹(shù)以樹(shù)或凹入法形式輸出;對(duì)每個(gè)字符進(jìn)行編碼并且輸出。

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

譯碼后的正文。

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

立哈夫曼樹(shù)，并進(jìn)行編碼和譯碼。

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

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

字符ABCDEFGHIJKLMN

頻度641322321032115475715322057

字符0PQRSTUVWXYZ空格

頻度63151485180238181161168

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

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

題目7（圖）

［問(wèn)題描述］

給定一個(gè)無(wú)向圖或有向圖，采用深度優(yōu)先遍歷和廣度優(yōu)先遍歷對(duì)給定圖進(jìn)行遍

歷。（難易程度：低）

［試驗(yàn)?zāi)康模?/p>

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

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

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

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

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

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

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

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

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

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

［問(wèn)題描述］

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

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

［試驗(yàn)?zāi)康模?/p>

1、把握?qǐng)D的各種存儲(chǔ)結(jié)構(gòu)和基本操作。

2、對(duì)于實(shí)際問(wèn)題的求解能夠選用合適的存儲(chǔ)結(jié)構(gòu)。

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

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

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

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

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

題目9(圖，最短路徑)

［問(wèn)題描述］

某旅行團(tuán)要從南寧坐飛機(jī)周游東南亞7國(guó)，假如八地之間都有直飛航班，已知

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

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

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

［試驗(yàn)?zāi)康模?/p>

1、把握?qǐng)D的各種存儲(chǔ)結(jié)構(gòu)和基本操作。

2、對(duì)于實(shí)際問(wèn)題的求解會(huì)選用合適的存儲(chǔ)結(jié)構(gòu)。

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

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

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

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

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

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

題目10（串、模式匹配）

［問(wèn)題描述］

統(tǒng)計(jì)英文文章中單詞個(gè)數(shù)、空格個(gè)數(shù)和標(biāo)點(diǎn)符號(hào)的個(gè)數(shù)，同時(shí)還能夠查找指定

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

［試驗(yàn)?zāi)康模?/p>

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

2、依據(jù)實(shí)際問(wèn)題選用合適的存儲(chǔ)結(jié)構(gòu)。

3、把握串的運(yùn)算和模式匹配算法。

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

1、通過(guò)模式匹配算法及串的運(yùn)算完成單詞的查找和替換。

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

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

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

英文文章的長(zhǎng)度不能過(guò)短，必需能夠說(shuō)明問(wèn)題。

題目11（散列表）

［問(wèn)題描述］

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

性別）進(jìn)行管理。（難易程度：高）

［試驗(yàn)?zāi)康模?/p>

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

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

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

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

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

實(shí)際，并且學(xué)號(hào)不肯定連續(xù)。

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

實(shí)現(xiàn)。

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

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

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

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

題目12（排序）

［問(wèn)題描述］

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

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

［試驗(yàn)?zāi)康模?/p>

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

用。

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

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

3、把握不同排序方法的空間簡(jiǎn)單度的計(jì)算。

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

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

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

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