第1題
請用Big-O 符號來表示下列函式的成長速率，並說明之： T(݊) = 3݊ଷ+ 7݊ଷ√݊+ ݊ଷlog ݊（5 分） T(݊) = 2T(݊2 ⁄ ) + ݊ଶ（10 分）
民國111年 地方三等 資訊處理 資料結構考古題
民國111年 地方三等 資訊處理 資料結構收錄考選部官方試題，共 5 題可線上瀏覽，考選部未公告本科目答案。
官方資料
題目與答案
第2題
常用的算術運算式（Arithmetic Expression）有：中序運算式（Infix Expression）、前序運算式（Prefix Expression）、後序運算式（Postfix Expression）三種表示法，考慮下面的算術運算式（Arithmetic Expression） 並回答下列問題： ((6 (5 – 3))-(1 + 2)) (((4 + 2)/ 3)+(5 4)) 請寫出其前序運算式（Prefix Expression）。（5 分） 請繪出其算術運算樹（Expression Tree）。（5 分） 請說明如何以此算術運算樹計算出算術運算式的值，並一步一步列出 運算過程。（10 分）
第3題
回顧二元樹結構，其為m 路樹（m-ary Trees，亦稱多元樹、m 元樹）的 一個特例，請回答下列相關問題： 給出m 路樹的定義。（5 分） 若用陣列來表示一個m 路樹，請說明如何利用陣列的索引值來表示節 點間的親子連結關係（意即，假設陣列索引起始值為0，若節點v 在 陣列的第i 個位置，節點v 的第c 個子節點的位置為何？另一方面， 節點v 的parent 位置為何？）？（10 分） 基於此m 路樹結構及二元搜尋樹（Binary Search Tree）的概念，我們 可以定義出一個多元搜尋樹。當m=4 的時候，可以稱此搜尋樹為四元 搜尋樹。請給出(2,4)-樹((2,4)-tree)的定義並比較與四元搜尋樹的差異。 （10 分）
第4題
二元堆積（Binary Heap）是一種優先佇列（Priority Queue），主要用來管 理具有優先權順序的資料物件，每個資料物件具有一個可以界定大小或 前後順序的鍵值（Key），我們在此假設鍵值越低的資料物件有越高的優 先權。 請完整描述最小堆積（Min_Heap）的定義與相關的操作功能。（5 分） 請說明堆積排序（Heap Sort）的方法並分析其時間複雜度。（5 分） 若有兩個二元樹T1 及T2，其節點具有堆積特性且高度分別是O(log n) 與O(log m)，請提供一個方法將此兩個二元樹結合成為一個節點具有 堆積特性的二元樹T，此方法的時間須為O(log n+ log m)。（10 分）
第5題
下圖是一個加權圖G=(V, E)，其中V 是點集合而E 是邊集合。 請使用相鄰矩陣（Adjacency Matrix）表示法來表示加權圖G。（5 分） 不考慮權重，從節點g 開始並按照字母順序對G 進行廣度優先尋 訪（Breadth-First Search, BFS），請繪出尋訪完後所產生的BFS 樹 （BFS Tree）。（5 分） 請利用Prim's 演算法，從節點d 起始，找出一個最小擴張樹（Minimum Spanning tree），請以圖示方式一步步畫出過程與結果，並說明Prim's 演算法的時間複雜度。（10 分）