資訊處理 113 年資料結構考古題

資料結構中的二元樹（binary tree）依其走訪節點的順序可以得出不同的 運算表示式。給予一中序（inorder）表示式FBACEIGJH 和後序（postorder） 表示式BCAFIHJGE，請說明並畫出其對應的二元樹。有一後序表示式 36 12 / 10 23 - * 50 40 - +（此運算式中的數值均為二位 數），利用堆疊運算其結果為何？（請勿只寫出最後結果，需詳細寫出堆 疊內每一步的變化並說明）。（20 分）

若有200 人，其中一個人開始打電話給兩個人。隨後，每個接到電話 的人都會打電話給另外兩個尚沒有接到電話的人。請問總共會撥打多 少通電話？有多少人不會打電話？（無推導過程不給分）（10 分） 若一個二元樹其前序追蹤順序（Preorder Traversal）及後序追蹤順序 （Postorder Traversal）分別如下，請問此樹是否唯一？並請列出此二元 樹的中序追蹤順序（Inorder Traversal）。（無推導過程不給分）（15 分） 前序追蹤順序：T, S, R, F, D, I, H, E, Z, G, M, L, J, N, Q 後序追蹤順序：F, I, H, D, R, Z, G, E, S, J, N, L, Q, M, T

一串含有8 個整數的資料：48, 55, 10, 88, 26, 80, 35, 40，請以第一個數值 為樞紐（pivot）進行快速排序法（quick sort），將這些資料由小排到大， 並寫出詳細的比較過程。（20 分）

快速排序法（Quick Sort）最壞的情況下所需的時間複雜度（Time Complexity）為O(n2)，請說明是在何種情況下造成？（10 分） 請列出其最壞的時間複雜度為O(n2)的推導過程。（15 分）

有一棵高度平衡二元搜尋樹（balanced binary search tree）又稱AVL 樹 （Adelson-Velskii Landis tree）如下圖，加入90，請詳細說明該如何調整 成一棵AVL 樹？接著再加入85，請詳細說明該如何調整成一棵AVL 樹？ 接著再刪除15，該如何調整成一棵AVL 樹？請將最後調整後的AVL 樹 中每個節點之平衡因子（balance factor）寫在節點旁邊。（25 分） 30 80 25 60 15

請使用虛擬碼（Pseudo Code）或任何程式語言，完成下列問題： 撰寫二元搜尋（Binary Search）的遞迴及非遞迴程式。（20 分） 推導二元搜尋的時間複雜度（Time Complexity）。（5 分）

有一棵二元樹（binary tree）利用一維陣列來存放其節點，假設樹根（root） 存放在索引（index）為1 的位置，若有一節點i 存放在索引為1024 的位 置，請問該節點i 的父節點存於陣列的那個位置，其索引為何？若節點i 有 一右子節點j，請問節點j 存於陣列的那個位置，其索引為何？用一維陣 列存放二元樹，最浪費陣列空間的二元樹是那一種？請畫出並詳細說明。 （15 分）

堆疊（Stack）與佇列（Queue）是常見的資料結構，請回答下列問題： 利用雙向佇列（Deque）循序輸入1, 2, 3, 4, 5, 6, 7，請問能否得到 5174236 的輸出排列？並說明其過程或理由。（10 分） 若有1, 2, 3, 4 四個數字要依序Push 進堆疊，再於任意時間點Pop 出 堆疊，請列出可能的輸出組合。（15 分）

給定一個以相鄰矩陣（adjacency matrix）表示的一無方向圖如下表，∞表 示沒有邊（edge）相鄰。請畫出對應的圖形，每個邊和其對應的權值必須 列出。另外請使用Kruskal’s 演算法計算權重最小的生成樹（minimum spanning tree），並詳細列出該生成樹的形成過程。（20 分） a b c d e f g a ∞ 13 9 10 ∞ ∞ ∞ b 13 ∞ ∞ 16 ∞ ∞ ∞ c 9 ∞ ∞ 12 2 3 ∞ d 10 16 12 ∞ ∞ ∞ 18 e ∞ ∞ 2 ∞ ∞ 4 ∞ f ∞ ∞ 3 ∞ 4 ∞

g ∞ ∞ ∞ 18 ∞ 6 ∞