東北大學(xué)2000年數(shù)據(jù)結(jié)構(gòu)考研試題

來(lái)源：時(shí)間：2007-06-06 14:35:41

1 （20分）

簡(jiǎn)要回答下列問(wèn)題

（注意：請(qǐng)將答案寫(xiě)在答題紙上，并注明題號(hào)）

① （3分）

內(nèi)存中一片連續(xù)空間（不妨假設(shè)地址從1到m），提供給兩個(gè)棧S1和S2使用，怎樣分配這部分存儲(chǔ)空間，使得對(duì)任一個(gè)棧，僅當(dāng)這部分空間全滿時(shí)才發(fā)生上溢。

②（5分）

假設(shè)字符a,b,c,d,e,f的使用頻度分別是0.07,0.09,0.12,0.22,0.23,0.27，寫(xiě)出a,b,c,d,e,f的Huffman（哈夫曼）編碼。

③（4分）

一棵共有n個(gè)結(jié)點(diǎn)的樹(shù)，其中所有分枝結(jié)點(diǎn)的度均為k，求該樹(shù)中葉子結(jié)點(diǎn)的子數(shù)。

④（4分）

圖1表示一個(gè)地區(qū)的通訊網(wǎng)，邊表示城市間的通訊線路，邊上的權(quán)表示架設(shè)線路花費(fèi)的代價(jià)，如何選擇能溝通每個(gè)城市且總代價(jià)最省的n-1條線路，畫(huà)出所有可能的選擇。

⑤（4分）

在起泡（汽泡）排序過(guò)程中，有的關(guān)鍵字在某趟排序中可能朝著與最終排序相反的方向移動(dòng)，試舉例說(shuō)明之�？焖倥判蜻^(guò)程中有沒(méi)有這種現(xiàn)象？

2 （15分）

設(shè)有一個(gè)由正整數(shù)組成的無(wú)序（向后）單鏈表，編寫(xiě)完成下列功能的算法：

① 找出最小值結(jié)點(diǎn)，且打印該數(shù)值；

② 若該數(shù)值是奇數(shù)，則將其與直接后繼結(jié)點(diǎn)的數(shù)值交換；

③若該數(shù)值是偶數(shù)，則將其直接后繼結(jié)點(diǎn)刪除；

3 （14分）

解答下列問(wèn)題：

① (4分）

將算術(shù)表達(dá)式 ((a b) c*(d e) f)*(g h) 轉(zhuǎn)化為二叉樹(shù)；

② (10分）

假設(shè)一個(gè)僅包含二元運(yùn)算符的算術(shù)表達(dá)式以二叉鏈表形式存儲(chǔ)在二叉樹(shù)BT中，寫(xiě)出計(jì)算該算術(shù)表達(dá)式值的算法。

4（21）

解答下列問(wèn)題：

① （5分）

畫(huà)出有向圖的十字鏈表存儲(chǔ)結(jié)構(gòu)中頭結(jié)點(diǎn)和表結(jié)點(diǎn)的結(jié)點(diǎn)結(jié)構(gòu)。

② (4分）

下面哪一個(gè)方法可以判斷出一個(gè)有向圖中是否有環(huán)（回路）？

(1)深度優(yōu)先遍歷 (2)拓樸排序 (3)求最短路徑 (4)求關(guān)鍵路徑

③(12分）

假設(shè)一個(gè)有向圖g已經(jīng)以十字鏈表形式存儲(chǔ)在內(nèi)中，試寫(xiě)一個(gè)判斷該有向圖中是否有環(huán)（回路）的算法。

5（15分）

寫(xiě)出刪除二叉排序樹(shù)bt中值為x的結(jié)點(diǎn)的算法（二叉排序樹(shù)以二叉鏈表形式存儲(chǔ)，刪除后仍然保持二叉排序性質(zhì)）。

6（15分）

設(shè)有大小不等的n個(gè)數(shù)據(jù)組（n個(gè)數(shù)據(jù)組中數(shù)據(jù)的總數(shù)為m），順序存放在空間區(qū)D內(nèi)，每個(gè)數(shù)據(jù)占一個(gè)存儲(chǔ)單元，數(shù)據(jù)組的首地址由數(shù)組s給出（如下圖所示），試編寫(xiě)將新數(shù)據(jù)x插入到第i個(gè)數(shù)據(jù)組的末尾且屬于第i個(gè)數(shù)據(jù)組的算法，插入后，空間區(qū)D和數(shù)組S的相互關(guān)系仍保持正確。