資訊處理 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

如何將以下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

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

當輸入（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 年公務人員、關務人員升官等考試試題 類 科： 資訊處理

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

10 24 10 2 15 29 ㈠若以下列不定長度二進位編碼（variable-length binary code）來編碼此檔案，請問 每個字母平均用幾個位元表示？（5 分） 字母 S T U V W X Y Z 編碼 00 10 010 011 ㈡霍夫曼碼（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 }