加載中. ..
PDF
102年公務人員特種考試外交領事人員及外交行政人員
考試、102年公務人員特種考試法務部調查局調查人員
考試、102年公務人員特種考試國家安全局國家安全情
報人員考試、102年公務人員特種考試民航人員考試、
102年公務人員特種考試經濟部專利商標審查人員考試試題
代號：70360
考 試 別： 專利商標審查人員
等 別： 三等考試
類 科 組： 資訊工程
科 目： 資料結構（包括資料庫）
考試時間： 2小時 座號：
※注意：
禁止使用電子計算器。
不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。
全一頁
一、
請使用 C或Java 語言，寫一遞迴（recursive）副程式，此副程式的輸入為一個未
排序的（unsorted）且長度為 n的整數陣列 A[0:n−1]，副程式將在此整數陣列中，
以遞迴的方式，尋找此整數陣列中的最大值，並回傳此最大值。（15 分）
請分析
此副程式的時間複雜度以 order 的方式表示。（5分）（注意：不可將此陣列數值進
行排序，請加註解說明程式碼作法）。
二、一個二元樹（binary tree）的中序尋訪序列（inorder traversal）為 DEBGFHAIJCK，
而其前序尋訪序列（preorder traversal）為 ABDEFGHCIJK。
請繪出此二元樹。
（10 分）
列出此二元樹之後序尋訪序列（postorder traversal）。（5分）
列出
此二元樹階層尋訪序列（level order traversal or breadth first search traversal）。（5分）
三、
請設計一個 Greedy 的演算法，來解決一個圖形著色的問題。使用最少的顏色，
對一個圖形（Graph）上的所有頂點（vertex）進行著色（coloring），使得任兩個相
連（鄰）的頂點，不著相同的顏色。（15 分）
請問你的 Greedy 演算法的解法是
否能保證永遠為最佳解？試舉例說明。（5分）
四、
何謂巨量資料（Big Data），試舉兩個實例說明，商業上如何應用巨量資料。
（10 分）
試各舉一個實例說明，擴增實境（Augmented Reality）與虛擬實境（Virtual
Reality），並比較其不同。（10 分）
五、
請使用霍夫曼編碼（Huffman code）技術，將一英文字母字串“AACSBSABAGG”
編碼成一個 01 字元字串，使得編碼後的字串長度最短。請繪出其霍夫曼編碼樹
（Huffman coding tree）並列出霍夫曼編碼表。（12 分）
一霍夫曼編碼表如下：
A: 01 B: 10 C:111 D:00 E:110
請將 01 字元字串“011011010001110000011100111110”解碼成原始的英文字母字串。
（8分）