資訊處理 111 年資料處理概要考古題

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

一個m × n 的二維矩陣Am × n，其中列數m = 5，行數n = 4，A 矩陣大部 分的元素值為0，屬於稀疏矩陣，請試述： 稀疏矩陣的缺點？（10 分） 使用一個二維密集矩陣B 表現稀疏矩陣A。A 矩陣的非零元素分別為 A(0,0) = 1, A(1,1) = 2, A(2,2) = 3, A(3,0) = 4, A(4,3) = 5，如圖，請畫出B 矩陣。（20 分） 1 0 0 0 0

設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。 44440

0 0 0 0

假設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 分） （※需寫出推導過程）

0

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

0 0 0 0 0 0

以下顯示一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}

二、有一資料表R，以R(A, B, C, D, E, F)表示，A～F 為資料表R 的欄位名 稱，功能相依以X→Y 表示，表欄位Y 依賴欄位X。資料表R 存在下列 功能相依： A→(E, F) B→C (A, D)→(B, C, E, F) 請問： R 資料表的主鍵為何？（10 分） 將資料表R 正規化為符合三階正規資料表，其中必須將三階正規化後 的所有資料表，標出主鍵(P)和外部鍵(F)。（20 分） 三、容錯式磁碟陣列（Redundant Array of Independent Disks; RAID）的使用 對於資料的儲存策略影響深遠，請試述何謂RAID 0、RAID 1？假設共 有n 顆硬碟，每顆硬碟規格皆相同，請就組成RAID 0、RAID 1 最少 硬碟數、最大容錯硬碟數、可用容量硬碟數三方面，比較它們的差異。 （10 分） 44630 四、網際網路上的應用，如全球資訊網（World Wide Web）的應用已蓬勃發 展，有所謂的WEB1.0、WEB2.0、WEB3.0 世代的演進，其中WEB3.0 有學者認為是語意網的發展，另一派學者認為是去中心化的發展，目前 尚無定論。請以資訊提供者、資訊品質、資訊互動性，試述比較WEB1.0 和WEB2.0 的差異。（30 分）