110 身心障礙特考四等 資訊處理 資料處理概要 考古題詳解
第 一 題20 分
已知 、、、、、、，係用不同進位表達的數字，例如 是一個用 8 進位表達的數字 51。
(一) 請將它們全部轉換為 10 進位的數字。
(二) 請用快速排序法（quick sort）來將這些表達成 10 進位的數字作排序，並說明過程。
登入後即可作答並保存紀錄。
核心觀念
題目考查進位制轉換與快速排序。將 進位數字換算成十進位時，依位值展開：
其中每個數字位數都必須小於底數 。排序時，先將數值轉成十進位，再以快速排序法選取樞紐（pivot），將資料分成小於及大於樞紐的部分，並對兩部分遞迴排序。
解題方法
（一）轉換為十進位
依各位數的位值展開：
因此，依題目原順序換算後為：
（二）快速排序
採用「每次取目前子序列第一個元素為樞紐」的方式；樞紐左側放小於樞紐的數，右側放大於樞紐的數，再分別遞迴排序。
第 二 題20 分
同步控制（concurrency control）是資料庫管理系統（DBMS）裡的必要功能之一。請說明下列有關問題：
(一) 如果資料庫管理系統沒有做好同步控制，則有可能在多筆交易（transactions）同時執行時，發生資料更新後有錯誤的情形，請說明這是指什麼問題。
(二) 二階段鎖定協定（two-phase locking protocol）可以保證有衝突的交易在更新資料時仍保持資料的正確性。請說明什麼是二階段鎖定協定，並解釋為什麼二階段鎖定能使有衝突的交易仍能被正確的執行。
登入後即可作答並保存紀錄。
核心觀念
本題考資料庫的同步控制與二階段鎖定協定。多筆交易同時讀寫資料時，DBMS 必須安排其操作順序，使執行結果等同於某種正確的序列執行；否則即使各交易單獨執行都正確，交錯執行仍可能造成資料錯誤。
（一）未妥善同步控制造成的更新錯誤
典型問題是遺失更新（lost update）：兩筆交易讀取同一筆資料，各自計算新值並寫回；後寫入的交易覆蓋先前交易的更新，導致其中一筆更新消失。
例如，資料 原值為 ：
| 操作順序 | 交易 ：存入 | 交易 ：提領 |
|---|---|---|
| 1 | 讀取 | |
| 2 | 讀取 | |
| 3 | 計算 | |
| 4 | 計算 | |
| 5 | 寫入 | |
| 6 | 寫入 |
若依序執行，正確結果應為 ；但上述交錯執行後，資料庫中的 為 ， 的更新被 覆蓋，這就是遺失更新。
（二）二階段鎖定協定
**二階段鎖定協定（Two-Phase Locking, 2PL）**規定，每筆交易的加鎖與解鎖分為兩個階段：
- 成長階段（growing phase）：交易可以取得新鎖，但不得釋放已持有的鎖。
第 三 題20 分
某資料庫有下列關聯，請用 SQL 語法回答下列查詢。
學生（學號、姓名、電話）
成績（學號、科目名稱、分數）
(一) 針對一查詢是「列出所有在科目名稱是“資料處理”這門課裡分數不及格（ 分）的學生的姓名和電話」，某同學想要用巢狀查詢（nested query）的寫法來回答此查詢。可是只完成了上半部，請幫他完成此查詢餘下的部分。亦即，請填入下列括號裡「？」部分應填入的指令。
SELECT 姓名，電話
FROM 學生
WHERE 學號 IN（？）；
(二) 請列出各個科目的科目名稱，和所有學生在該科目成績的平均分數。
登入後即可作答並保存紀錄。
核心觀念
本題考查 SQL 的巢狀查詢、IN 子查詢，以及彙總函數 AVG 搭配 GROUP BY 的使用。
- 「學生」關聯提供學生姓名與電話；「成績」關聯記錄各學生各科的分數。
- 子查詢可先從「成績」找出符合條件的學號，再由外層查詢至「學生」找出對應的姓名與電話。
- 計算各科平均分數時，使用
AVG(分數)彙總分數，並以科目名稱分組。
解題方法
（一）查詢「資料處理」不及格學生的姓名與電話
子查詢篩選「成績」中科目名稱為「資料處理」且分數低於 的紀錄，取出其中的學號。外層查詢再以 IN 比對學生學號，取得姓名與電話。
SELECT 姓名, 電話
FROM 學生
WHERE 學號 IN (
SELECT 學號
FROM 成績
WHERE 科目名稱 = '資料處理'
AND 分數 < 60
);
括號中的內容即為：
第 四 題20 分
已知一個二元樹如下圖。
（此題原卷文字擷取不全，請參考原卷）
(一) 說明用廣度優先的順序來走訪這棵樹，其順序為何？
(二) 說明用深度優先的順序來走訪這棵樹，其順序為何？
登入後即可作答並保存紀錄。
核心觀念
本題考二元樹的走訪方式：
- 廣度優先走訪（BFS）：逐層由上而下，同一層由左至右，通常使用佇列。
- 深度優先走訪（DFS）：沿著一條分支往下走到底，再回溯走訪其他分支。二元樹的 DFS 可依根節點的訪問時機分成前序、中序、後序。本題未指定種類，以下依常見的「根節點先訪問、左子樹優先」前序方式作答。
解題方法
先依圖辨認節點關係： 的左、右子節點為 ； 的左、右子節點為 ，且 的左子節點為 ； 的左子節點為 ，且 的左、右子節點為 。
（一）廣度優先
逐層由左至右列出：
- 第 1 層：
- 第 2 層：
- 第 3 層：
- 第 4 層：
因此，廣度優先走訪順序為：
第 五 題20 分
在關聯式資料庫（Relational Database）裡，針對關聯有一些限制條件（Constraints）。
(一) 請說明什麼是鍵值限制（Key Constraint）。
(二) 請說明什麼是參考完整限制（Referential Integrity Constraint）。
登入後即可作答並保存紀錄。
核心觀念
本題考查關聯式資料庫的兩種完整性限制：
- 鍵值限制（Key Constraint）：規範資料表中哪些屬性可用來唯一識別每一筆資料。
- 參考完整限制（Referential Integrity Constraint）：規範資料表之間的參照關係，確保外鍵所指向的資料確實存在。
解題方法
先區分兩種限制的作用範圍：鍵值限制關注同一個關聯內的列是否唯一；參考完整限制關注不同關聯之間的參照是否有效。再分別說明其定義與違反限制的情形。
（一）鍵值限制（Key Constraint）
在關聯 中，若屬性集合 的值可以唯一識別每一筆資料，則 是 的超鍵（Superkey）。換言之， 中任兩筆不同的資料列，在 上的值不得完全相同：
若 是不含多餘屬性的最小超鍵，則稱為候選鍵（Candidate Key）。資料表選定其中一個候選鍵作為主要鍵（Primary Key），其他候選鍵則稱為替代鍵（Alternate Key）。
因此，鍵值限制的重點是：鍵值不可重複，且能唯一識別資料列。例如「學生」資料表以學號為主鍵，則不同學生不得有相同學號。若主鍵由多個屬性組成，必須以整組屬性判斷唯一性；例如「選課」資料表可用（學號、課程編號）作為複合主鍵。