九九年高考三級資料結構
一、本題是關於演算法效率分析 (Algorithm and performance analysis)
(一)請分別寫出下列程式第一行 (line 1) 到第五行 (line 5) 的執行次數(frequency count)，於試卷上請標明是第幾行，次數是多少。（10分）
(二)於下列程式，請計算指令 x++；一共會執行多少次？（5分）
(三)請根據下列表格的數據，size 是問題量 (或問題大小)，count 是程式指令的總執行次數，來推測程式執行的時間複雜度 (time complexity)，請以 Big-Theta θ表示之 (例如：θ(3n))。（5分）
二、關於字串樣式比對 (string pattern matching)，最簡單的方法是使用窮舉樣式比對法 (exhaustive pattern matching)，此即將樣式 (pattern) 的字元逐一比較本文 (text) 的字元，若不對則移下一字元繼續比對，直到比對成功或本文剩下的字元數目少於樣式長度。
(一)假設本文是：THERE_IS_MORE_TO_LIFE_THAN_INCREASING_ITS_SPEED，欲找尋的樣式 (pattern) 為 GENTLE，問：
1.總共比較多少次？（5分）
2.一共比較多少個字元？（5分）
(二)假設本文是一千個"0"，欲找尋的樣式 (pattern) 為01010，請問：
1.總共比較多少次？（5分）
2.一共比較多少個字元？（5分）
三、(一)說明樹 (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分）
四、一個有向圖形 (directed graph)，若圖形的任何路徑 (path) 沒有環路 (cycle)，則此圖形可找到拓樸排序 (topological sorting)，問：
(一)說明什麼是拓樸排序？（5分）
(二)舉出一種拓樸排序的應用。（3分）
(三)於下圖中找出一種拓樸排序，要寫出產生的過程，最後畫出拓樸排序圖。（12分）
五、假設有一個陣列 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分）
一、本題是關於演算法效率分析 (Algorithm and performance analysis)
(一)請分別寫出下列程式第一行 (line 1) 到第五行 (line 5) 的執行次數(frequency count)，於試卷上請標明是第幾行，次數是多少。（10分）
(二)於下列程式，請計算指令 x++；一共會執行多少次？（5分）
(三)請根據下列表格的數據，size 是問題量 (或問題大小)，count 是程式指令的總執行次數，來推測程式執行的時間複雜度 (time complexity)，請以 Big-Theta θ表示之 (例如：θ(3n))。（5分）
二、關於字串樣式比對 (string pattern matching)，最簡單的方法是使用窮舉樣式比對法 (exhaustive pattern matching)，此即將樣式 (pattern) 的字元逐一比較本文 (text) 的字元，若不對則移下一字元繼續比對，直到比對成功或本文剩下的字元數目少於樣式長度。
(一)假設本文是：THERE_IS_MORE_TO_LIFE_THAN_INCREASING_ITS_SPEED，欲找尋的樣式 (pattern) 為 GENTLE，問：
1.總共比較多少次？（5分）
2.一共比較多少個字元？（5分）
(二)假設本文是一千個"0"，欲找尋的樣式 (pattern) 為01010，請問：
1.總共比較多少次？（5分）
2.一共比較多少個字元？（5分）
三、(一)說明樹 (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分）
四、一個有向圖形 (directed graph)，若圖形的任何路徑 (path) 沒有環路 (cycle)，則此圖形可找到拓樸排序 (topological sorting)，問：
(一)說明什麼是拓樸排序？（5分）
(二)舉出一種拓樸排序的應用。（3分）
(三)於下圖中找出一種拓樸排序，要寫出產生的過程，最後畫出拓樸排序圖。（12分）
五、假設有一個陣列 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分）
全站熱搜
留言列表
國考資訊處理解答 (7)
