資訊處理 109 年資料結構考古題

資料庫應用中，需要根據主鍵值（Primary Key）建立索引檔，索引檔的 建立常使用B-tree 樹狀結構，今有一串資料，其主鍵值分別為：44, 29, 39, 64, 67, 59, 69, 49，畫出將此串資料建成order 3 的B-tree，接著，畫出從此串 資料，新增（Insert）主鍵值55 後order 3 的B-tree，最後，畫出從此串資料 刪除（Delete）主鍵值49 後order 3 的B-tree。（20 分）

考慮數字1到n，若將其順序重新排置，每個排列順序都稱作一個排列或置換 （Permutation），例如5 1 4 3 2是1 2 3 4 5的一個排列。我們可以將一個數字1 到n的排列視為一個順序的映射P，則前述例子可表示為P(5) = 1、P(1) = 2、 P(4) = 3、P(3) = 4、P(2) = 5。當然，1 2 3 4 5也是1 2 3 4 5的一個排列。在 一個數字1到n的排列P中，若一對數字i和j，1 i < j n，P( j) < P(i)，也 就是在排列P中較大的數字j出現在較小的數字i左邊（前面），我們稱此 對數字為反向（Inversion），而排列P的反向數（Inversion number）則定義 為排列P中反向的總數量。請回答下列問題： 數字1到n的何種排列會有最大的反向數？最大反向數是多少？（5分） 若給定一個數字1到n的排列P，請提出一個線性遞迴（Linear Recursive） 的方式來算出排列P的反向數，並提供虛擬碼（Pseudo-code）與時間複 雜度分析。（10分）

給定一個無向圖（Undirected Graph）G 的鄰接列表（Adjacency List）如圖， 試依據該列表提供的資訊繪製出對應的無向圖G，然後由節點（Vertex）H 為 起始點繪製Depth First Search（DFS）與Breadth First Search（BFS）生成樹 （Spanning Tree），遇有多個節點可被走訪時，字母順序越前面的節點，其 被走訪的優先順序就越高。（20 分） 無向圖G 鄰接列表

優先佇列（Priority Queue）是依管理物件的優先權來考量，在此我們考慮 管理物件的鍵值（Key）愈小其優先權愈高，兩個主要操作則分別為加入 （Insert）與擷取最小者（Delete_Min）。 請說明如何利用優先佇列對n個鍵值進行排序。（6分） 我們使用一個未排序的陣列（Unsorted Array）來管理鍵值以實現一個 優先佇列，請回答下列問題：（10分） ⑴若有n個鍵值，請說明兩個主要操作（加入（Insert）與擷取最小者 （Delete_Min））的時間複雜度。 ⑵請判斷下面的敘述是否為真，並請說明原因： 若以此優先佇列進行排序（Sorting），其所對應的排序原理為插入排 序（Insertion Sort）。 二元堆積（Binary Heap）是一個優先佇列的資料結構，因為我們考慮鍵值 小的物件有高的優先權，所以又可稱為最小堆積（MinimumHeap）。（14分） ⑴在結構上最小堆積為一個完全二元樹（Complete Binary Tree），若使 用一個陣列來實作最小堆積，陣列中物件的鍵值放置如下，請描述此 陣列對應的完全二元樹（以樹狀結構表示）。 Index 1 2

新冠肺炎肆虐全球，目前世界各國生物及醫學實驗室均在尋找新型冠狀病 毒的基因，假設新型冠狀病毒的基因由A, T, C, G, H, M 核苷酸所組成， 今有一新型冠狀病毒的基因為ATATATCCHCGMCMA，請使用霍夫曼演 算法（Huffman Algorithm）設計霍夫曼樹（Huffman Trees），並設計出一 編碼表（Code Words），依序分別寫出A, T, C, G, H, M 核苷酸的編碼位 元數，將此新型冠狀病毒基因以最少位元數（Minimum Bit Strings）編碼， 並計算出最少位元數（Minimum Bit Strings）。（20 分）

給予一串資料：45,30,40, 65,68,60, 70,50，將此串資料依序建成一max-heap 樹，並說明如何從此max-heap 樹進行由小至大的排序（Sorting）。（20 分）

給予兩線性鏈結串列，其節點C 語言的宣告如下：（20 分） #include <stdio.h> #include <stdlib.h> struct node{ int data; struct node *next; }; typedef struct node *NODEPTR; 此兩線性鏈結串列，分別由指標plist1 與plist2 指在串列首，請完成下列 程式片段，將plist2 所指串列接在plist1 所指串列後面。 void concate（NODEPTR plist1, NODEPTR plist2） { NODEPTR p; }

9 10 11 12 四、在一棵高度為h(h=0,1,2,…)的AVL tree 中：⑴高度為6之AVL tree 最多 可能有幾個nodes？最少可能有幾個nodes？（假設root 之h=0）（6分） ⑵假設此樹共有45個nodes。請問此AVL tree 可能最高之高度及最矮 之高度各為何？（6分） 請將下列數字{17, 60, 24, 5, 7}逐步插入圖1的AVLtree 中，並平衡之。 （12分） 圖1 五、請利用堆積排序法（Heap Sort）將圖2逐步建立成Min Heap，並將數字 從小到大逐一列舉。（10分） 圖2 六、請利用KMP（Knuth, Morris, Pratt）演算法寫出失敗函數（failure function)之定義。（4分） 找出pattern “abcdabcabcdabcdabc”之失敗函數（failure function）值（請 填入表2 failure value 中）。（14分） 假設之pattern 嘗試在string “abcdabcabcdabcabcda…..”找出pattern。 當pattern 從index 0開始比對到index 13都一樣，而在index 14時發現 字母不一樣，請問pattern 如何利用failure function 所得之結果很快找 到下一個要對應之位置？也就是pattern 的那一位置的值要位移到 string 的那一對應位置。（4分） 表2 index 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 string a b c d a b c a b c d a b c a b c d a pattern a b c d a b c a b c d a b c d a b c failure value ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

9 10 Key 35 18 42 24 7 14 25 12 38 21 ⑵請說明二元堆積中何謂堆積特性（Heap Property）？ ⑶前揭⑴中的完全二元樹並未有堆積特性，請將其進行堆積化 （Heapify），並以陣列表示出堆積化後的最小堆積所對應之完全二元樹。 三、請回答下列關於AVL樹（AVL Tree）的問題： 我們欲將所管理的鍵值（Key）依序列出，請問是否可以利用一個AVL 樹對鍵值來進行排序（Sorting）？若不行，請說明原因；如果可以，請 描述方法及時間複雜度。（5分） 請提供一個線性時間的演算法來判斷一個二元搜尋樹是否為AVL樹。 （10分） 在AVL樹上進行一個加入（Insert）操作後，是否最多只需要一次的重構 （Restructuring）即可恢復其平衡的特性？請說明原因。（10分） 四、若我們用相鄰矩陣（Adjacency Matrix）M來表示圖一中的無向圖G = (V, E)， 請考慮下面的問題： 圖一、無向圖G = (V, E) 對於無向圖G = (V, E)：（12分） ⑴請給出對應的相鄰矩陣M。 ⑵以字母順序為考量進行深度優先搜尋（Depth-First Search, DFS），請 由節點a開始，描述此深度優先搜尋所產生的深度優先樹（DF-tree）。 請說明在用相鄰矩陣（Adjacency Matrix）表示的無向圖上，進行深度優 先搜尋的時間複雜度，其中節點與邊的數量分別為|V| = n與|E| = m。（8分） 若將圖一無向圖G = (V, E)中的邊給予方向成為如圖二中的有向圖 （Directed Graph）G’：（10分） 圖二、有向圖G’ ⑴有向圖G’沒有迴圈（Cycle），是一個無迴圈有向圖（Directed Acyclic Graph, DAG），所以存在節點的拓樸排序（Topological Sort），請對G’ 給出一個拓樸排序（Topological Sort）。 ⑵請給一個方法來判斷一個有向圖是否沒有迴圈。