民國114年 高考三級 統計 資料處理考古題

民國114年 高考三級 統計 資料處理收錄考選部官方試題，共 4 題可線上瀏覽，考選部未公告本科目答案。

官方資料

題目與答案

第1題

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

參考解答（AI 生成，非官方）

  • （一）令 K={學號,課程編號,學生電話}。由 學號→學生姓名、學生住址、聯絡人姓名、聯絡人電話、指導老師證號；指導老師證號→指導老師姓名、研究室、實驗室名稱；實驗室名稱→實驗室地點、指導老師證號；課程編號→課程名稱、學分；(學號,課程編號)→成績，可知 K+ 包含全部屬性。去掉電話無法決定多值電話，去掉課程編號無法決定課程與成績，去掉學號無法決定學生與老師資料，故 K 為最小超鍵，即 primary key。若先將電話抽出成獨立多值表，原表主鍵才可記為 (學號,課程編號)；本題未拆解前須含電話。題目未給電話→學號，不假設電話全球唯一。
  • （二）原表電話為重複群組，先化為 1NF：同一學生、課程、不同電話各一列，主鍵 (學號,課程編號,學生電話)。2NF 要求非主屬性完全相依於主鍵。因 學號→學生姓名、學生住址、聯絡人姓名、聯絡人電話、指導老師證號；課程編號→課程名稱、學分；(學號,課程編號)→成績，均只依賴部分主鍵，故拆為：學生(學號,學生姓名,學生住址,聯絡人姓名,聯絡人電話,指導老師證號,指導老師姓名,研究室,實驗室名稱,實驗室地點)、學生電話(學號,學生電話)、課程(課程編號,課程名稱,學分)、成績(學號,課程編號,成績)。四表均符合 2NF；遞移相依留待 3NF 處理。
  • （三）3NF 消除非主屬性之遞移相依。學生表有 學號→指導老師證號，指導老師證號→(指導老師姓名,研究室,實驗室名稱)，實驗室名稱→實驗室地點；另有 學號→(聯絡人姓名,聯絡人電話)，且 (聯絡人姓名,聯絡人電話)→聯絡人地址。故拆為：學生(學號,學生姓名,學生住址,聯絡人姓名,聯絡人電話,指導老師證號)、聯絡人(聯絡人姓名,聯絡人電話,聯絡人地址)、指導老師(指導老師證號,指導老師姓名,研究室)、實驗室(實驗室名稱,實驗室地點,指導老師證號)、學生電話(學號,學生電話)、課程(課程編號,課程名稱,學分)、成績(學號,課程編號,成績)。實驗室表的指導老師證號加 UNIQUE，維持一對一；各表符合 3NF。
  • （四）SQL 如下：SELECT S.學號, S.學生姓名, COUNT(DISTINCT G.課程編號) AS 修課數, T.指導老師姓名 FROM 學生 AS S LEFT JOIN 成績 AS G ON S.學號=G.學號 LEFT JOIN 指導老師 AS T ON S.指導老師證號=T.指導老師證號 GROUP BY S.學號, S.學生姓名, T.指導老師姓名; 使用 LEFT JOIN 可列出未修課學生並計為 0；COUNT(DISTINCT) 避免重複；不可 join 學生電話，否則多支電話會重複計數。
  • （五）此設計可減少插入、刪除與更新異常；自然連接 學生－成績－課程、學生－學生電話、學生－聯絡人、學生－指導老師－實驗室，可還原原表。限制：若電話可共用，學生電話鍵仍為 (學號,學生電話)；若需電話類型，應增欄位並調整鍵；若成績允許補考或多次修課，應增修課學期或成績版本，不能只以 (學號,課程編號) 為鍵。

第2題

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

參考解答（AI 生成，非官方）

  • （一）Row-major（列優先）是先存第 0 列所有元素，再存第 1 列；若 A 為 M×N、以 0 起始、元素大小 w、基底位址 B，則 A[i][j] 位址為 B+(i×N+j)×w。Column-major（行優先）是先存第 0 行所有元素，再存第 1 行，位址為 B+(j×M+i)×w。C/C++、Java 採列優先；Fortran、MATLAB 採行優先。兩者差別在於哪一個索引先連續變動。
  • （二）巨大型陣列之效率取決於 spatial locality（空間局部性）。CPU 一次載入一整條 cache line（快取線），若存取順序與記憶體排列一致，後續元素多半已在快取，可減少 cache miss、TLB miss 與記憶體頻寬浪費；跳躍式存取則可能每讀一元素就發生一次快取置換。故應依儲存順序走訪：列優先語言外層跑列、內層跑行；行優先語言外層跑行、內層跑列。
  • （三）以 C 列優先為例：int sum=0; for(i=0;i<M;i++) for(j=0;j<N;j++) sum+=A[i][j]; 內層 j 連續存取同一列，效率最佳。若改成 for(j=0;j<N;j++) for(i=0;i<M;i++) sum+=A[i][j]; 每次跨列，對大陣列會不斷 cache miss。若使用 Fortran 行優先，則應寫 do j=1,N; do i=1,M; sum=sum+A(i,j); end do; end do。編譯器雖可能自動迴圈交換，但含指標別名或動態記憶體時不可依賴。
  • （四）若單列或單行仍大於快取，可再用 loop tiling/blocking（迴圈分塊），切成 B×B 小塊，使每塊在快取中重複使用；矩陣乘法、轉置特別有效。另須注意資料對齊、prefetch、編譯器優化與多執行緒 false sharing。惟本題核心是「讀取順序與 layout 一致」；若函式庫可指定 order（如 NumPy 的 C order/F order），應配合設定或先轉置。

第3題

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

參考解答（AI 生成，非官方）

  • （一）BOM 為樹，欲使子件先於父件列印，採 postorder（後序）DFS：從根 P 出發，遞迴走訪每一子節點，待所有子樹列印完再列印目前節點。每節點僅訪問一次，時間 O(V+E)=O(n)，已是樹狀 BOM 的最快演算法；兄弟順序不影響正確性。以題示 C0 由 C11、C12、C13 組成、C11 由 C21、C22 組成，可輸出 C21,C22,C11,C12,C13,C0。
  • （二）虛擬碼：printBOM(N){ for each child C of N do printBOM(C); print(N); }，由 printBOM(P) 呼叫。若以 parent→child 儲存，後序即子先父後；若只存 child→parent，應先反轉邊或改用拓撲排序。若 BOM 不是樹而是共用零組件的 DAG，應改用 Kahn 拓撲排序，以 indegree 佇列輸出，複雜度同為 O(V+E)。遞迴過深時可用顯式堆疊模擬，避免 stack overflow。
  • （三）設 Tc(N) 為節點 N 的製程時間，機器與物料充足可平行生產，則 N 的最早完工時間 T(N)=Tc(N)+max{T(C)|C 為 N 的子節點}；葉節點 T(N)=Tc(N)。父件須等所有子件完成才開始，故取最慢子件而非加總。由根後序計算，答案 T(P) 即 critical path（關鍵路徑）的加權長度：T(P)=max over root-to-leaf paths ΣTc（含根節點）。
  • （四）虛擬碼：time(N){ if N is leaf return Tc(N); m=0; for each child C do m=max(m,time(C)); return Tc(N)+m; }。時間 O(n)、空間 O(h)。若題目的 Tc 不含組裝時間，應再加組裝時間；若機器或物料有限，平行假設不成立，問題變成資源受限排程，需以優先順序或整數規劃求解。題目未給各 Tc 數值，故只能列公式與步驟，無法算出唯一數值。

第4題

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

參考解答（AI 生成，非官方）

  • （一）IEEE 802.11 MPDU 的 Frame Control（訊框控制）長 2 octets（16 bits），含 11 個子欄位：Protocol Version、Type、Subtype、To DS、From DS、More Fragments、Retry、Power Management、More Data、Protected Frame、Order。前三個分別占 2、2、4 bits，其餘八個各 1 bit，合計 16 bits；此欄位位於 MAC header 最前端，接收端先解析再決定後續格式。
  • （二）Protocol Version（協定版本，2 bits）指出 MAC 版本，目前主要為 0。Type（訊框類型，2 bits）區分管理訊框（management, 00）、控制訊框（control, 01）、資料訊框（data, 10），11 保留。Subtype（子類型，4 bits）細分為 beacon、probe request/response、ACK、RTS、CTS、data 等；Type 與 Subtype 合併決定訊框用途與格式。
  • （三）To DS 與 From DS（各 1 bit）描述訊框是否往返 distribution system（DS，分散式系統），四種組合決定 Address 1~4 的意義與 BSS/IBSS/WDS 轉送路徑；例如兩者皆 0 表 IBSS 內直接通訊，To DS=1、From DS=0 表 STA 送至 AP。More Fragments（1 bit）表示後續是否還有片段；Retry（1 bit）表示是否為重傳，避免重複處理。
  • （四）Power Management（1 bit）表示 STA 送完此訊框後的省電模式，讓 AP 決定是否緩衝。More Data（1 bit）用於省電模式，告知 STA 尚有資料待傳。Protected Frame（舊稱 WEP bit，1 bit）表示 frame body 是否受 WEP/TKIP/CCMP 等保護；Order（1 bit）表示嚴格順序服務，或在 QoS/HT 訊框中表示帶有 HT Control 欄位，語意依版本與訊框型態而定。此 11 項共同決定訊框的版本、型態、轉送、片段、重傳、省電、緩衝、保護與順序處理。