109年資料結構分年題庫－國考資訊處理工作室(高考二級資訊處理/高考三級資訊處理/調查局三等/關務人員三等/地方特考三等)

關務三等資料結構：109

身心障礙人員三等資料結構：109

鐵路特考高員三級資料結構：無

高考三級資料結構：109

專利商標審查人員三等資料結構：無

關務人員升官等薦任資料結構：無

資訊技師高等資料結構與資料庫及資料探勘：109

地方特考三等資料結構：109

[一○九年關務三等資料結構]

代號：10460

頁次：2-1

109年公務人員特種考試關務人員、身心障礙人員考試及

109年國軍上校以上軍官轉任公務人員考試試題

考試別：關務人員考試

等別：三等考試

類科：資訊處理

科目：資料結構

考試時間：2小時座號：___________

※注意：(一)禁止使用電子計算器。

(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。

(三)本科目除專門名詞或數理公式外，應使用本國文字作答。

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

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

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

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

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

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

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

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

五、給予兩線性鏈結串列，其節點 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;

}

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

[一○九年身心障礙人員三等資料結構]

代號：30860

頁次：2-1

109年公務人員特種考試關務人員、身心障礙人員考試及

109年國軍上校以上軍官轉任公務人員考試試題

考試別：身心障礙人員考試

等別：三等考試

類科：資訊處理

科目：資料結構

考試時間：2小時座號：___________

※注意：(一)禁止使用電子計算器。

(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。

(三)本科目除專門名詞或數理公式外，應使用本國文字作答。

一、假設 A[1: n] 是一個矩陣，存有 n 個不同的整數，且已依序從小到大排列。給定一個整數 s，設計一個線性時間 (linear time) 的演算法，找出在 A[1: n] 中是否存在兩個相異之 A[i] 和 A[j]，使得 A[i]+A[j] = s。若存在，則印出任一組符合條件之 i 和 j；若不存在，則印出0。（須詳述或證明所設計程式之正確性及其計算複雜度，否則不計分）（25分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

二、令 G = (V, E) 為一點數 (number of vertexes) |V| > 2 的連通 (connected) 無向圖 (undirected graph)，w：E→Z 為權重 (weight) 函數。令 T = (V, E')，E’ ⊆ E，是 G 的一個最小權重擴張樹 (minimumspanning tree)。假設每個邊 (edge) 的權重都是正整數，且都不相同。判定下列敘述的正確性。若敘述是正確的，請說明理由；若敘述是錯的，請舉一個反例。(僅有答案，未說明理由或未舉出反例者，不予計分)

(一)若 e 是所有邊中權重最大者，則 e ∉ E’。（也就是 e 不會在任一個 G的最小權重擴張樹中）（10分）

(二)假設 G 是2-連通 (2-connected)。(也就是去掉任一條邊 G 仍是連通的) 此時，若 e 是所有邊中權重最大者，則 e ∉ E’。（15分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

三、斐波那契數 (Fibonacci number) F_n 的定義為：F₀ = 0, F₁ = 1, F_n = F_n-1+F_n-2 ,n > 1。下面是一個計算斐波那契數 F_n 的演算法，以類似 C 語言的函數 (C function) 表示，其中資料型態 integer 表示整數。

integer Fib(n)

{

If (n == 0) return 0;

If (n == 1) return 1;

return Fib(n-1)+Fib(n-2);

}

假設輸入的整數 n ≧ 0。證明此程式的計算複雜度 T(n) > F_n。在分析計算複雜度時，可將 “==”, “=”, “+” 和 “return” 當作只需要一個單位時間的運算。（25分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

四、假設有個矩陣 A[1: n] 儲存 n 個整數。本題將設計 heap 排序演算法 (heap sort) 之重要部分，將矩陣 A[1: n] 變成一個 max-heap。

(一)說明 A[1: n] 是一個 max-heap 之定義。（5分）

(二)設計一個副程式 sift(A, r, n) 其輸入參數 A 是一個矩陣，n 是矩陣 A 的大小，1 ≤ r ≤ n 是一個指標。副程式 sift(A, r, n) 的功能是將 A[r] 為樹根的子樹變成 heap。(在呼叫 sift(A, r, n) 之前，A[i] 的所有子樹必須已經是 heap) 並分析其計算時間確實是 O(h(r))，其中 h(r) 是以 A[r] 為樹根的子樹的高度。（10分）

(三)利用 sift(A, r, n) 設計一個線性時間的演算法，將矩陣 A[1:n] 變成 heap，並證明所設計的演算法的時間複雜度為線性。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

[一○九年高考三級資料結構]

代號：38450

頁次：2-1

109年公務人員高等考試三級考試試題

類科：資訊處理

科目：資料結構

考試時間：2小時座號：___________

※注意：(一)禁止使用電子計算器。

(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。

(三)本科目除專門名詞或數理公式外，應使用本國文字作答。

一、考慮數字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分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

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

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

(二)我們使用一個未排序的陣列 (Unsorted Array) 來管理鍵值以實現一個優先佇列，請回答下列問題：（10分）

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

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

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

(三)二元堆積 (Binary Heap) 是一個優先佇列的資料結構，因為我們考慮鍵值小的物件有高的優先權，所以又可稱為最小堆積 (Minimum Heap)。（14分）

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

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

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

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

三、請回答下列關於 AVL 樹 (AVL Tree) 的問題：

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

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

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

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

四、若我們用相鄰矩陣 (AdjacencyMatrix) M 來表示圖一中的無向圖 G = (V, E)，請考慮下面的問題：

(一)對於無向圖 G = (V, E)：（12分）

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

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

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

(三)若將圖一無向圖 G = (V, E) 中的邊給予方向成為如圖二中的有向圖 (Directed Graph) G’：（10分）

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

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

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

[一○九年資訊技師高等資料結構與資料庫及資料探勘]

代號：01310

頁次：2-1

109年專門職業及技術人員高等考試建築師、32類科技師（含第二次食品技師）、大地工程技師考試分階段考試（第二階段考試）暨普通考試不動產經紀人、記帳士考試、109年第二次專門職業及技術人員特種考試驗光人員考試試題

等別：高等考試

類科：資訊技師

科目：資料結構與資料庫及資料探勘

考試時間：2小時座號：___________

※注意：(一)禁止使用電子計算器。

(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。

(三)本科目除專門名詞或數理公式外，應使用本國文字作答。

一、請將數列「8、70、19、3、50、25、30、10」以合併排序法 (Merge Sort) 由小到大排序，並繪出排序過程。（20分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

二、下圖是一棵二元搜尋樹 (Binary Search Tree)，依序對此樹輸入68、4，請逐步繪出輸入結果；對下圖的二元搜尋樹依序刪除60、10，請逐步繪出刪除的結果。（20分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

三、資料庫管理系統並行控制 (Concurrency Control) 不佳時可能產生三種資料干擾問題：遺失更新 (Lost Update)、未確認相依 (Uncommitted Dependency)、不一致分析 (Inconsistent Analysis)，請說明這三種資料干擾問題。（20分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

四、SQL 合併查詢 (Join) 中的外部合併查詢 (Outer Join) 指令可分成那三種？並請說明三種外部合併查詢 (Outer Join) 及內部合併查詢 (Inner Join) 四者之間的差異。（20分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

五、正確率 (Accuracy)、精確率 (Precision)、召回率 (Recall) 為分類 (Classification) 技術中常用的評估機制，請說明三者的定義。假設有1000張照片，其中有200張為人物照，800張為風景照，我們建立了一個分類器(Classifier)，希望能正確辨識出人物照，此分類器的分類結果如下：

400張被判斷為人物照，其餘600張被判斷為非人物照，而被判斷為人物照的照片中有250張實際上並非人物照，請計算此分類器的 Accuracy、Precision、Recall。（20分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

[一○九年地方特考三等資料結構]

代號：34580

頁次：2-1

109年特種考試地方政府公務人員考試試題

等別：三等考試

類科：資訊處理

科目：資料結構

考試時間：2小時座號：___________

※注意：(一)禁止使用電子計算器。

(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。

(三)本科目得以本國文字或英文作答。

一、請設計演算法複製一棵二元樹 (copy a binary tree)。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

二、(一)請描述 order 為 m 的 B-tree 之特性。（6分）

(二)請問 order 為 m 高度為 h 的 B-tree：(1)最多有幾個節點？最多有幾個 Key？（6分）(2)最少有幾個節點？最少有幾個 Key？（8分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

三、請利用 Double Hashing 將下列 key 值放入 hash table of size 13 中 (如表1)：（14分）

{24, 53, 17, 46, 14, 32, 37, 92}

h1(k) = k mod 13，h2(k) = 1+(k mod 11)，

h(k, i) = (h1(k)+i*h2(k)) mod 13 (i = 0, 1, …, 12)

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

四、(一)在一棵高度為 h (h = 0, 1, 2, …) 的 AVL tree 中：

(1)高度為6之 AVL tree 最多可能有幾個 nodes？最少可能有幾個nodes？（假設 root 之 h = 0）（6分）

(2)假設此樹共有45個 nodes。請問此 AVL tree 可能最高之高度及最矮之高度各為何？（6分）

(二)請將下列數字 {17, 60, 24, 5, 7} 逐步插入圖1的 AVL tree 中，並平衡之。（12分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

五、請利用堆積排序法 (Heap Sort) 將圖2逐步建立成 Min Heap，並將數字從小到大逐一列舉。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構分年題庫」詳解。

http://goods.ruten.com.tw/item/show?21512692236852

六、(一)請利用 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分）