申論 1本題是關於演算法效率分析（Algorithm and performance analysis）㈠請分別寫出下列程式第一行（line 1）到第五行（line 5）的執行次數（frequencycount），於試卷上請標明是第幾行，次數是多少。（10 分）void mult(int a[][n], int b[][n], int c[][n]){int i, j, k;for(i = 0; i < n; i++) ........................................line 1for(j = 0; j < n; j++) .......................................line 2{c[i][j] = 0; ...................................................line 3for(k = 0; k < n; k++) ..............................line 4c[i][j] += a[i][k] * b[k][j]; .............line 5}}㈡於下列程式，請計算指令x++；一共會執行多少次？（5 分）for (i =0; i < n ; i ++)for (j = i +1; j < n; j++)x++;㈢請根據下列表格的數據，size是問題量（或問題大小），count是程式指令的總執行次數，來推測程式執行的時間複雜度（time complexity），請以Big-Theta Θ 表示之（例如：Θ(3n)）。（5 分）size 1,000 2,000 3,000 4,000 5,000 6,000 7,000 8,000count 11,863 24,227 40,003 53,217 67,393 78,961 91,985 113,997
本卷皆為申論題，點「看答案與解析」查看擬答。
弱點分析
未作答的題目不計分。看我的紀錄
申論 2關於字串樣式比對（string pattern matching），最簡單的方法是使用窮舉樣式比對法（exhaustive pattern matching），此即將樣式（pattern）的字元逐一比較本文（text）的字元，若不對則移下一字元繼續比對，直到比對成功或本文剩下的字元數目少於樣式長度。㈠假設本文是：THERE_IS_MORE_TO_LIFE_THAN_INCREASING_ITS_SPEED，欲找尋的樣式（pattern）為GENTLE，問：總共比較多少次？（5 分）一共比較多少個字元？（5 分）㈡假設本文是一千個"0"，欲找尋的樣式（pattern）為01010，請問：總共比較多少次？（5 分）一共比較多少個字元？（5 分）年公務人員高等考試三級考試試題 代號：36150 全一張類 科： 資訊處理科 目： 資料結構
申論 3㈠說明樹（tree）與二元樹（binary tree）有那三項主要的不同？（5 分）㈡已知某一樹其分支度（degree）為1 的節點（node）有5 個，分支度為2 的節點有4 個，分支度為3 的節點有3 個，分支度為4 的節點有2 個，分支度為5 的節點有1 個，請問此樹一共有幾個節點？（5 分）㈢證明：於任意一個二元樹中，若n代表分支度為0 的節點數目，n代表分支度為1 的節點數目，n代表分支度為2 的節點數目，則n=n+1。（10 分）
申論 4一個有向圖形（directed graph），若圖形的任何路徑（path）沒有環路（cycle），則此圖形可找到拓樸排序（topological sorting），問：㈠說明什麼是拓樸排序？（5 分）㈡舉出一種拓樸排序的應用。（3 分）㈢於下圖中找出一種拓樸排序，要寫出產生的過程，最後畫出拓樸排序圖。（12 分）ABC DEFG
申論 5假設有一個陣列A[0..12]，儲存13 個數字：4，14，25，31，37，42，56，70，73，83，86，90，94。今使用二元搜尋（binary search），問：㈠寫出找尋70 的比較過程（沒寫過程不予計分）。（8 分）㈡列出比較次數最多的所有數字。（6 分）㈢假設現有100,000 個數字已經依由小而大的次序排列好，請分別使用二元搜尋（binary search）與循序搜尋（sequential search），計算兩者成功找尋（successfulsearch）的平均比較次數，並說明兩者大概相差多少倍？（6 分）