統計 111 年資料處理概要考古題

設M 與N 分別含有m 及n 個元素之兩個數列陣列。 ㈠試設計一演算法Sort（M, N, P, m, n），將M 與N 內之元素，合併成一 個新陣列P。合併後P 內之元素需依小而大排序；該演算法的執行時 間需最佳。（15 分） ㈡試計算所設計出之演算法Sort（M, N, P, m, n）的執行時間複雜度。 （10 分）

設PFExp 為一字串，描述著一個以後置運算式（postfix expression）表示 之數學運算式，例如PFExp =“62/3-42*+”。當中每一個運算元 （operand）皆僅為一個位數整數，且只有‘+’、‘-’、‘*’、‘/’四 種可能運算子（operator）。 ㈠寫出一演算法(int)postfix_math(string PFExp)，利用堆疊（Stack）計算 該後置運算式，並傳回該運算結果。（15 分） ㈡以您所設計之演算法，來計算數學運算式PFExp =“62/3-42*+”。寫 出在執行過程中每一步驟Stack 及PFExp 的內容。（10 分） 以下是您可能會用到的副程式： (int)POPStack(Stack)：移除Stack 中最前面的整數，並傳回被移除的整數。 PUSHStack(Stack, V)：將整數V 放入Stack 的最前面。 (int)DECV(char C)：將一字元C 轉成一整數，並傳回該整數。 (char)First_Char(StringPFExp)：移除PFExp 中最前面的字元，並傳回該字元。 (Boolean)EMPTY(String PFExp)：如PFExp 為一空字串時，傳回TRUE， 否則傳回FALSE。

假設T 為一個符合第一正規化要求之關聯表格，且T 包含有屬性為 {A, B, C, D, E, F, G, H}，以下描述其屬性間之功能相依的關係性： BC → GH, AD → E, A → H, E → BCF, G → H ㈠決定出表格T 之最合適的主要鍵（primary key）。（5 分） ㈡將T 轉化成符合第二正規化要求的關聯表格，並指出關聯表格的主要鍵。 （8 分） ㈢將㈡轉化後的關聯表格，轉成符合第三正規化要求之表格，並標出表 格的主要鍵。（8 分） （※需寫出推導過程）

以下為某種程式語言的pseudocodes，其中main()為主程式，p(int x,int y, int z) 為被呼叫的副程式。 ㈠若副程式是以傳名呼叫（passed byname）法，則主程式印出的結果為何？ （3 分） ㈡若副程式是以傳址呼叫（passed by reference）法，則主程式印出的結 果為何？（3 分） ㈢若副程式是以傳值呼叫（passed by value）法，則主程式印出的結果為何？ （3 分）

以下顯示一Ethernet 2000 網路架構： ㈠當剛打開網路系統後，PC1 向PC3 傳遞資料，描述Switches 傳送該資 料的過程及資料內容的變化。（10 分） ㈡隨後PC5 向PC1 傳遞資料，描述Switches 傳送該資料的過程及資料 內容的變化。（10 分） PC3 00-F1-EE-50-DC-92 Switch 1 PC6 09-54-11-2d-c5-22 PC1 00-13-46-9A-63-74 PC4 00-E0-4C-39-00-1F PC2 80-C1-6E-F3-E7-6A PC5 00-03-FF-C0-CD-98 fa0/1 fa0/3 fa0/2 fa0/4 p(int y, int x, int z) { x = x+z; z = x+1; x = y+z; y = z;} main( ) { x = 2; y = 5; p(x, y, 3); print x, y}