民國114年 地方三等 資訊處理 資料結構收錄考選部官方試題，共 4 題可線上瀏覽，考選部未公告本科目答案。
請回答下列問題：（每小題4 分，共20 分） 請說明堆疊（Stack）及佇列（Queue）那一種資料結構較適合用來進 行後序（Postfix）運算式的計算？ 請說明在二元搜尋樹中，前序（Preorder）走訪、中序（Inorder）走訪、 後序（Postorder）走訪、層序（Level-order）走訪那一種走訪順序可得 到遞增的鍵值？ 請說明在使用雜湊表時，若使用鏈結串列（chaining）處理碰撞 （collision）問題，則搜尋的平均時間複雜度為下列何者？O(1)、O(logn)、 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 演算法？
Priority Queue（優先佇列）是一種「每次取出的元素都是優先權最高的」 資料結構。 如果用「排序好的陣列」來實作優先佇列，插入與取最大值的時間複 雜度為何？（5 分） 如果用「未排序陣列」，來實作優先佇列，插入與取最大值的時間複雜 度為何？（5 分） 如果用最大堆積（max-heap）來實作優先佇列，插入與取最大值的時 間複雜度為何？（5 分） 請以最大堆積來實作優先佇列，並顯示以下動作過程的最大堆積樹： 加入10, 30, 50, 40，取出最大數，加入50, 60，取出最大數。（10 分）
二元搜尋樹（binary search tree）是一種常見的資料結構。 請將50, 30, 70, 20, 40, 60, 80 依序插入一個二元搜尋樹，然後再從該 二元樹刪除50，並畫出每個數字放入或刪除後的二元搜尋樹。（10 分） 以下陣列儲存了一個二元搜尋樹，根節點為A(1)，若針對該二元樹刪 除40，請顯示該陣列的變化。（5 分） i A(i) -- -- -- -- -- -- -- -- 以下陣列儲存了一個二元搜尋樹，根節點為A(1)，若針對該二元樹刪 除30，請顯示該陣列的變化。（5 分） i A(i) -- -- -- -- -- -- -- -- 以下陣列儲存了一個二元搜尋樹，根節點為A(1)，請列舉可依序插入 的五個數值，使得該二元樹成為完整二元樹（full binary tree）。（10 分） i A(i) -- -- -- -- -- -- -- --
一個自動化工廠大量採用機器人協助裝箱作業。該工廠固定時間生產出 一組n 個不同大小的塑膠球並放到裝箱作業輸送帶上。輸送帶上配置數 個機器人，當輸送帶上的球經過時，機器人負責將眼前兩顆球將順序排 序正確，大的在前，小的在後。當輸送帶上的球經過了所有機器人後， 球的順序就完全由大排到小了。（每小題5 分，共25 分） 若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 個機器人， 整組球順序排好的速度可以加快多少？請說明。