東北大學2023年資料結構試題

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的相互關係仍保持正確。

東北大學2023年資料結構試題

1 20分 簡要回答下列問題 注意 請將答案寫在答題紙上，並註明題號 3分 記憶體中一片連續空間 不妨假設位址從1到m 提供給兩個棧s1和s2使用，怎樣分配這部分儲存空間，使得對任乙個棧，僅當這部分空間全滿時才發生上溢。5分 假設字元a,b,c,d,e,f的使用頻度分別是0.07,0.09,0.12...

東北大學印表機管理資料結構設計作業

三 實驗環境 作業系統 除錯軟體名稱 版本號，上機地點，機器台號 作業系統為win7，除錯軟體名稱 microsoft visual studio 2012，上機地點 寢室 四 實驗過程與分析 1 描述你在進行實現時，主要的函式或操作內部的主要演算法，分析這個演算法的時 空複雜度，並說明你設計的巧妙...

2023年東北大學考研經驗

看過很多經驗貼，也一直想寫寫自己的。礙於自己表達能力不佳分數不高，所以之前一直沒寫。經驗也說不上，教訓還是有的。如果能讓後來的學弟學妹少走彎路，也還是不錯的。個人觀點，僅供參考 簡單說說樓主的自己情況。樓主考過兩次研，去年報的控制工程專碩，今年報的學碩。樓主本科是二本理學院的，跨專業考的自動化，去年...