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

將中序運算式轉換成後序運算式演算法常使用堆疊資料結構，如相同 問題，改成使用二元樹資料結構來儲存一中序運算式，以中序運算式 A/B－C+D＊E－A＊C 為例，畫出表示此中序運算式的二元樹，並依前 序（Preorder）與後序（Postorder）列出拜訪（Visit）此二元樹的順序。 （25 分）

假設有一宣告為float A[18][10]的浮點數陣列（假設Sizeof(float) = 4 Bytes）： （每小題5 分，共15 分） 此陣列共占多少位元組（Bytes）？ 若A[0][0]在記憶體的位址為(03C4)16，則元素A[5][3]的位址為何？ 若A[16][2]在記憶體的位址為(10E9)16，則元素A[5][3]的位址為何？

某一公司有下圖所示的8個優先順序分別為高或低的待執行工作，且將依 順序自A至H每間隔一天的時間放入對應的高優先執行佇列（Queue）或低 優先執行佇列（Queue），例如A（低）表示A工作將於第一天放入低優先 執行佇列，而C（高）表示C工作將於第三天放入高優先執行佇列。此外， 執行每個工作所需完成的時間均於工作名稱下顯示，例如執行A工作需要 2天時間完成，而執行B工作需要1天時間完成。最後，各個工作的執行規 則為，當高優先執行佇列內有工作待完成時，須優先執行該佇列內的工作 （由第一個開始執行），直到高優先執行佇列內沒有任何待完成工作時， 方可執行低優先執行佇列內的工作（由第一個開始執行）。 自A至H每間隔一天的時間放入對應的高優先佇列或低優先佇列 H（低） G（高） F（高） E（低） D（高） C（高） B（低） A（低） 1

用G = (V, E)表示一個無方向性圖形，其中V 是點的集合，E 是一組節點 （Vertices）形成邊的集合。今有一圖形G = (V, E)，V(G) = {T, W, X, Y, Z}, E(G) = {(T, W),(T, Y),(T, Z),(W, X),(W, Z),(X, Z)}，每一個邊對應的權重值 分別為2, 1, 7, 4, 3, 6，請用相鄰矩陣（Adjacency Matrix）與相鄰串列 （Adjacency List）表示此圖形，並使用Prim’s 演算法，計算最小成本擴張 樹（Minimum Cost Spanning Tree），依序寫出從點X 加入邊的順序，最小 成本擴張樹的權重總和為何？（25 分）

請將下列表示式轉成後序（Postfix）（5 分） (A + B)× (C ^ (D − E) + F) – G 請將下列表示式轉成中序（Infix）（5 分） AB + D ∗EBA //+ AD ∗C /+ CD ∗ +A − B + CD ∗ −

1 1 2 2 1 2 試計算執行此8個工作需要多少天方可完成。（10分） 試計算此8個工作自放入佇列至開始執行的平均等待時間。（15分） 二、某一物流公司有下圖所示的8個地點要運送，每條方向性連線及其數字代 表兩個地點的運送順序及運送成本。 試使用拓樸排序法，找出此8個地點的運送順序以及總共運送成本。（15分） 若將上圖的地點2與地點4之間以及地點6與地點7之間的連線方向顛 倒，則運用拓樸排序法後，此8個地點的運送順序以及總共運送成本 為何？（10分）

給予一串資料60, 70, 50, 10, 20, 80, 95, 90，依序畫出產生2-3 樹（Order 3 的B-Tree）的過程，之後依序畫出刪除50、20 與80 的2-3 樹。（25 分）

下圖為一棵二元搜尋樹（Binary Search Tree），若要刪除節點48，在維持 最小變動的狀況下，但仍需維持一棵二元搜尋樹，請畫出所有可能的二 元搜尋樹。（20 分） 2 11 8 3 5

在電腦網路中，透過IP位址以查詢對應的裝置是常見的動作。今某電腦網 路有以下表格所示的IP位址以及對應裝置（假設每個IP位址有8個位元）， 當輸入某一IP位址以查詢對應的裝置時，最壞情況為此表格中的每個IP位 址的每個位元皆需要搜尋一次，以確認此輸入的IP位址是否有對應的裝 置。由於這樣的IP位址儲存方式，將造成查詢時的高複雜度（例如，若表 內有m個IP時，查詢的複雜度為m*8），因此運用適當的資料結構以減低查 詢複雜度，已成為電腦網路的重要課題。 IP位元0 IP位元1 IP位元2 IP位元3 IP位元4 IP位元5 IP位元6 IP位元7 裝置 0 0 1 1 1 1 0 0 A 0 0 1 1 0 0 1 1 B 1 1 0 0 0 0 1 1 C 1 1 0 0 1 1 0 0 D 1 1 0 1 1 1 0 0 E … … … … … … … … … 試建立並驗證一個樹狀資料結構，不僅可以儲存以上表格方式的IP位址以 及對應裝置資訊，並可使得查詢IP位址所對應的裝置的最壞情況複雜度維 持在常數8（也就是IP位址位元數）。（25分）

給予如下程式片段，假設x[] = [25, 57, 48, 37, 12, 92, 86, 33]，請只用下述 C 語言宣告的變數及兩個for 迴圈，完成下面的選擇排序（Selection Sort）， 假設有n 個資料要由小排到大，每一外迴圈將最大值放在第n-1 個位置， 然後第二大的資料放在第n-2 個位置，依此類推，將資料放到適當的位置， 執行後陣列x[]內容由小排至大。（25 分） Selectsort(x, n) int x[], n; { int i, index, j, large; for (i = n－1; i > 0; i－－){ for (j = 1; j <= i; j++){ } } }

6 4 9 2 四、若將下圖當作樹，請分別用陣列與鏈結串列（Linked List）的方式來表 示。（20 分）

某一系統有下表所示的使用者帳號與密碼資料，今為了保密需要欲將使 用者密碼透過雜湊函數加以加密，並將雜湊後的密碼連同使用者帳號儲 存於一個2-3樹（2-3 tree）（依使用者帳號英文字母順序儲存），而雜湊函 數h(x) =密碼之英文及數字加總，其中英文a-z相當於1-26。 使用者帳號 使用者密碼 AA 234abc BB 123bcd CD aa012 AC 555be BD 45fdd CA 712ccc 試計算出雜湊後的密碼資料。（10分） 試建立此2-3樹，以儲存系統的使用者帳號與（雜湊後）密碼資料。（15分）

請完成下列表格有關排序演算法的time complexity（假設排序資料有n 個，資料位數有d 個）、是否為In−Space 演算法、是否為Stable 演算法 及範例數列50, 46, 37, 28, 19 進行降冪排列時所需的比較次數。（30 分） 排序演算法 Time Complexity In−Space （Yes/No） Stable （Yes/No） 降冪比較次數 Best Worst 50, 46, 37, 28, 19 Bubble Insertion Merge（奇數時， 後半段多1） Quick（第一個當 pivot） Radix（base 10） Selection

請使用Prim 演算法找出下圖的最小生成樹（Minimum Spanning Tree）， 起始點為節點a，請將搜尋結果畫出來。（15 分）

假定一個整數序列：3, 12, 11, 13, 10, 8, 1, 4, 9, 15, 2, 6, 7, 14, 5, 16，請使 用合併排序（Merge Sort）從小到大進行排序及整理，並且一步步寫出過 程。（20 分） 3 a b c f e d