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

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

二元搜尋法（binary search）是用來從排序好的資料陣列中尋找資料。假設n 筆資料 由小到大按照順序存在一維陣列A 中，且每一筆資料長度一樣。 請簡要描述二元搜尋法的原理。（5 分） 設 f (n) 為二元搜尋法的執行時間，請分析 f (n) 和n 的關係。提示：設n=2k， 且每次搜尋的資料筆數為前次的一半。（15 分）

抽象資料型態（Abstract Data Type；簡稱ADT）是利用資料結構來設計演算法的重 要基礎，請定義下列資料結構的ADT：（每小題5 分，共20 分） Heap（5 分） Binary Tree（5 分） 23 Tree（5 分） Set（5 分）

圖（graph）的表示法（Graph Representation） 以下面的無向圖（undirected graph）為例，說明圖的鄰接串列（adjacency list）表 示法。（10 分） 以下面的有向圖（directed graph）為例，說明圖的鄰接矩陣（adjacency matrix） 表示法。（5 分） 給一n 個節點（vertex）的有向圖G 的鄰接矩陣，請問計算圖G 的一個節點的出 分支度（out degree）的時間複雜度為何？（5 分） 給一n 個節點（vertex）的有向圖G 的鄰接矩陣，請簡述判斷圖G 是否連通 （connected）的演算法。（5 分）

假設一個含有十個不相等鍵值（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 分）

有一個一維陣列（array）A，內含6 個元素，分別為A[1]、⋯、A[6]。每個元素 含有兩個欄位：data 和next。欄位data 用來存放整數資料，欄位next 儲存索引 （index）用來鏈結下筆資料或空位。若next 的值為-1 表示鏈結結束。所有存入的 資料經由next 欄位串在一起，所有空位亦經由next 欄位串在一起。另外，有兩個 變數start 和avail，分別表示第一筆資料和第一個空位的位置。每次一個整數要儲 存時，便從avail 中取出第一個空位，把整數放入，並且插入到資料串內適當的位 置，而avail 則記錄下一個空位的位置。當一筆資料被刪除時，其元素變成第一個 空位，其後接原來的第一個空位，而資料相關位置不變。假設A 陣列經過多次儲存 和刪除後，其狀態如下所示： 此時，start = 4 表示第一筆資料存在A[4]中，下一筆在A[1]中，再下一筆在A[6]中。 而avail = 3 表示第一個可用的空位為A[3]，下一個可用的空位為A[5]，再下一個可 用的空位為A[2]。 將一筆新的資料40 存入A 中，其位置介於資料10 和50 之間。請畫出存入40 後 的狀態。（5 分） 承上題，將10 從A 中刪除，請畫出刪除後的狀態。（5 分） 承上題，將60 存入A 中，使其成為第一筆資料，請畫出存入後的狀態。（5 分） 承上題，請畫出將50 刪除後的狀態。（5 分） start ﹦4 avail ﹦3 index data next 10 20 50 6 -1 5 1 2 -1 1 2 3 4 5 6 A array 96 年公務人員、關務人員升官等考試試題 代號： 類 科： 資訊處理（公務）、資訊處理（關務） 36160 70560 全一張 （背面）

今有一存有n 個整數的陣列（array），請設計一個遞迴演算法來找出這些整數的最 大數和最小數。（20 分）

霍夫曼碼（Huffman code）是一種依照字母出現的頻率決定編碼的不定長二進位編 碼法（variable-length binary code）。 說明霍夫曼碼的編碼與解碼原理。（10 分） 假設字母集為 {甲、乙、丙、丁、戊、己}，個別字母出現頻率如下表。請填寫 每個字母的霍夫曼碼。（15 分） 字母 甲 乙 丙 丁 戊 己 出現頻率 45 13 12 16 9 5 霍夫曼碼

以下為前序追蹤（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 分）

已知有一棵二元搜尋樹（binary search tree）如下圖所示： 現有一數X，其值大於B 但小於H，將X 加入此樹，請畫出加入後的二元搜尋樹。 （5 分） 承上題，今欲將A 刪除，請畫出刪除後的二元搜尋樹。注意：我們規定一個數 被刪除後，會被其左子樹（left subtree）的最大數取代。（5 分） 承上題，請寫出此二元樹的中序追蹤（inorder traversal）為何？（5 分） 承上題，請寫出此二元樹的後序追蹤（postorder traversal）為何？（5 分）

佇列（Queue）和堆疊（Stack）是重要的資料結構，請利用兩個堆疊來設計一個佇 列（Queue）的Enqueue（ ）和Dequeue（ ）動作。並請分析你設計的Enqueue（ ）和 Dequeue（ ）的時間複雜度。（20 分）

費氏級數定義於下： ⎪⎩ ⎪⎨ ⎧ = = ≥ − + − = 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 年公務人員特種考試關務人員考試試題 代號： 科 別： 資訊處理 全一張 （背面） 50470

一個一維陣列A 的元素A[1]、A[2]、⋯、A[n]，可視為一個含有n 個節點（node） 的完全二元樹（complete binary tree），每個元素為一個節點。根節點（root）為 A[1]，且對任何一個節點A[k]，其子女（children）為A[2k]和A[2k+1]。 假設有8 個整數：95、55、70、90、30、65、80、85，依序存入A[1]至A[8]中。 利用父母－子女（parents-children）節點交換的方式，將此8 個整數所形成的完 全二元樹轉化為一個最小堆積（min-heap），並列出A[1]到A[8]的值。（15 分） 承上題，將最小整數30 刪除，並將A[8]放入A[1]中，利用父母－子女節點交換 的方式，將A[1]至A[7]調整成一個最小堆積，並列出A[1]到A[7]的值。（5 分）

請設計一個遞迴演算法來計算下列平方和的值: 2 2 2 1 2 ... 3 2 1 n i S n i + + + + = = ∑ = 注意：你的演算法可用SQ（n）函數來做平方的計算。（20 分）

1

下列為一個環狀串列（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 分）

有7 個數依序為70、250、180、100、20、190、200。 請將上述資料建成一棵3 次的B－樹（B-tree of order 3）。（15 分） 承上題，將70 從此樹刪除，請畫出刪除後的B－樹。假設一個數被刪除後， 會被其右子樹（right subtree）的最小數取代。（5 分） A B D H I E F C G

假設有一個二元搜尋樹（Binary Search Tree；簡稱BST），若a 和b 為此BST 所存 的兩個節點值，且a < b。請證明若將此BST 用中序法（inorder）印出節點值時，a 一定在b 之前印出。（20 分）

2 4 5 2 1 3 96 年公務人員高等考試三級考試試題 類 科： 資訊處理 全一張 （背面） 三、遞迴演算法（recursive algorithm） 令A 為N 個數的整數陣列（Integer array）。請用虛擬碼（Pseudo Code）描述求 陣列A 中最大值的遞迴演算法。（5 分） 令A 為N 個數的整數陣列（Integer array）。假設A 中的數字已經由小到大排列 好。請用儘量接近程式語言的虛擬碼（Pseudo Code）描述搜尋整數X 是否存在 陣列A 中的二元搜尋（Binary Search）的遞迴演算法（recursive algorithm）。請 說明此一搜尋法的時間複雜度。（10 分） 請用儘量接近程式語言的虛擬碼（pseudo code）描述計算費氏數列（Fibonacci numbers）第N 項的遞迴演算法。請問該遞迴演算法的時間複雜度（time complexity）是否為多項式時間（polynomial time）複雜度？（10 分） 四、堆積排序（Heap Sort） 堆積排序將堆積樹（heap tree）用一個陣列（array）A 儲存。陣列的指標（index） 從1 到N。請說明堆積樹的根（root）在陣列中的位置。請說明陣列（array）A 第 i 個位置A[i] 所儲存的堆積樹節點的左子節點（left child）、右子節點（right child）、以及父節點（parent）各自在陣列A 中的位置。（5 分） 在Max-堆積樹中，除了根節點（root）外，每一個節點所儲存的數小於或等於其 父節點所儲存的數。假設陣列A 儲存一個十個節點的Max-堆積樹。陣列A 中的 數字從第一個位置到第10 個位置所存數字依序為16, 14, 10, 8, 7, 9, 3, 2, 4, 1。請 畫出陣列A 所儲存的堆積樹以及各節點所儲存的數。（5 分） 請以儘量接近程式語言虛擬碼描述如何將一個不符合Max-堆積樹性質的陣列轉換 成符合Max-堆積樹性質的陣列。請分析你的演算法的時間複雜度。（15 分）