東北大學2000年數據結構考研試題

來源：時間：2007-06-06 14:35:41

1 （20分）

簡要回答下列問題

（注意：請將答案寫在答題紙上，并注明題號）

① （3分）

內存中一片連續空間（不妨假設地址從1到m），提供給兩個棧S1和S2使用，怎樣分配這部分存儲空間，使得對任一個棧，僅當這部分空間全滿時才發生上溢。

②（5分）

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

③（4分）

一棵共有n個結點的樹，其中所有分枝結點的度均為k，求該樹中葉子結點的子數。

④（4分）

圖1表示一個地區的通訊網，邊表示城市間的通訊線路，邊上的權表示架設線路花費的代價，如何選擇能溝通每個城市且總代價最省的n-1條線路，畫出所有可能的選擇。

⑤（4分）

在起泡（汽泡）排序過程中，有的關鍵字在某趟排序中可能朝著與最終排序相反的方向移動，試舉例說明之。快速排序過程中有沒有這種現象？

2 （15分）

設有一個由正整數組成的無序（向后）單鏈表，編寫完成下列功能的算法：

① 找出最小值結點，且打印該數值；

② 若該數值是奇數，則將其與直接后繼結點的數值交換；

③若該數值是偶數，則將其直接后繼結點刪除；

3 （14分）

解答下列問題：

① (4分）

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

② (10分）

假設一個僅包含二元運算符的算術表達式以二叉鏈表形式存儲在二叉樹BT中，寫出計算該算術表達式值的算法。

4（21）

解答下列問題：

① （5分）

畫出有向圖的十字鏈表存儲結構中頭結點和表結點的結點結構。

② (4分）

下面哪一個方法可以判斷出一個有向圖中是否有環（回路）？

(1)深度優先遍歷 (2)拓樸排序 (3)求最短路徑 (4)求關鍵路徑

③(12分）

假設一個有向圖g已經以十字鏈表形式存儲在內中，試寫一個判斷該有向圖中是否有環（回路）的算法。

5（15分）

寫出刪除二叉排序樹bt中值為x的結點的算法（二叉排序樹以二叉鏈表形式存儲，刪除后仍然保持二叉排序性質）。

6（15分）

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

結束

特別聲明：①凡本網注明稿件來源為"原創"的，轉載必須注明"稿件來源：育路網"，違者將依法追究責任；

②部分稿件來源于網絡，如有侵權，請聯系我們溝通解決。

: 有用

25人覺得有用

閱讀全文

東北大學2000年數據結構考研試題

2019考研VIP資料免費領取