所屬科目：公職◆資料結構
一、請回答下列問題：(一)請說明堆疊（Stack）及佇列（Queue）那一種資料結構較適合用來進 行後序（Postfix）運算式的計算？
(二)請說明在二元搜尋樹中，前序（Preorder）走訪、中序（Inorder）走訪、 後序（Postorder）走訪、層序（Level-order）走訪那一種走訪順序可得 到遞增的鍵值？
(三) 請 說 明 在使用 雜 湊 表 時，若 使 用 鏈 結串列 （ chaining ）處 理 碰 撞 （collision）問題，則搜尋的平均時間複雜度為下列何者？O(1)、O(log n)、 O(n)或 O(sqrt{n})。
(四)請說明若一個圖 G（V, E）的頂點數|V|為 n，而邊數|E|接近 n²，則相 鄰串列（adjacency list） 、相鄰矩陣（adjacency matrix） 、或邊列表（edge list）中，那一種資料結構最適合用來儲存該圖？
(五)下列那幾項演算法可用於找出圖的最小生成樹（Minimum Spanning Tree）：Dijkstra 演算法、Floyd-Warshall 演算法、Prim 演算法、Bellman- Ford 演算法？
(一)如果用「排序好的陣列」來實作優先佇列，插入與取最大值的時間複 雜度為何？
(二)如果用「未排序陣列」 ，來實作優先佇列，插入與取最大值的時間複雜度為何？
(三)如果用最大堆積（max-heap）來實作優先佇列，插入與取最大值的時 間複雜度為何？
(四)請以最大堆積來實作優先佇列，並顯示以下動作過程的最大堆積樹： 加入 10, 30, 50, 40，取出最大數，加入 50, 60，取出最大數。
(一)請將 50, 30, 70, 20, 40, 60, 80 依序插入一個二元搜尋樹，然後再從該二元樹刪除 50，並畫出每個數字放入或刪除後的二元搜尋樹。
(二)以下陣列儲存了一個二元搜尋樹，根節點為 A(1)，若針對該二元樹刪 除 40，請顯示該陣列的變化。
(三)以下陣列儲存了一個二元搜尋樹，根節點為 A(1)，若針對該二元樹刪除 30，請顯示該陣列的變化。
(四)以下陣列儲存了一個二元搜尋樹，根節點為 A(1)，請列舉可依序插入的五個數值，使得該二元樹成為完整二元樹（full binary tree） 。
(一)若 n = 6，且生產後放上裝箱輸送帶的球的大小為 3, 2, 5, 6, 1, 4。請說明若輸送帶配有 4 個機器人是否足夠將球的順序完全由大排到小？
(二)若 n = 20，且生產後放上裝箱輸送帶的球的大小為 11, 12, 20, 16, 3, 1, 7, 15, 2, 18, 10, 5, 14, 6, 8, 13, 19, 4, 9, 17，請說明輸送帶上最少該配置幾個機器人才能將球的順序由大排到小？
(三)若 n = 6，且輸送帶上配有 4 個機器人，請給一組放上裝箱輸送帶的球的大小順序，使得其經過這 4 個機器人後，整組球的順序仍未能排好。
(四)若每一組球生產後放上裝箱輸送帶的 球的大小順序非固定順序 ，請說明輸送帶上最少該配置幾個機器人才能每次都能將球的順序由大排到小？
(五)若 n = 10，且每一組球生產後放上裝箱輸送帶的 球的大小順序非固定順序 。假設輸送帶上原本配置 n 個機器人，若改成配置 2n 個機器人， 整組球順序排好的速度可以加快多少？請說明。
阿摩線上測驗
登入
