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

解釋下列名詞並舉例說明：（每小題5 分，共25 分） 演算法（algorithm） 時間複雜度（time complexity） 遞迴式的解決問題方法（recursive solution） 雙向佇列（Deque） 最小成本生成樹（minimum cost spanning tree）

本題是關於演算法效率分析（Algorithm and performance analysis） 請分別寫出下列程式第一行（line 1）到第五行（line 5）的執行次數（frequency count），於試卷上請標明是第幾行，次數是多少。（10 分） void mult(int a[][n], int b[][n], int c[][n]) { int i, j, k; for(i = 0; i < n; i++) ........................................line 1 for(j = 0; j < n; j++) .......................................line 2 { c[i][j] = 0; ...................................................line 3 for(k = 0; k < n; k++) ..............................line 4 c[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,000 count 11,863 24,227 40,003 53,217 67,393 78,961 91,985 113,997

請用二元樹（binary tree）針對10 筆資料：「陳、劉、王、蘇、高、胡、蔡、何、 簡、莊」設計出以鏈結（link）表示的二元樹資料結構，10 筆資料的排序方式可自 行決定（例如，依據筆劃數、注音符號、拼音或其他）。（每小題5 分，共25 分） 請用任意程式語言寫出插入（insert）一個節點的演算法。 請用任意程式語言寫出刪除（delete）一個節點的演算法。 請用任意程式語言寫出中序（inorder）尋訪的演算法。 請將「陳、劉、王、蘇、高、胡、蔡、何、簡、莊」及你決定並明確寫出的排序 方式，用插入演算法逐一插入二元樹，請畫出最後的二元樹。 請分析二元樹搜尋（searching）的O（）時間複雜度。

關於字串樣式比對（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 分） 99 年公務人員高等考試三級考試試題 代號：36150 類 科： 資訊處理 全一張 （背面）

考慮某地區的地圖，地圖上有n 個城市，城市之間共有m 條相通的公路，每條公路 有一個長度（例如，10 公里）。某人經常需從城市S 出發，開車前往另一城市T 送 貨，請你設計一個軟體系統的資料結構與演算法，幫忙找出路程最短的建議路徑與 該路徑的總長度。（每小題5 分，共15 分） 請設計一資料結構表示出地圖之n 個城市、m 條公路及公路長度。 依據你設計的資料結構，寫出Dijkstra 演算法，找出路程最短的建議路徑與該路 徑的總長度，並舉例說明。 分析Dijkstra 的時間複雜度。

說明樹（tree）與二元樹（binary tree）有那三項主要的不同？（5 分） 已知某一樹其分支度（degree）為1 的節點（node）有5 個，分支度為2 的節點 有4 個，分支度為3 的節點有3 個，分支度為4 的節點有2 個，分支度為5 的節 點有1 個，請問此樹一共有幾個節點？（5 分） 證明：於任意一個二元樹中，若n0代表分支度為0 的節點數目，n1代表分支度為 1 的節點數目，n2代表分支度為2 的節點數目，則n0=n2+1。（10 分）

給予資料：3, 1, 5, 7, 15, 13, 9, 11， 請寫出Shell 排序演算法。（15 分） 並用Shell 排序法，將資料排成由大到小排列，請務必將每一步驟詳細畫出並詳 細說明。（10 分） 99年特種考試地方政府公務人員考試試題 類 科： 資訊處理 全一張 （背面）

一個有向圖形（directed graph），若圖形的任何路徑（path）沒有環路（cycle）， 則此圖形可找到拓樸排序（topological sorting），問： 說明什麼是拓樸排序？（5 分） 舉出一種拓樸排序的應用。（3 分） 於下圖中找出一種拓樸排序，要寫出產生的過程，最後畫出拓樸排序圖。（12 分） A B F G D C E

考慮設計中式象棋（如圖）電腦程式系統：（每小題5 分，共10 分） 請設計一資料結構使能隨時表示出棋盤現狀（current state），包含所有棋子的位 置、有那些棋子在棋盤上。 寫出一演算法能產生「象」或「相」在任意位置之下一步可前往且合規則的所有 位置（next feasible positions），注意，務必考慮其他棋子阻礙的因素。「象」或 「相」的移動規則：田字形的對角移動；田字正中央有棋子時，不能移動前 往。

假設有一個陣列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），計算兩者成功找尋（successful search）的平均比較次數，並說明兩者大概相差多少倍？（6 分）

寫出以深度優先搜尋（depth first search）之順序。（5 分） 寫出以廣度優先搜尋（breadth first search）之順序。（5 分） 試說明如何以堆疊（stack）完成深度優先搜尋（depth first search）演算法之關鍵 技術。（10 分）