109年 - 109 關務特考_三等_資訊處理：資料結構#86484

試卷資訊

選擇題 (0)

申論題 (5)

一、資料庫應用中，需要根據主鍵值（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 分）

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

三、新冠肺炎肆虐全球，目前世界各國生物及醫學實驗室均在尋找新型冠狀病毒的基因，假設新型冠狀病毒的基因由 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 分）

此兩線性鏈結串列，分別由指標 plist1 與 plist2 指在串列首，請完成下列程式片段，將 plist2 所指串列接在 plist1 所指串列後面。