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

關於時間複雜度（time complexity）： 下列那兩個敘述是錯的？（10 分） (A) 0.5n2+100n=O(n2) (B) 1000=O(1) (C) 0.5n+5logn=O(n2) (D) 2n2+5n=O(2n) (E) n7+1.5n=O(n7) (F) 3n2+nlog4n=O(nlog4n) 承上，請把上題錯的敘述改正並且寫下。（20 分）

解釋名詞：（每小題5 分，共20 分） 資料結構（data structure） 資料型態（data type） 陣列（array） 堆積樹（heap tree）

將整數資料80, 40, 19, 120, 94, 110, 115, 90, 88, 92, 98 依序存入一棵空的二元搜尋樹 （binary search tree）。 請畫出完成資料輸入的二元搜尋樹。（6 分） 從產生的二元搜尋樹中刪除（delete）資料 94，請畫出完成刪除動作後的二元 搜尋樹。（給出一個正確樹即可）（6 分） 請寫出自二元搜尋樹找到最大值資料所在節點（node）的演算法。（10 分）

已知一棵二元樹（binary tree）的前序走訪（preorder traversal）與中序走訪（inorder traversal）之結果分別如下：（每小題10 分，共20 分） 前序－A B D E G H C F I 中序－D B G E H A C I F 請繪出這棵二元樹。 這棵二元樹的後序走訪（postorder traversal）結果為何？

請使用陣列實作堆疊，給予如下C 程式語言有關堆疊結構的宣告： #define MAX_STACK 100; typedef int ITEM_TYPE; typedef struct stack_type { ITEM_TYPE item[MAX_STACK]; int top; } STACK_TYPE; 其中ITEM_TYPE 可以是0, 1, 2 等的整數值，可以定義成整數、字元等各種不同的 資料型態；請用C 語言或類似虛擬語言（pseudo code）實作如下兩個堆疊之運算： （每小題10 分，共20 分） void push（STACK_TYPE *stack, ITEM_TYPE new_item）; /*將new_item 加 到堆疊頂端 */ void pop（STACK_TYPE *stack, ITEM_TYPE *old_item）; /*將堆疊頂端資料 移出，並放在old_item */ 一開始，設定stack -> top = -1；表示堆疊是空的。（註：符號 stack -> top 指到 堆疊頂端， stack -> item [stack -> top] 是堆疊頂端的資料）

請寫出執行下列程式碼的時間複雜度，並敘明理由。（10 分） for (i = 1; i < n; i++){ a = 1; b = n; while( a < b ){ a = 3 * a; b = b / 3; } }

請找出並且從小到大依序列出下列有向圖（directed graph）中，從頂點A 到所有其 他頂點的最短路徑（path）與路徑長度。（20 分）

給予如下資料: 12, 8, 17, 4, 26, 6, 11, 請將這些資料建成一個二元搜尋樹（Binary Search Tree）；如何利用此binary search tree 來做資料之排序。（10 分） 有一個二元搜尋樹，其結構不清楚，節點的值為1 到10000，當搜尋“2013”的值 時，拜訪的節點值依序為：1396, 7248, k, 1523, 1865, 3152, 2013，請問k 值的範 圍為何？（10 分）

下圖為一 AVL 樹T，請依各小題要求加入指定新資料後，畫出新產生的AVL 樹。 每小題各自獨立，都是對原先的AVL 樹T，加入資料。 加入資料27。（6 分） 加入資料45。（6 分） 加入資料95。（6 分） 40 20 10 30 25 70 35 50 60 90 80 102年公務人員高等考試三級考試試題 類 科： 資訊處理 全一張 （背面）

考慮排序（sort）的問題：（每小題10 分，共30 分） 如果要排序的資料很少，例如只有十幾筆資料，那麼你將採用快速排序法（quick sort）？合併排序法（merge sort）？還是氣泡排序法（bubble sort）？為什麼？ 如果要排序的資料很多，例如多到超過主記憶體容量許多，那麼你將採用快速排 序法？合併排序法？還是氣泡排序法？為什麼？ 快速排序法、合併排序法以及氣泡排序法這三個排序法當中，那一（些）排序法 是穩定的（stable）？或者都不穩定？

假設一生物DNA 序列由a, e, i, s, t, b, 和n 基本單元所構成。已知某一微生物DNA 序列之每一基本單元在此序列中出現之頻率如下：a, 10 次; e, 15 次; i, 12 次; s, 3 次; t, 4 次; b, 13 次; n, 1 次。請設計一最佳編碼表編碼此序列，並計算出最小之編碼位 元數。（20 分） 102年公務人員升官等考試、102年關務人員升官等考試 102年交通事業郵政、港務、公路人員升資考試試題 等別(級)： 薦任 類科(別)： 資訊處理 全一張 （背面）

函數f (n)定義如下，其中n 為非負整數。 ⎪⎩ ⎪⎨ ⎧ > − + − = = = 1 ), 2 ( )1 ( 1 ,1 0 ,0 ) ( n n f n f n n n f 若 若 若 請設計遞迴演算法，輸入非負整數n，輸出f (n)數值。（7 分） 請設計非遞迴演算法，輸入非負整數n，輸出f (n)數值。（7 分） 請分別說明與所設計演算法的時間複雜度（time complexity）。（10 分）

給予如下之Weighted Graph G：（每小題10 分，共20 分） 利用 Kruskal’s algorithm 來找最小擴張樹（Minimal spanning tree）。 在演算法中有一動作：選擇一最低成本的邊（edge），加入此邊（edge），如不 形成一迴圈（cycle），則加入此邊至最小擴張樹，請問運用何運算（operations） 或原理可完成此動作？

依據下圖內容，請寫出它的相鄰矩陣（adjacency matrix）表示法。（4 分） 請定義生成樹（spanning tree）。（6 分） 請畫出此圖的最小成本生成樹（minimum cost spanning tree），以及計算最小成本。 （10 分） 六、有一雜湊表格（hash table）T 的記憶空間共含11 個桶（buckets），位址編號由0 至 10，每個桶有一個槽（slot）。雜湊函數h1 定義為h1(key) = key % 11，當有碰撞 （collision）發生時採二次雜湊開放定址法（open addressing with double hashing） 處理，其函數定義為h(key, j) = (h1(key)＋j * h2(key)) % 11，其中j 為碰撞次數， j = 1, 2, 3, ..., 11，h2(key) = 1＋(key % 10)。欲將26 放入雜湊表格T，總共經過6 次 探測才成功找到存放位址。請問26 在雜湊表格T 的探測順序為何？（6 分） a b e c f g d 5 9

13 15 16 12

9 pattern a b b a b c a b b a failure ？ ？ ？ ？ ？ ？ ？ ？ ？ ？ 四、請參考圖2。每一條線段上的數字代表兩節點間的距離。請找出a 節點到k 節點的 最短路徑的長度。並請說明你的方法如何應用在非常大型的圖裡。（15 分） 五、請參考圖3。圖3 是一個activity-on-edge 網路。在activity-on-edge 網路中，一項計 畫可以分成很多件工作，每一件工作由一條線段代表，線段上的數字代表該工作所 需的時間（以工作日為單位），線段的箭頭代表工作的先後關係。例如在圖3 中， ab 及db 線段代表的工作完成之後，bc、be、及bf 線段代表的工作才可以開始進行， 其他的先後關係依此類推。a 節點是起點，k 節點是全部工作的完成點。請找出k 節點的最早完成時間及關鍵路線（critical path）。並請說明你的方法如何應用在非 常大型的圖裡。（15 分） （請接第三頁） 圖3 Activity-on-edge 網路 圖2 最短路徑 a 22 21 11 11 21 12 12 21 13 13 19 27 23 23 5 14 b c d e f g h k a b c d e f g h k 16 11 12 13 17 23 27 21 41 10 26 49 4 5 3 7 35 14 3 7 102年特種考試地方政府公務人員考試試題 類 科： 資訊處理 全三頁 第三頁 六、在一個二元樹裡有許多節點（nodes）。假設每一個節點的資料結構如下圖： 其中DATA 欄位為該節點的資料。LEFT 欄位為指向左方子樹的指標變數。RIGHT 欄位為指向右方子樹的指標變數。 如果節點p 沒有左方子樹，其LEFT 欄位為空指標（null pointer）。同理，如果節 點p 沒有右方子樹，其RIGHT 欄位為空指標（null pointer）。 如果一個二元樹有n 個節點，那麼它有幾個空指標？（5 分） 我們可以利用原本是空指標的欄位來儲存引線（threads）。二元樹加上引線的結 果稱為引線樹（threaded trees）。當然我們必須在各節點再加上兩個欄位LTAG 及RTAG，共5 個欄位，如下圖所示： 如果LEFT 欄位代表一般的節點指標，則LTAG = 0。如果LEFT 欄位代表引線指標， 則LTAG = 1。同理，如果RIGHT 欄位代表一般的節點指標，則RTAG = 0。如果 RIGHT 欄位代表引線指標，則RTAG = 1。 請將下圖的二元樹加上適當的引線指標，讓它變成引線樹，並請繪圖標出A 到I 共 9 個節點中所有引線指標指向的節點。（10 分） LEFT DATA RIGHT LTAG LEFT DATA RIGHT RTAG A B C D E F G H I

3