資訊處理 96 年資料結構考古題

假設我們要對一組訊息 AAAAABBCCCDDDDE 進行二進位數的編碼（Code） ㈠若每個字元編碼為相等長度，則此訊息進行編碼後，最少需多少位元？（10 分） ㈡若每個字元編碼為可變長度，則此訊息進行編碼後，最少需多少位元？（10 分）

假設一個含有十個不相等鍵值（Key）的檔案，每個鍵都有對應使用頻率如下： 鍵 （Key） 使用頻率 （%） K1 5 K2 10 K3 5 K4 20 K5 25 K6 5 K7 10 K8 5 K9 5 K10 10 ㈠若使用循序搜尋法（Sequential Search），試問搜尋一個鍵值（Key）的平均比 較次數（Average Number of Comparisons）為多少？（10 分） ㈡若想有效減少平均比較次數，這些鍵值應重新安排（Arrangement），經過重新安 排之後，試問其平均比較次數為多少？（10 分）

以下為前序追蹤（Preorder Traversal）及後序追蹤（Postorder Traversal）的順序 前序追蹤順序：M, N, I, A, H, B, C, J, G, F, K, L, E, D, Y 後序追蹤順序：A, B, C, H, I, G, F, J, N, E, D, L, Y, K, M ㈠請畫出此二元樹。（10 分） ㈡請寫出此二元樹的中序追蹤（Inorder Traversal）順序。（10 分）

費氏級數定義於下： ⎪⎩ ⎪⎨ ⎧ = = ≥ − + − = 0 N if , 0 1 N if , 1 2 N if , 2) F(N 1) F(N F(N) ㈠試求算F(5)的值。（5 分） ㈡計算F(5)的值需呼叫函數的次數。（5 分） ㈢計算F(5)的值需加法運算的次數。（5 分） 96 年公務人員特種考試關務人員考試試題 科 別： 資訊處理

下列為一個環狀串列（Circular Queue）中加入與刪除一個元素的演算法： Procedure ADDQ(item,Q,n,front,rear) rear←(rear+1) mod n if front=rear then call QUEUE_FULL Q(rear)←item end ADDQ Procedure DELETEQ(item,Q,n,front,rear) if front=rear then call QUEUE_EMPTY front←(front+1) mod n item←Q(front) end DELETEQ ㈠在演算法ADDQ 中當front=rear 時發生溢位（Overflow），實際上還有一個空間， 請說明為何不使用呢？（5 分） ㈡若欲使用此一空間，則ADDQ 及DELETEQ 應如何改寫，試寫出他們修改後的 ADDQ 及DELETEQ 演算法。（20 分）