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

100年公務人員特種考試海岸巡防人員考試、100年公務 人員特種考試關務人員考試、100年公務人員特種考試稅 務人員考試、100年特種考試退除役軍人轉任公務人員考 試及100年國軍上校以上軍官轉任公務人員考試試題 類(科)別： 資訊處理 考試時間： 2 小時 座號： 不必抄題，作答時請將試題題號及答案依照順序寫在試卷上，於本試題上作答者，不予計分。 （請接背面） 全一張 （正面） 、下圖為二元搜尋樹（binary search tree），請回答下列問題：（每小題5 分，共30 分） 一 70 50 35 的successor 為何？ 50 的successor 為何？ 寫出Entry<E> successor(Entry<E> e) 的pseudo code。 寫出preorder traversal。 寫出postorder traversal。 寫出inorder traversal。 二、下圖為min heap，請回答下列問題：（25 分） 10 15 21 19 30 50 畫出min heap 實際上在大小為10 的array 中的data structure。 insert 11 至min heap 之後， 1.畫出insert 後的tree-like min heap。 2.畫出其array data structure。 承上，再delete root 且向left sub-tree 調整， 1.畫出調整後的tree-like min heap。 2.畫出其array data structure。 80 60 20 10 30 55 35 100年公務人員特種考試海岸巡防人員考試、100年公務 人員特種考試關務人員考試、100年公務人員特種考試稅 務人員考試、100年特種考試退除役軍人轉任公務人員考 試及100年國軍上校以上軍官轉任公務人員考試試題 類(科)別： 資訊處理 全一張 （背面） 題組：請根據下圖回答第三至五題： 圖中表示有4 個朋友，名（name）叫張三（Chang San, CS）、李四（Lee Si, LS）、 王五（Wang Wu, WW）及趙六（Chao Liu, CL），用兩個字母代表各人，如CS 代表 張三，並標示兩兩住家交通狀況及距離（distance），如張三家有7 公里的路到李四 家。 hash function：h(name) = int (1st char of name)*31+int(2nd char of name) hash table size：11 (index 0 - 10) index：h(name) mod 11 int( “C” )=67, int( “S” )=83, int( “L” )=76, int( “W” )=87 舉張三為例： index( “CS” )=(int( “C” )*31+int( “S” )) mod 11 = (67*31+83) mod 11 = 4 三、用HashMap <Name, LinkedList <NameDistancePair>> 的Java data structure 畫出此 directed weighted graph。（15 分） 四、找出張三到王五的Dijkstra’s Shortest Path，要畫出3 個data structures: 1. weight sum 2. predecessor 3. priority queue 的最後結果。（15 分） 五、找出以張三為root 的Prim’s Minimal Spanning Tree，要畫出1. tree 2. priority queue 2 個data structures 的最後結果。（15 分）

複雜度big-Oh O的定義為：f(n) = O(g(n)) 若且唯若存在一實數c＞0 和一整數n0＞0，使 得對所有整數n≧n0，f(n) ≦ cg(n)皆成立。假設有如下的程式： 1. Procedure Sum(A, n) 2. sum = 0; 3. i = 0; 4. while(i< n) { 5. sum Å sum + A[i]; 6. i = i+1; } 7. return sum; 設敘述2 執行一次需1 個單位時間，敘述3 執行一次需1 個單位時間，敘述4 執行 一次需2 個單位時間，敘述5 執行一次需3 個單位時間，敘述6 執行一次需2 個單 位時間，敘述7 執行一次需1 個單位時間。 對一個含n 個元素的陣列A，執行呼叫Sum(A, n)需要花多少個單位時間？（註： 只需計算敘述2-7 所花的時間即可。）（5 分） 此程式之時間複雜度（time complexity）為何？以big-Oh 表示之，並請用上述的 定義證明答案的正確性。（註：無證明者此小題不給分。）（10 分） 若A 含有八個整數 60, 5, 25, 20, 35, 10, 15, 85，請問呼叫Sum(A, 8)的回傳值為何？ （5 分）

0 1 0 0 0 0 1 0 0 0 0 1 0 3

N為問題大小，K為大於1 的常數。請以Big-O方式比較以下時間複雜度（Time complexity）的大小：log(N)K Klog(N) log(N)*log(log(N)K) Nlog(N) log(NN) log(N)N（10 分）

假設有一整數資料陣列 B[0..7]，裡面儲存8 個整數數值分別為{25, 57, 86, 37, 12, 92, 48, 33}。今欲對此陣列進行由小到大排序： 試寫出氣泡浮昇排序（bubble sort）演算法或函式。（10 分） 將排序過程中每一回合（iteration）陣列內容的變化情形寫出。（10 分）

假設有一個雙鏈結串列（doubly-linked list）L，如圖1 所示。此串列中的每一個節 點（node）有三個欄位：前指指標、存放的資料、後指指標。此外，有一個header 存放指到第一個節點的指標（pointer），有一個trailer 存放指到最後一個節點的指 標。節點中的前指指標指到上一個節點或header，後指指標指到下一個節點或 trailer。如圖1 所示，header 的位址是800，trailer 的位址是150，存放BMI 資料的 節點的位址是600，存放PVD 資料的節點的位址是300，存放JFK 資料的節點的位 址是700，存放SFO 資料的節點的位址是1100。 將資料NYU 插入在存放JFK 資料的節點 之前，且此新節點的位址是850。請畫出 插入後的L。（5 分） 圖1 續前，將存放JFK 資料的節點刪除。請畫 出刪除後的L。（5 分） 續前，將資料KAH 插入並成為第一個節點， 且此新節點的位址是400。請畫出插入後 的L。（5 分） 續前，將L 的最後一個節點刪除。請畫出 刪除後的L。（5 分） 100 年公務人員升官等考試、100 年關務人員升官等考試試題 代號：36160 類 科： 資訊處理 全一張 （背面）

1 0

輸入運算式（expression）為-A-(B+C)*D^E，請畫出其對應之運算樹（expression tree）。（10 分）

假設鏈結串列（linked list）資料結構的宣告如下： struct node { char info; struct node *next; } *list; 試寫一函式（function）計算並回傳鏈結串列 list 內部節點（node）之數量。 （10 分） 試寫一函式（function）將鏈結串列list 進行反轉（inverse）。（10 分）

假設有10 個整數 42, 22, 32, 74, 47, 52, 94, 29, 40, 58，請利用雜湊（hash）函數 h(k) = k%11 及線性探測（linear probing）碰撞解決法，建立一個11 個元素的雜湊表 （hash table）。（註：a%b 是表示a 除以b 的餘數。） 請畫出此雜湊表。（10 分） 將22 刪除，請畫出刪除後的雜湊表。（10 分）

2 1 0 一、下列矩陣為代表某圖形（graph）的相鄰矩陣（adjacency matrix）：（20 分） 請畫出該圖。 請列出該圖長度為2 之路徑矩陣（path matrix of length 2）。 何謂遞移封閉矩陣（transitive closure matrix）？請以該圖為例說明如何求其遞移 封閉矩陣。 何謂反射遞移封閉矩陣（reflexive transitive closure matrix）？請列出該圖之反射 遞移封閉矩陣。 二、請使用霍夫曼演算法（the Huffman algorithm）編碼下列字串 （20 分） AEACABDBDB 列出霍夫曼樹（the Huffman tree：產生該樹時請以字母順序較前者列於左子樹為 原則）。 列出各字母之編碼。 寫出該字串之編碼。 三、從一個空的AVL 樹（AVL tree）開始依序執行以下的插入：MAR、MAY、NOV、 AUG、APR、JAN、DEC、JULY、FEB。在每次插入後繪出AVL 樹，並註明每一 次插入時所使用的旋轉類型（如果有的話）。（20 分）

輸入中序(in-order)表示之運算式A*(B+C)，可以根據運算元優先次序關係，使用堆 疊(stack)來產生其後序(post-order)表示之運算式。請依演算法追蹤其執行情形，完 成如下表格。（10 分） 輸入 堆疊內容 輸出 A *

依序輸入一組整數資料{25, 57, 86, 37, 12, 92, 48, 33}並建立出二元搜尋樹（binary search tree）。 說明對二元搜尋樹（binary search tree）加入一筆資料的方法為何？（10 分） 請畫出所建立之二元搜尋樹（binary search tree）。（10 分）

圖2 為一個圖型（graph）。 請利用廣度優先搜尋法（breadth-first search, BFS），從節點c 開始，列出此圖型 的所有節點。請將字元較小的節點優先列出。（10 分） 請利用深度優先搜尋法（depth-first search, DFS），從節點c 開始，列出此圖型的 所有節點。請將字元較小的節點優先列出。（10 分） 圖2

請分別依如下要求畫出下列資料的查找樹（tries）：（20 分） SYKHOI 、MUSTANG 、AMIOT 、MARAUDER 、HELLDIVER 、MACCHI 、 HEINKEL、AVENGER、SPITFIRE、AVRO 由左到右一次抽樣一個字元不限定階數。 由右到左一次抽樣一個字元限定階數為3。 利用單一字元抽樣法找出一個階數最少的查找樹。

我們可以使用KMP（Knuth, Morris, Pratt）快速字串比對演算法找出字串裡面是否包 含有某子字串。輸入字串datedadatete與子字串datdadatdatt，請完成此演算法所需之 failure function F(i)如下表格。（10 分） i 0 F(i) -1

給一個加權連通無向圖（weighted connected graph），所有邊線的加權值為正整數。 使用下列的貪婪演算法（Greedy algorithm）尋找從出發的節點Start 到目的地節點 Goal 之最短路徑。  初始化集合Path ={Start}  初始化集合VisitedVertices ={Start}  如果Start =Goal, 離開;否則,繼續第4 步驟  找出具有最小加權值的邊線edge（Start, v）其中v 不在集合VisitedVertices 內  將 {v} 加入集合Path  將 {v} 加入集合VisitedVertices  將Start 設為v 並執行第3 步驟 請問是否可以正確找到最短路徑？（10 分） 請說明原因或理由。（需舉圖例說明理由，否則不予計分）（10 分）

假設有一個二元樹（binary tree）如圖3 所示，定義一個自創追蹤法如下：對於任一 個節點（node），其右子節點先印出，這個節點印出，然後其左子節點才印出。 請問圖3 的自創追蹤為何？（10 分） 若圖3 為一個二元搜尋樹（binary search tree），請問其自創追蹤有何特性？ （10 分） 圖3

請使用疊代函式及遞迴函式完成下列：（20 分） 計算階層函數n!的值：在n＝0 或1 時的值是1；在n > 1 時，它的值為n*(n-1)! 。 使用二元搜尋（binary search），在排序好的整數陣列list[0] ≦ list[1] ≦ … ≦ list[n-1]中找出一個要找的整數（searchnum），若有找到則傳回它的位置，不然 就傳回 -1。

外部排序（external sorting）最常使用的是2-way合併排序法（merge sorting）。 假設檔案裡面包含18000 筆資料，而記憶體最多只能容許3000 筆資料。假設每次 I/O block大小為1000 筆資料，則需讀多少次I/O block才能完成排序？（10 分） 六、已知二元樹可以用一維陣列來儲存。請依此概念設計一方法，儲存以下三元樹於如 下之一維陣列中。（10 分） A D C B E F G H I J index 0 data A 100年公務人員高等考試三級考試試題 類 科： 資訊處理 全一張 （背面） 七、將數字25,5,75,0,60,10,55,15,45,15 依序存入一維陣列如下，以heap sort 方式進行由小 到大的排序。請顯示其在第一次執行完initial heap 步驟後的一維陣列內容。（10 分） index 0 1 2 3 4 5

9 data 25 5 75 0 60 10 55 15 45 15 八、輸入10000 個字元，其中字元出現次數：#(A)=1400，#(B)=800，#(C)=3000， #(D)=2700，#(E)=600，#(F)=1500，#(其他字母)=0。使用霍夫曼（Huffman）編碼 進行壓縮，其壓縮結果不含編碼簿（codebook）需要多少bits？（10 分） V5 V1 V6 V4 V2 V0 V3 E1=2天 E3=2天 E2=4天 E4=16天 E6=6天 E5=8天 E7=6天 E8=2天 E9=10天 九、計畫中各項工作的關係如以下的AOE（Activity On Edge）網路圖所示。 整個計畫至少需多少天才能完工？（10 分） 找出會提前或延後工期的關鍵路徑（critical path）。（10 分）