108 年 國立清華大學服務科學研究所科管組《計算機概論》

這題考驗對迴圈與條件判斷的理解。程式碼中，for 迴圈初始化 k 為 0，條件是 k < 20，每次迭代 k 增加 2。在迴圈內部，有一個 if 條件判斷 k % 3 == 1，意思是當 k 除以 3 的餘數為 1 時，才執行 print(k + " ")。

我們來逐步追蹤 k 的值：

1. k = 0: 0 % 3 = 0 (不符合條件)
2. k = 2: 2 % 3 = 2 (不符合條件)
3. k = 4: 4 % 3 = 1 (符合條件)，印出 "4 "

此題主要在考察物件導向設計 (Object-Oriented Design, OOD) 的原則，特別是類別 (class) 的繼承 (inheritance) 與組合 (composition) 的應用。題目描述了一個計程車公司的需求，需要記錄每種車輛的「最大乘載人數」、「是否有娛樂系統」以及「每公升的平均里程數 (kml)」。

我們來分析各選項：

(a) Use one class, Taxi, with three instance variables: max_riders, entertainment, and kml
這是最直接的設計。一個 Taxi 類別，包含三個屬性：max_riders (整數)、entertainment (布林值或字串) 和 kml (浮點數)。這種設計簡單明瞭，能夠滿足需求。

(b) Use four unrelated classes: Taxi, Riders, Entertainment, and Kml
這顯然是錯誤的。Riders、Entertainment 和 Kml 並不是獨立的實體，它們是 Taxi 的屬性或特徵。將它們設為不相關的類別，無法有效地表示它們與計程車的關係。

(c) Use a class Taxi with three subclasses of itself: Riders, Entertainment, and Kml
繼承的目的是建立「is-a」的關係。例如，SportsCar is-a Car。在這裡，Riders、Entertainment 和 Kml 並不是 Taxi 的子類別。一個計程車不是「乘載人數」，也不是「娛樂系統」，更不是「每公升里程數」。這種設計是誤用繼承。

核心觀念

本題考查物件導向分析與設計中的：

1. 類別（class）與物件（object）
2. 繼承（inheritance）與 IS-A 關係
3. 關聯（association）與多對多關係
4. 封裝及多型（polymorphism）
5. 必要模型元素與可選的程式設計結構

題目中的主要關係可表示如下：

• 教師提供課程：Teacher 與 Course 的關聯
• 學生修習課程：Student 與 Course 的關聯
• 顧問指導學生：Advisor 與 Student 的關聯
• 教師或顧問具有薪資計算行為：salary()
• 教師可查詢目前開設的課程：courses_offered()
• 學生可查詢目前修習的課程：courses()
• 顧問可查詢被指導的學生：advisees()

其中，「不是所有教師都是顧問」及「不是所有顧問都在授課」表示：

$$Teacher \neq Advisor$$

兩者不能直接視為彼此的子類別；但兩者仍可能共享某個上層類別。

---

解題方法

判斷各選項是否「essential」時，應區分：

• 領域中的概念是否需要被表示
• 是否一定要使用繼承建立類別階層

物件導向設計中，繼承不是唯一的建模方式。只要使用獨立類別搭配關聯，就能完成題目要求。例如：

Teacher ── offers ── Course
Student ── takes ── Course
Advisor ── advises ── Student

因此，Person 或 Faculty 這類 superclass 可以減少重複程式碼，但不是系統能運作的必要條件。

---

選項分析

(a) Separate classes for each of: Course, Teacher, Advisor, Student

此選項表示分別建立：

• Course
• Teacher
• Advisor
• Student

這些類別能直接表示題目中的四種主要領域概念，並承載各自的資料與行為，例如：

Teacher.id
Teacher.name
Teacher.offeredCourses

Student.id
Student.name
Student.takingCourses

Advisor.advisees

題目要求區分教師、顧問、學生與課程的身份及關係，因此以獨立類別建模是合理且直接的做法。

此選項屬於必要的領域模型結構。即使實際程式也可以採用其他表示方式，例如使用角色（role）或標籤，仍必須在模型中清楚區分這些概念。

判定：不是本題所指的非必要元素。

---

(b) Superclass Person with subclasses: Teacher, Advisor, and Student

此選項建立：

Person
├── Teacher
├── Advisor
└── Student

由於教師、顧問與學生都具有：

• 身份編號
• 姓名

因此它們可以共享 Person 的共同屬性：

核心觀念

本題考查「連續序列計數」與程式迴圈中的變數更新。

要找出某個值 value 在陣列中的最長連續出現次數，應維護兩個變數：

• length：目前這一段連續序列的長度。
• longest：目前找到的最長連續序列長度。

當 num == value 時，length 加一；當 num != value 時，代表連續序列中斷，必須先更新 longest，再將 length 歸零，才能開始計算下一段序列。

---

解題方法

題目陣列為：

$$[4,6,8,8,2,9,8,8,8,7]$$

目標值為 $8$。

程式第 7 行在遇到 $8$ 時執行：

length++

但在第 8 至 12 行中，遇到非 $8$ 的數字時，程式只更新 longest：

if (length > longest) {
    longest = length
}

缺少以下關鍵指令：

length = 0

因此，length 不會在序列中斷時歸零，而是累計整個陣列中出現的 $8$ 的總次數。

逐步追蹤如下：

讀取數字	是否為 8	length	longest
4	否	0	0
6	否	0	0
8	是	1	0
8	是	2	0
2	否	2	2
9	否	2	2
8	是	3	2
8	是	4	2
8	是	5	2
7	否	5	5

迴圈結束後，第 15 至 17 行再次比較：

if (length > longest) {
    longest = length
}

此時：

核心觀念

length = 0 是變數的初始化敘述。程式在執行 length 的累加、比較或回傳之前，必須先為它指定初始值，否則會發生未定義變數錯誤，或使用錯誤的舊值。

若函式中後續使用：

length += 1

其實等價於：

length = length + 1

因此，length 必須在第一次執行 length += 1 之前完成初始化。

解題方法

判斷插入位置時，依序檢查各位置之後的程式碼：

1. 找出 length 第一次被讀取、累加、比較或回傳的位置。
2. 將 length = 0 放在該次使用之前。
3. 若初始化放在第一次使用之後，程式會先讀取尚未建立的變數，無法正常執行。

本題題幹未附上第 5 至第 14 行的原始程式碼；依題目選項所對應的標準程式結構，length 的第一次使用位於第 10 行，因此初始化應插入第 9 行與第 10 行之間。

選項分析

• (a) Between lines 5 and 6：錯誤。
  此位置不是題目中 length 第一次被使用前的必要初始化位置，無法依程式執行順序判定為正確插入點。

核心觀念

本題考查物件導向程式設計中的：

1. 繼承（inheritance）
2. 方法覆寫（method overriding）
3. 動態繫結／多型（dynamic dispatch / polymorphism）
4. super 呼叫父類別版本的方法

BadActor < Actor 表示 BadActor 繼承 Actor。因此，BadActor 可以覆寫父類別的 act() 與 rest() 方法。

關鍵規則如下：

• 直接呼叫 rest()：依照物件的實際型別，執行被覆寫後的版本。
• 呼叫 super.act()：強制執行父類別 Actor 的 act()。
• 呼叫 super.rest()：強制執行父類別 Actor 的 rest()。

雖然變數宣告為：

Actor somebody = BadActor.new()

但 somebody 實際參考的物件是 BadActor，所以透過 somebody.act() 呼叫時，會執行 BadActor.act()。

---

解題方法：依照方法呼叫順序追蹤輸出

執行：

somebody.act()

由於實際物件是 BadActor，首先執行：

BadActor.act()

其內容為：

super.act()
print("crying ")

第一步：執行 super.act()

super.act() 強制呼叫父類別 Actor.act()：

function act() {
  print("acting ")
  rest()
}

因此先輸出：

acting 

接著執行其中的：

rest()

這裡沒有使用 super，所以會依照實際物件型別進行動態繫結。實際物件是 BadActor，因此呼叫：

BadActor.rest()

第二步：執行 BadActor.rest()

function rest() {
  print("smoking ")
  super.rest()
}

先輸出：

smoking 

再執行 super.rest()，強制呼叫父類別 Actor.rest()：

function rest() {
  print("sleeping")
}

輸出：

sleeping

第三步：回到 BadActor.act()

父類別的 super.act() 執行完畢後，回到：

print("crying ")

輸出：

crying

因此完整輸出順序為：

acting smoking sleeping crying

---

呼叫流程

此題涉及資料庫設計中的實體 (Entity)、屬性 (Attribute) 和關係 (Relationship) 的概念，特別是處理多對多關係時的屬性儲存位置。

題目情境：

• 只能實現一個三元關係 (ternary relationship) R4。
• 不能實現任何二元關係 (binary relationships)。
• 需要記錄「學期 (semester)」和「年份 (year)」這些屬性，這些屬性是與「課程」相關的。

分析：

• 實體 (Entities)：Teacher, TA, Course。

• 關係 (Relationships)：

  • R1, R2, R3 是二元關係 (題目禁止使用)。
  • R4 是三元關係。從圖示和後續題目推測，R4 很可能代表 Teacher, TA, Course 之間的某種協作關係（例如，某 Teacher 在某學期教授某 Course，並由某 TA 協助）。

• 屬性 (Attributes)：semester (spring/fall), year。這些屬性是關於「課程」在特定時間（學期和年份）的安排。

問題： 這些屬性（semester, year）應該存放在哪裡？

考量點：

1. 屬性與哪個實體或關係最相關？ semester 和 year 是描述一個課程在特定時間點的安排。
2. 資料庫設計原則：
   • 實體的屬性應該存放在實體本身。
   • 關係的屬性（例如，在多對多關係的連結表中）應該存放在關係中。

選項分析：

(a) Teacher entity: Teacher 是一個實體。Semester 和 year 是關於課程安排的，不是 Teacher 本身的屬性。例如，一個 Teacher 可能在 2019 年秋季教 CS101，在 2020 年春季教 CS101。Teacher 本人沒有 semester 和 year 的屬性。

此題是關於資料庫設計中，如何透過實體、關係和屬性來強制執行「政策」(Policies)。題目限制只能使用三元關係 R4，禁止使用二元關係。我們需要找出哪些政策無法被這樣的設計所強制執行 (cannot be enforced)。

首先，回顧題目中提到的政策：
基本政策 (Basic Policies):

1. 一個課程 (Course) 在一個學期最多只能有一個分部 (section)。(A course can only be held at most once every semester.)
2. 一個學期中，只有一位教師 (Teacher) 負責教授某個課程 (Course)，但同一課程可以在不同學期由不同教師教授。(Only one teacher is responsible to teach a given course in a given semester, but the same course can be taught by different teachers in different semesters.)
3. 一個或多個助教 (TA) 可以選擇性地被分配到某個學期的課程。(One or more TAs can be optionally assigned to a course in a given semester.)

新政策 (New Policies): (出現在題目 8, 9, 10 中)
(b) 一位老師不能使用他/她目前正在指導的學生作為某課程的 TA。(A teacher cannot use someone they are currently advising as a TA for a course)
(c) 一位老師在同一個學期，不能使用同一個 TA 來協助兩個不同的課程。(One teacher cannot use the same TA for two different courses in the same semester)
(d) 一位 TA 在給定的學期內，不能在一個以上的課程工作。(A TA cannot work on more than one course in a given semester)

設計限制：

• 只能使用三元關係 R4。
• R4 涉及 Teacher, TA, Course。
• 從第 7 題得知，R4 可以包含 semester 和 year 屬性。

分析政策的可執行性：

1. 基本政策 1 (課程在學期最多一次)：

   • R4 包含 (Teacher, TA, Course, Semester, Year)。
   • 如果我們將 CourseID, Semester, Year 組合作為 R4 的一部分，並加入唯一約束 (unique constraint)，就可以確保一個課程在一個學期只出現一次。
   • 可執行。

2. 基本政策 2 (學期內每門課最多一位 Teacher)：

   • R4 包含 (Teacher, TA, Course, Semester, Year)。
   • 我們可以對 (CourseID, Semester, Year) 組合應用唯一約束，或者如果 R4 是 Teacher-Course-Semester 的關聯，則可以約束 (CourseID, Semester, Year) 的組合只能對應一個 TeacherID。
   • 可執行。

3. 基本政策 3 (一個或多個 TA 可選分配)：

   • R4 包含 (Teacher, TA, Course, Semester, Year)。
   • 如果 R4 設計為 (TeacherID, CourseID, Semester, Year) 是一個記錄，然後我們可以有多個 TAID 與這個記錄關聯（例如，透過另一個多對多關係，但我們被限制只能用 R4）。
   • 如果 R4 本身就是 Teacher-TA-Course-Semester-Year 的組合，那麼一個 (Course, Semester, Year) 可以關聯到多個 (Teacher, TA) 組合。
   • 由於 R4 是三元關係，它通常是 (Entity1, Entity2, Entity3) 的組合。

此題與上一題類似，但限制條件不同：只能使用二元關係 (R1, R2, R3)，禁止使用三元關係 R4。我們需要找出哪些政策無法被執行。

設計限制：

• 只能使用二元關係 R1, R2, R3。
• R1, R2, R3 可以包含 semester 和 year 屬性（從第 7 題的邏輯推斷）。
• 實體：Teacher, TA, Course。

基本政策 (Basic Policies):

1. 一個課程 (Course) 在一個學期最多只能有一個分部。
2. 一個學期中，只有一位教師 (Teacher) 負責教授某個課程 (Course)。
3. 一個或多個助教 (TA) 可以選擇性地被分配到某個學期的課程。

新政策 (New Policies):
(b) 一位老師不能使用他/她目前正在指導的學生作為某課程的 TA。
(c) 一位老師在同一個學期，不能使用同一個 TA 來協助兩個不同的課程。
(d) 一位 TA 在給定的學期內，不能在一個以上的課程工作。

分析政策的可執行性：

首先，我們需要假設 R1, R2, R3 是什麼關係，才能判斷政策。
從圖示看，R1, R2, R3 可能是：

• R1: Teacher <-> Course (表示 Teacher 教 Course)
• R2: TA <-> Course (表示 TA 協助 Course)
• R3: Teacher <-> TA (表示 Teacher 指導 TA，或 Teacher 和 TA 的某種關聯)
• 另外，還可能有一個 Teacher <-> Student 的指導關係，但題目中沒明確列出 R3 是 Teacher-Student。

重要假設： 題目提到「The model must include all three entities (Teacher, TA, and Course) used by their prior system」。圖示中 R1, R2, R3 是 Teacher-Course, TA-Course, Teacher-TA。

政策分析：

1. 基本政策 1 (課程在學期最多一次)：

   • 如果 Course 實體有 semester 和 year 屬性，則無法強制執行。
   • 如果我們建立一個 CourseOffering (課程開設) 的連結表，它與 Course, Semester, Year 相關聯，並且 CourseOffering ID 或 (CourseID, Semester, Year) 是唯一的，就可以執行。
   • 或者，如果 Teacher-Course 關係 (R1) 包含 semester 和 year，並且約束 (CourseID, Semester, Year) 只能有一個 TeacherID。
   • 需要仔細考慮 R1, R2, R3 的實現方式。 題目說「Entities will be implemented as tables, and relationships (R1, R2, R3, R4) might be implemented either foreign keys (1:1) or join tables (1:n, m:n). Attributes (such as id, name, semester, year, etc.) can be assigned to entities or to join tables of 1:n and m:n relationships.」
   • 假設 R1 是 Teacher-Course 的 m:n 關係，可以透過一個 Enrollment 或 TeachingAssignment 表來實現，這個表包含 TeacherID, CourseID, Semester, Year。對 (CourseID, Semester, Year) 加唯一約束。
   • 可執行。

2. 基本政策 2 (學期內每門課最多一位 Teacher)：

   • 如果 R1 (Teacher-Course) 使用 TeachingAssignment 表，並包含 TeacherID, CourseID, Semester, Year，我們可以對 (CourseID, Semester, Year) 組合施加唯一約束，確保只有一個 Teac

核心觀念

本題考查資料庫中「關係（relationship）」的選擇與最小化設計。判斷某組關係是否足以實作所有政策，必須檢查：

1. 每項政策涉及哪些實體。
2. 該政策需要二元關係（binary relationship）或三元關係（ternary relationship）。
3. 某個關係是否能由其他關係推導，避免重複建立。

其中：

• 二元關係一次連結兩種實體，例如 $A$ 與 $B$。
• 三元關係一次連結三種實體，例如 $A$、$B$ 與 $C$。
• 三元關係通常不能任意拆成數個二元關係，否則可能遺失三者同時成立的語意。

解題方法

本題題幹提到「前三項基本政策」與「後三項新政策」，但提供的內容沒有列出這六項政策分別由 $R1$、$R2$、$R3$、$R4$ 中哪些關係實作。因此，嚴格而言，無法僅依第 10 題的片段判定 $R1$、$R2$、$R3$ 哪一個可以涵蓋三項基本政策。

判斷流程應為：

1. 建立「政策—關係」對應表。
2. 檢查三元關係 $R4$ 是否為三項新政策共同需要。
3. 在 $R1$、$R2$、$R3$ 中，找出能涵蓋三項基本政策的最小組合。
4. 若某一個二元關係即可涵蓋全部基本政策，則答案會是該二元關係加上 $R4$。
5. 若三個二元關係各自代表不可省略的基本政策，則三者都必須保留。

依本題選項的設計，合理假設前文已說明：

• 三項基本政策可由一個特定的二元關係表示；
• 三項新政策必須透過三元關係 $R4$ 表示；
• $R4$ 無法由單純二元關係取代。

在此前提下，最小集合的形式必為：

$$\{\text{一個必要的二元關係}, R4\}$$

若前文指定基本政策由 $R1$ 涵蓋，則最小集合為：

$$\{R1,R4\}$$

選項分析

(a) Only binary $R1$ and ternary $R4$

這題考驗對不同資料結構適用性的理解，特別是在處理序列資料和排序時。題目描述了三種處理圖像的順序：

1. 按接收順序 (by order received)：先進先出 (FIFO)。
2. 按反向接收順序 (by reverse order received)：後進先出 (LIFO)。
3. 按圖像大小排序 (by size of image in bytes)：需要排序功能。

我們要找出「least suitable」（最不適合）的資料結構。

分析各資料結構：

• (a) Queue (佇列)：

  • 特性：FIFO (先進先出)。
  • 適用於：接收順序 (1)。
  • 不適用於：反向接收順序 (2) 和按大小排序 (3) (除非額外處理)。

• (b) Stack (堆疊)：

  • 特性：LIFO (後進先出)。
  • 適用於：反向接收順序 (2)。
  • 不適用於：接收順序 (1) 和按大小排序 (3) (除非額外處理)。

• (c) Hash Table (雜湊表)：

  • 特性：提供快速的鍵值查找、插入和刪除。它本身不維護順序。
  • 適用於：如果我們使用圖像 ID 或某種標識符作為鍵，可以快速存取特定圖像。但它不直接支援按接收順序、反向順序或大小順序進行存取或排序。
  • 要實現順序存取，需要額外的機制（例如，將圖像放入 Hash Table，然後再遍歷 Hash Table 的內容，但 Hash Table 的遍歷順序不是預定義的）。
  • 要實現按大小排序，Hash Table 本身不提供。

• (d) Binary Tree (二元樹)：

  • 特性：如果是一個二元搜尋樹 (Binary Search Tree, BST)，則可以支援排序。中序遍歷 BST 可以得到有序序列。
  • 適用於：按大小排序 (3)。
  • 對於順序 (1) 和 (2)，BST 本身不直接支援，但可以透過遍歷來實現。

這題考驗對資料結構在「分組」和「依類型查詢」方面的應用。題目描述需要儲存具有不同緊急程度 (urgency) 的任務 (tasks)，並且可能出現新的緊急程度類型。要求找出最適合「依類型檢索」任務的資料結構。

核心需求：

1. 儲存任務。
2. 任務有緊急程度屬性（例如 "now", "soon", "later", "never"，以及其他可能的類型）。
3. 能夠根據緊急程度類型，快速檢索出屬於該類型的所有任務。

分析各資料結構：

• (a) Array (陣列)：

  • 陣列是一段連續記憶體，用於儲存固定大小的元素。
  • 如果我們將所有任務放入一個陣列，要按緊急程度分組檢索，我們需要遍歷整個陣列，檢查每個任務的緊急程度，然後收集符合條件的。這不是最高效的「依類型檢索」。
  • 如果我們為每個緊急程度類型維護一個單獨的陣列，則可以實現，但這不是「by itself」（單獨使用）。

• (b) Hash Table (雜湊表)：

  • 特性：提供鍵值對 (key-value) 的儲存。鍵通常是唯一的，用於快速查找對應的值。
  • 應用於此問題：我們可以將「緊急程度類型」作為鍵 (key)，將「屬於該緊急程度的任務列表」作為值 (value)。
  • 例如：
    • Key: "now", Value: [Task1, Task5, Task8]

這題考驗對資料結構如何支援「決策樹」或「規則系統」的理解，這類系統常被用於專家系統，透過一系列問題導向最終結論。題目中的例子是一個簡單的決策過程，根據一系列是/否問題，導向一個推薦（Major: Service Science）。

核心需求：

• 建立一個決策過程，其中每個節點代表一個問題（或一個決策點）。
• 根據用戶的回答（y/n），導向不同的路徑。
• 最終達到一個葉節點，給出答案或推薦。

分析各資料結構：

• (a) Hash Table (雜湊表)：

  • Hash Table 主要用於快速查找鍵值對。它本身不包含結構化的路徑或層次關係，不適合表示決策樹。

• (b) Stack (堆疊)：

  • 堆疊是 LIFO 結構，常用於深度優先搜尋 (DFS) 或回溯。在實現遞迴函數時，堆疊是底層支援。
  • 在專家系統中，如果我們將決策過程看作是 DFS 遍歷，堆疊可以用來追蹤當前的路徑或待處理的分支。例如，在回溯時，可以將之前的決策點彈出。
  • 一個基於堆疊的 DFS 演算法，可以模擬走訪決策樹。

• (c) Queue (佇列)：

  • 佇列是 FIFO 結構，常用於廣度優先搜尋 (BFS)。