111年 - 111 地方政府特種考試_三等_資訊處理：資料結構#112604

科目：公職◆資料結構 | 年份：111年 | 選擇題數：0 | 申論題數：14

試卷資訊

所屬科目：公職◆資料結構

選擇題 (0)

申論題 (14)

(一)T(n)=（5分）

(二)T(n)=2T(n/2)+n²（10分）

(一)請寫出其前序運算式（PrefixExpression）。（5 分）

(二)請繪出其算術運算樹（ExpressionTree）。（5分）

(三)請說明如何以此算術運算樹計算出算術運算式的值，並一步一步列出運算過程。（10分）

(一)給出m路樹的定義。（5分）

(二)若用陣列來表示一個m路樹，請說明如何利用陣列的索引值來表示節點間的親子連結關係（意即，假設陣列索引起始值為0，若節點v在陣列的第i個位置，節點v的第c個子節點的位置為何？另一方面，節點v的parent位置為何？）？（10分）

(三)基於此m路樹結構及二元搜尋樹（BinarySearchTree）的概念，我們可以定義出一個多元搜尋樹。當m=4的時候，可以稱此搜尋樹為四元搜尋樹。請給出(2,4)-樹((2,4)-tree)的定義並比較與四元搜尋樹的差異。（10分）

(一)請完整描述最小堆積（Min_Heap）的定義與相關的操作功能。（5分）

(二)請說明堆積排序（HeapSort）的方法並分析其時間複雜度。（5分）

(三)若有兩個二元樹T₁及T₂，其節點具有堆積特性且高度分別是O(logn) 與O(logm)，請提供一個方法將此兩個二元樹結合成為一個節點具有堆積特性的二元樹T，此方法的時間須為O(logn+logm)。（10分）

(一)請使用相鄰矩陣（AdjacencyMatrix）表示法來表示加權圖G。（5分）

(二)不考慮權重，從節點g開始並按照字母順序對G進行廣度優先尋訪（Breadth-FirstSearch,BFS），請繪出尋訪完後所產生的BFS樹（BFSTree）。（5分）

(三)請利用Prim's演算法，從節點d起始，找出一個最小擴張樹（Minimum Spanningtree），請以圖示方式一步步畫出過程與結果，並說明Prim's演算法的時間複雜度。（10分）