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

假設三維陣列 Ｘ[3:10, 4:15, 5:20] 的第一個元素在記憶體的位址是200。假設每個元 素佔4 個位元組（bytes），那麼當採用以行為主（column-major）時， X[5, 7, 10] 之 位址為何？（20 分）

某函數F 以遞迴的方式定義如下： a , b 均為自然數  F(a , b) = 0, 如果a＜ b  F(a , b) = F(a－b , b)＋1, 如果a b ≧ 試求F(88 , 7)的函數值？（5 分） 試說明F(a , b)函數的功能為何？（5 分）

用一維陣列A[1.. k×52]表示由k 副相同的撲克牌組成的一疊撲克牌。試寫一段程式將 這疊撲克牌排序，其順序為A <2<3< …< 10 <J <Q <K，當大小相同時則♣<♦<♥<♠， 並分析其時間複雜度（time complexity）。（20 分）

寫出累堆排序法（Heap Sort）的演算法。（10 分） 針對輸入數列（53、26、41、18、35、10、55、45、9、21），寫出排序過程。（10 分）

已知某二元樹（binary tree）之後序（postorder）追蹤（traversal）為F H I G D E B C A； 中序（inorder）追蹤為F D H G I B E A C； 試畫出此二元樹。（15 分） 此二元樹之前序（Preorder）追蹤為何？（5 分）

有三個堆疊A，B，C，其中堆疊A 已有資料4,3,2,1 由大到小排列，堆疊B 與C 是 空的（如下圖）。堆疊的運算為： Push(V, X)：將變數V 中的資料加入堆疊X，其中X 為A，B，C。 Pop(V, X)：取出堆疊X 中的資料放到變數V，其中X 為A，B，C。 寫出一序列的堆疊運算將堆疊A 的資料保持原有順序搬移到堆疊B。（5 分） 設定在資料搬移過程中，堆疊A，B，C 的資料都保持由大到小排列。寫出一序 列的堆疊運算將堆疊A 的資料保持原有順序搬移到堆疊B。（5 分） 如堆疊A 中有n 筆資料n, n-1, n-2, …, 1 由大到小排列，寫一遞迴程式將堆疊A 中的資料保持原有順序搬動到堆疊B，且資料搬移過程中，堆疊A，B，C 的資 料都保持由大到小排列。（10 分）

有一遞迴函數如下： int f(int n) { if (n < 3) return n; else return f(n-3) + f(n-2) + f(n-1); } 以f(9) 叫用之，將傳回值多少？（5 分） 令函數g(n) 為計算f(n) 時需呼叫f(0) 的次數，試寫出g(n) 的遞迴關係 （recurrence relation）。（10 分） 函數g(9) 的值為何？（5 分）

有一雜湊函數（hashing function）H 表示如下：  H(id)＝ id, 如果id＜m  H(id) = (id)3 mod m, 如果id ≧m 其中id 是紀錄的鍵值，m 是記憶區大小。 現有兩個紀錄，其紀錄的鍵值分別為15 及30，又記憶區分為23 個區域。 試問上述兩個紀錄在記憶體的第幾個區域？是否有碰撞（collision）產生？（10 分） 試說明一般解決碰撞的方法為何？（10 分）

可合併堆積（mergable heap）是一種抽象的資料結構，支援五個資料結構運算： Make-Heap：造一個空的可合併堆積。 Insert：插入一新鍵值到可合併堆積。 Minimum：報告可合併堆積中的最小鍵值。 Extract-Min：將可合併堆積中的最小鍵值從堆積中移除。 Union：將兩個可合併堆積合成一個可合併堆積。 試用有序串列（sorted linked list）來實作一個可合併堆積。請敘明你所知達成各個運 算最有效率的演算法並分析其最差情形的時間複雜度（worst-case time complexity）。 （20 分） A B C 1 2 3

假設編碼系統中有A、B、C、D、E、F 等符號，其出現機率依序為 0.43, 0.13, 0.12, 0.18, 0.08, 0.06， 請依據此畫出霍夫曼樹（Huffman tree）並設計一套霍夫曼碼（Huffman code），並依 此所設計的霍夫曼碼將011000001000111010011 進行解碼。（20 分）

給予資料序列，依序為25, 37, 52, 68, 16, 43, 9； 試將上述資料建成二元搜尋樹（binary searching tree）。（5 分） 利用所建二元搜尋樹將資料由大而小排序，請詳明方法。（10 分） 試將上述資料建成最大堆積樹（max heap）。（5 分） 請逐步列出堆積排序（heap sort）每一次調整後的堆積（heap）。（10 分） 94 年公務人員升官等考試、94 年關務人員升官等考試試題 代號： 科 別： 資訊工程、資訊處理（公務）、資訊處理（關務） 全一張 （背面） 38350 38550 70550

94 年交通事業鐵路人員、公路人員升資考試試題 代號： 級 別： 員級晉高員級 科 別： 公路：資訊管理、資訊處理 全一張 （背面） 40430 41730 四、有一網路圖如下，邊上的值為邊的長度。 試用Prim 演算法由端點a 出發找出其最小生成樹（minimum spanning tree）。（請 寫出演算過程）（10 分） 試用Kruskal 演算法找出其最小生成樹。（請寫出演算過程）（10 分）

如下圖以頂點0 為啟始點，找出其深度優先展開樹（Depth-first Spanning Tree）並計 算出其成本（cost）。（20 分） 0 1

有一加權圖形（weighted graph）如圖一所示， 運用Kruskal 方法，逐步畫出最小成本擴張樹（minimum cost spanning tree）。（15 分） 並計算從A 頂點到其他各頂點的最低成本。（5 分） A B C D E G I F H 7 5 5 9 7 9 8 5 7 3

將下列十二個鍵值： 15, 3, 5, 17, 10, 8, 6, 2, 14, 16, 18, 9 依序插入一空的B-tree 中，此B-tree 中的節點至少含一個鍵值，至多含三個鍵值。（20 分） 12 14 10 11 11 g h j p e i f m n a d b c k 9 5 2 9

5 4 3 28 16 12 18 22 25 14 24 2 10

4 8 圖一 加權圖形

8 4 6

5 9

4 4 7

5 9 7 5 7

5 7 9 6 7 2