電子工程 108 年電子計算機原理考古題

以下是一個演算法，給定一個含有n 個數字元素的陣列A[1]～A[n]， 它會輸出其中最大的元素：（每小題5 分，共25 分） Algorithm arrayMax(A, n) 1 currentMax ←A[1]

for i ←2 to n do

if A[i] >= currentMax then

currentMax ←A[i]

return currentMax ㈠此演算法若使用C 或C++程式語言來實作，請問其中「←」應該用什 麼符號來表示？ ㈡給定一個含有n = 8 個數字元素的陣列A = < 8, 22, 22, 13, 34, 3, 34, 13>， 請問最後會輸出currentMax 的值為何？ ㈢給定一個含有n = 8 個數字元素的陣列A = < 8, 22, 22, 13, 34, 3, 34, 13>， 請問此演算法的第3 行指令「if A[i] >= currentMax then」總共被執行 了多少次？ ㈣給定一個含有n = 8 個數字元素的陣列A = < 8, 22, 22, 13, 34, 3, 34, 13>， 請問此演算法的第4 行指令「currentMax ←A[i]」總共被執行了多少次？ ㈤此演算法處理一個含有n 個數字元素的陣列時，其執行時間T(n)的複 雜度（time complexity）為何？ 二、下圖可用來表示程式執 n、log2n 等6 種函數。 ㈠請問其中那些函數是 ㈡傳統的Merge sort 在 種？ ㈢傳統的Quick sort 在 是這6 種的那一種？ ㈣傳統的Selection sor 一種？ ㈤傳統的Heap sort 在 種？ f(n) 0 40 30 20 10 執行時間f(n)的成長圖。其中有 。（每小題5 分，共25 分） 是屬於polynomial-time growth？ 在排序n 個資料時，其時間複雜度 在排序n 個資料時，在最糟的狀況 ？ rt 在排序n 個資料時，其時間複 在排序n 個資料時，其時間複雜度 n! 2n n2 n nlog2 lo 2 1 3 4 5

9 n!、2n、n2、nlog2n、 雜度是這6 種的那一 狀況下，時間複雜度 複雜度是這6 種的那 度是這6 種的那一 n 2n og2n n 三、在電腦內部有許多工作 需要安排很多queue 來 Ready queue、I/O queue （每小題5 分，共25 ㈠請問工作（job）及程 ㈡請問圖中「Time slo ㈢請問圖中「I/O satis ㈣請問Ready queue 儲 ㈤在實作queue 時，一 四、資料結構的分類可如下 ㈠請問Linear Data Stru 為何？ ㈡請問圖中Static 和D ㈢請問圖中何者亦稱為 ㈣在實作LinkedList 時 請問這兩個部分各存 ㈤下面顯示一個Grap adjacency matrix 及 兩個做法。 作（job）及程序（process）同時 來將它們做先後順序的排列。下圖 e 等3 種queue 在處理job 及proc 分） 程序（process）的主要差別為何 ot exhausted」所指意思為何？ fied」所指意思為何？ 儲存的內容為何？ 一般常用FIFO queue，請問FIFO 下圖所示：（每小題5 分，共25 ucture和Non-Linear Data Structu Dynamic 兩者主要的差別為何？ 為LIFO？ 時，每個元素通常會含有兩個部 存什麼資訊？ ph 例子。在實作Graph 時，通 adjacency list，請使用上面的G 時在爭用資源，因此 圖顯示Job queue、 cess 的整體流程圖。 何？ 意義為何？ 分） ure兩者主要的差別 部分：data 和link。 通常有兩種做法： Graph 例子，說明這