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

已知110002，1103，1024，1025，556，447，518，係用不同進位表達的數 字，例如518 是一個用8 進位表達的數字51。（每小題10 分，共20 分） 請將它們全部轉換為10 進位的數字。 請用快速排序法（quick sort）來將這些表達成10 進位的數字作排序， 並說明過程。

在Microsoft Access 中，建有「老師資料表」與「課程資料表」，兩個表 格皆有四個欄位，內容如下圖： 老師資料表 課程資料表 老師ID 姓名 電話 年紀 課程ID 課程名稱 老師ID 人數 1 張三 123 30 1 國文 1 58

同步控制（concurrency control）是資料庫管理系統（DBMS）裡的必要功 能之一。請說明下列有關問題：（每小題10 分，共20 分） 如果資料庫管理系統沒有做好同步控制，則有可能在多筆交易 （transactions）同時執行時，發生資料更新後有錯誤的情形，請說明這 是指什麼問題。 二階段鎖定協定（two-phase locking protocol）可以保證有衝突的交易在 更新資料時仍保持資料的正確性。請說明什麼是二階段鎖定協定，並解 釋為什麼二階段鎖定能使有衝突的交易仍能被正確的執行。

王武 456 56 2 英文 2 63

某資料庫有下列關連，請用SQL 語法回答下列查詢。 （每小題10 分，共20 分） 學生（學號，姓名，電話） 成績（學號，科目名稱，分數） 針對一查詢是「列出所有在科目名稱是“資料處理”這門課裡分數不及 格（< 60 分）的學生的姓名和電話」，某同學想要用巢狀查詢（nested query）的寫法來回答此查詢。可是只完成了上半部，請幫他完成此查詢 餘下的部分。亦即，請填入下列括號裡“？”部分應填入的指令。 SELECT 姓名，電話 FROM 學生 WHERE 學號IN（？）； 請列出各個科目的科目名稱，和所有學生在該科目成績的平均分數。

劉丹 897 42 3 數學 1 42

已知一個二元樹如下圖。（每小題10 分，共20 分） 說明用廣度優先的順序來走訪這棵樹，其順序為何？ 說明用深度優先的順序來走訪這棵樹，其順序為何？

陳河 658 39 4 物理 2 89

在關聯式資料庫（Relational Database）裡，針對關聯有一些限制條件 （Constraints）。（每小題10 分，共20 分） 請說明什麼是鍵值限制（Key Constraint）。 請說明什麼是參考完整限制（Referential Integrity Constraint）。

高樂 756 60

假如某公司的關聯式資料庫包含以下三個表格，其內之欄位如括號內所示。 客戶（客戶編號，姓名，電話，地址，年齡） 產品（產品編號，產品名稱，價格，庫存數量） 訂單（訂單編號，購貨日期，客戶編號，產品編號，購買數量） 請寫出SQL 敘述（statement）以列出地址在臺北市的客戶姓名與電話。 （5 分） 請寫出SQL 敘述以列出各個產品名稱及其平均購買數量。（7 分） 針對不同客戶，請寫出SQL 敘述以計算各個客戶所購買之各產品的購 買數量。（8 分）

化學 3 67

微積分 4 75

音樂 5 30 9 美術 5 36 10 電子學 4 69 其資料庫關聯圖如下圖所示， 在「課程資料表」中，PK 與FK 的欄位名稱為何？（5 分） 請說明上圖1↔∞關聯的特色與優點。（8 分） 寫一個SQL 指令查詢來得到下表，其中欄位「人數總和」為該老師所 開所有課程的人數總和。（10 分） 姓名 人數總和 王武 152 高樂 66 張三 100 陳河 144 劉丹 67 寫一個SQL 指令查詢來得到課程老師的年紀小於55 歲，且人數大於 50 人的課程資訊表，如下表所示，且該資料需以人數遞減排序。（12 分） 課程ID 課程名稱 姓名 電話 人數 7 微積分 陳河 658 75 10 電子學 陳河 658 69 6 化學 劉丹 897 67 1 國文 張三 123 58 1 ∞ 老師資料表 老師ID 姓名 電話 年紀 課程資料表 課程ID 課程名稱 老師ID 人數 45130 二、有一筆資料的鍵值依序為32，17，85，16，51，60。使用除法雜湊函數 ( ) mod 7 h k k  來建立7 個桶（buckets）且每個桶只有一個槽（slot）的 雜湊表（hash table）。當發生碰撞（collision）與溢位問題時， 如果使用開放定址（open addressing）中的線性探測法（linear probing）， 請寫出產生的雜湊表格。（5 分）而此方法的主要缺點為何？（5 分） 如果使用開放定址（open addressing）中的平方探測法（quadratic probing），新的雜湊函數為：    2 , mod 7 H k i h k i       ，其中i 為目前 進行的探測次數。請寫出產生的雜湊表格。（10 分） 請說明何謂連結串列法（chaining）。（8 分） 請寫出使用連結串列法而產生的雜湊表格。（7 分） 三、電腦無線網路的標準為IEEE802.11 系列，常見的包含有802.11ac 802.11b 802.11n 802.11g 802.11ax， 請問WiFi 5 與WiFi 6 各指的是那一個標準？（10 分） 請問何謂MIMO？（10 分） 上述標準中，支援MIMO 的標準有那幾個？（5 分） 上述標準中，工作頻率可為2.4 kHz 或5 kHz 標準有那幾個？（5 分）