統計 114 年資料處理考古題

在資訊安全中，雜湊函數（Hash Function）與數位簽章（Digital Signature） 常被用來確保資料的正確與完整。請敘述兩者的功能，並說明雜湊函數 的主要特性及數位簽章的運作過程。（25 分）

假設一關聯資料庫中有一關係（relation）R，其包含有A, B, C, D, E, F, G, H 八個屬性。屬性間之功能相依性（Functional Dependencies）如下： C, H → G；A → B, C；B → C, F, H；E → A；F → E, G。請試述下列問 題：（每小題10 分，共30 分） 請為該關係（relation）R 決定出一組最適當的主鍵（primary key）。 請對關係（relation）R 進行分解，使其能符合第二正規化之要求。 請對前面分解後之所有關係（relation）再進行分解，使其能符合第三 正規化之要求。

設有一校務資料表格，含有以下屬性：學號, 學生姓名, 學生住址, 學生 電話, 聯絡人姓名, 聯絡人電話, 聯絡人地址, 指導老師證號, 指導老師 姓名, 研究室, 課程編號, 課程名稱, 學分, 成績, 實驗室名稱, 實驗室 地點。 且一位學生可能有多支電話號碼。 該校務資料表格，屬性間之功能相依性如下： 學號學生姓名, 學生住址, 聯絡人姓名, 聯絡人電話, 指導老師證號； 課程編號課程名稱, 學分； 指導老師證號指導老師姓名, 研究室； 聯絡人姓名, 聯絡人電話聯絡人地址； 實驗室名稱實驗室地點, 指導老師證號； 指導老師證號實驗室名稱； 學號, 課程編號成績。 （每小題10 分，共40 分） 請以功能相依之特性，推導出該校務資料表格之primary key。 請修改該校務資料表格，使其能符合第二正規化之要求。 請修改該校務資料表格，使其能符合第三正規化之要求。 請依小題所產生的所有表格，撰寫一SQL 程式碼片段，列印出每一 位學生之學號、姓名、共修多少門課，以及其指導老師之姓名。

請完成下列各小題，內容包含運算式轉換、樹狀結構走訪與最小堆積樹 （Min Heap），請寫出詳細步驟或畫出結果。（25 分） ⑴將下列運算式由中序式（Infix）轉換為前序式（Prefix）： (A-B)*(C+D)/F ⑵根據下列二元樹，寫出其後序（Postfix）走訪結果： ⑶依序將數字12, 8, 20, 4, 15, 7, 3, 10 插入一個空的最小堆積樹，畫出 最後的堆積樹。 ⑷承上題，刪除最小數字3 後的最小堆積樹，畫出其最後結果。

請說明路由器（Router）、IP 分享器、交換器（Switch）、防火牆（Firewall） 之主要功能。（28 分）

編譯器（compiler）將二維陣列資料映射到線性記憶體空間，一般採Row- major 或Column-major 兩種不同儲存順序。 何謂Row-major 儲存順序與Column-major 儲存順序？（8 分） 試問程式碼應如何撰寫，對整個巨大型二維陣列之資料讀取，才能獲得 較高的讀取時間效率？（6 分）並請給予一程式片段範例做說明。（6 分）

正規化是為資料表的優化，而資料庫正規化有一些規則，每條規則都稱 為「正規形式」（Normal Form），請說明各階段正規化的規則（包含第一 正規化、第二正規化、第三正規化和BCNF 等）。（25 分）

試分別以時間複雜度、額外記憶體空間複雜度、相同鍵值（key）排序順 序之穩定性、欲被處理之資料量龐大至大於主記憶體空間、儲存資料的 資料結構（如Array、linked list）等不同面向，比較Merge Sort 與Quick Sort 之不同特性。（30 分）

BOM 表為一棵樹的結構，描述一產品P 的製作過程，其每一節點N 描 述P 之某一零組件C 的製程；而其所連結之子樹，描述組合該零組件 C，所需的所有零組件之製程。如圖範例所示，零組件 0 Ｃ是由零組件 11 12 13 C C C 、 及 所組合製作而成；零組件 12 C 是由零組件 21 22 C C 及 所組合製 作而成。而零組件 21 22 C C 及 何者先製作完成是無所謂；同樣地零組件 11 12 13 C C C 、 及 何者先製作完成也是無所謂。但在製作過程中，需先製作完 成零組件 21 22 C C 及 後，才能製作零組件 12 C ；且需先製作完成零組件 11 12 13 C C C 、 及 後，才能製作零組件 0 Ｃ。（每小題10 分，共20 分） 圖BOM 之範例 試寫一最快速演算法，列印出某一BOM 表所對應之產品P 之零組件 製程的製作順序。列印之順序為需先被生產之零組件的製程，需先被 列印出來。例如對範例圖所示，零組件 11 12 13 C C C 、 及 ，皆需比零組件 0 Ｃ 早被列印出來；而零組件 21 22 C C 及 ，皆需比零組件 12 C 早被列印出來。 若每一節點N，都有紀錄欲生產一件產品P 時，所需該節點之零組件 的製程時間Tc。且假設有充足機器及原物料，可供其隨時生產該節點 之零組件；即可忽略等待機器及原物料的準備時間。請寫一最快速演 算法，以計算當欲生產完一件產品P 之最快生產時間。

請依照下列程式碼，當執行函數呼叫Test(3)時，最後輸出結果為何？並 請寫出詳細過程。（25 分） String Test(int n) { String s = n + Test(n - 1) + n + Test(n - 2); if (n <= 0) return ""; return s; }

設A 為一含有l×m 個元素的矩陣，B 為一含有m×n 個元素的矩陣，C 為 一含有m×p 個元素的矩陣，D 為A×B×C 之結果矩陣。並以A[i, j]、 B[i, j]、C[i, j]、D[i, j]分別代表矩陣A、B、C、D 位於[i, j]處之元素值。 試以近似程式語言格式，撰寫一計算A×B×C 之結果矩陣D 之演算法。 （12 分）

IEEE 802.11 無線網路協定的MPDU（MAC Protocol Data Unit）訊框格 式之訊框標頭（Header）的訊框控制（Frame Control），包含有11 項目 資訊。試問此11 項目資訊，分別被用以描述什麼？（20 分） C0 C11 C12 C13 C21 C22