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

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

102年公務人員特種考試關務人員考試、102年公務人員特種考試稅務人員考試、102年公務人員特種考試海岸巡防人員考試、102年公務人員特種考試移民行政人員考試、102年特種考試退除役軍人轉任公務人員考試及102年國軍上校以上軍官轉任公務人員考試試題

代號：13560 全一頁

等別：三等關務人員考試

類(科)別：資訊處理

科目：資料結構

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

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

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

一、關於時間複雜度 (time complexity)：

(一)下列那兩個敘述是錯的？（10分）

(A) 0.5n²+100n = O(n²) (B) 1000 = O(1) (C) 0.5n+5logn = O(n²)

(D) 2n²+5ⁿ = O(2ⁿ) (E) n⁷+1.5ⁿ = O(n⁷) (F) 3n²+nlog⁴n = O(nlog⁴n)

(二)承上，請把上題錯的敘述改正並且寫下。（20分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

二、已知一棵二元樹 (binary tree) 的前序走訪 (preorder traversal) 與中序走訪(inorder traversal) 之結果分別如下：（每小題10分，共20分）

前序－A B D E G H C F I

中序－D B G E H A C I F

(一)請繪出這棵二元樹。

(二)這棵二元樹的後序走訪 (postorder traversal) 結果為何？

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

三、請找出並且從小到大依序列出下列有向圖 (directed graph) 中，從頂點 A 到所有其他頂點的最短路徑 (path) 與路徑長度。（20分）

undefined

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

四、考慮排序 (sort) 的問題：（每小題10分，共30分）

(一)如果要排序的資料很少，例如只有十幾筆資料，那麼你將採用快速排序法 (quick sort)？合併排序法 (merge sort)？還是氣泡排序法 (bubble sort)？為什麼？

(二)如果要排序的資料很多，例如多到超過主記憶體容量許多，那麼你將採用快速排序法？合併排序法？還是氣泡排序法？為什麼？

(三)快速排序法、合併排序法以及氣泡排序法這三個排序法當中，那一 (些)排序法是穩定的 (stable)？或者都不穩定？

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

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

102年公務人員高等考試三級考試試題代號：36250 全一張

類科：資訊處理

科目：資料結構

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

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

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

一、將整數資料80, 40, 19, 120, 94, 110, 115, 90, 88, 92, 98 依序存入一棵空的二元搜尋樹 (binary search tree)。

(一)請畫出完成資料輸入的二元搜尋樹。（6分）

(二)從(一)產生的二元搜尋樹中刪除 (delete) 資料94，請畫出完成刪除動作後的二元搜尋樹。（給出一個正確樹即可）（6分）

(三)請寫出自二元搜尋樹找到最大值資料所在節點 (node) 的演算法。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

二、請寫出執行下列程式碼的時間複雜度，並敘明理由。（10分）

for (i = 1; i < n; i++){

a = 1;

b = n;

while( a < b ){

a = 3 * a;

b = b / 3;

}

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

三、下圖為一 AVL 樹 T，請依各小題要求加入指定新資料後，畫出新產生的AVL 樹。每小題各自獨立，都是對原先的 AVL 樹 T，加入資料。

undefined

(一)加入資料27。（6分）

(二)加入資料45。（6分）

(三)加入資料95。（6分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

四、函數 f(n) 定義如下，其中 n 為非負整數。

undefined

(一)請設計遞迴演算法，輸入非負整數n，輸出 f(n) 數值。（7 分）

(二)請設計非遞迴演算法，輸入非負整數n，輸出 f(n) 數值。（7 分）

(三)請分別說明(一)與(二)所設計演算法的時間複雜度 (time complexit)。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

五、(一)依據下圖內容，請寫出它的相鄰矩陣 (adjacency matrix) 表示法。（4分）

(二)請定義生成樹 (spanning tree)。（6分）

(三)請畫出此圖的最小成本生成樹 (minimum cost spanning tree)，以及計算最小成本。（10分）

undefined

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

六、有一雜湊表格 (hash table) T 的記憶空間共含11 個桶 (buckets)，位址編號由0至10，每個桶有一個槽 (slot)。雜湊函數 h1 定義為 h1(key) = key% 11，當有碰撞 (collision) 發生時採二次雜湊開放定址法 (open addressing with double hashing) 處理，其函數定義為 h(key, j) = (h1(key)+j*h2(key))% 11，其中 j 為碰撞次數，j = 1, 2, 3, ..., 11，h2(key) = 1+(key%10)。欲將26放入雜湊表格 T，總共經過6次探測才成功找到存放位址。請問26在雜湊表格 T 的探測順序為何？（6分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

[一○二年檢察事務官三等資料結構]

102年公務人員特種考試司法人員考試試題代號：30960 全一張

等別：三等考試

類科：檢察事務官電子資訊組

科目：資料結構

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

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

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

一、(一)假設有8個排序好的數列 (如圖1)，請建構一 loser tree 並顯示取出前4 個最小值之 loser tree 變化。（16分）

(二)請說明 loser tree 和 winner tree 差異為何？（4分）

undefined

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

二、(一)請利用 dfn (depth-first number) 及 low (the lowest depth-first number) 值，找出圖2所有之關節點 (articulation points)。假設利用深度優先搜尋法 (depth first search) 讀取節點之順序為 4-2-1-3-5-6-8-9-7，也就是節點4之 dfn 值為1，節點2之 dfn 值為2，節點1之dfn 值為3，依此類推。（15分）

(二)請說明如何判斷那一節點為關節點？low 計算之公式為何？（5分）

undefined

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

三、給一稀疏矩陣 (sparse matrix) M 如圖3所示。

(一)請以 3-tuple form (i, j, value) 來表示此矩陣 M。（6分）

(二)針對(一)之3-tuple form，請設計一有效率而時間複雜度不大於 O (columns+terms) 之快速矩陣轉置 (fast matrix transposing) 演算法。其中 columns 為欄的數目，terms 為非零項目的數目。以圖3所示，columns = 4、terms = 6。（14分）

undefined

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

四、(一)請設計一演算法，將一個二元樹 (binary tree) 每一節點之左子樹和右子樹對調 (swap)，如下圖4所示。（8分）

(二)假設一 n 個 nodes 之 k-ary tree (即分支度為 k 之樹) T，每一個 node 有一固定大小之欄位如下，請說明共有多少欄位是 Null？（8分）

undefined

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

五、(一)請說明紅黑樹 (red-black tree) 之特性。（4分）

(二)建立一紅黑樹，其數字依序為10、72、14、68、20、58、30、50、65、63。（10分）

(三)請一步一步刪除圖5紅黑樹之節點，依序為10、18、3、16、13、12、17。其中在圖5之節點7、12、20 為紅色節點。（10分）

undefined

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

[一○二年專利商標審查人員三等資料結構]

102年公務人員特種考試外交領事人員及外交行政人員考試、102年公務人員特種考試法務部調查局調查人員考試、102年公務人員特種考試國家安全局國家安全情報人員考試、102年公務人員特種考試民航人員考試、102年公務人員特種考試經濟部專利商標審查人員考試試題

代號：70360 全一頁

考試別：專利商標審查人員

等別：三等考試

類科組：資訊工程

科目：資料結構（包括資料庫）

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

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

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

一、(一)請使用 C 或 Java 語言，寫一遞迴 (recursive) 副程式，此副程式的輸入為一個未排序的 (unsorted) 且長度為 n 的整數陣列 A[0:n-1]，副程式將在此整數陣列中，以遞迴的方式，尋找此整數陣列中的最大值，並回傳此最大值。（15分）(二)請分析此副程式的時間複雜度以 order 的方式表示。（5分）（注意：不可將此陣列數值進行排序，請加註解說明程式碼作法）。

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

二、一個二元樹 (binary tree) 的中序尋訪序列 (inorder traversal) 為DEBGFHAIJCK，而其前序尋訪序列 (preorder traversal) 為ABDEFGHCIJK。(一)請繪出此二元樹。（10分）(二)列出此二元樹之後序尋訪序列 (postorder traversal)。（5分）(三)列出此二元樹階層尋訪序列 (level order traversal or breadth first search traversal)。（5分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

三、(一)請設計一個 Greedy 的演算法，來解決一個圖形著色的問題。使用最少的顏色，對一個圖形 (Graph) 上的所有頂點 (vertex) 進行著色 (coloring)，使得任兩個相連 (鄰) 的頂點，不著相同的顏色。（15分）(二)請問你的 Greedy 演算法的解法是否能保證永遠為最佳解？試舉例說明。（5分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

四、(一)何謂巨量資料 (Big Data)，試舉兩個實例說明，商業上如何應用巨量資料。（10分）

(二)試各舉一個實例說明，擴增實境 (Augmented Reality) 與虛擬實境 (Virtual Reality)，並比較其不同。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

五、(一)請使用霍夫曼編碼 (Huffman code) 技術，將一英文字母字串“AACSBSABAGG” 編碼成一個01字元字串，使得編碼後的字串長度最短。請繪出其霍夫曼編碼樹 (Huffman coding tree) 並列出霍夫曼編碼表。（12分）

(二)一霍夫曼編碼表如下：

A:01 B:10 C:111 D:00 E:110

請將01字元字串“011011010001110000011100111110”解碼成原始的英文字母字串。（8分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

[一○二年關務人員升官等薦任資料結構]

102年公務人員升官等考試、102年關務人員升官等考試代號：26260 全一張

102年交通事業郵政、港務、公路人員升資考試試題

等別(級)：薦任

類科(別)：資訊處理

科目：資料結構

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

※注意：(一)可以使用電子計算器。

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

一、解釋名詞：（每小題5分，共20分）

(一)資料結構 (data structure)

(二)資料型態 (data type)

(三)陣列 (array)

(四)堆積樹 (heap tree)

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

二、請使用陣列實作堆疊，給予如下 C 程式語言有關堆疊結構的宣告：

#define MAX_STACK 100;

typedef int ITEM_TYPE;

typedef struct stack_type {

ITEM_TYPE item[MAX_STACK];

int top;

} STACK_TYPE;

其中ITEM_TYPE 可以是0, 1, 2等的整數值，可以定義成整數、字元等各種不同的資料型態；請用C 語言或類似虛擬語言 (pseudo code) 實作如下兩個堆疊之運算：（每小題10分，共20分）

(一)void push(STACK_TYPE *stack, ITEM_TYPE new_item); /* 將 new_item 加到堆疊頂端 */

(二)void pop(STACK_TYPE *stack, ITEM_TYPE *old_item); /* 將堆疊頂端資料移出，並放在 old_item */

一開始，設定 stack->top = -1；表示堆疊是空的。（註：符號 stack->top 指到堆疊頂端，stack->item [stack -> top] 是堆疊頂端的資料）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

三、(一)給予如下資料：12, 8, 17, 4, 26, 6, 11，請將這些資料建成一個二元搜尋樹 (Binary Search Tree)；如何利用此 binary search tree 來做資料之排序。（10分）

(二)有一個二元搜尋樹，其結構不清楚，節點的值為1到10000，當搜尋 “2013” 的值時，拜訪的節點值依序為：1396, 7248, k, 1523, 1865, 3152, 2013，請問 k 值的範圍為何？（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

四、假設一生物 DNA 序列由 a, e, i, s, t, b, 和 n 基本單元所構成。已知某一微生物 DNA 序列之每一基本單元在此序列中出現之頻率如下：a, 10次；e, 15 次；i, 12次；s, 3次；t, 4次；b, 13次；n, 1次。請設計一最佳編碼表編碼此序列，並計算出最小之編碼位元數。（20分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

五、給予如下之 Weighted Graph G：（每小題10分，共20分）

(一)利用 Kruskal’s algorithm 來找最小擴張樹 (Minimal spanning tree)。

(二)在演算法中有一動作：選擇一最低成本的邊 (edge)，加入此邊 (edge)，如不形成一迴圈 (cycle)，則加入此邊至最小擴張樹，請問運用何運算(operations) 或原理可完成此動作？

undefined

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

[一○二年資訊技師高等資料結構]

102年專門職業及技術人員高等考試建築師、技師、第二次代號：01310全一張

食品技師考試暨普通考試不動產經紀人、記帳士考試試題

等別：高等考試

類科：資訊技師

科目：資料結構（包括資料庫）

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

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

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

一、(一)假設要搜尋已排序的陣列 list[left], list[left+1], ..., list[right]，請完成下列二分搜尋 (Binary Search) 法的遞移 (iterative) C 語言程式，其中searchnum 代表要搜尋的資料。（10分）

int binsearch(int list[ ], int serachnum, int left, int right)

{ int middle;

while( (a) )

{ middle = (left + right) / 2;

if( list[middle] == searchnum) return ( (b) ) ;

else if( list[middle] < searchnum ) ( (c) ) ;

else ( (d) ) ;

} return ( (e) ) ; /* 找不到資料 */

(二)假設陣列 list 全部資料有 n 筆，用 Big-O 表示並說明循序搜尋(Sequential Search) 法與二分搜尋法這兩個演算法在最差情況 (worst case) 的時間複雜度。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

二、(一)有8筆資料 26, 05, 77, 01, 61, 11, 59, 15 要排序，請寫出合併排序(mergesort) 法前二回合 (pass) 的結果。（10分）

(二)假設陣列全部資料有 n 筆，用 Big-O 表示並說明快速排序 (quicksort)法在最差情況 (worst case) 的時間複雜度。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

三、(一)一棵二元樹 (Binary Tree) 以前序追蹤 (preorder traversal) 為FDAGICBEJH，以中序追蹤 (inorder traversal) 為 ADIGCFEJBH，則其後序追蹤 (postorder traversal) 為何？（10分）

(二)如果一棵樹其節點 (node) 的兒子數可以為任意個數 (超過兩個，非二元樹)，例如說20個兒子，請說明該如何設計其每一節點的資料結構。為什麼要如此設計？（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

四、(一)請寫出 Dijkstra 演算法找出一點到所有點的最短距離。（10分）

(二)請用 Dijkstra 演算法找出如圖所示點 a 到所有點的最短距離。（10分）

undefined

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

五、資料庫 (database) 中第二正規格式 (second normal form) 是要去除什麼？如果沒有做這個正規化，在更新 (update) 資料庫時要如何更新？否則會造成什麼異常狀況？（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

六、試說明資料庫的階層式與關連式資料模式 (Data Model)。（10分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

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

102年特種考試地方政府公務人員考試試題代號：34180 全三頁

等別：三等考試

類科：資訊處理

科目：資料結構

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

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

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

一、請參考圖1：

(一)由 a 點出發，做 depth-first traversal (深度優先拜訪)，請問那些節點(node) 不會被訪問到？（3分）

(二)由a 點出發，做 breadth-first traversal (寬度優先拜訪)，請問那些節點(node) 不會被訪問到？（2分）

(三)假設圖1 代表 heap 上各個節點 (node) 及其相互指向的關係。p、q、r 三節點代表全域變數 (global variables)，其他的節點代表 heap 上的記憶體區塊。如果 p→a 的指標被消除，那些節點會變成無用的垃圾節點？你必須詳細描述尋找垃圾節點的方法及所需之資料結構。你的演算法只能從 a 節點出發，它必須指出所有的垃圾節點，並且你的演算法只能在每一個節點儲存很少量的資料。請問你的演算法必須在每一個節點儲存那些資料？（15分）

undefined

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

二、定義如下的函數 F：

如果 x 是偶數，則 F(x) = x/2;

否則 F(x) = F(F(3x+1))

(一)請問 F(11) =？（5分）

(二)請證明對於任何正整數 w，我們都可以在有限時間內計算 F(w)。（提示：每個奇數可以寫成 (2i+1)2^k-1 的形式，再採用數學歸納法來證明。）（15分）

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

三、Knuth，Morris 及Pratt 發明了一個快速的字串比對方法 (string pattern matching)。他們的方法採用一個失敗函數 (failure function)。失敗函數其實就是一個輔助的資料結構，用來加速比對。請依他們的方法計算下列字串的失敗函數。你必須說明失敗函數的定義為何，以及失敗函數如何加速比對。（15分）

undefined

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

四、請參考圖 2。每一條線段上的數字代表兩節點間的距離。請找出 a 節點到k 節點的最短路徑的長度。並請說明你的方法如何應用在非常大型的圖裡。（15分）

undefined

答：

請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。

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

五、請參考圖3。圖3是一個 activity-on-edge 網路。在 activity-on-edge 網路中，一項計畫可以分成很多件工作，每一件工作由一條線段代表，線段上的數字代表該工作所需的時間 (以工作日為單位)，線段的箭頭代表工作的先後關係。例如在圖3中，ab 及db 線段代表的工作完成之後，bc、be、及bf 線段代表的工作才可以開始進行，其他的先後關係依此類推。a 節點是起點，k 節點是全部工作的完成點。請找出 k 節點的最早完成時間及關鍵路線 (critical path)。並請說明你的方法如何應用在非常大型的圖裡。（15分）