2022 OCR A-Level Computer Science - H446 模擬試題連答案詳解

Pipelining divides the execution of an instruction into separate sequential stages, such as Fetch, Decode, and Execute. Instead of waiting for an entire instruction to complete before starting the next one, the processor overlaps these stages. While one instruction is being executed, the next is being decoded, and the one after is being fetched. This maximizes the utilization of the processor's resources and increases the throughput (number of instructions completed per second).

1 mark for explaining that instruction stages are overlapped (e.g. fetching one instruction while another is decoded/executed). 1 mark for stating that this increases instruction throughput / reduces overall execution time.

Operating systems cannot natively understand the specific technical interfaces of every hardware peripheral. A device driver is specialized software that translates generic system commands from the operating system into a format and protocol that the specific hardware device can execute, enabling hardware abstraction.

1 mark for stating it acts as an interface/translator between the OS and the hardware. 1 mark for stating it allows the OS to control/communicate with a specific peripheral device without needing to know its internal hardware details.

In symmetric encryption, the sender and receiver must both possess the exact same secret key to secure and read the data. In contrast, asymmetric encryption eliminates the need to share a secret key by utilizing a public key (which is freely distributed to anyone for encrypting messages) and a separate private key (kept secret by the owner and used to decrypt the messages).

1 mark for explaining that symmetric encryption uses the same key for encrypting and decrypting. 1 mark for explaining that asymmetric encryption uses a pair of keys (public key for encryption and private key for decryption).

While humans easily remember alphabetical web addresses (like example.com), network routers and servers use numerical IP addresses to locate resources. The DNS acts as a distributed database directory that looks up the domain name requested by a client and returns the corresponding IP address so a connection can be established.

1 mark for stating it translates domain names/URLs to IP addresses. 1 mark for explaining that this allows web browsers/computers to locate and connect to the correct server on the internet.

A foreign key is used to create a relationship between two database tables. It is a column (or group of columns) in one table that references the unique primary key of another table, ensuring referential integrity by preventing orphaned records and linking related data across tables.

1 mark for defining it as a primary key from one table that is placed/used in another table. 1 mark for stating its purpose is to link the tables / establish a relationship (e.g. one-to-many relationship) / enforce referential integrity.

An interpreter parses the source code and immediately executes it instruction-by-instruction, requiring the interpreter program to be present every time the code runs and stopping immediately if a syntax error is reached. A compiler, however, translates the complete source code file into a standalone object code/executable file (like machine code), which can then be executed repeatedly without needing the compiler or original source code.

1 mark for stating that an interpreter translates and runs code line-by-line / instruction-by-instruction. 1 mark for stating a compiler translates the whole source code into an executable/machine code file before execution.

Under the Data Protection Act 2018 (which incorporates GDPR standards), personal data must be: processed lawfully, fairly, and transparently; collected for specified, explicit, and legitimate purposes; adequate, relevant, and limited to what is necessary; accurate and kept up to date; kept for no longer than necessary; and processed securely to ensure protection against unauthorized access.

1 mark per valid principle stated (up to a maximum of 2 marks). Acceptable principles include: processed lawfully/fairly/transparently; collected for specified/explicit/legitimate purposes; adequate/relevant/not excessive; accurate/kept up-to-date; kept no longer than necessary; processed securely.

A RISC processor uses a small set of simple, uniform-length instructions that can be executed in a single clock cycle. This simplicity allows the hardware to be physically smaller, cheaper, and more power-efficient. In contrast, CISC processors use a larger set of complex, variable-length instructions that may take multiple clock cycles, requiring more complex hardware decoding circuitry.

1 mark per valid characteristic of a RISC processor (up to a maximum of 2 marks). Acceptable answers: Each instruction takes one clock cycle; instructions are of a fixed length; simpler instruction set; simpler/fewer transistors; lower power consumption/heat dissipation; relies more heavily on the compiler to optimize code.

The Program Counter (PC) is a dedicated register in the CPU that stores the memory address of the next instruction scheduled to be fetched and executed. As part of the Fetch-Decode-Execute cycle, this address is sent to the Memory Address Register (MAR) via the address bus, and the PC is subsequently incremented to point to the next instruction.

1 mark: Stating that it stores the memory address of the next instruction to be fetched or executed. 1 mark: Stating that its value is automatically incremented during the fetch phase.

A device driver is a specialized system software program. It serves as an interface or translator between the operating system and a hardware peripheral. Since hardware devices vary significantly across manufacturers, the driver abstracts these hardware-specific differences by converting generic input/output commands from the operating system into low-level instructions that the physical device's controller can understand and execute.

1 mark: Explaining that it acts as a software interface or translator between the operating system and a hardware peripheral. 1 mark: Explaining that it converts generic OS commands into instructions that the specific hardware device can execute.

First, hashing is designed to be a one-way mathematical process that cannot be reversed to recover the original plaintext, whereas symmetric encryption is a two-way process where the ciphertext can be decrypted back into plaintext using a shared secret key. Second, a hashing algorithm always produces a fixed-length output (such as 256 bits) regardless of how large or small the input is, while symmetric encryption produces ciphertext that varies in length depending on the size of the input data.

1 mark: Stating that hashing is one-way/irreversible whereas encryption is two-way/reversible (can be decrypted using a key). 1 mark: Stating that hashing yields a fixed-length output whereas symmetric encryption output length scales with the input size.

A gateway is a network node used to connect two completely different networks that utilize distinct protocol suites or network architectures. It intercepts traffic from one network, strips off the existing protocol wrapper, and repackages it using the protocols of the destination network, thereby allowing communication between incompatible network architectures.

1 mark: Stating that it connects two networks that run on different protocols or architectures. 1 mark: Stating that it translates network packets or data formats between these different protocol suites to allow interoperability.

Referential integrity is a fundamental data integrity constraint in a relational database. It ensures that any relationship between tables remains consistent by requiring that every foreign key value in a table must point to an existing, valid primary key in the parent table. This constraint prevents orphan records and maintains database consistency during record updates or deletions.

1 mark: Describing it as a database constraint that ensures consistency across related tables or prevents orphan records. 1 mark: Specifying that a foreign key value must correspond directly to an existing, valid primary key in the related table (or be null).

A linker is software that runs after source code has been translated into separate object modules. Its role is to merge these independent object files along with any static library modules into a single, executable machine-code file. It performs address resolution by matching function calls and variable references across different modules to their absolute or relative memory offsets.

1 mark: Stating that it merges separate compiled object modules and/or library files into a single executable file. 1 mark: Explaining that it resolves external references, variable addresses, or function calls between those separate files.

The Regulation of Investigatory Powers Act (RIPA) provides public authorities with legally defined powers for surveillance. These powers include intercepting internet communications, emails, and phone calls in transit; demanding that ISPs or network hosts store and release user communications data; and legally forcing individuals or businesses to hand over decryption keys or decrypt protected data during investigations.

1 mark per correct power listed (maximum of 2 marks): Intercepting communications (e.g., telephone calls, emails) in transit; Demanding data/traffic records from ISPs; Compelling individuals to disclose decryption keys or decrypt encrypted data; Authorizing covert surveillance of suspects.

An assembler translates assembly language, which is low-level, into machine code. In this translation, there is a direct, one-to-one mapping where each mnemonic corresponds directly to a single machine code instruction. In contrast, a compiler translates high-level code into machine code, where high-level abstract statements have a one-to-many relationship, compiling into multiple machine-level instructions.

1 mark: Explaining that an assembler translates assembly (low-level) code with a one-to-one mapping of instructions to machine code. 1 mark: Explaining that a compiler translates high-level code with a one-to-many mapping of statements to machine code instructions.

A device driver is a specialized software program that acts as an interface between the operating system and a physical hardware peripheral. It translates the operating system's general-purpose command signals into the specific, low-level machine instructions that the hardware device can understand and execute. This allows the computer to interact with new external devices without needing any modifications to the core operating system software.

Award 1 mark for stating that it acts as an interface/translator between the operating system and hardware. Award 1 mark for stating that it translates generic OS commands into device-specific instructions (or vice-versa).

A cryptographic hashing algorithm has several distinct characteristics. First, it is a one-way function, meaning it is computationally infeasible to reverse the process and determine the original input from the resulting hash value. Second, it always produces a fixed-length output (such as 256 bits) regardless of the size or length of the original input data. Other characteristics include being deterministic (same input always gives the same hash) and high collision resistance (different inputs are extremely unlikely to produce the same hash).

Award 1 mark each for any two of the following up to 2 marks: 1. One-way / non-reversible (cannot reverse-engineer the input from the hash). 2. Fixed-size/length output (regardless of input size). 3. Deterministic (same input always produces the same output). 4. Avalanche effect (a small change in input produces a completely different hash). 5. High collision resistance (different inputs are extremely unlikely to yield the same hash).

Let's trace Option A with A = 7 and B = 3.
1. LOOP: LDA A loads 7 into the accumulator.
2. SUB B subtracts 3, yielding 4 in the accumulator.
3. BRP SAV branches to SAV because the accumulator is positive.
4. SAV: STA A stores 4 back into A.
5. BRA LOOP branches back to LOOP.
6. LOOP: LDA A loads 4.
7. SUB B subtracts 3, yielding 1.
8. BRP SAV branches to SAV because the accumulator is positive.
9. SAV: STA A stores 1 back into A.
10. BRA LOOP branches back to LOOP.
11. LOOP: LDA A loads 1.
12. SUB B subtracts 3, yielding -2.
13. BRP SAV does not branch because the accumulator is negative.
14. LDA A loads the last saved value of A, which is 1 (the remainder).
15. OUT outputs 1.
16. HLT halts the program.
This correctly outputs the remainder. Option B fails when the subtraction is positive but not zero. Option C outputs the negative accumulator value (-2) instead of the remainder. Option D subtracts A from B, which is incorrect.

1 Mark: Correctly loading A and subtracting B inside the loop.
1 Mark: Using BRP to branch to a save routine when the subtraction result is positive or zero.
1 Mark: Correctly saving the decremented value back to A in the save routine to preserve the running remainder.
1 Mark: Branching back to the start of the loop to repeat the subtraction.
1 Mark: Correctly reloading the last valid positive remainder from variable A when the negative branch is triggered before outputting.

Option A is correct because in OCR pseudocode, subclass inheritance is designated by 'class Mage inherits Character'. Since 'name' and 'health' are private to the base class, they cannot be directly modified or accessed by the subclass constructor. Therefore, the subclass must call the parent constructor using the 'super.new()' syntax. Passing 'givenName' and 'givenHealth' to 'super.new' correctly delegates their initialization to the superclass constructor, while 'mana = givenMana' handles the subclass-specific attribute.

1 Mark: Correctly declaring inheritance using the keyword 'inherits'.
1 Mark: Declaring 'mana' as a private attribute in the subclass.
1 Mark: Creating a public procedure 'new' (constructor) that takes all three parameters.
1 Mark: Correctly calling the superclass constructor using 'super.new()' with the parent parameters.
1 Mark: Assigning the subclass-specific parameter to 'mana' after calling the super constructor.

For the loop to execute exactly Y times, the value of Y (currently loaded in the accumulator at 'LOOP LDA Y') must be decremented by 1. This is done by subtracting the constant 'ONE' (which stores the value 1). Thus, must be 'SUB ONE'. The decremented value must then be stored back into variable Y to update the counter for subsequent loops, which is achieved with 'STA Y' at . If Y is not updated, the program will result in an infinite loop.

1 Mark: Identifying that the accumulator holds the value of Y at the start of the missing segment.
1 Mark: Recognizing that decrementing the loop counter requires subtracting 1 using the 'SUB ONE' instruction.
1 Mark: Identifying that 'SUB ONE' must occupy the first missing instruction spot ().
1 Mark: Recognizing that the modified counter must be saved back to Y using 'STA Y'.
1 Mark: Identifying that 'STA Y' must occupy the second missing instruction spot ().

Option A is the correct design because it first checks if subtracting the withdrawal amount from the balance would keep the balance non-negative (balance - amount >= 0). If this condition is met, it updates the balance and returns true. If not, it leaves the balance unmodified and returns false. Option B is incorrect because it modifies the balance first and only checks afterwards, leaving the state corrupt (negative balance) if the check fails. Option C has inverted condition logic. Option D modifies the parameter 'amount' instead of the instance variable 'balance'.

1 Mark: Defining the method as a public function accepting 'amount' as a parameter.
1 Mark: Implementing a defensive validation check (e.g. balance - amount >= 0) before modifying the balance.
1 Mark: Correctly modifying the private state 'balance' by subtracting 'amount' only when the transaction is valid.
1 Mark: Correctly returning true to the calling routine on success.
1 Mark: Correctly returning false and ensuring balance remains unchanged when the transaction is invalid.

### Architectural Characteristics:
- **RISC (Reduced Instruction Set Computer):** Uses a simple, highly standardized instruction set. Each instruction is usually of fixed length and takes a single clock cycle to execute. RISC makes heavy use of internal registers and relies on pipelining to increase performance.
- **CISC (Complex Instruction Set Computer):** Uses a large, complex instruction set where individual instructions can perform multi-cycle operations (such as loading from memory, calculating, and storing back to memory). It has fewer general-purpose registers and heavily relies on complex hardware control units.

### Application to Component 1 (Edge Devices at Intersections):
- **Suitability:** Highly suited to RISC.
- **Justification:**
- **Power & Cooling:** Edge devices are installed in outdoor street cabinets with limited ventilation. RISC processors have fewer transistors, which minimizes power consumption and eliminates the need for active cooling (fans), reducing mechanical failure rates.
- **Predictable Real-Time Performance:** Because RISC instructions execute in a single cycle, interrupt latency is low and execution times are deterministic, which is essential for micro-second traffic signal decisions.
- **Cost and Physical Size:** Since thousands of units will be deployed across the city, the lower unit cost and smaller physical footprint of RISC microcontrollers make them highly economical.
- **Limitation:** RISC code size is typically larger, meaning more system memory (RAM/ROM) may be required to hold the programs, though this is rarely a bottleneck for dedicated, fixed-function control programs.

### Application to Component 2 (Central Control Server):
- **Suitability:** Highly suited to CISC.
- **Justification:**
- **Instruction Complexity:** Neural networks and city-wide flow simulations require highly complex, dense computations. CISC architectures (such as x86_64) feature dedicated hardware instructions (e.g., SIMD, AVX) designed to accelerate mathematical operations and parallel vector calculations.
- **Memory Efficiency:** CISC instructions pack more work into fewer instructions, resulting in smaller compiled binaries, which optimizes cache hits on large-scale databases.
- **Power & Cost Flexibility:** Central servers are located in climate-controlled server rooms with uninterrupted mains power. Thus, the high power consumption, heat generation, and premium purchase costs of CISC processors are acceptable trade-offs for raw single- and multi-threaded processing power.
- **Limitation:** Pipelining is less efficient and more complex on CISC systems due to varying instruction formats and execution times, but this is offset by sophisticated out-of-order execution engines.

### Conclusion:
There is a clear divide in suitability: the localized, cost-sensitive, power-constrained, and time-critical nature of the edge intersections necessitates RISC, whereas the highly complex, computationally demanding, and resource-abundant environment of the centralized server demands CISC.

**Level 3 (8-10 marks):**
- Demonstrates a detailed, accurate knowledge of both RISC and CISC characteristics (instruction set complexity, clock cycles, register usage, pipelining).
- Sustained, balanced evaluation of both components (Edge Devices and Central Server) within the context.
- Explicitly discusses constraints such as power, cooling, cost, physical size, and execution speed.
- Structure is logical and technical terminology is used accurately throughout.

**Level 2 (5-7 marks):**
- Shows sound understanding of RISC and CISC.
- Evaluates both architectures against the scenarios, but the discussion may be unbalanced (focusing heavily on one component over the other) or lacks technical depth in specific areas (e.g., pipelining or instruction-set differences).
- Generally structured with appropriate use of technical terms.

**Level 1 (1-4 marks):**
- Demonstrates basic or fragmented knowledge of RISC and/or CISC.
- Makes limited attempts to apply knowledge to the given scenario; assertions are generalized or contain technical inaccuracies.
- Presentation lacks clear structure and relies on everyday language.

**Key Points to Award (up to 6 marks for knowledge/analysis, 4 marks for evaluation/contextual application):**
- RISC: 1 instruction per cycle, simpler hardware, relies on software/compiler, many registers, highly efficient pipelining.
- CISC: Multi-cycle instructions, complex hardware, smaller code footprint, fewer general-purpose registers.
- Context 1 (Edge): Low power, low heat (no fans), small footprint, cheap for mass deployment, predictable execution matches real-time needs of traffic lights.
- Context 2 (Server): Handles database/AI modeling, high throughput, high power/thermal budget is acceptable, advanced instructions accelerate complex calculations.

### Architectural Comparison:
- **Real-Time Operating System (RTOS):** Designed for systems where the correctness of a calculation depends not only on its logical result but also on the time at which it is delivered. It is deterministic, meaning response times have guaranteed maximum limits.
- **Desktop Operating System:** Designed for general-purpose multi-tasking, prioritizing average throughput, fair resource allocation, and user experience. It is non-deterministic, with variable response times.

### Evaluation criteria in the context of the Patient Ventilator:

1. **Scheduling & Determinism:**
- **RTOS:** Employs priority-based preemptive scheduling. If a critical task (such as the airway pressure sensor detecting an over-pressure event) demands CPU time, the RTOS will immediately suspend lower-priority tasks (like updating the screen) and run the alarm handler. Execution times are completely predictable.
- **Desktop OS:** Employs complex, fair-share scheduling algorithms (like Multi-Level Feedback Queues). A background update, driver activity, or a GUI freeze could cause the scheduler to temporarily starve the valve-control process of CPU cycles, resulting in catastrophic failure.

2. **Interrupt Handling & Latency:**
- **RTOS:** Engineered for minimal interrupt latency. The system switches context in micro-seconds to address physical hardware interrupts from the oxygen valves.
- **Desktop OS:** Has significantly higher and unpredictable interrupt latency due to complex kernel layers, virtual memory paging, and disk caching, which are unacceptable for biological feedback loops.

3. **Reliability & Operating System Footprint:**
- **RTOS:** Has a minimal, monolithic, or microkernel architecture with few lines of code, significantly reducing software bugs. Memory is usually statically allocated to prevent memory fragmentation and "out of memory" crashes.
- **Desktop OS:** Extremely large codebase with millions of lines of code, running numerous background processes, services, and dynamic memory allocations. This increases the attack surface for security threats and the likelihood of unexpected memory leaks, crashes, or unprompted restarts.

4. **Safety-Critical Certification:**
- **RTOS:** Easier to test mathematically and verify, making it eligible for stringent medical safety certifications (e.g., ISO 13485 or IEC 62304).
- **Desktop OS:** Nearly impossible to certify for life-critical tasks due to its unpredictable nature and proprietary, closed-source components (in the case of Windows).

### Conclusion & Design Compromise:
For a life-support system like a ventilator, an RTOS is mandatory for the core control system. However, a common modern architectural compromise is to use a dual-processor system: an RTOS runs on a microcontroller to handle the physical valves and alarms, while an embedded desktop-like OS runs on a separate, sandboxed processor to drive the rich graphical user interface, ensuring a GUI crash never halts the life-support software.

**Level 3 (8-10 marks):**
- Thorough understanding of the difference between deterministic (RTOS) and non-deterministic (Desktop OS) systems.
- Comprehensive evaluation of scheduling algorithms (preemptive vs fair-share) and how they impact life-support systems.
- Covers key themes: interrupt latency, memory management (static vs dynamic/paging), software reliability, and certification.
- Suggests a sensible engineering solution (e.g., separation of safety-critical control and GUI display).

**Level 2 (5-7 marks):**
- Shows sound knowledge of RTOS and Desktop OS.
- Evaluates both OS types in the context of the ventilator, though some aspects (like interrupt handling or memory allocation) may be explained in a general way without deep technical analysis.
- Well-structured and uses appropriate technical terminology.

**Level 1 (1-4 marks):**
- Basic knowledge of what an RTOS or Desktop OS is.
- Limited application to the medical device context (e.g., only stating "desktop systems crash a lot").
- Lacks formal structure and technical depth.

**Key Technical Terms to look for:**
- Determinism / Non-deterministic
- Hard real-time vs soft real-time
- Priority-based preemptive scheduling
- Interrupt latency / Context switching
- Static memory allocation vs paging/virtual memory

### Analysis of Benefits:

1. **Data Redundancy & Normalisation:**
- **Flat-File:** Customer details are repeated across different branch spreadsheets (e.g., in a booking sheet and a payment sheet). This wastes storage and leads to inconsistencies (e.g., updating an address in one file but not another).
- **RDBMS:** Employs relational tables designed using normalisation techniques (typically to Third Normal Form / 3NF). Every attribute is stored exactly once, ensuring that updates to customer data propagate system-wide instantly.

2. **Data Integrity:**
- **Flat-File:** Highly prone to data corruption, missing links, and input errors, as there are no validation constraints preventing the deletion of a member while their payment records remain.
- **RDBMS:** Automatically enforces referential integrity using primary and foreign keys, ensuring related tables remain synchronised. Domain and entity integrity checks block invalid data entry at the database level.

3. **Security:**
- **Flat-File:** Spreadsheets are difficult to secure; they can easily be copied, printed, or emailed, creating huge compliance risks (e.g., GDPR violations).
- **RDBMS:** Offers granular Access Control Lists (ACLs), user privileges, transaction auditing, and built-in encryption, ensuring staff only access records relevant to their role.

### Analysis of Challenges:

1. **Concurrent Access & The Multi-User Problem:**
- Multiple users (members and staff) will attempt to book the last spot in a fitness class simultaneously.
- Without control, this leads to "lost updates" or double-bookings. The RDBMS must implement **Record Locking** or **Optimistic/Pessimistic Concurrency Control** to ensure that once a record is being modified, other transactions are queued or rejected.

2. **Enforcing ACID Transactions:**
- **Atomicity:** A class booking payment transaction must be "all-or-nothing." If the payment succeeds but the database fails to write the booking, the whole transaction must roll back.
- **Consistency:** The database must transition from one valid state to another, maintaining all schema rules (e.g., booking capacity limits).
- **Isolation:** Transactions running concurrently must execute as if they were sequential, preventing uncommitted data from being read ("dirty reads").
- **Durability:** Once a booking is confirmed, it must survive any subsequent power failures or server crashes, achieved via non-volatile write-ahead transaction logs.

3. **Implementation Costs & Data Cleansing:**
- Porting chaotic, semi-structured spreadsheet data into a strict relational schema requires substantial data cleansing and ETL (Extract, Transform, Load) processes.
- High upfront costs for database engines, web servers, and database administrator (DBA) talent.

### Conclusion:
Despite the challenges of managing concurrency, ACID transaction overhead, and migration costs, transitioning to a centralized RDBMS is highly recommended. It is the only viable architecture to support a secure, scalable, and consistent nationwide web booking portal.

**Level 3 (8-10 marks):**
- Demonstrates precise and comprehensive knowledge of both flat-files and RDBMS architectures.
- Deeply analyzes benefits (redundancy, referential integrity, security) and maps them to the fitness center context.
- Detailed discussion of concurrency challenges (e.g., double booking classes) and how they are solved via locking.
- Fully explains the elements of ACID (Atomicity, Consistency, Isolation, Durability) in relation to booking and payment transactions.
- Clear, logical structure with excellent technical vocabulary.

**Level 2 (5-7 marks):**
- Sound knowledge of database concepts.
- Explains the benefits of an RDBMS over flat files but may discuss ACID properties or concurrency control in general terms rather than applying them deeply to the scenario.
- Mostly structured and clear.

**Level 1 (1-4 marks):**
- Basic knowledge of databases and spreadsheets.
- Limited focus on the scenario; lists benefits of databases without addressing technical complexities like concurrency or ACID.
- Unstructured or contains key misconceptions.

**Key Points / Concepts to reward:**
- Normalisation (eliminating redundancy)
- Referential Integrity (Foreign keys blocking orphaned records)
- Concurrency issues (Race conditions, double bookings, record locking)
- ACID criteria defined and contextualized to payments/bookings
- Cost and data-cleansing challenges

1. Identify the value of the mantissa:
The mantissa starts with 0, meaning it is positive.
\(0.1011000_2 = 2^{-1} + 2^{-3} + 2^{-4} = 0.5 + 0.125 + 0.0625 = 0.6875\).

2. Identify the value of the exponent:
The exponent starts with 0, meaning it is positive.
\(0011_2 = 2^1 + 2^0 = 3\).

3. Calculate the denary value:
\(0.6875 \times 2^3 = 0.6875 \times 8 = 5.5\).

- 1 mark: Correct conversion of the mantissa to denary (\(0.6875\) or \(\frac{11}{16}\)).
- 1 mark: Correct conversion of the exponent to denary (\(3\)).
- 1 mark: Correct final calculation showing \(5.5\) (or \(5 \frac{1}{2}\)).

1. Convert \(-6.25\) to binary:
\(+6.25_{10} = 0110.01_2\)
To find the negative representation, write in two's complement:
Invert the bits of \(0110.0100\) to get \(1001.1011\), then add \(1\) to get \(1001.1100\).
Thus, \(-6.25_{10} = 1001.1100_2\).

2. Normalize the binary number:
A negative normalized floating-point number must start with \(1.0\).
Currently, the binary point is at \(1001.1100\).
Move the binary point 3 places to the left to obtain \(1.0011100\).
Since we shifted the point 3 places to the left, the exponent is \(+3\).

3. Form the final bits:
The mantissa is 8 bits: `10011100`.
The exponent is \(+3\) in 4-bit two's complement: `0011`.
Combined 12-bit representation: `10011100 0011`.

- 1 mark: Correct binary representation of \(-6.25\) in two's complement (e.g., \(1001.11_2\) or equivalent working).
- 1 mark: Correct 8-bit normalized mantissa (`10011100`).
- 1 mark: Correct 4-bit exponent (`0011`).

1. Calculate the total number of white pixels:
\(40 \text{ rows} \times 64 \text{ pixels/row} = 2560 \text{ white pixels}\).
Since the maximum count for a single RLE run is 255:
\(2560 \div 255 = 10\) runs of 255, and \(1\) run of \(10\) (since \(10 \times 255 + 10 = 2560\)).
Total runs for white pixels = \(11\) runs.

2. Calculate the total number of black pixels:
\(24 \text{ rows} \times 64 \text{ pixels/row} = 1536 \text{ black pixels}\).
Since the maximum count is 255:
\(1536 \div 255 = 6\) runs of 255, and \(1\) run of \(6\) (since \(6 \times 255 + 6 = 1536\)).
Total runs for black pixels = \(7\) runs.

3. Calculate the compressed size:
Total number of runs = \(11 + 7 = 18\) runs.
Each run requires 2 bytes.
Total compressed size = \(18 \times 2 = 36\) bytes.

- 1 mark: Correctly identifies that the white pixel block requires 11 runs due to the 255-count limit.
- 1 mark: Correctly identifies that the black pixel block requires 7 runs.
- 1 mark: Calculates the correct final compressed file size of 36 bytes.

During the fetch phase:
- The address in the PC (45) is copied to the MAR.
- The instruction at address 45 (`ADD 80`) is loaded into the MDR.
- The PC is incremented to 46.

During the execute phase:
- The address portion of the instruction (80) is copied to the MAR.
- The data at memory address 80 (which is 25) is loaded into the MDR.
- The ALU adds the contents of the Accumulator (15) and the MDR (25), giving 40, which is stored in the Accumulator (ACC).

Thus, at the end of the cycle:
- PC = 46
- MDR = 25
- ACC = 40

- 1 mark: Correct value for PC (46).
- 1 mark: Correct value for MDR (25).
- 1 mark: Correct value for ACC (40).

1. To divide a /24 network into 4 subnets, we need \(\log_2(4) = 2\) bits. Adding these to the prefix length: \(24 + 2 = 26\). So, the CIDR mask is `/26`.
2. A /26 network uses 26 bits for the network and \(32 - 26 = 6\) bits for hosts. Total IP addresses per subnet = \(2^6 = 64\). Subtracting 2 (for network and broadcast addresses) gives \(64 - 2 = 62\) usable host IP addresses.
3. The subnet ranges with block size of 64 are:
- Subnet 1: `192.168.10.0` to `192.168.10.63` (Subnet address: `192.168.10.0`)
- Subnet 2: `192.168.10.64` to `192.168.10.127` (Subnet address: `192.168.10.64`)
- Subnet 3: `192.168.10.128` to `192.168.10.191` (Subnet address: `192.168.10.128`)

- 1 mark: Correct subnet mask of `/26`.
- 1 mark: Correct calculation of 62 usable host addresses.
- 1 mark: Correct subnet address of `192.168.10.128`.

The array has 10 rows (0 to 9) and 15 columns (0 to 14) per row.

In Row-Major order, elements are stored row by row.
To find the address of `matrix[6, 8]`:
1. Calculate how many elements are stored before `matrix[6, 8]`:
- Rows 0 to 5 are completely filled. This is 6 rows of 15 elements each: \(6 \times 15 = 90\) elements.
- In row 6, there are 8 elements stored before index 8 (indices 0 to 7): \(8\) elements.
- Total elements skipped = \(90 + 8 = 98\) elements.

2. Calculate the memory offset:
- Each element is 8 bytes.
- Offset = \(98 \text{ elements} \times 8 \text{ bytes/element} = 784\) bytes.

3. Add the offset to the base address:
- Address = \(4000 + 784 = 4784\).

- 1 mark: Correctly determines that 6 full rows are skipped, containing 90 elements.
- 1 mark: Correct total of 98 elements skipped before the target element.
- 1 mark: Correctly calculates final address as 4784.

1. Perform binary addition:
```
01011100
+ 01001011
----------
10100111
```
2. Convert `10100111` to denary:
The sign bit is 1, indicating a negative number.
Invert bits: `01011000`
Add 1: `01011001`
Convert to denary: \(64 + 16 + 8 + 1 = 89\).
So, the value is \(-89\).

3. Overflow:
Overflow has occurred.
Reason: We added two positive numbers (\(01011100_2 = +92_{10}\) and \(01001011_2 = +75_{10}\)). The true sum is \(+167_{10}\), which exceeds the maximum positive value of an 8-bit signed integer (\(+127\)). This caused the sign bit to become 1 (indicating negative).

- 1 mark: Correct binary addition result (`10100111`).
- 1 mark: Correct denary conversion of result (\(-89\)).
- 1 mark: Correctly states overflow has occurred with a valid explanation (e.g. adding two positive numbers gave a negative, or sum \(+167\) exceeded maximum limit of \(+127\)).

We process the expression from left to right:
1. Push `12`, then push `4` onto the stack. Stack: `[12, 4]`
2. Operator `/` is encountered: Pop `4` and `12`. Compute `12 / 4 = 3`. Push `3`. Stack: `[3]`
3. Push `5`, then push `3` onto the stack. Stack: `[3, 5, 3]`
4. Operator `*` is encountered: Pop `3` and `5`. Compute `5 * 3 = 15`. Push `15`. Stack: `[3, 15]`
5. Operator `+` is encountered: Pop `15` and `3`. Compute `3 + 15 = 18`. Push `18`. Stack: `[18]`
6. Push `2` onto the stack. Stack: `[18, 2]`
7. Operator `^` is encountered: Pop `2` and `18`. Compute `18^2 = 324`. Push `324`. Stack: `[324]`

The final value of the expression is 324.

- 1 mark: Correct intermediate stack state after `/` (`[3]`) and `*` (`[3, 15]`).
- 1 mark: Correct intermediate stack state after `+` (`[18]`).
- 1 mark: Correct final answer of 324 (with stack state `[324]`).

1. Convert \(-3.25\) to binary: \(-3.25 = -(2^1 + 2^0 + 2^{-2}) = -11.01_2\).
2. Write this in two's complement form:
- Positive: \(0011.0100_2\)
- Flip bits: \(1100.1011_2\)
- Add 1: \(1100.1100_2\)
3. Normalise the two's complement binary number \(1100.1100_2\):
A normalised negative number must begin with \(1.0\).
We shift the binary point 2 places to the left to get \(1.0011000\). Because we shifted the point 2 places to the left, the exponent is \(+2\).
4. Format into 8-bit mantissa and 4-bit exponent:
- Mantissa: \(10011000\)
- Exponent: \(0010\) (representing \(+2\) in 4-bit two's complement).

- 1 mark: Correct conversion of \(-3.25\) to an unnormalised two's complement representation (e.g., \(1100.11\) or equivalent).
- 1 mark: Correctly normalising the mantissa to 8 bits: \(10011000\).
- 1 mark: Correct 4-bit exponent in two's complement: \(0010\).

1. Identify the formula for row-major order addressing in a 0-indexed 2D array:
\(\text{Address} = \text{Base} + ((\text{RowIndex} \times \text{TotalColumns}) + \text{ColIndex}) \times \text{Size}\)

2. Substitute the given values:
- \(\text{Base} = 4000\)
- \(\text{RowIndex} = 6\)
- \(\text{TotalColumns} = 15\)
- \(\text{ColIndex} = 4\)
- \(\text{Size} = 4\) bytes

3. Calculate the index offset:
\(6 \times 15 = 90\) rows bypassed.
\(90 + 4 = 94\) total elements bypassed.

4. Calculate the byte offset:
\(94 \times 4 = 376\) bytes.

5. Calculate the final address:
\(4000 + 376 = 4376\).

- 1 mark: Correct calculation of elements bypassed (94 elements or showing \(6 \times 15 + 4\)).
- 1 mark: Correct calculation of byte offset (376 bytes or showing \(94 \times 4\)).
- 1 mark: Correct final address (4376).

The algorithm initializes a running sum variable to 0. It then loops through each index of the array from 0 to the length of the array minus one. In each iteration, it checks if the current element matches the `runningSum`. If it does, the index is immediately returned. Otherwise, the current element's value is added to `runningSum` before proceeding to the next element. If the loop completes without finding a match, the function returns -1.

1 Mark: Initializing a variable to track the sum of preceding elements to 0.
1 Mark: Implementing a loop that correctly iterates through the indices of the array `arr`.
1 Mark: Correct conditional statement checking if the current element equals the running sum and returning the current index.
1 Mark: Correctly updating the running sum variable and returning -1 if no such element is found.

First, the function checks if the queue is empty by checking if `size == 0`. If true, an error is printed and `null` is returned. If not empty, the item at the `head` index of `q` is saved in a temporary variable. The `head` pointer is then incremented and wrapped around the bounds of the array using `(head + 1) MOD capacity`. Finally, `size` is decremented by 1, and the saved item is returned.

1 Mark: Correctly checking if the queue is empty (using `size == 0` or checking pointers) and returning `null`/error.
1 Mark: Storing the element from `q[head]` in a temporary variable prior to updating pointers.
1 Mark: Updating the `head` pointer using modulo arithmetic (`(head + 1) MOD capacity`).
1 Mark: Decrementing `size` by 1 and returning the retrieved element.

The algorithm first checks the base case: if `low` is greater than `high`, the target is not in the array, so it returns -1. It calculates the middle index `mid` using integer division `(low + high) DIV 2`. If the element at `mid` is the target, it returns `mid`. If the middle element is larger than the target, the search continues recursively in the lower half (`low` to `mid - 1`). Otherwise, it continues recursively in the upper half (`mid + 1` to `high`).

1 Mark: Base case condition to check if search space is exhausted (`low > high`) returning -1.
1 Mark: Correct calculation of the middle index (using `DIV 2` or equivalent integer division).
1 Mark: Checking if the element at `mid` is equal to `target` and returning `mid` if true.
1 Mark: Correct recursive calls with updated search limits (`mid - 1` and `mid + 1`).

The two-pointer technique initializes `left` at index 0 and `right` at the last index of the array (`arr.length - 1`). Within a loop that runs while `left` is strictly less than `right`, the sum of the elements at these two pointers is calculated. If the sum matches the `target`, `true` is returned. If the sum is less than the `target`, the `left` pointer is moved to the right (incremented) to increase the sum. If the sum is greater, the `right` pointer is moved to the left (decremented) to decrease the sum. If the pointers meet or cross, the loop terminates and `false` is returned.

1 Mark: Initializing two pointers correctly (one at index 0, one at `arr.length - 1`).
1 Mark: Using a loop condition `left < right` to prevent pointers from crossing or comparing the same element.
1 Mark: Correct comparison of `currentSum` with `target` returning `true` on match.
1 Mark: Correctly incrementing `left` when sum is too small, decrementing `right` when sum is too large, and returning `false` after the loop.

The memoized function first checks if `memo[n]` is not equal to `-1` (meaning it has already been computed). If it has, the cached value is returned immediately. Otherwise, the function recursively calculates the value by summing `fibMemo(n - 1, memo)` and `fibMemo(n - 2, memo)`, stores the result in `memo[n]`, and then returns `memo[n]`.

1 Mark: Correctly checking if the value is already computed and cached in `memo[n]` (i.e. `memo[n] != -1`) and returning it.
1 Mark: Making the correct recursive calls to `fibMemo(n - 1, memo)` and `fibMemo(n - 2, memo)`.
1 Mark: Summing the two recursive results and storing the outcome in `memo[n]`.
1 Mark: Correctly returning the calculated/stored value from the function.

1. Algorithmic Operation:
- Dijkstra's algorithm is a single-source shortest path algorithm. It systematically visits adjacent nodes, updating their shortest distance from the start, and choosing the next unvisited node with the smallest cumulative distance using a priority queue. It expands uniformly in all directions (radial search).
- A* is an extension of Dijkstra's that guides the search towards the goal node using a heuristic. For each node \(n\), it calculates \(f(n) = g(n) + h(n)\), where \(g(n)\) is the actual cost from the start to \(n\), and \(h(n)\) is the estimated cost from \(n\) to the goal. It chooses the node with the lowest \(f(n)\) to expand next.

2. Heuristic Function & Admissibility:
- The heuristic \(h(n)\) estimates the remaining cost to the destination. For a delivery drone, a typical heuristic is the 3D Euclidean (straight-line) distance.
- An admissible heuristic is one that never overestimates the true cost to reach the goal (i.e., \(h(n) \le h^*(n)\) where \(h^*(n)\) is the actual optimal cost). Because a straight-line is the shortest path between two points in space, the Euclidean distance is guaranteed to be admissible (it will always be less than or equal to the actual flight path which might have to navigate around obstacles or wind currents). If the heuristic is admissible, A* is guaranteed to find the optimal shortest path.

3. Relative Efficiency:
- Search Space / Execution Time: Dijkstra's algorithm searches in a circular pattern, exploring nodes in directions away from the goal, which leads to high execution times. A* uses the heuristic to focus the search toward the destination, drastically reducing the number of nodes evaluated (smaller search space) and thus running significantly faster.
- Memory Usage: Both algorithms have similar theoretical space complexity as they both maintain open lists (to-be-evaluated nodes) and closed lists (visited nodes). However, because A* evaluates fewer nodes, its actual memory footprint during execution is typically smaller than Dijkstra's in practical scenarios.

Level 3 (9-11 marks):
- Detailed and accurate description of both algorithms, showing clear understanding of \(f(n) = g(n) + h(n)\).
- Comprehensive explanation of admissibility with a contextual example (Euclidean distance for the drone).
- Thorough comparison of efficiency (time/search space/memory) with clear technical terminology.
- Logical structure and excellent use of computer science vocabulary.

Level 2 (5-8 marks):
- Explains both algorithms but may lack detail on how they select the next node.
- Explains the role of the heuristic and admissibility, but the drone context may not be fully integrated.
- Compares efficiency, but may miss details on space complexity or search space shape.
- Reasonable structure with minor technical inaccuracies.

Level 1 (1-4 marks):
- Basic outline of at least one algorithm.
- Mentions heuristics but does not explain admissibility clearly.
- Superficial comparison of efficiency.
- Answer lacks structure.

1. Divide-and-Conquer Mechanisms:
- Quick Sort selects a 'pivot' element and partitions the array such that all elements smaller than the pivot are on its left, and all larger elements are on its right. It then recursively applies this process to the left and right sub-arrays. It performs the sorting in-place.
- Merge Sort recursively divides the array in half until sub-arrays of size 1 are reached. It then merges these sub-arrays back together in sorted order, which requires auxiliary workspace to hold the merged elements.

2. Time Complexity:
- Quick Sort: Best and Average case are \(O(n \log n)\). The worst-case is \(O(n^2)\), which occurs when the pivot consistently splits the array unevenly (e.g., if the data is already sorted or reverse-sorted and the first/last element is always chosen as the pivot).
- Merge Sort: Best, Average, and Worst-case time complexities are all strictly \(O(n \log n)\) because the array is always split exactly in half, regardless of the initial order of the data.

3. Space Complexity:
- Quick Sort: It is an in-place sorting algorithm, requiring only \(O(\log n)\) auxiliary space on the call stack for recursion.
- Merge Sort: It is not an in-place algorithm; it requires \(O(n)\) auxiliary memory space to store the temporary sub-arrays during the merge phase. For large data streams, this doubling of memory usage is highly significant.

4. Recommendation & Embedded Context:
- The smart band has a 'memory-constrained' microcontroller. A \(O(n)\) space requirement (Merge Sort) for a large array of 24 hours of heart rate readings could exceed the available RAM, causing a system crash.
- Therefore, Quick Sort is the superior choice because of its minimal \(O(\log n)\) memory footprint.
- To mitigate Quick Sort's worst-case \(O(n^2)\) time complexity (which could occur if heart rate streams are already sorted or highly ordered), the developer must implement an intelligent pivot selection method, such as a random pivot or 'median-of-three' pivot, ensuring average-case \(O(n \log n)\) performance is maintained.

Level 3 (9-11 marks):
- Clear, accurate explanation of both Quick Sort and Merge Sort mechanics under divide-and-conquer.
- Precise identification of all time complexities (best/average/worst) and the reasons behind Quick Sort's \(O(n^2)\) worst case.
- Precise comparison of auxiliary space complexity (\(O(\log n)\) vs \(O(n)\)).
- Fully justified recommendation based on the constraints of the embedded system, showing deep understanding of memory limitations and worst-case mitigation.

Level 2 (5-8 marks):
- Explains both sorting mechanisms reasonably well.
- States correct time and space complexities but may lack depth on how they are derived or why Quick Sort's worst-case occurs.
- Suggests a recommendation, but the justification regarding the memory-constrained context might be weak or incomplete.

Level 1 (1-4 marks):
- Basic descriptions of one or both algorithms.
- Some correct mention of time or space complexity but with errors.
- Weak or missing recommendation with little or no link to the scenario.

Step-by-step trace: 1. enqueue("A") -> head = 0, tail = 0, array = ['A', '', '', '', '']. 2. enqueue("B") -> head = 0, tail = 1, array = ['A', 'B', '', '', '']. 3. dequeue() -> removes 'A', head becomes 1, tail = 1, array = ['', 'B', '', '', '']. 4. enqueue("C") -> head = 1, tail = 2, array = ['', 'B', 'C', '', '']. 5. enqueue("D") -> head = 1, tail = 3, array = ['', 'B', 'C', 'D', '']. 6. enqueue("E") -> head = 1, tail = 4, array = ['', 'B', 'C', 'D', 'E']. 7. dequeue() -> removes 'B', head becomes 2, tail = 4, array = ['', '', 'C', 'D', 'E']. 8. enqueue("F") -> tail wraps around to 0, head = 2, tail = 0, array = ['F', '', 'C', 'D', 'E'].

Award marks as follows: 1.5 marks for the correct final state of the array (0.5 marks for F at index 0, 0.5 marks for index 1 being empty, 0.5 marks for C, D, E at indices 2, 3, 4). 1.0 mark for head = 2. 1.0 mark for tail = 0.

1. Push 7 -> Stack: [7]. 2. Push 5 -> Stack: [7, 5]. 3. Operator '+': Pop 5, Pop 7, calculate 7 + 5 = 12, Push 12 -> Stack: [12]. 4. Push 2 -> Stack: [12, 2]. 5. Operator '*': Pop 2, Pop 12, calculate 12 * 2 = 24, Push 24 -> Stack: [24]. 6. Push 3 -> Stack: [24, 3]. 7. Operator '-': Pop 3, Pop 24, calculate 24 - 3 = 21, Push 21 -> Stack: [21].

Award marks as follows: 1.5 marks for showing correct intermediate stack states up to and including the * operator. 1.0 mark for stating the stack state immediately after * is [24]. 1.0 mark for stating the final value is 21.

1. The node used is the one pointed to by freePointer, which is Node 3. 2. The freePointer is updated to Node 3's current next value, which is 4. 3. The value 15 is stored in Node 3. 4. Since 15 is numerically between 12 (Node 0) and 18 (Node 2), Node 3 must be inserted between them. 5. Node 0's next pointer is updated to point to Node 3 (next = 3). 6. Node 3's next pointer is set to point to Node 2 (next = 2).

Award marks as follows: 1.0 mark for identifying Node 3 is used. 1.0 mark for identifying freePointer becomes 4. 1.5 marks for correct next pointer updates (0.75 marks for Node 0 next = 3, and 0.75 marks for Node 3 next = 2).

1. 50 is inserted at Index 0 (root): [-1, 50, -1]. 2. 30 is less than 50, goes left, stored at Index 1. Index 0 becomes [1, 50, -1], Index 1 becomes [-1, 30, -1]. 3. 70 is greater than 50, goes right, stored at Index 2. Index 0 becomes [1, 50, 2], Index 2 becomes [-1, 70, -1]. 4. 40 is less than 50 (left to Index 1), greater than 30 (right to Index 3). Index 1 becomes [-1, 30, 3], Index 3 becomes [-1, 40, -1]. 5. 60 is greater than 50 (right to Index 2), less than 70 (left to Index 4). Index 2 becomes [4, 70, -1], Index 4 becomes [-1, 60, -1].

Award marks as follows: 1.0 mark for correct Index 0 row [1, 50, 2]. 1.0 mark for correct Index 1 row [-1, 30, 3]. 1.0 mark for correct Index 2 row [4, 70, -1]. 0.5 marks for correct leaf nodes at Index 3 and Index 4.

1. Start at P. Dequeue P. Add unvisited neighbors Q and S to queue. Queue: [Q, S]. Visited: {P, Q, S}. 2. Dequeue Q. Add unvisited neighbors R and T to queue. Queue: [S, R, T]. Visited: {P, Q, S, R, T}. 3. Dequeue S. Neighbors P and T are already visited. Queue: [R, T]. 4. Dequeue R. Add unvisited neighbor U to queue. Queue: [T, U]. Visited: {P, Q, S, R, T, U}. 5. Dequeue T. Neighbors Q, S, U are visited. Queue: [U]. 6. Dequeue U. Queue is empty. The order of dequeued vertices is P, Q, S, R, T, U.

Award marks as follows: 1.0 mark for the correct first three nodes (P, Q, S). 1.5 marks for the correct final three nodes (R, T, U). 1.0 mark for correctly showing application of alphabetical ordering rule during queue additions.

1. 15 MOD 7 = 1. Index 1 is empty. Insert 15 at Index 1. 2. 22 MOD 7 = 1. Index 1 is occupied. Probe Index 2. Empty. Insert 22 at Index 2. 3. 8 MOD 7 = 1. Index 1 and 2 occupied. Probe Index 3. Empty. Insert 8 at Index 3. 4. 29 MOD 7 = 1. Index 1, 2, 3 occupied. Probe Index 4. Empty. Insert 29 at Index 4. 5. 3 MOD 7 = 3. Index 3 is occupied by 8. Probe Index 4 (occupied by 29). Probe Index 5. Empty. Insert 3 at Index 5.

Award marks as follows: 1.0 mark for correctly placing 15 at Index 1 and 22 at Index 2. 1.0 mark for correctly placing 8 at Index 3 after 2 collisions. 1.5 marks for correctly placing 29 at Index 4 and 3 at Index 5 (0.75 marks each).

The circular queue must keep track of its size (limit of 5) using an count variable or index mathematics. Here is a complete Python solution:

```python
class PacketQueue:
def __init__(self):
self.__buffer = ["" for _ in range(5)] # Create array of size 5
self.__head = 0
self.__tail = 0
self.__numElements = 0

def enqueue(self, packet):
if self.__numElements == 5:
print("Queue Full")
else:
self.__buffer[self.__tail] = packet
self.__tail = (self.__tail + 1) % 5
self.__numElements += 1

def dequeue(self):
if self.__numElements == 0:
print("Queue Empty")
return ""
else:
packet = self.__buffer[self.__head]
self.__buffer[self.__head] = "" # Optional clean up
self.__head = (self.__head + 1) % 5
self.__numElements -= 1
return packet
```

Marks are awarded as follows:
- 1 Mark: Correct constructor initializing private buffer of size 5 and pointers (head, tail, and numElements set to 0).
- 1 Mark: Enqueue checks if queue is full using numElements (or pointer math) and outputs an error message.
- 1 Mark: Enqueue adds packet at index tail, and updates tail circularly using modular division: (tail + 1) % 5.
- 1 Mark: Enqueue increments numElements correctly on success.
- 1 Mark: Dequeue checks if queue is empty (numElements == 0), printing an error and returning "".
- 1 Mark: Dequeue retrieves the item, updates head circularly: (head + 1) % 5, decrements numElements, and returns the retrieved item.

This is an example implementation in Python:

```python
class Healer(GameCharacter):
def __init__(self, name, health, mana):
# Call parent class constructor
super().__init__(name, health)
# Initialize private attribute mana
self.__mana = mana

def takeDamage(self, amount):
if self.__mana > 10:
self.__mana -= 10
final_damage = amount // 2
else:
final_damage = amount

# Update health using inherited methods
new_health = self.getHealth() - final_damage
self.setHealth(new_health)
```

Marks are awarded as follows:
- 1 Mark: Correct subclass definition showing inheritance from GameCharacter (e.g., class Healer(GameCharacter)).
- 1 Mark: Constructor accepts parameters name, health, and mana.
- 1 Mark: Constructor calls super / parent constructor passing name and health.
- 1 Mark: Constructor sets self.__mana to the parameter value.
- 1 Mark: Method takeDamage is overridden and checks if mana is > 10; if so, reduces mana by 10 and damage by half.
- 1 Mark: Accesses health using parent methods self.getHealth() and self.setHealth() to correctly update character health.

An implementation in Python:

```python
class ExpressionGuard:
def __init__(self):
self.__stack = []

def __push(self, item):
self.__stack.append(item)

def __pop(self):
if len(self.__stack) == 0:
return None
return self.__stack.pop()

def isValid(self, expr):
self.__stack = [] # Reset stack
for char in expr:
if char == '(':
self.__push(char)
elif char == ')':
if self.__pop() is None:
return False
return len(self.__stack) == 0
```

Marks are awarded as follows:
- 1 Mark: Correct constructor initializing private stack (e.g. self.__stack = []).
- 1 Mark: Correct implementations of private methods push and pop, where pop handles empty stack by returning None or similar indicator.
- 1 Mark: isValid method processes the input string character-by-character using a loop.
- 1 Mark: On encountering '(', pushes the character to the stack using the internal push method.
- 1 Mark: On encountering ')', calls the internal pop method and returns False if the pop returns None (empty stack).
- 1 Mark: At the end of the loop, checks if stack is empty; returns True if empty, and False otherwise.

Below is a complete implementation in OCR-style pseudocode:

```text
function countSingleChildNodes(currentNode)
if currentNode == null then
return 0
endif

if (currentNode.left != null and currentNode.right == null) or (currentNode.left == null and currentNode.right != null) then
return 1 + countSingleChildNodes(currentNode.left) + countSingleChildNodes(currentNode.right)
else
return countSingleChildNodes(currentNode.left) + countSingleChildNodes(currentNode.right)
endif
endfunction
```

1 mark: Correct base case checking if the current node is null and returning 0.
1 mark: Logical check for a node with a left child but no right child.
1 mark: Logical check for a node with a right child but no left child.
1 mark: Correct recursion when exactly one child exists (adds 1 to the sum of the left and right recursive calls).
1 mark: Correct recursion when either zero or two children exist (sums the left and right recursive calls without adding 1).
1 mark: Correct function structure with clear parameters, return statements, and recursive depth handling.

Below is a complete implementation in OCR-style pseudocode:

```text
function compressString(inputStr)
compressed = ""
count = 1
for i = 0 to inputStr.length - 2
if inputStr[i] == inputStr[i+1] then
count = count + 1
else
compressed = compressed + count.toString() + inputStr[i]
count = 1
endif
next i
compressed = compressed + count.toString() + inputStr[inputStr.length - 1]
return compressed
endfunction
```

1 mark: Correct initialization of a target accumulation string to "" and counter variable to 1.
1 mark: Correct loop bounds iterating up to the second-to-last character (index `length - 2`).
1 mark: Comparison logic to check if current character equals the next character (`inputStr[i] == inputStr[i+1]`).
1 mark: Increment of counter variable on matches.
1 mark: Correctly appending count and character to the accumulator string on non-matches, and resetting counter to 1.
1 mark: Correctly handling the final character cluster after the loop terminates, and returning the completed string.

### Comparison and Evaluation:

#### 1. Memory Management and Overhead
- **Approach A (Static Array)**:
- Allocates a contiguous block of memory of a fixed size (100 elements) upon instantiation.
- Memory usage is constant \(O(1)\) relative to the active number of undo states.
- Wastes memory if the stack is mostly empty, but guarantees that the application will never exceed a known, predictable memory footprint for the undo history.
- **Approach B (Dynamic Linked List)**:
- Allocates memory dynamically on the heap only when a new state is pushed, and deallocates it when popped.
- Avoids wasting memory when there are few undo states.
- Introduces memory overhead because each node must store a reference/pointer to the next node in addition to the actual state data.

#### 2. Algorithmic Efficiency (Time Complexity)
- **Approach A (Static Array)**:
- Both `push` and `pop` operations are strictly \(O(1)\).
- Because elements are contiguous, they benefit from excellent CPU cache locality, leading to ultra-fast access times.
- Overwriting oldest elements in a circular setup is a simple pointer-arithmetic operation.
- **Approach B (Dynamic Linked List)**:
- Programmatically, inserting or deleting at the head of a linked list is also \(O(1)\).
- However, dynamic memory allocation (calling `new` or `malloc`) and garbage collection/deallocation can introduce significant, unpredictable runtime latency spikes.
- Lacks cache locality because nodes are scattered across the heap, causing potential CPU cache misses.

#### 3. Suitability for High-Performance Graphics Editor
- **Approach A** is highly suitable. A limit of 100 undo states is standard in professional graphics editors (e.g., Photoshop). It acts as a natural memory safeguard, preventing the app from consuming gigabytes of RAM during long sessions. The execution time is highly predictable.
- **Approach B** is less suitable. An unlimited undo history on complex vector files containing thousands of paths could easily deplete the host system's RAM, causing crashes. The overhead of heap allocations could also cause frame drops during intensive editing operations.

This is an essay-style question marked out of 9 using a levels-of-response framework.

### Mark Bands:

**Level 3 (7-9 marks)**
- **Knowledge**: Comprehensive knowledge of both static arrays and dynamic linked lists.
- **Application**: Clear application to the context of a high-performance graphics editor.
- **Evaluation**: Balanced comparison covering memory, time complexity (including cache locality/heap latency), and suitability. The final recommendation is fully justified.

**Level 2 (4-6 marks)**
- **Knowledge**: Good understanding of both data structures.
- **Application**: Some reference to the vector graphics editor scenario.
- **Evaluation**: Discusses at least two of the prompt's aspects (memory, complexity, suitability) with reasonable detail. Some technical points may lack depth.

**Level 1 (1-3 marks)**
- **Knowledge**: Basic definition of arrays and/or linked lists.
- **Application**: Limited or no application to the scenario.
- **Evaluation**: Identifies basic pros/cons (e.g., "arrays have a limit, lists do not") without evaluating performance or memory implications in a structured way.

### Indicative Content to look for:
- **Static Array Pros/Cons**: Fixed memory size (predictable), Fast \(O(1)\) indexing, Cache-friendly, risks overflow if circular logic isn't used or hard limits are hit.
- **Dynamic List Pros/Cons**: Grows/shrinks dynamically, Pointer overhead per node, Memory fragmentation risk, Latency of dynamic instantiation.
- **Contextual synthesis**: Connecting vector states (large memory footprint per state) to why a hard-limited circular array is safer than an unbounded dynamic list.