|
102年公務人員特種考試關務人員考試、102年公務人員特種考試稅務人員考試、102年公務人員特種考試海岸巡防人員考試、102年公務人員特種考試移民行政人員考試、102年特種考試退除役軍人轉任公務人員考試及102年國軍上校以上軍官轉任公務人員考試試題 |
代號：13560 全一頁 |
等 別：三等關務人員考試
類(科)別：資訊處理
科 目：資料結構
考試時間：2小時 座號：______________
※注意：(一)禁止使用電子計算器。
(二)不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
一、關於時間複雜度 (time complexity)：
(一)下列那兩個敘述是錯的？（10分）
(A) 0.5n2+100n = O(n2) (B) 1000 = O(1) (C) 0.5n+5logn = O(n2)
(D) 2n2+5n = O(2n) (E) n7+1.5n = O(n7) (F) 3n2+nlog4n = O(nlog4n)
(二)承上，請把上題錯的敘述改正並且寫下。（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分）
答：
請到「露天拍賣」購買 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，加入資料。
(一)加入資料27。（6分）
(二)加入資料45。（6分）
(三)加入資料95。（6分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、函數 f(n) 定義如下，其中 n 為非負整數。
(一)請設計遞迴演算法，輸入非負整數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分）
答：
請到「露天拍賣」購買 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分）
答：
請到「露天拍賣」購買 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分）
答：
請到「露天拍賣」購買 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分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、(一)請設計一演算法，將一個二元樹 (binary tree) 每一節點之左子樹和右子樹對調 (swap)，如下圖4所示。（8分）
(二)假設一 n 個 nodes 之 k-ary tree (即分支度為 k 之樹) T，每一個 node 有一固定大小之欄位如下，請說明共有多少欄位是 Null？（8分）
答：
請到「露天拍賣」購買 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分）
答：
請到「露天拍賣」購買 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) 或原理可完成此動作？
答：
請到「露天拍賣」購買 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分）
答：
請到「露天拍賣」購買 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分）
答：
請到「露天拍賣」購買 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)2k-1 的形式，再採用數學歸納法來證明。）（15分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
三、Knuth，Morris 及Pratt 發明了一個快速的字串比對方法 (string pattern matching)。他們的方法採用一個失敗函數 (failure function)。失敗函數其實就是一個輔助的資料結構，用來加速比對。請依他們的方法計算下列字串的失敗函數。你必須說明失敗函數的定義為何，以及失敗函數如何加速比對。（15分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
四、請參考圖 2。每一條線段上的數字代表兩節點間的距離。請找出 a 節點到k 節點的最短路徑的長度。並請說明你的方法如何應用在非常大型的圖裡。（15分）
答：
請到「露天拍賣」購買 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分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
http://goods.ruten.com.tw/item/show?21442488728505
六、在一個二元樹裡有許多節點 (nodes)。假設每一個節點的資料結構如下圖：
其中 DATA 欄位為該節點的資料。LEFT 欄位為指向左方子樹的指標變數。RIGHT 欄位為指向右方子樹的指標變數。
如果節點 p 沒有左方子樹，其 LEFT 欄位為空指標 (null pointer)。同理，如果節點 p 沒有右方子樹，其 RIGHT 欄位為空指標 (null pointer)。
(一)如果一個二元樹有 n 個節點，那麼它有幾個空指標？（5分）
(二)我們可以利用原本是空指標的欄位來儲存引線 (threads)。二元樹加上引線的結果稱為引線樹 (threaded trees)。當然我們必須在各節點再加上兩個欄位 LTA 及 RTAG，共5個欄位，如下圖所示：
如果 LEFT 欄位代表一般的節點指標，則 LTAG = 0。如果 LEFT 欄位代表引線指標，則 LTAG = 1。同理，如果 RIGHT 欄位代表一般的節點指標，則 RTAG = 0。如果 RIGHT 欄位代表引線指標，則 RTAG = 1。
請將下圖的二元樹加上適當的引線指標，讓它變成引線樹，並請繪圖標出 A 到 I 共9個節點中所有引線指標指向的節點。（10分）
答：
請到「露天拍賣」購買 Jacksaleok 親自編寫的「資料結構筆記」。
留言列表
國考資訊處理解答 (7)
