IB CCEA Computer Science: Typical Example Questions Explained | IB CCEA 计算机：典型例题详解

📚 IB CCEA Computer Science: Typical Example Questions Explained | IB CCEA 计算机：典型例题详解

Understanding core concepts through worked examples is one of the most effective ways to prepare for IB and CCEA Computer Science exams. This article presents ten typical exam-style questions, each with step-by-step solutions, covering algorithm analysis, data structures, Boolean logic, finite state machines, SQL, object-oriented programming, recursion, scheduling, and networking. The bilingual explanations help you solidify both technical vocabulary and problem-solving strategies.

通过典型例题掌握核心概念是备考 IB 和 CCEA 计算机科学考试最有效的方法之一。本文精选十道常考题型，逐一给出详细解答，涵盖算法分析、数据结构、布尔逻辑、有限状态机、SQL、面向对象编程、递归、调度和网络等主题。中英双语讲解能同时巩固你的专业术语和解题思路。

1. Algorithmic Complexity: Big-O Notation | 算法复杂度：大O表示法

Question: Analyse the time complexity of the following pseudocode that searches for a target value in a sorted array using both a sequential scan and a binary search approach. Determine the best-case and worst-case Big-O.

题目：分析以下伪代码在有序数组中查找目标值的时间复杂度，分别给出顺序扫描和二分查找的最佳与最坏情况大O表示。

For a sequential scan over an array of n elements, the worst-case occurs when the target is at the final position or not present. The algorithm must examine all n elements, giving O(n). The best-case is O(1) when the target is at the first element.

对于含有 n 个元素的有序数组，顺序扫描的最坏情况是目标在最后一个位置或不存在，此时需要检查全部 n 个元素，复杂度为 O(n)。最佳情况是目标在第一个元素处，复杂度为 O(1)。

Binary search repeatedly halves the search space. In each step it compares the middle element. The worst-case number of steps is log₂ n, so the complexity is O(log n). The best-case is O(1) when the middle element matches immediately.

二分查找每次将搜索空间减半，每一步比较中间元素。最坏情况下最多需要 log₂ n 步，复杂度为 O(log n)。最佳情况是中间元素立即匹配，复杂度为 O(1)。

Remember that Big-O notation describes the upper bound of growth. When loops are nested, the complexities multiply; for two nested loops each iterating n times, the total is O(n²).

记住，大O表示法描述的是增长的上界。当循环嵌套时，复杂度相乘；若两个分别迭代 n 次的循环嵌套，总复杂度为 O(n²)。

2. Binary Search Tree Insertion and Traversals | 二叉搜索树插入与遍历

Question: Insert the following keys in order into an initially empty binary search tree (BST): 50, 30, 70, 20, 40, 60, 80. Then list the nodes visited during pre-order, in-order, and post-order traversals.

题目：将以下键值按顺序插入一棵初始为空的二叉搜索树：50, 30, 70, 20, 40, 60, 80。然后列出先序、中序和后序遍历所访问的节点。

Traversal	Order of nodes visited	遍历方式	访问节点顺序
Pre-order	50, 30, 20, 40, 70, 60, 80	先序	50, 30, 20, 40, 70, 60, 80
In-order	20, 30, 40, 50, 60, 70, 80	中序	20, 30, 40, 50, 60, 70, 80
Post-order	20, 40, 30, 60, 80, 70, 50	后序	20, 40, 30, 60, 80, 70, 50

The BST property ensures that for any node, all keys in its left subtree are smaller and all keys in the right subtree are larger. In-order traversal always yields keys in ascending order, which is a key characteristic often tested in exams.

BST 的性质保证任意节点的左子树中的所有键值都比该节点小，右子树中的所有键值都比该节点大。中序遍历总是按升序输出键值，这是考试中常考的一个重要特点。

3. Boolean Algebra Simplification Using Laws and Karnaugh Maps | 布尔代数化简：使用定律与卡诺图

Question: Simplify the Boolean expression F = A·B’ + A·B + A’·B. Verify your result using a 2-variable Karnaugh map.

题目：化简布尔表达式 F = A·B’ + A·B + A’·B，并使用二变量卡诺图验证结果。

Apply the consensus and absorption laws: A·B’ + A·B = A·(B’ + B) = A·1 = A. Now F = A + A’·B. Using the distributive law: A + A’·B = (A + A’)·(A + B) = 1·(A + B) = A + B.

应用吸收律和一致律：A·B’ + A·B = A·(B’ + B) = A·1 = A。此时 F = A + A’·B。再使用分配律：A + A’·B = (A + A’)·(A + B) = 1·(A + B) = A + B。

In a 2-variable Karnaugh map with rows for A and columns for B, place 1s in cells corresponding to minterms A·B’ (10), A·B (11), and A’·B (01). The cell A’·B’ (00) contains 0. Grouping the three 1s yields two prime implicants: the group covering (10, 11) gives A, and the group covering (01, 11) gives B. The simplified expression is A + B.

在二变量卡诺图中（行 A，列 B），将 1 填入与最小项对应的单元格：A·B’ (10)、A·B (11) 和 A’·B (01)，A’·B’ (00) 填入 0。将三个 1 分组得到两个质蕴含项：覆盖 (10, 11) 的组给出 A，覆盖 (01, 11) 的组给出 B。化简结果为 A + B。

4. Logic Circuit Design from a Truth Table | 根据真值表设计逻辑电路

Question: A combinational circuit has three inputs X, Y, Z and one output F. F is 1 when exactly two inputs are 1, or when all three inputs are 0. Derive the Sum-of-Products (SOP) expression, simplify it, and sketch the gate-level diagram.

题目：某组合电路有三个输入 X、Y、Z，一个输出 F。当恰好有两个输入为 1，或所有输入均为 0 时，F = 1。写出最小项之和（SOP）表达式，化简并画出门级电路图。

X Y Z	F	Minterm
0 0 0	1	X’·Y’·Z’
0 0 1	0	–
0 1 0	0	–
0 1 1	1	X’·Y·Z
1 0 0	0	–
1 0 1	1	X·Y’·Z
1 1 0	1	X·Y·Z’
1 1 1	0	–

SOP: F = X’·Y’·Z’ + X’·Y·Z + X·Y’·Z + X·Y·Z’. This expression cannot be further simplified by Boolean algebra easily, but a Karnaugh map shows no adjacent 1s except that the zero combination is isolated. The simplified expression is actually the XOR and XNOR combination: F = (X ⊕ Y ⊕ Z)’. Alternatively, F = (X ≡ Y ≡ Z), which can be built using two XOR gates and one NOT.

SOP 表达式：F = X’·Y’·Z’ + X’·Y·Z + X·Y’·Z + X·Y·Z’。该表达式通过布尔代数不易进一步化简，但卡诺图显示除了全零项外没有相邻的 1。实际上 F = (X ⊕ Y ⊕ Z)’，可以表示为 F = (X ≡ Y ≡ Z)，用两个异或门和一个非门即可实现。

The circuit consists of an XOR gate taking X and Y, whose output feeds a second XOR gate together with Z. The output of the second XOR is then inverted to produce F.

电路由一个异或门处理 X 和 Y，其输出与 Z 共同接入第二个异或门，第二个异或门的输出再经反相得到 F。

5. Finite State Machine: Sequence Detector for ‘1101’ | 有限状态机：序列 ‘1101’ 检测器

Question: Design a Moore FSM that detects the overlapping sequence ‘1101’ in a serial input stream. Draw the state transition diagram and write the state transition table.

题目：设计一个 Moore 型有限状态机，检测串行输入流中的重叠序列 ‘1101’。画出状态转移图，并写出状态转移表。

We need five states: S0 (reset/no match), S1 (detected ‘1’), S2 (detected ’11’), S3 (detected ‘110’), S4 (detected ‘1101’ output = 1). Overlapping is allowed, so from S4 on input 1 the next state is S2 (because the last two bits become ’11’), and on input 0 it goes to S1.

需要五个状态：S0（复位/无匹配）、S1（检测到 ‘1’）、S2（检测到 ’11’）、S3（检测到 ‘110’）、S4（检测到 ‘1101’ 输出 = 1）。由于允许重叠，从 S4 在输入为 1 时下一状态为 S2（因为最后两位变为 ’11’），输入为 0 时转至 S1。

Current State	Input = 0	Input = 1	Output
S0	S0	S1	0
S1	S0	S2	0
S2	S3	S2	0
S3	S0	S4	0
S4	S1	S2	1

The output is 1 only in S4, indicating the sequence has been detected. This FSM correctly handles overlapping sequences such as ‘1101101’ where the second detection starts before the first ends.

输出仅在 S4 状态为 1，表示检测到目标序列。该 FSM 能正确处理重叠序列，例如对于输入 ‘1101101’，第二个检测在第一个检测结束之前即已开始。

6. SQL Query Writing with JOINs | 使用 JOIN 编写 SQL 查询

Question: Given two tables: Students(StudentID, Name, Major) and Enrolments(StudentID, CourseCode, Grade). Write SQL queries to (a) list all students enrolled in the ‘Computer Science’ major and their courses, (b) find the average grade for each course, and (c) identify students who have not enrolled in any course.

题目：给定两张表：Students(StudentID, Name, Major) 和 Enrolments(StudentID, CourseCode, Grade)。编写 SQL 查询实现：(a) 列出所有主修 ‘Computer Science’ 的学生及其所选课程；(b) 计算每门课的平均成绩；(c) 找出未选修任何课程的学生。

(a) SELECT s.Name, e.CourseCode FROM Students s INNER JOIN Enrolments e ON s.StudentID = e.StudentID WHERE s.Major = ‘Computer Science’; The INNER JOIN ensures only students with enrolment records appear.

(a) SELECT s.Name, e.CourseCode FROM Students s INNER JOIN Enrolments e ON s.StudentID = e.StudentID WHERE s.Major = ‘Computer Science’; 使用 INNER JOIN 确保只返回有选课记录的学生。

(b) SELECT e.CourseCode, AVG(e.Grade) AS AvgGrade FROM Enrolments e GROUP BY e.CourseCode; The AVG function calculates the mean, and GROUP BY aggregates per course. NULL grades are typically ignored.

(b) SELECT e.CourseCode, AVG(e.Grade) AS AvgGrade FROM Enrolments e GROUP BY e.CourseCode; AVG 函数计算平均值，GROUP BY 按课程分组。通常忽略 NULL 值的成绩。

(c) SELECT s.Name FROM Students s LEFT JOIN Enrolments e ON s.StudentID = e.StudentID WHERE e.StudentID IS NULL; A LEFT JOIN includes all students; filtering for NULL in the enrolment side finds those without any course.

(c) SELECT s.Name FROM Students s LEFT JOIN Enrolments e ON s.StudentID = e.StudentID WHERE e.StudentID IS NULL; 左连接保留所有学生，筛选入学记录为 NULL 即可找出未选课的学生。

7. Object-Oriented Programming: Designing a BankAccount Class | 面向对象编程：BankAccount 类设计

Question: Design a Java/Python-like BankAccount class encapsulating balance, with methods deposit(amount), withdraw(amount), and getBalance(). Ensure that withdraw imposes a minimum balance constraint of 0. Explain the principles of encapsulation and data hiding.

题目：设计一个类似 Java/Python 的 BankAccount 类，封装余额属性，提供 deposit(amount)、withdraw(amount) 和 getBalance() 方法，要求 withdraw 时确保余额不低于 0。阐述封装和数据隐藏原理。

class BankAccount:
    def __init__(self, initial=0):
        self.__balance = initial   # private attribute

    def deposit(self, amount):
        if amount > 0:
            self.__balance += amount

    def withdraw(self, amount):
        if 0 < amount <= self.__balance:
            self.__balance -= amount

    def getBalance(self):
        return self.__balance

The double underscore prefix (__balance) makes the attribute private, preventing direct external modification. Access is forced through public methods, which can enforce validation rules. This is the core of encapsulation: internal state is protected, and the class maintains its own invariants.

双下划线前缀（__balance）将属性设为私有，阻止外部直接修改。只能通过公有方法访问，从而执行验证规则。这就是封装的核心：内部状态受保护，类自行维护其不变量。

Data hiding ensures that changes to the internal representation do not affect external code that uses the class, as long as the public interface remains consistent. This reduces coupling and improves maintainability.

数据隐藏确保，只要公有接口保持一致，内部表示的改变就不会影响使用该类的外部代码，从而降低耦合度、提高可维护性。

8. Recursive Problem Solving: Fibonacci Sequence and Time Complexity | 递归问题求解：斐波那契数列与时间复杂度

Question: Implement a recursive function fib(n) that returns the n-th Fibonacci number. Analyse its time complexity and explain why memoization or iteration is preferred for large n.

题目：实现一个递归函数 fib(n) 返回第 n 个斐波那契数。分析其时间复杂度，并解释为何对较大的 n 更推荐记忆化或迭代。

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

The recurrence T(n) = T(n-1) + T(n-2) + O(1) solves to O(2^n), because the function recomputes the same subproblems many times, creating an exponential explosion.

递推关系 T(n) = T(n-1) + T(n-2) + O(1) 的解为 O(2^n)，因为该函数多次重复计算相同的子问题，造成指数级爆炸。

With memoization (caching results in a dictionary), each fib(k) is computed only once, reducing the complexity to O(n). Alternatively, an iterative approach using two variables also achieves O(n) time and O(1) space. This demonstrates the importance of avoiding naive recursion for problems with overlapping subproblems.

采用记忆化（使用字典缓存结果）时，每个 fib(k) 只计算一次，复杂度降为 O(n)。另一种迭代方法使用两个变量，也可实现 O(n) 时间和 O(1) 空间。这表明对有重叠子问题的情况应避免简单递归。

9. Scheduling Algorithms: Round Robin with Context Switch Overhead | 调度算法：带上下文切换开销的轮转法

Question: Three processes P1, P2, P3 arrive at time 0 with service times 10, 5, and 8 ms respectively. Using Round Robin scheduling with a time quantum of 4 ms and context switch overhead of 2 ms, compute the average waiting time and draw the Gantt chart.

题目：三个进程 P1、P2、P3 均在时间 0 到达，服务时间分别为 10、5、8 ms。采用时间片为 4 ms、上下文切换开销为 2 ms 的轮转调度，计算平均等待时间并画出甘特图。

Execution order (including context switch intervals CS): CS(2) → P1(4) → CS(2) → P2(4) → CS(2) → P3(4) → CS(2) → P1(4) → CS(2) → P2(1) → CS(2) → P3(4) → CS(2) → P1(2). Context switches before the first process and after the last are not counted by convention, but we include them as they add overhead. Waiting time for P1: starts at 2, runs 4, then waits until its next turn at time 2+4+2+4+2+4+2 = 20, so total wait = (2-0) + (20-6) = 2+14 = 16 ms. Finish time = 36. Similar for others.

执行顺序（含上下文切换 CS 间隔）：CS(2) → P1(4) → CS(2) → P2(4) → CS(2) → P3(4) → CS(2) → P1(4) → CS(2) → P2(1) → CS(2) → P3(4) → CS(2) → P1(2)。按惯例不计算首个进程之前和最后一个进程之后的切换，但这里我们将其视为额外开销。P1 的等待时间：从时间 2 开始运行 4 后，下一次轮到在 2+4+2+4+2+4+2=20，所以等待总长 = (2-0)+(20-6)=2+14=16 ms。完成时间 36。其余类推。

Process	Burst	Finish Time	Waiting Time
P1	10	36	16
P2	5	27	18
P3	8	34	18

Average waiting time = (16+18+18)/3 ≈ 17.33 ms. Context switches significantly increase wait times; without overhead the average wait would be around 12-13 ms.

平均等待时间 = (16+18+18)/3 ≈ 17.33 ms。上下文切换显著增加了等待时间；若无此开销，平均等待时间约在 12-13 ms 左右。

10. Network Protocols: TCP vs UDP and the Three-Way Handshake | 网络协议：TCP 与 UDP 及三次握手

Question: Compare TCP and UDP in terms of reliability, ordering, and connection setup. Explain the three-way handshake used by TCP to establish a connection, and give one application scenario for each protocol.

题目：从可靠性、顺序性和连接建立方面比较 TCP 和 UDP。解释 TCP 建立连接的三次握手过程，并各举一个适用场景。

TCP is connection-oriented: it uses a three-way handshake (SYN, SYN-ACK, ACK) to set up a reliable channel. It guarantees delivery through acknowledgments and retransmissions, and preserves data order using sequence numbers. UDP is connectionless with no handshake; it does not guarantee delivery or order, making it faster and lighter.

TCP 面向连接：通过三次握手（SYN、SYN-ACK、ACK）建立可靠通道。它通过确认与重传保证交付，使用序号保持数据顺序。UDP 无连接、无握手，不保证交付或顺序，因此更快、开销更小。

Three-way handshake steps: (1) Client sends SYN with random sequence number x. (2) Server replies with SYN-ACK containing its own sequence number y and acknowledging x+1. (3) Client sends ACK with acknowledgment y+1. Only then is the connection established and data transfer begins.

三次握手步骤：(1) 客户端发送带有随机序号 x 的 SYN。(2) 服务器回复 SYN-ACK，包含自己的序号 y 并确认 x+1。(3) 客户端发送确认 y+1 的 ACK。连接至此建立，开始传输数据。Published by TutorHao | IB Computer Science Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

IB CCEA Computer Science: Typical Example Questions Explained | IB CCEA 计算机：典型例题详解