109年 - 109 高等考試_三級_資訊處理：資料結構#88766

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

試卷資訊

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

選擇題 (0)

申論題 (16)

(一)數字1到n的何種排列會有最大的反向數？最大反向數是多少？

(二)若給定一個數字1到n的排列P，請提出一個線性遞迴（Linear Recursive）的方式來算出排列P的反向數，並提供虛擬碼（Pseudo-code）與時間複雜度分析。

二、優先佇列（Priority Queue）是依管理物件的優先權來考量，在此我們考慮管理物件的鍵值（Key）愈小其優先權愈高，兩個主要操作則分別為加入（Insert）與擷取最小者（Delete_Min）。

(一)請說明如何利用優先佇列對n個鍵值進行排序。

(1)若有n個鍵值，請說明兩個主要操作（加入（Insert）與擷取最小者（Delete_Min））的時間複雜度。

(2)請判斷下面的敘述是否為真，並請說明原因：

若以此優先佇列進行排序（Sorting），其所對應的排序原理為插入排序（Insertion Sort）。

(1)在結構上最小堆積為一個完全二元樹（Complete Binary Tree），若使用一個陣列來實作最小堆積，陣列中物件的鍵值放置如下，請描述此陣列對應的完全二元樹（以樹狀結構表示）。

(2)請說明二元堆積中何謂堆積特性（Heap Property）？

(3)前揭「在結構上最小堆積為一個完全二元樹（Complete Binary Tree），若使用一個陣列來實作最小堆積，陣列中物件的鍵值放置如下，請描述此陣列對應的完全二元樹（以樹狀結構表示）。

」中的完全二元樹並未有堆積特性，請將其進行堆積化（Heapify），並以陣列表示出堆積化後的最小堆積所對應之完全二元樹。

(一)我們欲將所管理的鍵值（Key）依序列出，請問是否可以利用一個AVL 樹對鍵值來進行排序（Sorting）？若不行，請說明原因；如果可以，請描述方法及時間複雜度。

(二)請提供一個線性時間的演算法來判斷一個二元搜尋樹是否為AVL樹。

(三)在AVL樹上進行一個加入（Insert）操作後，是否最多只需要一次的重構（Restructuring）即可恢復其平衡的特性？請說明原因。

(一)對於無向圖G = (V, E)

(1)請給出對應的相鄰矩陣M。

(一)對於無向圖G = (V, E)

(2)以字母順序為考量進行深度優先搜尋（Depth-First Search, DFS），請由節點a開始，描述此深度優先搜尋所產生的深度優先樹（DF-tree）。

(二)請說明在用相鄰矩陣（Adjacency Matrix）表示的無向圖上，進行深度優先搜尋的時間複雜度，其中節點與邊的數量分別為|V| = n與|E| = m。

(1)有向圖G’沒有迴圈（Cycle），是一個無迴圈有向圖（Directed Acyclic Graph, DAG），所以存在節點的拓樸排序（Topological Sort），請對G’ 給出一個拓樸排序（Topological Sort）。

(2)請給一個方法來判斷一個有向圖是否沒有迴圈。