2024 Cambridge IAL Computer Science (9618) 模擬試題連答案詳解

Part (a):
1. Convert positive \(+42.625\) to binary fixed-point:
- Integer part \(42 = 32 + 8 + 2 = 00101010_2\) (8 bits)
- Fractional part \(0.625 = 0.5 + 0.125 = 0.1010_2\) (4 bits)
- Positive binary: \(00101010.1010\)
2. Perform Two's Complement to get the negative value:
- Invert all bits: \(11010101.0101\)
- Add 1 to the least significant bit (position \(2^{-4}\)):
\(11010101.0101 + 0.0001 = 11010101.0110\)
- Final representation: \(110101010110\)

Part (b):
- ASCII uses 7 bits (standard) or 8 bits (extended), which can only represent a maximum of 128 or 256 distinct characters. This is only sufficient for English and basic symbols.
- Unicode can represent over a million unique characters, allowing it to support multiple languages, mathematical symbols, and emojis globally.
- UTF-8 is a variable-length encoding system for Unicode:
- For standard ASCII (U+0000 to U+007F), it uses 1 byte, where the MSB is set to 0 (e.g., 0xxxxxxx).
- For larger code points, it uses between 2 and 4 bytes.
- The number of leading 1s in the first byte indicates the total number of bytes used (e.g., 110xxxxx for 2 bytes, 1110xxxx for 3 bytes).
- Subsequent continuation bytes always start with 10xxxxxx to maintain synchronization and allow easy scanning.

Part (a) [4 Marks]:
- 1 mark for correct positive integer part (00101010) or fractional part (1010).
- 1 mark for correct full positive fixed-point representation (00101010.1010).
- 1 mark for correct inversion of bits (11010101.0101).
- 1 mark for correct final 12-bit binary representation (110101010110).

Part (b) [6.7 Marks]:
- 1 mark: ASCII is restricted to 7/8 bits (max 128/256 characters).
- 1 mark: Unicode supports multi-byte representations allowing globally diverse characters/emojis.
- 1 mark: UTF-8 is variable-length (1 to 4 bytes).
- 1 mark: Identifies that ASCII-compatible characters use a single byte starting with a '0' bit.
- 1 mark: Explains that multi-byte characters have leading '1's in the first byte indicating the byte length (e.g., '110xxxxx' or '1110xxxx').
- 1.7 marks: Explains continuation bytes starting with '10' pattern to ensure robust synchronization.

Part (a):
1. \(\text{MAR} \leftarrow [\text{PC}]\) - The contents of the Program Counter (PC) are copied to the Memory Address Register (MAR).
2. \(\text{PC} \leftarrow [\text{PC}] + 1\) - The PC is incremented to point to the next instruction in memory.
3. \(\text{MDR} \leftarrow [[\text{MAR}]]\) - The instruction at the memory location stored in MAR is loaded into the Memory Data Register (MDR).
4. \(\text{CIR} \leftarrow [\text{MDR}]\) - The contents of MDR are copied into the Current Instruction Register (CIR) for decoding.

Part (b):
- At the end of the current instruction cycle (before fetching the next instruction), the processor checks for the presence of an interrupt signal.
- If an interrupt exists and has a higher priority than the currently running process:
- The current state (including the PC, Accumulator, and other status registers) is saved by pushing them onto a system stack.
- The processor identifies the source of the interrupt and determines the memory address of the corresponding Interrupt Service Routine (ISR).
- The Program Counter (PC) is loaded with the start address of the ISR.
- The ISR code is executed to handle the interrupt (e.g., reading data from an I/O device).
- Once the ISR finishes executing, the saved register states are popped from the stack and restored to their original registers.
- The PC resumes execution of the interrupted program at the correct next instruction.

Part (a) [4 Marks]:
- 1 mark: \(\text{MAR} \leftarrow [\text{PC}]\)
- 1 mark: \(\text{PC} \leftarrow [\text{PC}] + 1\)
- 1 mark: \(\text{MDR} \leftarrow [[\text{MAR}]]\) or equivalent read action.
- 1 mark: \(\text{CIR} \leftarrow [\text{MDR}]\)

Part (b) [6.7 Marks]:
- 1 mark: Checking for interrupt signal at the end of the current instruction cycle.
- 1 mark: Checking/comparing the priority of the interrupt.
- 1.7 marks: Saving the current register states (including PC/Accumulator) onto the stack.
- 1 mark: Loading the PC with the address of the Interrupt Service Routine (ISR).
- 1 mark: Executing the ISR.
- 1 mark: Restoring (popping) the saved values back to the registers and resuming normal execution.

Part (a):
- The relation is not in 3NF because:
- It contains partial key dependencies: \(StudentID \rightarrow StudentName\) and \(BookID \rightarrow BookTitle\) only depend on parts of a potential composite key \(\{StudentID, BookID, DateDue\}\), violating 2NF.
- It contains a transitive dependency: \(BookID \rightarrow AuthorID\) and \(AuthorID \rightarrow AuthorName\), which violates 3NF because a non-key attribute (AuthorName) depends on another non-key attribute (AuthorID).
- Data Anomalies:
- **Update Anomaly**: If a student changes their name, multiple records of past loans for that student must be updated. Failure to do so leads to inconsistent data.
- **Insertion Anomaly**: We cannot record a new student in the database unless they have borrowed at least one book, or we cannot store a new book and its author details until a student actually loans it.
- **Deletion Anomaly**: If a loan record is deleted, we might completely lose the only record of a student's name or a book's existence from our system.

Part (b):
- To reach 3NF, we decompose the database into four entities:
1. \(\text{STUDENT}(\underline{\text{StudentID}}, \text{StudentName})\)
2. \(\text{AUTHOR}(\underline{\text{AuthorID}}, \text{AuthorName})\)
3. \(\text{BOOK}(\underline{\text{BookID}}, \text{BookTitle}, \text{AuthorID}*)\)
- *Note: \(AuthorID\) is a Foreign Key referencing \(\text{AUTHOR}\).*
4. \(\text{LOAN}(\underline{\text{StudentID}*, \text{BookID}*, \text{DateDue}})\)
- *Note: \(StudentID\) and \(BookID\) are Foreign Keys. The primary key is composite \(\{\text{StudentID}, \text{BookID}, \text{DateDue}\}\).*

Part (a) [4.7 Marks]:
- 1 mark: Stating partial dependency exists (e.g., StudentName depends on StudentID, BookTitle on BookID).
- 1 mark: Stating transitive dependency exists (e.g., AuthorName depends on AuthorID, which depends on BookID).
- 1.35 marks: Explaining one anomaly (e.g., Update, Insertion, or Deletion) with context from the library scenario.
- 1.35 marks: Explaining a second distinct anomaly with context.

Part (b) [6 Marks]:
- 1 mark: STUDENT table with correct PK/attributes.
- 1 mark: AUTHOR table with correct PK/attributes.
- 1.5 marks: BOOK table with correct PK, attributes, and AuthorID as a Foreign Key.
- 1.5 marks: LOAN table with composite PK (StudentID, BookID, DateDue) and foreign keys clearly identified.
- 1 mark: Notation clearly distinguishes primary keys (e.g., underlined) and foreign keys (e.g., asterisk or labelled).

Part (a):
- **Comparison**:
- In a client-server model, a dedicated, centralized server hosts the files and manages resources, while client computers request files from it.
- In a peer-to-peer (P2P) model, there is no centralized server. Each node (peer) acts as both a client and a server, sharing its own files and downloading directly from other peers.
- **Advantages of Client-Server**:
1. Centralized backup: All shared files reside on the server, making it simple to perform regular backups.
2. Centralized security: Access rights, firewalls, and security policies are managed at a single point, ensuring higher security control.
- **Advantages of Peer-to-Peer**:
1. Scalability: As more peers join the network, the available bandwidth and source locations increase, improving overall system performance.
2. No single point of failure: If one peer goes offline, other peers can still provide files, ensuring high redundancy and availability.

Part (b):
- **Necessity of Transition**:
- IPv4 uses 32-bit addressing, which supports approximately \(4.3 \times 10^9\) unique addresses. Due to the rapid proliferation of internet-connected devices, these addresses are exhausted.
- IPv6 uses 128-bit addressing, providing \(2^{128}\) (approx. \(3.4 \times 10^{38}\)) unique addresses, which resolves this issue indefinitely.
- **Structural Differences**:
1. **Address Size**: IPv4 addresses are 32 bits long, whereas IPv6 addresses are 128 bits long.
2. **Notation Format**: IPv4 addresses are written in dotted-decimal format (e.g., \(192.168.1.1\)). IPv6 addresses are written in hexadecimal format separated by colons (e.g., \(2001:0db8:85a3:0000:0000:8a2e:0370:7334\)).

Part (a) [5.7 Marks]:
- 1 mark: Correct contrast of topology/structure (centralized vs decentralized peer-to-peer relationship).
- 1 mark: Advantage 1 of Client-Server (e.g., Centralized security / backups / management).
- 1 mark: Advantage 2 of Client-Server (e.g., Consistent performance, reliable infrastructure).
- 1 mark: Advantage 1 of P2P (e.g., No single point of failure / fault tolerance).
- 0.7 marks: Advantage 2 of P2P (e.g., Low cost / easy setup / scalable bandwidth with more nodes).

Part (b) [5 Marks]:
- 1 mark: Explanation of IPv4 address exhaustion due to the explosion of devices.
- 1 mark: Mention of 32-bit vs 128-bit address sizes.
- 1 mark: Correct calculation or state of address capacity differences (\(4.3 \times 10^9\) vs \(3.4 \times 10^{38}\)).
- 1 mark: Identification of dotted-decimal vs hexadecimal colon-separated notation.
- 1 mark: Mention of built-in features (e.g., IPv6 native support for IPsec, lack of NAT necessity, or packet header simplification).

Part (a):
- **Capacitive Touchscreen Operation**:
- A capacitive touchscreen consists of a glass panel coated with a transparent, conductive layer (such as Indium Tin Oxide).
- An electrostatic field is created across the panel.
- When a conductive object (such as a bare human finger) touches the glass, it draws a small amount of electrical current, causing a change in capacitance at that specific point.
- Sensors located at the screen corners measure this change in capacitance and calculate the coordinates of the touch.
- **Contrast with Resistive Touchscreen**:
- A resistive touchscreen consists of two flexible layers with a thin air gap or micro-dots between them.
- When pressed physically, the outer layer deforms and touches the inner layer, completing an electrical circuit at that location.
- While capacitive screens detect changes in *electrical charge* (no pressure needed), resistive screens detect physical *pressure*.
- **Disadvantage of Capacitive**:
- Capacitive touchscreens require a conductive input device; they cannot be operated with standard non-conductive plastic styluses, gloved hands, or fingernails, whereas resistive screens can be operated with any object.

Part (b):
- **NAND Flash & Floating Gate Storage**:
- NAND flash memory consists of cells made of floating gate transistors.
- Each transistor contains a control gate and a floating gate, separated by an insulating oxide layer.
- Electrons can be trapped inside the floating gate by applying a high programming voltage (quantum tunneling).
- When electrons are trapped in the floating gate, they block or modify the electric field from the control gate, altering the threshold voltage of the transistor.
- The level of charge (trapped vs. empty) dictates whether the cell represents a binary '1' or '0'.
- Since the oxide layer prevents electrons from escaping, the data is non-volatile.
- **Benefits of SSD over HDD**:
- **Speed**: SSDs have much faster read/write speeds because they do not require physical read/write heads to move to a magnetic track.
- **Durability**: SSDs have no moving parts, making them far more resistant to physical shock, drops, or vibrations.

Part (a) [5.7 Marks]:
- 1 mark: Explaining the capacitive screen structure (conductive coating, electrostatic field).
- 1 mark: Explaining how touch causes a change in capacitance/electrical charge.
- 1 mark: Explaining how coordinates are calculated from the corners/edges.
- 1 mark: Explaining that resistive touchscreens rely on physical pressure completing an electrical circuit between two flexible layers.
- 1 mark: Explaining the difference in activation (electrical conduction vs physical pressure).
- 0.7 marks: Correct disadvantage of capacitive touchscreens (cannot use with standard gloves/dry plastic styluses).

Part (b) [5 Marks]:
- 1 mark: Mention of floating gate transistors separated by insulating oxide layers.
- 1 mark: Explaining how high voltage is used to trap electrons within the floating gate.
- 1 mark: Explaining that trapped electrons alter the threshold voltage, representing binary states 1 or 0.
- 1 mark: Benefit 1 of SSD (Faster read/write/access times / no latency).
- 1 mark: Benefit 2 of SSD (Robustness / silent operation / lower power consumption due to lack of mechanical moving parts).

Part (a):
- **Difference**:
- **Validation** is an automatic computer-based check that ensures data entered is sensible, realistic, and conforms to predefined validation rules (e.g., data type, length, or range) before it is processed.
- **Verification** is a process that checks whether data entered exactly matches the original source data (preventing transposition or transcription errors).
- **Examples during registration**:
- **Validation**: A format check on the email address field to ensure it contains an '@' symbol and a domain extension (e.g., '.com').
- **Verification**: Asking the user to enter their chosen password twice (double-entry check) to ensure they didn't make a typing error in the first attempt.

Part (b):
- **Confidentiality (Sending the instruction)**:
1. The customer's browser obtains the bank's validated **Public Key**.
2. The browser encrypts the transaction details using this public key to create ciphertext.
3. The ciphertext is sent over the internet.
4. Only the bank can decrypt this ciphertext because only the bank possesses the corresponding secret **Private Key**.

- **Authenticity and Integrity (Digital Signature)**:
1. The browser creates a cryptographic **hash** of the transaction message.
2. This hash is encrypted using the customer's private key to create the **Digital Signature**.
3. The digital signature is sent along with the encrypted transaction message.
4. The bank decrypts the signature using the customer's **Public Key** to recover the original hash.
5. The bank calculates a new hash of the received transaction message.
6. If the calculated hash matches the decrypted hash, it proves:
- **Integrity**: The message has not been altered during transit.
- **Authenticity (Non-repudiation)**: The message must have been sent by the customer, as only their private key could have produced the signature.

Part (a) [4.7 Marks]:
- 1 mark: Clear definition of data validation.
- 1 mark: Clear definition of data verification.
- 1.35 marks: Realistic registration example of validation (e.g., format check on email/date of birth).
- 1.35 marks: Realistic registration example of verification (e.g., double entry of password).

Part (b) [6 Marks]:
- 1 mark: Customer's browser encrypts the message using the bank's Public Key.
- 1 mark: Bank decrypts the message using its Private Key to ensure confidentiality.
- 1 mark: Browser hashes the message and encrypts this hash with the customer's Private Key to form the digital signature.
- 1 mark: Bank decrypts the digital signature using the customer's Public Key.
- 1 mark: Bank hashes the received message and compares it to the decrypted hash.
- 1 mark: Explaining how a match guarantees integrity (no alterations) and non-repudiation/authenticity.

Part (a):
The State-Transition Diagram consists of 5 states and 5 directional transitions:
1. **State `UP` to State `WARNING`**:
- Triggered when a train approaches: input `T = True`.
2. **State `WARNING` to State `DESCENDING`**:
- Triggered when the warning phase completes: input `W = True`.
3. **State `DESCENDING` to State `DOWN`**:
- Triggered when the barrier reaches the bottom sensor: input `D = True`.
4. **State `DOWN` to State `ASCENDING`**:
- Triggered when the train has cleared the crossing: input `C = True`.
5. **State `ASCENDING` to State `UP`**:
- Triggered when the barrier reaches the top sensor: input `U = True`.

Part (b):
```pseudocode
PROCEDURE UpdateCrossingState()
CASE OF CurrentState
"UP":
IF T = TRUE THEN
CurrentState <-- "WARNING"
ENDIF
"WARNING":
IF W = TRUE THEN
CurrentState <-- "DESCENDING"
ENDIF
"DESCENDING":
IF D = TRUE THEN
CurrentState <-- "DOWN"
ENDIF
"DOWN":
IF C = TRUE THEN
CurrentState <-- "ASCENDING"
ENDIF
"ASCENDING":
IF U = TRUE THEN
CurrentState <-- "UP"
ENDIF
ENDCASE
ENDPROCEDURE
```

Part (a) [5.7 Marks]:
- 1 mark: Stating the 5 states clearly (UP, WARNING, DESCENDING, DOWN, ASCENDING).
- 1 mark: Correct transition from UP to WARNING on input T.
- 1 mark: Correct transition from WARNING to DESCENDING on input W.
- 1 mark: Correct transition from DESCENDING to DOWN on input D.
- 1 mark: Correct transition from DOWN to ASCENDING on input C.
- 0.7 marks: Correct transition from ASCENDING to UP on input U.

Part (b) [5 Marks]:
- 1 mark: Using a syntactically correct selection structure (e.g., CASE OF or nested IF-THEN-ELSE) mapping `CurrentState` values.
- 1 mark: Correct condition checking for `UP` state transitioning to `WARNING` using boolean variable `T`.
- 1 mark: Correct condition checking for `WARNING` and `DESCENDING` state transitions using `W` and `D`.
- 1 mark: Correct condition checking for `DOWN` and `ASCENDING` state transitions using `C` and `U`.
- 1 mark: Proper assignment statements (e.g., `CurrentState <-- "WARNING"`) with matching variable types and ending the conditional structures cleanly.

The function initializes Low to 1, High to 100, and Result to -1. During the binary search loop, if the Target matches DataArray[Mid], the index is stored in Result. Instead of terminating, the search continues in the left half by setting High to Mid - 1 to find any earlier occurrences. If DataArray[Mid] is less than Target, Low is updated to Mid + 1. Otherwise, High is updated to Mid - 1. This guarantees the search successfully finds the first (lowest index) occurrence of Target in \(O(\log N)\) time.

Total Marks: 9.375
- Correct function header and return type declaration (1.875 marks)
- Proper initialization of Low, High, and Result variables (1.875 marks)
- Correct loop condition (Low <= High) and Mid calculation using DIV (1.875 marks)
- Correct adjustment to check the left subarray when Target matches DataArray[Mid] (1.875 marks)
- Correct handling of standard binary search conditions (Low/High adjustments) and final RETURN statement (1.875 marks)

The variables TotalCount and PrimeCount are declared and initialized to 0. An initial input is read outside the loop. The loop runs while the input Num is not equal to the sentinel value -1. Within the loop, we check if Num is strictly greater than 0. If so, TotalCount is incremented, and we evaluate IsPrime(Num). If true, PrimeCount is incremented. Inside the loop, another input is prompted. After the loop, a selection statement prevents a division-by-zero error if no positive integers were supplied. Otherwise, the percentage is computed and outputted.

Total Marks: 9.375
- Declaration and initialisation of variables (TotalCount, PrimeCount) (1.875 marks)
- Proper reading of user inputs, including correct sentinel check (Num <> -1) (1.875 marks)
- Correctly ignoring non-positive inputs while processing valid numbers (1.875 marks)
- Correct call to IsPrime helper function and updating of PrimeCount and TotalCount (1.875 marks)
- Calculation of percentage with validation to prevent division by zero, and correct outputs (1.875 marks)

The procedure first checks if the queue is full by comparing NumItems to 10. If so, it outputs an overflow error. Otherwise, TailPointer is updated. Because it is a circular queue, if TailPointer is at 10, it wraps around to 1; otherwise, it is incremented by 1. The item is inserted at Queue[TailPointer], and NumItems is incremented. If this is the first item added (HeadPointer is 0), HeadPointer is initialized to 1.

Total Marks: 9.375
- Correct procedure header accepting NewItem parameter (1.875 marks)
- Correct overflow validation using NumItems (1.875 marks)
- Correct circular pointer wrap-around logic for TailPointer (1.875 marks)
- Storing the new item at the calculated TailPointer and incrementing NumItems (1.875 marks)
- Correct initialization of HeadPointer when queue transitions from empty to non-empty (1.875 marks)

The procedure scans CmdStr using a loop from index 1 to the length of the string to find the first space character. If a space is found, its index is stored in SpacePos, and we terminate the loop early. If SpacePos is greater than 0, LEFT and RIGHT functions extract the respective substrings (excluding the space). Otherwise, the whole string is copied to Command, and Parameter is assigned "".

Total Marks: 9.375
- Correct procedure header with BYREF/BYVAL parameters (1.875 marks)
- Correct loop declaration to iterate through the string and detect the space character (1.875 marks)
- Correct identification of the first space index (SpacePos) and exit logic (1.875 marks)
- Correct extraction of the Command string using LEFT or MID (1.875 marks)
- Correct extraction of the Parameter string using RIGHT or MID, and handling the no-space scenario (1.875 marks)

The function initializes CurrentPointer to StartPointer and PreviousPointer to 0. It traverses the linked list using a WHILE loop until it either reaches the end (0) or finds the node matching Target. If CurrentPointer is 0, the node is not found, so it returns FALSE. If the node to delete is the first node (PreviousPointer = 0), StartPointer is updated. Otherwise, the predecessor's pointer is updated to bypass the deleted node. Finally, the freed node is linked to the head of the free list pool, and FreePointer is updated. The function then returns TRUE.

Total Marks: 9.375
- Correct function header, parameters, and variable declarations (1.875 marks)
- Correct traversal loop tracking previous and current pointer nodes (1.875 marks)
- Correct check for not-found condition (returning FALSE) (1.875 marks)
- Correct re-linking of the active list pointers (handling both start node and middle/end nodes) (1.875 marks)
- Correct re-linking of the deleted node to the free list pool and returning TRUE (1.875 marks)

The function first determines the length of InputStr and handles the empty string base case by returning "". It initializes CurrentChar to the first character, sets Count to 1, and initializes EncodedStr to empty. A FOR loop iterates from the second character to the end. If the current character matches CurrentChar, Count is incremented. Otherwise, the compressed token is concatenated to EncodedStr, CurrentChar is updated, and Count is reset to 1. After the loop, the final run must be appended. Finally, EncodedStr is returned.

Total Marks: 9.375
- Correct function header, parameters, and return type (1.875 marks)
- Correct handling of empty string edge-case (1.875 marks)
- Loop designed to scan through each character of InputStr sequentially (1.875 marks)
- Accurate detection of repeating characters vs character changes (1.875 marks)
- Correct string conversion, concatenation, and appending of the final character block (1.875 marks)

The procedure handles potential file open errors using an exception block. It opens 'words.txt' and reads the first line to initialize ShortestWord and MinLength. It then enters a WHILE loop, reading line-by-line until EOF is true. If any read word has a length strictly less than MinLength, ShortestWord and MinLength are updated. This handles finding the first shortest word. Finally, it outputs the values and closes the file.

Total Marks: 9.375
- Correct procedure header and file open command (1.875 marks)
- Correct logic to handle empty file condition (1.875 marks)
- Loop to read words until EOF is reached (1.875 marks)
- Correct condition to compare string lengths and capture the strict shortest (using < rather than <=) (1.875 marks)
- Proper file closing and outputting of the results (1.875 marks)

The procedure declares the boolean variable Swapped to check if any swaps happened during a pass. Within a REPEAT...UNTIL loop, Swapped is set to FALSE, and we iterate from index 1 to n - 1. If an out-of-order pair is found, the elements are swapped, and Swapped is updated to TRUE. After each pass, the upper bound n is decremented, because the largest element of that pass is already in its final sorted position. The loop terminates either when Swapped remains FALSE or n is less than or equal to 1.

Total Marks: 9.375
- Correct procedure header with BYREF parameter and variable declarations (1.875 marks)
- Proper initialization of loop limits and resetting the Swapped flag at the beginning of each pass (1.875 marks)
- Inner loop comparing adjacent elements and carrying out swap correctly (1.875 marks)
- Correctly setting Swapped flag to TRUE when a swap occurs (1.875 marks)
- Decrementing loop limit n and correct termination conditions in REPEAT-UNTIL (1.875 marks)

(a) Working:
- The mantissa is `10110100`. Since the leftmost bit is 1, this represents a negative normalized number.
- Converting the mantissa to decimal:
Weight of MSB is \(-1\).
Value = \(-1 + 0 \times 2^{-1} + 1 \times 2^{-2} + 1 \times 2^{-3} + 0 \times 2^{-4} + 1 \times 2^{-5}\)
Value = \(-1 + 0.25 + 0.125 + 0.03125 = -0.59375\)
- The exponent is `0101`.
Since it starts with 0, it is a positive number.
Value = \(4 + 1 = 5\).
- Overall value = Mantissa \(\times 2^{\text{exponent}}\)
Value = \(-0.59375 \times 2^5 = -0.59375 \times 32 = -19\).

(b) Explanation:
- Overflow occurs when the result of a floating-point calculation is too large to be represented within the allocated range.
- In this system, this happens when the positive exponent required to represent the number is greater than the maximum possible value of the exponent (which is \(+7\) for a 4-bit two's complement exponent).

**Part (a) [4 marks]**
- 1 mark for identifying the correct decimal exponent: \(5\) (or \(2^5\) / 32).
- 1 mark for identifying that the mantissa is negative and showing correct two's complement expansion (e.g., \(-1 + 0.25 + 0.125 + 0.03125\)).
- 1 mark for correct decimal mantissa: \(-0.59375\) (or \(-19/32\)).
- 1 mark for correct final decimal answer: \(-19\).

**Part (b) [3 marks]**
- 1 mark for defining overflow (the value is too large to be represented by the system).
- 1 mark for identifying that this occurs when the required exponent is larger than the maximum representable exponent.
- 1 mark for identifying the maximum exponent value in this system is \(+7\) (binary `0111`).

(a) A Virtual Machine relies on software called a hypervisor (or Virtual Machine Monitor, VMM). The hypervisor sits between the host hardware and the guest operating system. It emulates a physical hardware environment (including virtual CPU, memory, storage, and network interfaces). The guest operating system interacts with this virtualized hardware as if it were physical, while the hypervisor translates these instructions and manages the actual physical resources.

(b) Two disadvantages:
1. Performance Overhead: Because instructions must be translated/managed by the hypervisor layer before executing on physical hardware, there is a loss of execution speed compared to running bare-metal.
2. Resource Consumption: Running multiple operating systems simultaneously requires significant RAM, CPU, and storage, which can starve the host system or other virtual machines of resources.

**Part (a) [3 marks]**
- 1 mark for mentioning the hypervisor / Virtual Machine Monitor (VMM).
- 1 mark for explaining that the hypervisor emulates hardware / creates virtual hardware environment.
- 1 mark for explaining that the guest OS runs on top of this emulation, translating guest calls to host hardware calls.

**Part (b) [4 marks]**
- 1 mark for naming/identifying a first disadvantage (e.g., performance overhead / slower execution).
- 1 mark for explaining the first disadvantage (e.g., due to hypervisor translating instructions / emulation overhead).
- 1 mark for naming/identifying a second disadvantage (e.g., heavy resource consumption).
- 1 mark for explaining the second disadvantage (e.g., requires splitting RAM and CPU capacity between host and guest OS).

(a) (i) `XY3$` is VALID.
- `XY` is a valid `` because `` can recursively expand to ` `, which expands to ` `, matching `X` and `Y`.
- `3$` is a valid `` because it matches the base rule ` `, where `3` is a `` and `$` is a ``.
- Therefore, ` ` matches `XY` and `3$`.

(ii) `Z4#5` is INVALID.
- While `Z` is a valid `` (defined as a ``), the sequence `4#5` is not a valid ``.
- The base case for `` is ` `, and the recursive case is ` `. In both cases, the terminal character on the right must be a ``.
- Since `5` is a `` and not a ``, `4#5` cannot be parsed as a ``.

(b) Purpose of recursion:
- Recursion allows the BNF rules to define sequences of arbitrary/indefinite length using a finite set of rules.
- In the rule ` ::= | `, the recursive reference to `` allows any number of digits to be chained together before the final symbol. This allows a suffix with 1, 2, 3, or more digits (e.g., `3$`, `53$`, `153$`, etc.) to be valid, ending with exactly one symbol.

**Part (a)(i) [2 marks]**
- 1 mark for stating it is valid.
- 1 mark for explaining that `XY` matches the recursive `` rule and `3$` matches ` `.

**Part (a)(ii) [2 marks]**
- 1 mark for stating it is invalid.
- 1 mark for explaining that a `` must end with a ``, but `Z4#5` ends with `5` (a digit), violating the rules.

**Part (b) [3 marks]**
- 1 mark for stating that recursion allows defining sequences of infinite / arbitrary / indefinite length.
- 1 mark for explaining that the recursive part ` ` allows adding another digit to the left of an existing suffix.
- 1 mark for explaining that the base case ` ` terminates the recursion with a single symbol at the end.

(a) Three items in the packet header:
1. Source IP address (identifies the sender).
2. Destination IP address (identifies the intended recipient, used for routing).
3. Packet sequence number / ID (used by the destination to reassemble the packets in the correct order).

(b) Role of a router:
- The router acts as a node connecting different networks together.
- When a packet arrives, the router inspects the packet header to extract the destination IP address.
- It references its internal routing table, which contains paths and metrics for different network segments.
- It determines the most efficient path (next hop) for the packet to take.
- It then forwards the packet to the next router or destination host on that path.

**Part (a) [3 marks]**
- 1 mark each for any of the following (max 3):
- Source IP address
- Destination IP address
- Packet sequence number / Packet ID
- Time to Live (TTL)
- Protocol type

**Part (b) [4 marks]**
- 1 mark for stating that a router connects different networks together.
- 1 mark for stating that it reads/extracts the destination IP address from the packet header.
- 1 mark for mentioning the use of a routing table to look up the path/interface.
- 1 mark for explaining that it forwards the packet to the next node/hop along the most efficient route.

(a) Two tasks during lexical analysis:
1. Tokenization: The stream of characters in the source code is grouped into meaningful sequences called lexemes, which are then converted into tokens (such as keywords, operators, identifiers, and literals).
2. Removal of unnecessary elements: Elements that do not affect the program's execution, such as comments and whitespace (spaces, tabs, newlines), are stripped out of the source code.

(b) Two items of information stored in the symbol table:
1. Identifier Name (e.g., the variable name or function name).
2. Data Type (e.g., Integer, Real, String) to ensure type checking in later stages of compilation (such as semantic analysis).

**Part (a) [4 marks]**
- 1 mark for identifying Task 1 (e.g., Tokenization / grouping lexemes into tokens).
- 1 mark for explaining Task 1 (e.g., replacing source keywords/operators with fixed-size token values).
- 1 mark for identifying Task 2 (e.g., Removal of comments and whitespace).
- 1 mark for explaining Task 2 (e.g., to reduce the size of the stream and simplify syntax analysis).

**Part (b) [3 marks]**
- 1 mark for stating that the symbol table contains the identifier's name.
- 1 mark for each of the following (max 2):
- Data type (e.g., Integer, Boolean)
- Scope (e.g., local, global)
- Object type / Category (e.g., variable, constant, procedure, class)
- Memory address / allocation size

(a) Purpose of the activation function:
- It receives the weighted sum of inputs (plus a bias) and decides whether, and to what extent, the neuron should 'fire' (be activated).
- Crucially, it introduces non-linearity into the network. Without non-linear activation functions, the entire neural network would behave like a single-layer linear regression model, regardless of how many hidden layers it has, making it unable to learn complex non-linear patterns.

(b) Backpropagation process:
- During training, input data is passed forward through the network (forward propagation) to generate an output.
- The difference between this output and the actual target value is calculated using a loss function to determine the error.
- This error is then propagated backward from the output layer through the hidden layers.
- The algorithm calculates the gradient of the loss function with respect to each weight using the chain rule of calculus.
- These gradients are used by an optimization algorithm (like gradient descent) to adjust the weights and biases in order to minimize the error in subsequent predictions.

**Part (a) [3 marks]**
- 1 mark for stating that it determines the output of a neuron based on its weighted sum of inputs and bias.
- 1 mark for stating that it introduces non-linearity into the network.
- 1 mark for explaining that non-linearity allows the network to learn complex, non-linear relationships/patterns in data.

**Part (b) [4 marks]**
- 1 mark for stating that the error is calculated at the output layer (difference between predicted and target output).
- 1 mark for stating that this error is propagated backwards through the network layers.
- 1 mark for explaining that the gradient of the error with respect to each weight is calculated.
- 1 mark for explaining that the weights/biases are adjusted (using an optimization method like gradient descent) to reduce the error.

(a) Creating and verifying a digital signature:
Creation (Sender's side):
1. The sender runs the document through a cryptographic hash function to produce a unique, fixed-size message digest (hash).
2. The sender encrypts this hash using their own private key. This encrypted hash is the digital signature.
3. The digital signature is appended to the document and sent to the recipient.

Verification (Recipient's side):
4. The recipient decrypts the digital signature using the sender's public key to recover the original hash.
5. The recipient applies the same cryptographic hash function to the received document to generate a new hash.
6. The recipient compares the decrypted hash with the newly generated hash. If they match, the signature is valid, confirming integrity and authenticity.

(b) Confidentiality:
- A digital signature only signs a hash of the document; the actual document is sent in plaintext (or unencrypted form) along with the signature, meaning anyone can read it.
- To achieve confidentiality, the entire document (and its signature) must be encrypted using the recipient's public key (so that only the recipient can decrypt it using their private key).

**Part (a) [5 marks]**
- 1 mark for stating that a hash/digest of the document is generated first.
- 1 mark for stating that the hash is encrypted using the sender's private key to form the digital signature.
- 1 mark for stating that the recipient decrypts the signature using the sender's public key to get the original hash.
- 1 mark for stating that the recipient hashes the received document again using the same function.
- 1 mark for explaining that if the decrypted hash and the new hash match, it proves authenticity and integrity (no tampering).

**Part (b) [2 marks]**
- 1 mark for stating that the document itself is still sent in plaintext / is not encrypted by the signature process.
- 1 mark for explaining that confidentiality is achieved by encrypting the document using the recipient's public key.

(a) (i) Outputs:
`X = sarah`
`X = tom`

(ii) Output:
`true` (or `yes` depending on the Prolog environment).

(b) Resolution process:
- The interpreter first attempts to satisfy the query using the first rule: `ancestor(helen, emily) :- parent(helen, emily).` It searches the database for `parent(helen, emily)` but cannot find it, so this fails.
- It then backtracks and tries the second (recursive) rule: `ancestor(helen, emily) :- parent(helen, Z), ancestor(Z, emily).`
- It searches the database for `parent(helen, Z)`. It finds `parent(helen, jack)` and binds `Z = jack`.
- Now, it recursively evaluates the subgoal `ancestor(jack, emily).`
- For `ancestor(jack, emily)`, it first tries the base rule: `parent(jack, emily)`, which fails.
- It then tries the recursive rule for this subgoal: `parent(jack, Z1), ancestor(Z1, emily).`
- It finds `parent(jack, sarah)` (binding `Z1 = sarah`) and evaluates `ancestor(sarah, emily).`
- For `ancestor(sarah, emily)`, it tries the base rule: `parent(sarah, emily)`. This is found directly in the database, returning `true`.
- Since all subgoals are satisfied, the query returns `true`.

**Part (a) [4 marks]**
- **(i)** 2 marks for both correct values of `X` (`sarah` and `tom`). Award 1 mark if only one is listed.
- **(ii)** 2 marks for `true` (or `yes` / confirmation of success).

**Part (b) [3 marks]**
- 1 mark for explaining that the interpreter first tries the base rule `parent(helen, emily)` which fails.
- 1 mark for explaining that it then uses the recursive rule, identifying `jack` as the intermediate node `Z` (since `parent(helen, jack)` is true) and making a recursive call `ancestor(jack, emily)`.
- 1 mark for explaining that it recursively repeats this process (finding `sarah` as the next step) until the base case `parent(sarah, emily)` is matched, which succeeds.

Part (a): 1. Write the absolute value 3.75 in binary: \(11.11_{2}\). 2. Write as positive with a leading zero: \(011.1100_{2}\). 3. Take the two's complement for the negative value \(-3.75\): Invert the bits to get \(100.0011\), then add 1 to get \(100.0100_{2}\). 4. To normalize, negative numbers must start with '10'. Move the binary point to get \(1.000100\) (7-bit mantissa: 1000100). 5. The binary point was shifted 2 places to the left, so the exponent is \(+2\). 6. Convert exponent \(+2\) to 5-bit two's complement: 00010. Final Answer: Mantissa = 1000100, Exponent = 00010. Part (b): Increasing the mantissa size from 7 to 8 bits increases the precision (accuracy) of the represented numbers. Decreasing the exponent size from 5 to 4 bits decreases the range of the numbers that can be represented. Part (c): Underflow occurs when a calculated value is too close to zero (too small in magnitude) to be represented with the minimum positive or negative limit of the floating-point format.

Part (a) [4 marks total]: 1 mark for showing binary conversion of 3.75 (e.g. 11.11). 1 mark for correct two's complement of -3.75 (100.0100). 1 mark for correct normalization (Mantissa: 1000100). 1 mark for correct exponent representation (+2 as 00010). Part (b) [2 marks total]: 1 mark for stating precision increases. 1 mark for stating range decreases. Part (c) [1 mark total]: 1 mark for explaining underflow (absolute value of number is too small/close to zero to be represented).

Part (a): During syntax analysis, the compiler accesses the symbol table to perform scope checking (verifying that variables have been declared in the appropriate scope before use) and type checking (verifying that operators are applied to compatible data types). Part (b)(i): X Y Z * + W / translates as follows: Y Z * becomes \((Y \times Z)\). X (Y * Z) + becomes \((X + (Y \times Z))\). (X + (Y * Z)) W / becomes \((X + (Y \times Z)) / W\). Part (b)(ii): Evaluation trace: 1. Push X (8). Stack: [8]. 2. Push Y (3). Stack: [8, 3]. 3. Push Z (4). Stack: [8, 3, 4]. 4. Operator '*': Pop 4 and 3, compute \(3 \times 4 = 12\). Push 12. Stack: [8, 12]. 5. Operator '+': Pop 12 and 8, compute \(8 + 12 = 20\). Push 20. Stack: [20]. 6. Push W (2). Stack: [20, 2]. 7. Operator '/': Pop 2 and 20, compute \(20 / 2 = 10\). Push 10. Stack: [10]. Final result is 10.

Part (a) [2 marks total]: 1 mark for stating that the symbol table is checked to verify variable declaration/scope. 1 mark for stating it is checked/updated for type verification. Part (b)(i) [2 marks total]: 2 marks for correct infix notation: \((X + (Y \times Z)) / W\). Deduct 1 mark if parentheses are missing or incorrect but operator precedence is correct. Part (b)(ii) [3 marks total]: 1 mark for pushing operands correctly on stack. 1 mark for correct evaluation of multiplication and addition (resulting in 20 on the stack). 1 mark for correct division and final answer (10).

Part (a): During the TLS handshake (establishment phase), asymmetric encryption is used. The client uses the server's public key (from its digital certificate) to authenticate the server and securely exchange/negotiate a symmetric session key. Once the handshake is complete, symmetric encryption is used for the actual session (operation phase) because symmetric encryption is computationally faster and highly efficient for encrypting large volumes of transmitted data. Part (b): A digital certificate contains: 1. The owner's public key. 2. The owner's name/organization identity. 3. The digital signature of the Certificate Authority (CA) that issued the certificate.

Part (a) [4 marks total]: 1 mark for stating asymmetric encryption is used during the handshake/establishment phase. 1 mark for explaining asymmetric encryption is used to authenticate the server / securely exchange session keys. 1 mark for stating symmetric encryption is used for the data transfer/operation phase. 1 mark for explaining that symmetric encryption is used because it is faster / computationally less intensive than asymmetric encryption. Part (b) [3 marks total]: 1 mark per valid item of data identified (max 3), such as: Subject/Owner identity, Subject's public key, Issuer/CA name, Digital signature of CA, Serial number, Validity dates.

```python
# Class definition for Package
class Package:
def __init__(self, package_id, weight, destination):
self.__PackageID = package_id
self.__Weight = float(weight)
self.__Destination = destination
self.__Status = "Pending"

def GetPackageID(self):
return self.__PackageID

def GetWeight(self):
return self.__Weight

def GetDestination(self):
return self.__Destination

def GetStatus(self):
return self.__Status

def SetStatus(self, status):
self.__Status = status

def CalculateCost(self):
return self.__Weight * 2.50

# Class definition for ExpressPackage
class ExpressPackage(Package):
def __init__(self, package_id, weight, destination, rapid_delivery, flight_number):
super().__init__(package_id, weight, destination)
self.__RapidDelivery = rapid_delivery
self.__FlightNumber = flight_number

def GetRapidDelivery(self):
return self.__RapidDelivery

def GetFlightNumber(self):
return self.__FlightNumber

def CalculateCost(self):
standard_cost = super().CalculateCost()
if self.__RapidDelivery:
return (standard_cost * 1.5) + 10.00
else:
return standard_cost * 1.20

# Global Array to hold 10 elements
PackageArray = [None] * 10

def ReadData():
global PackageArray
try:
file = open("packages.txt", "r")
for i in range(10):
package_type = file.readline().strip()
pkg_id = file.readline().strip()
weight = float(file.readline().strip())
destination = file.readline().strip()

if package_type == "EXPRESS":
rapid_delivery_str = file.readline().strip()
rapid_delivery = (rapid_delivery_str.upper() == "TRUE")
flight_number = file.readline().strip()
PackageArray[i] = ExpressPackage(pkg_id, weight, destination, rapid_delivery, flight_number)
else:
PackageArray[i] = Package(pkg_id, weight, destination)
file.close()
except IOError:
print("File error: Could not open packages.txt")

def FindHeavyPackages(MaxWeight):
global PackageArray
count = 0
for pkg in PackageArray:
if pkg is not None:
if pkg.GetWeight() > MaxWeight:
print(f"ID: {pkg.GetPackageID()} | Destination: {pkg.GetDestination()}")
count += 1
return count

# Main execution block
if __name__ == "__main__":
# Example of creating a sample file for testing
with open("packages.txt", "w") as f:
test_data = (
"STANDARD
PKG001
12.5
New York
"
"EXPRESS
PKG002
20.0
London
TRUE
BA178
"
"STANDARD
PKG003
8.2
Tokyo
"
"EXPRESS
PKG004
16.4
Paris
FALSE
AF015
"
"STANDARD
PKG005
22.1
Sydney
"
"STANDARD
PKG006
5.0
Berlin
"
"EXPRESS
PKG007
14.8
Rome
TRUE
AZ201
"
"EXPRESS
PKG008
18.5
Cairo
FALSE
MS779
"
"STANDARD
PKG009
9.3
Toronto
"
"STANDARD
PKG010
11.2
Mumbai
"
)
f.write(test_data)

ReadData()
heavy_count = FindHeavyPackages(15.5)
print(f"Total heavy packages found: {heavy_count}")
```

- **Base Class `Package` Implementation (6 Marks)**:
- 1 mark: Defining base class with 4 private attributes initialized appropriately.
- 1 mark: Constructor sets PackageID, Weight, and Destination.
- 1 mark: Standard public getter methods for private attributes.
- 1 mark: Public method `SetStatus()` correctly updates the `Status` attribute.
- 2 marks: Method `CalculateCost()` correctly calculates and returns Weight * 2.50.

- **Subclass `ExpressPackage` Implementation (6 Marks)**:
- 1 mark: Correct inheritance syntax from `Package`.
- 1 mark: Class constructor calls the superclass constructor with super class attributes.
- 1 mark: Class constructor sets two additional subclass private attributes.
- 1 mark: Public getters for additional attributes.
- 2 marks: Overridden `CalculateCost()` calls superclass method and applies correct logical modification based on `RapidDelivery` boolean.

- **`ReadData()` Procedure (7 Marks)**:
- 1 mark: Attempt to open the correct text file (`packages.txt`) with try-except or equivalent handling.
- 1 mark: Correctly loops through 10 iterations to populate 10 objects.
- 1 mark: Reads lines and strips whitespace or newlines correctly.
- 2 marks: Evaluates `package_type` correctly to separate logic for standard and express packages.
- 1 mark: Instantiates `Package` and `ExpressPackage` with correct arguments retrieved from file.
- 1 mark: Stores instantiated object into the correct index of global `PackageArray`.

- **Filtering and Main Program Integration (6 Marks)**:
- 1 mark: Declaring global `PackageArray` of size 10.
- 2 marks: Function `FindHeavyPackages()` loops through the array, safely handling potential null elements, and correctly compares weight strictly greater than `MaxWeight`.
- 1 mark: Prints correct information (ID and Destination) inside the search function.
- 1 mark: Returns the correct count of items found.
- 1 mark: Main program calls `ReadData()`, calls `FindHeavyPackages(15.5)` and prints final output.

```python
class TreeNode:
def __init__(self, data=-1):
self.Data = data
self.LeftPointer = -1
self.RightPointer = -1

# Global Tree structure and pointers
Tree = [TreeNode() for _ in range(15)]
RootPointer = -1
FreePointer = 0

def InitializeTree():
global Tree, RootPointer, FreePointer
RootPointer = -1
FreePointer = 0
for i in range(14):
Tree[i].Data = -1
Tree[i].LeftPointer = i + 1
Tree[i].RightPointer = -1
Tree[14].Data = -1
Tree[14].LeftPointer = -1
Tree[14].RightPointer = -1

def InsertNode(NewData):
global Tree, RootPointer, FreePointer

if FreePointer == -1:
print("Error: Tree is full. Insertion failed.")
return

# Get index of the next free node
newNodeIndex = FreePointer
# Update FreePointer to point to the next node in the free list
FreePointer = Tree[FreePointer].LeftPointer

# Set up the new node
Tree[newNodeIndex].Data = NewData
Tree[newNodeIndex].LeftPointer = -1
Tree[newNodeIndex].RightPointer = -1

# If the tree is empty
if RootPointer == -1:
RootPointer = newNodeIndex
else:
currentNode = RootPointer
placed = False
while not placed:
if NewData < Tree[currentNode].Data:
# Go left
if Tree[currentNode].LeftPointer == -1:
Tree[currentNode].LeftPointer = newNodeIndex
placed = True
else:
currentNode = Tree[currentNode].LeftPointer
else:
# Go right
if Tree[currentNode].RightPointer == -1:
Tree[currentNode].RightPointer = newNodeIndex
placed = True
else:
currentNode = Tree[currentNode].RightPointer

def InOrder(NodePointer):
global Tree
if NodePointer != -1:
InOrder(Tree[NodePointer].LeftPointer)
print(Tree[NodePointer].Data)
InOrder(Tree[NodePointer].RightPointer)

# Main Program Execution
if __name__ == "__main__":
InitializeTree()

numbers_to_insert = [50, 30, 70, 20, 40, 60, 80]
print("Inserting numbers:", numbers_to_insert)
for num in numbers_to_insert:
InsertNode(num)

print("
In-Order Traversal of Binary Search Tree:")
InOrder(RootPointer)
```

- **`TreeNode` Class and Globals Definition (5 Marks)**:
- 1 mark: Define class `TreeNode` with standard default or parametrized constructor.
- 1 mark: Attribute `Data` correctly declared/typed.
- 1 mark: Attributes `LeftPointer` and `RightPointer` correctly initialized to -1.
- 2 marks: Global variables `Tree` initialized as array of 15 `TreeNode` items, along with `RootPointer` and `FreePointer` as integers.

- **`InitializeTree()` Procedure (5 Marks)**:
- 1 mark: Iterates through the entire array size of 15 elements.
- 1 mark: Resets node data values of all elements to -1.
- 2 marks: Correctly implements the free list link structure (index `i` points to `i+1`, except the final item which has `-1`).
- 1 mark: Correctly resets `RootPointer` to -1 and `FreePointer` to 0.

- **`InsertNode()` Implementation (8 Marks)**:
- 1 mark: Correct check for Tree Full condition (`FreePointer == -1`) and outputs error message.
- 1 mark: Allocates new node index using current `FreePointer`.
- 1 mark: Updates global `FreePointer` to the next element on the free list.
- 1 mark: Initializes the target node properties (Data set to input value, pointers reset to -1).
- 1 mark: Correctly handles case where `RootPointer == -1` by setting it to the new node index.
- 2 marks: Implements while-loop traversal of tree nodes using comparison (left vs right paths).
- 1 mark: Correctly sets the left or right pointer of parent node to the new node index when empty slot is found.

- **Traversal and Main Execution (7 Marks)**:
- 1 mark: Recursive function `InOrder()` has correct base case condition (`NodePointer != -1`).
- 2 marks: Navigates left child first recursively, then processes/prints node, then navigates right child recursively.
- 1 mark: Loops insertion of specified test integers (50, 30, 70, 20, 40, 60, 80).
- 1 mark: Calls `InOrder(RootPointer)` from main block to display outputs.
- 2 marks: Correct ascending sequence is produced and verified in execution (20, 30, 40, 50, 60, 70, 80).

```python
class SearchStack:
def __init__(self):
self.__StackArray = [0] * 10
self.__Top = -1

def Push(self, value):
if self.__Top < 9:
self.__Top += 1
self.__StackArray[self.__Top] = value
return True
else:
return False

def Pop(self):
if self.__Top >= 0:
value = self.__StackArray[self.__Top]
self.__Top -= 1
return value
else:
return -1

def IsEmpty(self):
return self.__Top == -1

def RecursiveBinarySearch(Array, SearchValue, Low, High, Stack):
if Low > High:
return -1

mid = (Low + High) // 2
Stack.Push(mid)

if Array[mid] == SearchValue:
return mid
elif Array[mid] > SearchValue:
return RecursiveBinarySearch(Array, SearchValue, Low, mid - 1, Stack)
else:
return RecursiveBinarySearch(Array, SearchValue, mid + 1, High, Stack)

# Main Program
if __name__ == "__main__":
# Test data: sorted list of 10 items
data_list = [12, 18, 23, 34, 45, 56, 67, 78, 89, 90]

# Instantiate search stack
path_stack = SearchStack()

try:
search_target = int(input("Enter a number to search for: "))
except ValueError:
print("Invalid input. Defaulting search target to 78.")
search_target = 78

# Perform recursive search
result_index = RecursiveBinarySearch(data_list, search_target, 0, len(data_list) - 1, path_stack)

if result_index != -1:
print(f"Target {search_target} found at array index: {result_index}")
else:
print(f"Target {search_target} was not found in the array.")

print("Path of indexes visited (popped from stack): ")
while not path_stack.IsEmpty():
idx = path_stack.Pop()
print(idx)
```

- **`SearchStack` Class Implementation (8 Marks)**:
- 1 mark: Declares private attributes: `StackArray` (initialized to size 10) and integer `Top`.
- 1 mark: Constructor initializes `Top` pointer to -1.
- 1 mark: Method `Push()` checks if stack is full (compares `Top < 9` or equivalent index range).
- 1 mark: `Push()` updates `Top` index pointer and assigns value.
- 1 mark: `Push()` returns boolean success status (`True`/`False`).
- 1 mark: Method `Pop()` checks for empty condition (`Top >= 0` or equivalent).
- 1 mark: `Pop()` retrieves top item, decrements pointer, and returns element correctly (or `-1` on underflow).
- 1 mark: Method `IsEmpty()` correctly evaluates and returns True/False.

- **Recursive Binary Search (10 Marks)**:
- 1 mark: Correct function signature with standard array, search key, lower/upper boundaries, and stack object parameters.
- 1 mark: Correct calculation of midpoint index `Mid = (Low + High) // 2`.
- 1 mark: Correctly pushes the calculated midpoint `Mid` onto the stack object inside the function.
- 2 marks: Base case checks `Low > High` and returns `-1` (unsuccessful search exit).
- 1 mark: Successful search comparison checks `Array[Mid] == SearchValue` and returns index `Mid`.
- 2 marks: Correct recursive step down the left subtree (passes `Low, mid - 1` and same stack).
- 2 marks: Correct recursive step down the right subtree (passes `mid + 1, High` and same stack).

- **Integration and Outputs (7 Marks)**:
- 1 mark: Sorted test array is declared and initialized exactly as specified.
- 1 mark: Search stack object is correctly instantiated.
- 1 mark: Inputs are read from the keyboard or standard test runner.
- 1 mark: Correct initialization arguments called on the search (`Low = 0, High = 9`).
- 1 mark: Prints the resulting index from binary search or not found status.
- 1 mark: Uses a loop check `IsEmpty()` on the stack to extract items.
- 1 mark: Pops and displays stack values correctly (reflecting the index path).