108 年 國立臺北大學資訊管理學系碩士班《計算機概論》
第 一、 題30 分
一、現擬建構一所大學的Relational DB。請回答以下問題:(30%)
-
滿足以下所有需求,建立ER Model,並繪製ER Diagram。(20%)
● ER Diagram 包含以下個體(Entity): COLLEGE、DEPARTMENT、STUDENT、TEACHER、COURSE。
● 有下列個體間的關係:
<COLLEGE, DEPARTMENT> - 學院有許多學系
<DEPARTMENT, STUDENT> - 學系有許多學生
<DEPARTMENT, TEACHER> - 學系有許多老師
<DEPARTMENT, COURSE, TEACHER> - 學系各老師開設許多課程
<STUDENT, COURSE> - 每學期每個學生應至少選讀一門課程並記錄成績
<TEACHER, COURSE> - 各老師應開設多門課程且一門課程可以由多個老師共同課設
● 應繪出個體的相關屬性(attributes)以表達個體間關係。
● 個體間關係以菱形表示,請參考圖1。
Company
Employee
Projects
圖1 ER Diagram 範例
● 個體間的關係,請以圖2的符號繪圖表達。
from Zero to Many
from One to Many
from One to One
i.e., one and only one
from Zero to One
一叶
圖2個體的關係符號 -
請寫出 SQL命令,找出修課成績低於60分的同學的學號、姓名、課程名稱。(10%)
登入後即可作答並保存紀錄。
核心觀念
本題評量**關聯式資料庫系統（Relational Database System）**的系統分析與設計能力，主要包含兩大核心：
- 實體關聯模型（ER Model）與基數限制（Cardinality / Multiplicity Constraints）：
- 實體（Entity）與屬性（Attribute）：識別主鍵（Primary Key）與外部鍵（Foreign Key）關聯。
- 關聯基數表示法（Crow's Foot Notation / 鴨嘴筆法）：題目圖 2 要求使用資訊工程與商管系統分析常用的 Crow's Foot 符號來表達基數：
Zero to Many（0 或多）：圓圈加三叉線（）One to Many（1 或多）：單槓加三叉線（）from One to One（恰好 1 個，one and only one）：雙槓（）from Zero to One（0 或 1）：圓圈加單槓（）
- 關聯屬性（Relationship Attribute）：兩個多對多實體之間的交會屬性（如選課成績），在實體關聯圖中應依附於關聯（Relationship）或交會實體上。
- 結構化查詢語言（SQL - Structured Query Language）：
- 跨多資料表關聯查詢（
INNER JOIN）與條件過濾（WHERE）。
- 跨多資料表關聯查詢（
解題方法
第 1 小題：實體、屬性與關聯基數設計
依題目規定的 5 個個體（Entity）以及個體間關係進行正規化屬性與基數分析：
-
實體及其基本屬性設計（底線表示主鍵 Primary Key）：
COLLEGE（學院）：<u>college_id</u>,college_nameDEPARTMENT（學系）：<u>dept_id</u>,dept_name,college_id（FK）STUDENT（學生）：<u>student_id</u>,student_name,dept_id（FK）TEACHER（教師）：<u>teacher_id</u>,teacher_name,dept_id（FK）COURSE（課程）：<u>course_id</u>,course_name
-
關聯與基數（Cardinality）分析：
<COLLEGE, DEPARTMENT>（包含/隸屬）：- 一個學院有許多學系（至少 1 個學系，
1..N）。 - 一個學系恰好屬於一個學院（
1..1）。
- 一個學院有許多學系（至少 1 個學系，
<DEPARTMENT, STUDENT>（主修/所屬）：- 一個學系有許多學生（
0..N或1..N）。 - 一個學生恰好屬於一個學系（
1..1）。
- 一個學系有許多學生（
<DEPARTMENT, TEACHER>（聘僱/所屬）：- 一個學系有許多老師（
1..N）。 - 一個老師恰好屬於一個學系（
1..1）。
- 一個學系有許多老師（
<STUDENT, COURSE>（選課關係，命名為ENROLL）：- 需求：「每學期每個學生應至少選讀一門課程並記錄成績」。
- 學生對課程：一個學生至少修 1 門課（
1..N）。 - 課程對學生：一門課可以有 0 到多位學生修讀（
0..N）。 - 關係屬性：
grade（成績）、semester（學期）。
<TEACHER, COURSE>（授課關係，命名為TEACH）：- 需求：「各老師應開設多門課程且一門課程可以由多個老師共同開設」。
- 老師對課程：老師必須開設多門課（
1..N，或考慮新進教師為0..N，題目明確說明「各老師應開設多門課程」，故下限為 1，為1..N）。 - 課程對老師：一門課程由 1 到多位老師共同開設（
1..N）。
<DEPARTMENT, COURSE, TEACHER>（學系各老師開設許多課程）：- 題目列出
<DEPARTMENT, COURSE, TEACHER>與<TEACHER, COURSE>。在關聯式架構中，若老師與學系是1..1歸屬，則學系透過其聘任的老師開課；若將開課單位明確化，COURSE亦可隸屬於開課的DEPARTMENT（1..1）。圖形中以獨立二元關聯即可精確表達所有限制，或依題意將開課視為老師與課程的多對多關聯。
- 題目列出
-
繪製 ER Diagram（依題目要求：個體為矩形、關聯為菱形、連線端點標示圖 2 符號）：
第 二、 題20 分
二、請回答下列有關後序表示式(postfix expression)的運算處理。(20%)
- 後序表示式 的前序表示式(prefix expression)為何?(5%)
- 請以 pseudo-code 或您所熟悉的程式語言,寫出中序表示式轉成後序表示式的演算法。(15%)
登入後即可作答並保存紀錄。
本題主要考察表達式的轉換與處理，涵蓋了前序、中序、後序表達式之間的轉換，以及棧 (Stack) 資料結構在演算法中的應用。
二、1. 後序轉前序表達式
核心觀念：
後序表達式 (Postfix Expression)，又稱逆波蘭表示法 (Reverse Polish Notation, RPN)，操作數在前，操作符在後。前序表達式 (Prefix Expression)，又稱波蘭表示法 (Polish Notation)，操作符在前，操作數在後。兩種表達式都無需括號。
轉換方法：
一種常見的轉換方法是利用棧。從後序表達式的右側開始掃描。
- 遇到操作數，壓入棧。
- 遇到操作符，從棧中彈出兩個操作數，將「操作符 + 第二個彈出的操作數 + 第一個彈出的操作數」組合起來，再壓入棧。
解題步驟：
後序表達式：
-
從右往左掃描：
- 掃描到
/：這是操作符。- 從棧彈出：
F(operand1),E(operand2) - 組合：
/ E F(操作符 operand2 operand1) - 壓入棧：
/ E F
- 從棧彈出：
- 掃描到
+：這是操作符。- 從棧彈出：
D(operand1),/ E F(operand2) - 組合：
+ D / E F - 壓入棧：
+ D / E F
- 從棧彈出：
- 掃描到
F：這是操作數。- 壓入棧：
F
- 壓入棧：
- 掃描到
/：這是操作符。- 從棧彈出：
E(operand1),D(operand2) - 組合：
/ E D - 壓入棧：
/ E D
- 從棧彈出：
- 掃描到
E：這是操作數。- 壓入棧：
E
- 壓入棧：
- 掃描到
*：這是操作符。- 從棧彈出：
C(operand1),B(operand2) - 組合：
* C B - 壓入棧：
* C B
- 從棧彈出：
- 掃描到
D：這是操作數。- 壓入棧：
D
- 壓入棧：
- 掃描到
C：這是操作數。- 壓入棧：
C
- 壓入棧：
- 掃描到
-：這是操作符。- 從棧彈出：
A(operand1),B(operand2) - 組合：
- A B - 壓入棧：
- A B
- 從棧彈出：
- 掃描到
B：這是操作數。- 壓入棧：
B
- 壓入棧：
- 掃描到
A：這是操作數。- 壓入棧：
A
- 壓入棧：
錯誤的掃描方向！ 後序表達式是從左往右掃描，而不是從右往左。
我們重新從左往右掃描。後序表達式：
- A: 操作數，壓入棧。 棧: [A]
- B: 操作數，壓入棧。 棧: [A, B]
- -: 操作符。彈出 B (operand2), 彈出 A (operand1)。組合成前序：
- A B。壓入棧。 棧: [- A B] - C: 操作數，壓入棧。 棧: [- A B, C]
- *: 操作符。彈出 C (operand2), 彈出 - A B (operand1)。組合成前序：
* - A B C。壓入棧。 棧: [* - A B C] - D: 操作數，壓入棧。 棧: [* - A B C, D]
- E: 操作數，壓入棧。 棧: [* - A B C, D, E]
- /: 操作符。彈出 E (operand2), 彈出 D (operand1)。組合成前序：
/ D E。壓入棧。 棧: [* - A B C, / D E] - F: 操作數，壓入棧。 棧: [* - A B C, / D E, F]
- +: 操作符。彈出 F (operand2), 彈出 / D E (operand1)。組合成前序：
+ / D E F。壓入棧。 棧: [* - A B C, + / D E F] - /: 操作符。彈出 + / D E F (operand2), 彈出 * - A B C (operand1)。組合成前序：
/ * - A B C + / D E F。壓入棧。 棧: [/ * - A B C + / D E F]
最終棧頂的元素就是前序表達式。
檢查：
- ->
- A B (- A B) C *->* (- A B) CD E /->/ D E(/ D E) F +->+ (/ D E) F(* (- A B) C) (+ (/ D E) F) /->/ (* (- A B) C) (+ (/ D E) F)
所以，前序表達式為：
/ * - A B C + / D E F - 掃描到
二、2. 中序轉後序表達式演算法
核心觀念：
將中序表達式（操作符在操作數之間，如 ）轉換為後序表達式（操作符在操作數之後，如 ）。
第 三、 題20 分
三、目前流行的線上遊戲(例如:Freefire 生存射擊遊戲),它讓多人組隊線上對戰,戰敗者也可以繼續觀看生存者的過程,你可以想像背後網路要如何將遊戲過程群播給所有參賽者或是觀賽者嗎?請搭配(1)繪製網路簡圖:提出(2)前置處理和(3)遊戲對戰多人連線遊戲訊息傳送的群播方法,以使分布在不同地區的玩家可以在最短時間收到遊戲現況資料。(20%)
登入後即可作答並保存紀錄。
本題主要考察網路通訊中的群播 (Multicast) 技術在遊戲應用中的實踐，以及相關的網路架構設計。
核心觀念：
- 群播 (Multicast): 一種網路傳輸技術，允許一個發送者將數據包一次性發送給預定的一組接收者，而不是點對點 (Unicast) 或廣播 (Broadcast) 給所有主機。這能顯著提高網路效率，減少頻寬消耗。
- 遊戲網路架構： 遊戲需要低延遲、高頻寬的傳輸，特別是即時對戰遊戲。
- 地理分佈： 玩家分散在不同地區，需要考慮網路延遲和頻寬限制。
解題步驟：
(1) 繪製網路簡圖
這個網路簡圖需要展示遊戲伺服器、玩家（參賽者和觀賽者）之間的連接關係，並體現群播的架構。
簡圖要素：
- 遊戲伺服器 (Game Server): 核心，負責遊戲邏輯、狀態同步、訊息處理。可能有多個伺服器（例如：遊戲邏輯伺服器、認證伺服器、錄影伺服器等）。
- 玩家端 (Client): 參與遊戲的玩家（參賽者）和觀看比賽的玩家（觀賽者）。
- 網路基礎設施： 網際網路 (Internet)、路由器 (Routers)、網路交換機 (Switches)。
- 群播傳輸路徑： 示意如何將遊戲狀態訊息從伺服器傳遞到多個玩家。
簡圖示意 (文字描述):
+-----------------+ +----------------------+
| Player A | | Player B |
| (Participant) | | (Spectator) |
+-----------------+ +----------------------+
| |
| |
+-----------------+ +----------------------+
| Player C | | Player D |
| (Participant) | | (Spectator) |
+-----------------+ +----------------------+
| |
--------------------------
|
+-------------------------+
| Internet (WAN) |
+-------------------------+
|
+-------------------------+
| Game Server Cluster |
| (Logic, State Sync, |
| Multicast Sender) |
+-------------------------+
|
+-----------------+ (Multicast Group)
| |
v v
+-----------------+ +-----------------+
| Player E | | Player F |
| (Participant) | | (Spectator) |
+-----------------+ +-----------------+
更詳細的簡圖說明：
- 中心節點： 遊戲伺服器群集 (Game Server Cluster)。這通常是單一邏輯實體，但物理上可能有多台伺服器協同工作。
- 連接： 玩家通過網際網路連接到遊戲伺服器。
- 群播的體現： 遊戲伺服器將遊戲狀態更新（如玩家位置、動作、事件）作為群播數據包發送。
- 群播組 (Multicast Group): 伺服器將數據發送到一個特定的群播地址。所有訂閱了該群播地址的玩家（參賽者和觀賽者）都會接收到這些數據。
- 路由器角色： 網路中的路由器需要支援 IP Multicast 協議（如 IGMP - Internet Group Management Protocol，PIM - Protocol Independent Multicast），以便將群播數據有效地路由到訂閱的接收者。
第 四、 題15 分
四、請分析一旦自動駕駛(甚至是無人駕駛)結合共享經濟之下,將帶來生活怎樣的影響?請就個人、社會、以及環境等三方面來探討。(15%)
登入後即可作答並保存紀錄。
本題主要考察自動駕駛技術與共享經濟結合後，可能對個人、社會和環境帶來的多面向影響。這是一個應用與趨勢分析題。
核心觀念：
- 自動駕駛 (Autonomous Driving): 汽車無需人類駕駛員操作即可行駛，根據技術成熟度分為不同等級（L1-L5）。
- 共享經濟 (Sharing Economy): 透過網路平台，將閒置的資源（如汽車、房屋、技能）分享給他人使用，以獲取報酬。
- 整合效應： 自動駕駛技術與共享經濟的結合，可能放大各自的優勢，並產生新的影響。
解題步驟：
針對個人、社會、環境三個層面，分別探討自動駕駛與共享經濟結合的影響。
一、個人層面影響：
- 提升便利性與自由度：
- 無需駕駛： 駕駛員可以將通勤時間用於工作、學習、娛樂、休息，提高時間利用效率。
- 行動能力增強： 對於無法駕駛的群體（如老年人、視障者、未成年人、有飲酒習慣者）提供極大的行動自由。
- 點對點的無縫接駁： 透過共享平台，可以隨時隨地呼叫到自動駕駛汽車，減少等待時間，實現更靈活的出行。
- 降低擁有成本與負擔：
- 減少購車需求： 大多數人可能不再需要擁有私家車，只需按需使用共享自動駕駛汽車，節省購車、保險、維護、停車等費用。
- 更實惠的出行方式： 共享自動駕駛汽車的運營成本（人力成本為零，規模化效應）可能比傳統計程車或網約車更低，提供更經濟的出行選擇。
- 生活方式的改變：
- 通勤體驗改善： 從枯燥的駕駛變為舒適的移動空間，可能改變人們對通勤的看法。
- 新的服務機會： 車內空間可被改造成移動辦公室、娛樂室、休息室等，催生新的車內服務。
- 潛在的技術依賴與隱私問題： 對自動駕駛系統的依賴增加，個人出行數據（路線、時間、偏好）可能被收集和利用，引發隱私擔憂。
二、社會層面影響：
- 交通系統的革新：
- 減少交通事故： 自動駕駛技術有望大幅降低因人為失誤造成的交通事故，提高道路安全。
- 緩解交通擁堵： 共享自動駕駛汽車可以更有效地利用道路空間（例如：更小的車距、智能調度），並減少閒置車輛佔用的停車位，從而緩解擁堵。
- 優化交通流量： 系統可以進行全局調度，引導車輛避開擁堵區域，實現更流暢的交通。
- 改變城市規劃： 停車場需求可能減少，釋放城市空間用於其他用途（如綠地、住宅、商業）。公共交通系統可能需要與自動駕駛共享汽車協同發展。
- 就業結構的轉變：
- 傳統駕駛員失業： 計程車司機、貨車司機、公車司機等職業可能面臨大規模失業。
第 五、 題15 分
五、程式分流是大量雲端運算節能的方法之一,於下圖的四則運算程式範例中,當選擇做加法,就會跳到加法的執行程式,作答完就會跳到檢查的程式,如果答對就顯示 Correct,反之則顯示Wrong,不同練習程式執行所需的資源是有所差異的。倘若時段 A有非常龐大的使用者(如:數千萬位小朋友)同時上線練習加法,另一個時段B上線練習乘法,你如何依下圖的程式結構和提示,提出適當的主機處理資源配置演算法,以達到部分雲端主機關機或進入睡眠節能狀態,又能達到服務品質而不發生練習過程停頓的現象?(15%)
圖、雲端分流運算範例程式
Main()
Select Case operator x
Case 1: Add()
Case 2: Substract()
Case 3: Multiply()
Case 4: Divide()
End Select
End Main()
Case 1
Add()
Cloud Host #1
x2 = Random()
x = Random()
R = x2 + x
Please input the answer for x2+x
Check(R, answer)
...
Case 2
Substract()
Cloud Host #2
x2 = Random()
x = Random()
R = x2 - x
Please input the answer for x2-x
Check(R, answer)
...
Case 3
Multiply()
Cloud Host #3
x2 = Random()
x = Random()
R = x2 * x
Please input the answer for x2*x
Check(R, answer)
...
Case 4
Divide()
Cloud Host #4
x2 = Random()
x = Random()
R = x2 / x
Please input the answer for x2/x
Check(R, answer)
...
Cloud Host #5
Check(R, answer)
if (R == answer) Correct
else Wrong
...
The range of x, is x=1-4
Once x, is determined
Once x, is determined
Only Cloud Host #n is determined
🖼️【此處有附圖，請對照原卷】
(圖示為一個流程圖，Main() 根據 operator x 分流到 Case 1-4，每個 Case 執行對應運算並跳轉到 Check()。Check() 函數在 Cloud Host #5 中，根據運算結果 R 和使用者輸入 answer 判斷對錯，並跳轉到 Correct 或 Wrong。每個 Case 都關聯一個 Cloud Host #n，暗示運算可能在特定主機上執行。)
登入後即可作答並保存紀錄。
本題考察雲端運算中的資源調度與節能策略，特別是在面對不同負載情境下，如何分配計算資源以兼顧服務品質 (QoS) 和節能。
核心觀念：
- 雲端運算資源調度： 如何將計算任務分配到不同的伺服器或主機上。
- 節能策略： 關閉或進入低功耗模式的伺服器，以減少能源消耗。
- 服務品質 (QoS)： 確保使用者能夠獲得穩定、快速的服務，不因資源分配或節能措施而受到影響。
- 負載均衡 (Load Balancing)： 將請求分散到多個伺服器，避免單一伺服器過載。
- 彈性擴展 (Elasticity): 根據實際負載動態增減計算資源。
解題步驟：
題目描述的場景是：
- 時段 A： 大量使用者 (數千萬) 同時練習加法 (Case 1)。
- 時段 B： 大量使用者同時練習乘法 (Case 3)。
- 目標：在保證服務品質（不發生停頓）的前提下，實現部分雲端主機關機或進入睡眠節能狀態。
分析程式結構與提示：
- 分流：
Main()根據選擇的操作符 (operator x) 將請求分流到不同的 Case (1-4)。 - 運算主機： 每個 Case (運算) 都關聯一個
Cloud Host #n。這表示加法運算可能在Cloud Host #1，乘法在Cloud Host #3等執行。 - 檢查主機：
Check()函數獨立於運算主機，可能由Cloud Host #5執行。 - 資源需求： 題目提示「不同練習程式執行所需的資源是有所差異的」。雖然加法和乘法都是基本運算，但為了節能，我們可以假設某些運算（如加法）所需的計算資源相對較少，而其他運算（如乘法、除法）可能需要更多資源，或者更適合分配到專用的、更強大的主機上。
- 提示： "Once is determined, Once is determined, Only Cloud Host #n is determined"。這句話似乎在強調，一旦確定了運算類型（由 或 決定，這裡指 operator x），則對應的運算主機就被確定了。
資源配置演算法設計：
核心思想是基於「負載預測」和「彈性資源分配」。
-
資源池劃分與預設配置：
- 加法專用資源池 (Pool A): 由於時段 A 有「數千萬」使用者練習加法，這意味著加法運算負載極高。需要配置足夠的
Cloud Host #1來處理這個高負載。 - 乘法專用資源池 (Pool B): 時段 B 有大量使用者練習乘法。
- 其他運算資源池 (Pool C, D): 減法、除法。
- 檢查服務資源池 (Pool Check): 專門為
Check()函數分配資源。 - 節能資源池 (Pool Sleep): 預留一部分主機，在低負載時進入睡眠模式。
- 加法專用資源池 (Pool A): 由於時段 A 有「數千萬」使用者練習加法，這意味著加法運算負載極高。需要配置足夠的
-
負載監控與預測：
- 實時監控每個運算池（Pool A, B, C, D）的請求數量和處理延遲。
- 根據歷史數據和當前請求速率，預測未來一段時間內的負載趨勢。
-
彈性資源調度策略：
-
時段 A (大量加法練習):
- 策略： 集中資源處理加法。
- 執行：
- 確保
Cloud Host #1所在的加法資源池 (Pool A) 擁有足夠多的伺服器來應對數千萬級的請求。 - 對於其他運算 (Case 2, 3, 4)，如果請求量很低（例如，只有少量使用者練習乘法或除法），則可以將這些運算請求導向較少的主機，或者暫時不啟動專門的主機。
- 節能措施：
- 如果加法池的負載不是持續性的極高，可以在請求量低峰期（例如，使用者活躍度下降時），動態地關閉一部分
Cloud Host #1。 - 對於乘法、減法、除法等請求量極低時，可以將其導向少數幾台共享主機，或者直接將請求拒絕（如果允許部分服務降級）。
- 最關鍵的節能點： 如果在時段 A，只有加法有極高負載，而乘法、減法、除法的請求量非常少，那麼可以將負責乘法、減法、除法的
Cloud Host #3,#2,#4關閉或置於睡眠模式。
- 如果加法池的負載不是持續性的極高，可以在請求量低峰期（例如，使用者活躍度下降時），動態地關閉一部分
- 確保
- 服務品質保證： 確保加法運算的
Cloud Host #1數量充足，延遲在可接受範圍內。Check()服務 (Cloud Host #5) 也需要有足夠資源。
-
時段 B (大量乘法練習):
- 策略： 集中資源處理乘法。
- 執行：
- 確保
Cloud Host #3所在的乘法資源池 (Pool B) 擁有足夠多的伺服器。 - 節能措施：
- 如果加法請求量不高（例如，只有少量使用者練習加法），則可以關閉或讓部分
Cloud Host #1進入睡眠模式。 - 嚴格來說，題目只說「時段 A 有非常龐大的使用者...練習加法」，「另一個時段 B 上線練習乘法」。這暗示了在時段 A，加法是主要負載，其他相對較小；在時段 B，乘法是主要負載，其他相對較小。
- 如果加法請求量不高（例如，只有少量使用者練習加法），則可以關閉或讓部分
- 確保
-