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

將四個字母A、B、C、D 依序放入（push）一個堆疊（stack）內。在放入之過程， 堆疊內之字母可隨機取出（pop）。若此四個字母最終皆被取出，則以下何者可為 此四個字母被取出的順序（例如，D、C、B、A 代表D 首先被取出，其次為C，再 其次為B，A 最後被取出）？（可複選）（20 分) A、B、C、D C、B、D、A B、D、A、C D、C、A、B C、B、A、D

有N 份資料，每份資料皆以兩個大寫英文字母標記（例如AK、TA 等等）。請設計 一O(N) 時間的演算法，將此組資料依標記的字典順序排序，並請說明此演算法所 需使用的空間。（20 分）

如何將以下15 個英文單字存入陣列（array）A[1]，A[2]，…，A[15]，使得以後搜尋 （search）其中任何一個字，至多只需執行三次字比較（word comparisons）？又搜 尋方法為何？請詳述。（20 分） read，educate，place，touch，fill，calculate，save，increase， gain，print，begin，work，take，derive，operate

圖形（graph）G有12 個節點（node），分別用數字0, 1, 2, 3, 6, 7, 8, 9, 12, 13, 14, 15 標 記。標記為a, b的兩個節點間有邊線（edge），若且唯若a =a1a2a3a4, b =b1b2b3b4的四位 元二進位表示法恰有一個位元不相同。例如1 = 0001, 3 = 0011, 9 = 1001, 則標記為 3 的節點與標記為1 的節點間有邊線，與標記為9 的節點間沒有邊線。 請分別用鄰接矩陣（adjacency matrix）與鄰接串列（adjacency list）的方式表示圖 形G。（10 分） 請在標記小的節點先搜尋的規則下，產生以節點0 為起始節點的廣度優先搜尋擴 張樹（breadth-first search spanning tree）與深度優先搜尋擴張樹（depth-first search spanning tree）。（10 分）

請設計一個遞迴程式（recursive procedure）。當輸入（input）為一顆有順序性且有固 定根的二元樹（ordered rooted binary tree）T 時，此遞迴程式可依中序追蹤（inorder traversal）方式拜訪T 的每一個節點（node）恰好一次。（20 分）

令N 為2 的m 次方，a 為任意正整數。 請寫一使用O(log N)次乘法運算的遞迴（recursive）程式計算a 的N 次方。（10 分） 請寫一使用O(log N)次乘法運算的疊代（iterative）程式計算a 的N 次方。（10 分）

當輸入（input）為x1, x2, …, xn時，塞入排序（insertion sort）可將此n個輸入值從小 到大排列。塞入排序的執行（execution）可簡略表示如下： For i＝2, 3, …,n, insert xi into x1, x2, …, xi−1 such that these i data items are sorted. 例如，當輸入為7, 5, 1, 4, 3, 2, 6 時，塞入排序的執行如下： i = 2: 5, 7 i = 3: 1, 5, 7 i = 4: 1, 4, 5, 7 i = 5: 1, 3, 4, 5, 7 i = 6: 1, 2, 3, 4, 5, 7 i = 7: 1, 2, 3, 4, 5, 6, 7 若T(n) 表示執行塞入排序所需的時間複雜度（time complexity），其中n 表示輸入 值的個數。請用O( f(n)) 的符號估算T(n) 在最佳情況（best case）與最壞情況（worst case）之值，其中f(n) 表示n 的一個函數。（20 分） 98 年公務人員、關務人員升官等考試試題 類 科： 資訊處理 全一張 （背面）

今有一採用開放位址（open addressing）方式儲存鍵值，大小為14 的雜湊表 （hash table），其雜湊函數為Hi(k) = h1(k) + i h2(k) (mod 14)，i = 0, 1, …, 13,其中 h1(k) = k (mod 14)。依序存入下列鍵值15、18、42、19、10、28、27、38、80、55。 設h2(k) ≣ 1，請列出最後雜湊表的結果與使用雜湊函數的次數。（10 分） 設h2(k) = 1 + k (mod 13)，請列出最後雜湊表的結果與使用雜湊函數的次數。 （10 分）

假設L 是一指標（pointer），指向一個雙鏈結串列（doubly linked list），圖示如下。 L 請設計一個程式（procedure）：當輸入（input）為x, y 與L 時（x 為存在於L 所 指的串列內之資料，y 為不存在於L 所指的串列內之資料），此程式可在L 所指的串 列內增加（insert）y 於x 之後。增加y 之後，串列仍必須為雙鏈結結構。（20 分)

有一檔案其字母集為{S, T, U, V, W, X, Y, Z}，字母出現的頻率如下表： 字母 S T U V W X Y Z 頻率 4

10 24 10 2 15 29 若以下列不定長度二進位編碼（variable-length binary code）來編碼此檔案，請問 每個字母平均用幾個位元表示？（5 分） 字母 S T U V W X Y Z 編碼 00 10 010 011 1100 1101 1110 1111 霍夫曼碼（Huffman code）是一種與檔案中字母出現頻率有關的不定長度二進位 編碼法，檔案經其編碼後，長度是所有不定長度二進位編碼中最短的。請為此檔 案建立其霍夫曼碼，並算出此編碼下每個字母平均用幾個位元表示。（15 分）

printf("ADD ");

return (f (n-1) + f (n-2)); 9 } 以f(4)呼叫上面函式，會列印出多少個"ADD"？（6 分） 如果以f(n)呼叫上面函式，n 為任意正整數，程式執行完畢後，會列印出多少個 "ADD"？請推導其通式（只要推導出其關係式即可）。（12 分） 在忽略第7 列的情形下，可將上面函式改寫成更有效率的函式如下。請完成第 10~12 列的程式內容。（8 分） 1 int f(int n) 2 { 3 int i, a,b,c; 4 if (n <= 1) 5 return(n); 6 a=0; 7 b=1; 8 for (i = 2; i <= n; i++) 9 { 10 11 12 13 } // end of for 14 return (c); 15 }