資訊處理 93 年程式設計概要考古題

結構化程式設計有三種基本控制流程，分別為循序（Sequence）、選擇（Selection） 及重複（Iteration）。請分別以例子並用流程圖方式繪出此三種流程。（25 分）

已知費氏數列（Fibonacci sequence）如下： 0, 1, 1, 2, 3, 5, 8, 13, 21,…… 撰寫一遞 函數fibonacci，其輸入參數為大於或等於0 之整數n，輸出為費氏數列第 n 個值。假設0, 1, 1, …分別稱為第0 個值、第1 個值、第2 個值，依此類推。（25 分）

假設有一個整數陣列（Integer Array），其內有10 個元素，且此陣列元素的編號為0 至9。資料27, 77, 68, 83, 15, 31 放入此陣列的位置如下圖所示。圖中陣列之位置0， 2，4，6 內為空位沒有放資料，位置1 放31，位置3 放83，位置5 放15，位置7 放 27，位置8 放77，位置9 放68。若要找尋任何一筆輸入之資料是否在此陣列內，可 以使用I =資料% 10（% 10 為計算資料除以10 的餘數）之計算公式，並比對陣列編 號I 的位置是否存在此筆資料。若遇到位置I 內的資料與此筆輸入資料相同，則找到。 若位置I 內為空位沒有資料，則找不到。若遇到位置I 內的資料與輸入資料不同，則 依序由位置I+1, I+2, I+3, …去找，遇到第一個空位仍未比對到相同資料，則找不到。 0 1 2

撰寫一程式：（25 分） 輸入：一個正整數n。 輸出：印出如下之n 列資料，第一列是一個*號、第二列是二個*號、直到第n 列是 n 個*號。 * ** *** **** ….

請設計一個程式，輸入N 個整數，統計各整數出現的次數，並按整數值由小至大順 序輸出。例如輸入10 個整數12, 43, 22, 67, 43, 23, 22, 43, 67, 13，其輸出結果如下： （25 分） 12 出現1 次 13 出現1 次 22 出現2 次 23 出現1 次 43 出現3 次 67 出現2 次

撰寫一函數LinearSearch，能從有n 個元素的整數陣列b，用線性搜尋法（linear search），搜尋一個整數值key 在陣列b 中的位址，若key 不在陣列b 中，則傳回 -1。 用Big-O 符號表示此函數之複雜度（complexity），並說明之。（25 分）

下列程式之輸出為何？（25 分） N = 5 S = 0 FOR A = 3 TO 5 K = N ： B = 1 ： C = A WHILE K>0 IF K MOD 2 = 0 THEN K = K/2 ： C = C*C ELSE K = K－1 ： B = B*C END IF WEND S = S+B NEXT A PRINT S END

利用陣列（array）宣告一個可作佇列（queue）的結構及相關變數。撰寫兩個佇列（queue） 常用的運算函數insert 與delete。（25 分）

9 31 83 15 27 77 68 例如 輸入15，則I=5，在第5 個位置找到。 輸入77，則I=7，在第7 個位置找不到，往後在第8 個位置找到。 輸入58，則I=8，在第8 個位置找不到，在第9 個位置找不到，往後在第0 個位置看到空位，表示找不到。 請說明找尋97 的處理情形及結果。（5 分） 請說出這是什麼方法？在最壞情況要比對多少次才找到？（5 分） 請撰寫一個程式可以輸入一筆資料，並將在那個位置找到或找不到此筆資料的訊 息輸出。為方便程式撰寫，你可以將空位以0 表示。（15 分） 三、請用迴圈寫一個程式可以讓使用者輸入多個學生之考試分數，直到輸入的值為負數 時，結束輸入。此程式並可以計算所輸入分數之平均分數、最高分數及最低分數。 其中最後輸入的負數不算學生之分數。（25 分） 四、有兩個陣列其內之數字已經排序，且被宣告為 int data1[5]={6,10,18,27,30}; int data2[5]={7,8,25,26,35}; 若要將此兩個陣列合併為一個排好序之陣列，則： 請說明你如何解此問題。（10 分） 請撰寫一個程式解此問題。（15 分）