第1題
考慮下面以虛擬碼（Pseudocode）表示的遞迴演算法，請回答相關問題： Algorithm Q(n) if n＝1 return 1 else return Q(n－1)＋2 n－1 列出虛擬碼中Q(n)的遞迴關係式，並說明此虛擬碼最終計算的是什麼？ （5 分） 用遞迴函式表示此虛擬碼所使用的乘法運算次數，並用漸進式符號 Big-O 表示此遞迴函式的成長速率。（5 分） 以遞迴函式表示此虛擬碼的執行時間T(n)並說明其時間複雜度（以 Big-O 表示）。（10 分）
民國113年 離島三等 資訊處理 資料結構考古題
民國113年 離島三等 資訊處理 資料結構收錄考選部官方試題，共 5 題可線上瀏覽，考選部未公告本科目答案。
官方資料
題目與答案
第2題
請回答下列關於二元樹（Binary Tree）的問題： 一個算術運算式（Arithmetic Expression）可以用一個二元樹表示，稱 為算術運算樹（Expression Tree），請將下列算術運算式以算術運算樹 表示。（5 分） ( ( ( 5 + 1 ) 3 －(7 + 2 ) ) / ( ( ( 2 8 ) + 5 ) / 7 ) ) 請判斷下列敘述是否正確：（5 分） “一個算術運算樹是一個滿二元樹（Full Binary Tree, or Proper Binary Tree）” 子題 中的算術運算式是何種順序的運算表示式？請利用其算術運 算樹將此運算式表示為一前序表示式（Preorder Expression），並說明 其過程。（5 分） 請敘述如何以子題 的算術運算樹計算出算術運算式的值，並逐步表 示其過程。（10 分）
第3題
在許多應用中，往往需要以物件的優先權來進行處理，為了區別物件的 優先順序，我們可以簡單地賦予物件一個鍵值（Key）來代表優先權，此 鍵值通常是一個數值可以用來區別物件前後順序。在此，我們考慮物件 的鍵值是一個數值而其值愈小，物件的優先權愈高，優先佇列（Priority Queue）則是一種以物件的優先權來管理物件的資料結構。 請說明優先佇列的抽象資料型態（abstract data type, ADT）定義。（10 分） 給定一個最小二元堆積（Minimum Heap）H 與一個鍵值k，在H 中快速 地找出所有鍵值小於或等於k 的資料物件。請描述一個有效的方法，此 方法所花的時間（或運算量）與欲找出的資料物件之數量成線性比例。 （5 分）
第4題
關於紅黑樹（Red Black Tree）與(2,4)-樹((2,4)-Tree)： 請分別說明紅黑樹與(2,4)-樹的定義。（10 分） 考慮下面的紅黑樹（實線節點代表黑色節點，虛線節點代表紅色節 點），代表節點的字元符號可視為鍵值，請說明如何將此紅黑樹轉換為 一個(2,4)-樹，並將其結果畫出。此外，請申論轉換的(2,4)-樹是否唯一。 （10 分） 請說明為何一個有n 個節點（鍵值）的紅黑樹其高度是O(log n)。（5 分）
第5題
下面的矩陣M 是表示一個無向圖G=(V, E)的相鄰矩陣（Adjacency Matrix），V 與E 分別為節點與邊的集合： a b c d e f g a b c d e f g 請畫出此無向圖G。（10 分） 若以字母順序為考量對G 進行廣度優先搜尋（Breadth-First Search, BFS），因此將由節點a 開始，請繪出尋訪完後所產生的BF 樹（Breadth- First (BF) Tree）。（5 分）