An original Thinka practice paper modelled on the structure and difficulty of the Nov 2023 (V3) Cambridge International A Level Computer Science (9618) paper. Not affiliated with or reproduced from Cambridge.
卷一 (AS Theory Fundamentals)
Answer all questions. Calculators must not be used.
9 題目 · 74.97 分
題目 1 · Short Answer
8.33 分
A stereo sound recording has a duration of 20 seconds. It is sampled at a frequency of 44.1 kHz (44,100 Hz) using a sample resolution of 16 bits. Calculate the final file size of this uncompressed audio recording in Megabytes (MB). Use 1 MB = 1,000,000 bytes. Show your working.
查看答案詳解收起答案詳解
解題
Step 1: Calculate the total number of samples. 44,100 samples per second multiplied by 20 seconds equals 882,000 samples. Step 2: Since it is a stereo recording, there are 2 channels. Total samples for both channels is 882,000 multiplied by 2, which equals 1,764,000 samples. Step 3: Multiply by the sample resolution to find total bits. 1,764,000 samples multiplied by 16 bits per sample equals 28,224,000 bits. Step 4: Convert bits to bytes. 28,224,000 bits divided by 8 equals 3,528,000 bytes. Step 5: Convert bytes to Megabytes (MB). 3,528,000 bytes divided by 1,000,000 equals 3.528 MB.
評分準則
1 mark for calculating the total samples for mono (44,100 * 20 = 882,000). 1 mark for multiplying by 2 to account for stereo. 1 mark for multiplying by 16 bits to get 28,224,000 bits. 1 mark for dividing by 8 to convert to bytes (3,528,000 bytes). 1 mark for dividing by 1,000,000 to convert to Megabytes. Correct final answer of 3.528 MB (with or without working) earns full marks (8.33 marks).
題目 2 · Short Answer
8.33 分
Describe the function of a router in a computer network and explain how it utilizes a routing table to forward packets.
查看答案詳解收起答案詳解
解題
A router is a network device that forwards data packets between different networks. Its primary roles include: 1. Acting as a gateway between local and external networks. 2. Inspecting the destination IP address of each incoming packet. 3. Querying its routing table, which is a database containing paths, network destinations, and metrics (such as hop counts or link speeds). 4. Identifying the most efficient next hop or path for the packet based on the table. 5. Forwarding the packet to the next router or destination node. It dynamically updates the routing table using routing protocols to adapt to network topology changes.
評分準則
Up to 4 marks for router functions: 1 mark for forwarding packets between networks; 1 mark for acting as a gateway; 1 mark for inspecting the destination IP address; 1 mark for converting between different network protocols/architectures. Up to 4.33 marks for routing table role: 1 mark for storing network destinations; 1 mark for storing metrics/costs/hop counts; 1 mark for matching destination IP to find the next hop; 1.33 marks for dynamic updates via routing protocols.
題目 3 · Short Answer
8.33 分
An automated ventilation system in a warehouse uses sensors and actuators controlled by a microprocessor to maintain a stable internal temperature. Explain the roles of the temperature sensor, the actuator, and the Analog-to-Digital Converter (ADC) in this control system.
查看答案詳解收起答案詳解
解題
1. Sensor: The temperature sensor continuously monitors the warehouse physical environment and outputs analog readings representing the current temperature. 2. Analog-to-Digital Converter (ADC): Microprocessors can only process discrete digital signals. The ADC converts the continuous analog signal from the sensor into digital data that the microprocessor can read. 3. Microprocessor: The processor compares the incoming digital temperature values against preprogrammed threshold values. 4. Actuator: An actuator (such as an electric motor or solenoid) receives digital command signals from the microprocessor (sometimes converted back via a DAC if necessary) and performs the physical action of opening or closing the ventilation windows to regulate the temperature.
評分準則
2 marks for Sensor: 1 mark for measuring physical temperature, 1 mark for outputting continuous analog signals. 2 marks for ADC: 1 mark for converting analog to digital, 1 mark for explaining that the processor can only understand digital data. 2.33 marks for Microprocessor: 1 mark for comparing input data to preset thresholds, 1.33 marks for sending control signals to actuators. 2 marks for Actuator: 1 mark for receiving control signals, 1 mark for performing physical action (e.g. operating a motor/vent).
題目 4 · Short Answer
8.33 分
Describe step-by-step how the Program Counter (PC), Memory Address Register (MAR), and Memory Data Register (MDR) are used during the FETCH stage of the instruction cycle.
查看答案詳解收起答案詳解
解題
During the fetch stage: 1. The Program Counter (PC) holds the memory address of the next instruction to be fetched. 2. This address is copied from the PC to the Memory Address Register (MAR) via the internal bus. 3. The PC is immediately incremented by one to point to the address of the next sequential instruction. 4. A read signal is sent along the control bus to main memory (RAM). 5. The instruction stored at the address currently in the MAR is retrieved from RAM and sent along the data bus. 6. This instruction is loaded into the Memory Data Register (MDR). 7. Finally, the instruction is copied from the MDR to the Current Instruction Register (CIR) for decoding.
評分準則
1 mark for stating PC holds the address of the next instruction. 1 mark for copying address from PC to MAR. 1 mark for incrementing the PC. 1.33 marks for sending the address from MAR to main memory via the address bus. 1 mark for control unit sending a read signal. 1 mark for retrieving instruction via the data bus. 1 mark for loading the retrieved instruction into the MDR. 1 mark for copying instruction from MDR to CIR.
題目 5 · Short Answer
8.33 分
Compare a compiler and an interpreter. Explain three key differences between them in terms of translation method, execution speed, and error reporting.
查看答案詳解收起答案詳解
解題
1. Translation Method: A compiler translates the entire source code of a high-level language program into an independent executable machine code file (object code) prior to execution. Any syntax errors will prevent compilation. An interpreter translates and executes the source code line-by-line in real time during execution. 2. Execution Speed: Compiled code runs much faster because translation is completed beforehand. Interpreted code runs more slowly as translation must take place on-the-fly during runtime. 3. Error Reporting: A compiler scans the entire program and lists all detected syntax errors at the end of compilation. An interpreter halts execution immediately upon encountering the first syntax error, making debugging easier but preventing further execution until that error is fixed.
評分準則
Up to 6 marks for the three direct comparisons (2 marks per category): Translation: compiler produces standalone object code / interpreter does not produce object code. Speed: compiled runs faster / interpreted runs slower. Error reporting: compiler lists all errors at the end / interpreter stops at first error. 2.33 marks for overall technical accuracy, clarity, and depth of explanation.
題目 6 · Short Answer
8.33 分
In a relational database, explain the concepts of a primary key, a foreign key, and referential integrity. Describe how they work together to ensure data consistency.
查看答案詳解收起答案詳解
解題
1. Primary Key: A unique identifier for each record in a table. It cannot contain duplicate values or null values. 2. Foreign Key: A column in a table that references the primary key of another table. It is used to establish and enforce a link between the data in the two tables. 3. Referential Integrity: A set of rules that ensures relationships between tables remain consistent. It dictates that any foreign key value in a table must have a corresponding, matching primary key value in the related table. This prevents users from adding invalid records or deleting parent records that are still referenced by child records, thereby preventing orphaned records.
評分準則
2 marks for Primary Key definition (uniqueness, no nulls). 2 marks for Foreign Key definition (referencing primary key of another table to link them). 2.33 marks for Referential Integrity definition (ensuring foreign keys match valid primary keys). 2 marks for explaining database consistency mechanisms (preventing orphaned records, blocking invalid deletions/updates of primary keys).
題目 7 · Short Answer
8.33 分
Identify the difference between data validation and data verification. Give one distinct example of a validation check and one distinct example of a verification check in the context of user input.
查看答案詳解收起答案詳解
解題
1. Data Validation: This is an automatic check performed by the computer system to verify that the entered data is reasonable, sensible, and obeys a set of predefined rules. Example: A length check which ensures a PIN code is exactly 4 digits. 2. Data Verification: This is a check designed to ensure that the data entered into the system is identical to the source data and free of transcription errors. Example: Double-entry, where a user is prompted to enter an email address twice to ensure they match exactly, or visual verification, where the user reads over the text on screen to confirm it matches their paper document.
評分準則
2 marks for validation definition (automated, checks against rules/reasonableness). 2 marks for verification definition (ensures accuracy against source / prevents transcription errors). 2 marks for a valid validation check example and explanation (e.g. range check, type check, length check). 2.33 marks for a valid verification check example and explanation (e.g. double entry, visual check).
題目 8 · Short Answer
8.33 分
Describe the differences between Commercial Software, Shareware, and Open Source Software. For each type of software, outline the user rights regarding copying, modification, and payment.
查看答案詳解收起答案詳解
解題
1. Commercial Software: This software is proprietary and requires the user to pay a fee to obtain a license. The source code is closed (not accessible). Users have no legal rights to copy, redistribute, or modify the software. 2. Shareware: This software is distributed free of charge on a trial basis, often with limited features or a time limit. Users are allowed to copy and distribute the trial version. However, payment is required after the trial period to unlock full features. The source code remains closed, and users cannot modify it. 3. Open Source Software: The source code is publicly accessible. Users are free to view, modify, and improve the code. They can copy, redistribute, and use the software, often for free, provided they follow the open-source licensing agreement.
評分準則
2.77 marks for Commercial Software (payment required, closed source, no modification/copying rights). 2.77 marks for Shareware (free trial, payment needed later, copy/redistribution allowed for trial, closed source/no modification). 2.79 marks for Open Source (source code open, free copying/modification/redistribution permitted).
題目 9 · Short Answer & Recall
8.33 分
During the execution of a program, the processor continuously performs the Fetch-Execute cycle.
(a) Explain the purpose of the following two registers during the Fetch-Execute cycle: (i) Program Counter (PC) (ii) Memory Data Register (MDR)
(b) The Fetch stage of the cycle can be represented using Register Transfer Notation (RTN). Write the RTN for the sequential steps of the Fetch stage, starting from copying the address in the PC up to loading the instruction into the Current Instruction Register (CIR).
查看答案詳解收起答案詳解
解題
Part (a): (i) Program Counter (PC): Holds the memory address of the next instruction that is to be fetched and executed. (ii) Memory Data Register (MDR): Acts as a temporary buffer that holds the instruction or data currently read from or written to the memory address held in the MAR.
Part (b): 1. \(MAR \leftarrow [PC]\) : The address in the PC is copied to the MAR. 2. \(PC \leftarrow [PC] + 1\) : The PC is incremented to point to the next instruction. 3. \(MDR \leftarrow [[MAR]]\) : The instruction stored at the address in the MAR is loaded into the MDR. 4. \(CIR \leftarrow [MDR]\) : The instruction in the MDR is copied into the CIR.
評分準則
Part (a) [Max 4 marks]: - 1 mark: PC holds an address. - 1 mark: PC address is for the *next* instruction to be fetched/executed. - 1 mark: MDR holds data/instruction read from memory or to be written to memory. - 1 mark: MDR acts as a buffer/intermediate register between memory and CPU.
Part (b) [Max 4 marks]: - 1 mark: \(MAR \leftarrow [PC]\) (accept verbal description if clear, e.g., MAR receives contents of PC) - 1 mark: \(PC \leftarrow [PC] + 1\) (incrementing PC) - 1 mark: \(MDR \leftarrow [[MAR]]\) (copying content from memory address in MAR to MDR) - 1 mark: \(CIR \leftarrow [MDR]\) (copying instruction from MDR to CIR)
卷二 (AS Problem-solving & Programming)
Answer all questions using the standard Cambridge Pseudocode guidelines.
8 題目 · 74.96 分
題目 1 · Pseudocode Algorithms & Flowcharts
9.37 分
A software application requires a standard module to validate employee ID strings. Each employee ID must be exactly 9 characters long and must conform to the following rules: - The first three characters must be uppercase alphabetical letters ('A' to 'Z'). - The fourth character must be a hyphen '-'. - The fifth to ninth characters must be digits ('0' to '9').
Write a pseudocode function ValidateEmployeeID(ID : STRING) RETURNS BOOLEAN that implements this validation process. It should return TRUE if the ID is valid, and FALSE otherwise. You can assume the following standard built-in functions: - LENGTH(s : STRING) RETURNS INTEGER - MID(s : STRING, start : INTEGER, length : INTEGER) RETURNS STRING - ASC(ch : CHAR) RETURNS INTEGER
查看答案詳解收起答案詳解
解題
The function ValidateEmployeeID checks each segment of the input string step-by-step. First, it ensures that the length of the string is exactly 9 characters. If not, it returns FALSE immediately. Second, it loops through the first 3 characters, retrieves their ASCII values, and confirms they fall within the range [65, 90] (representing uppercase 'A' to 'Z'). Third, it verifies that the 4th character is indeed a hyphen. Fourth, it loops through characters 5 to 9, checking that their ASCII values lie within the range [48, 57] (representing digits '0' to '9'). If all conditions are met, the function returns TRUE.
評分準則
Total Marks: 9.37 - 1 Mark: Correct function header with parameter and return type - 2 Marks: Checking string length and returning FALSE if length is not equal to 9 - 2 Marks: Correct loop and ASCII range check (65 to 90) for characters 1 to 3 - 1 Mark: Correct validation of hyphen at index 4 - 2 Marks: Correct loop and ASCII range check (48 to 57) for characters 5 to 9 - 1.37 Marks: Returning TRUE only when all conditions are satisfied and correct ENDFUNCTION structure
題目 2 · Pseudocode Algorithms & Flowcharts
9.37 分
A system designer has produced the following logic description to process an array Temperatures containing 365 real numbers representing daily temperature recordings: 1. Initialize a variable Total to 0.0 and a variable Count to 0. 2. Initialize an index counter to 1. 3. Use a loop to iterate through the array: - If the temperature at the current index is greater than or equal to 30.0, add the temperature to Total and increment Count by 1. - Increment the index counter. 4. After processing all elements, check if Count is greater than 0: - If so, calculate the average temperature of the hot days and store it in AvgTemp. Output \"Average hot temperature: \" followed by AvgTemp. - If not, output \"No hot days recorded\".
Write a pseudocode algorithm that implements this logic. Declare all variables used.
查看答案詳解收起答案詳解
解題
The pseudocode starts by declaring the array and variables with matching data types (REAL for temperature averages and sums, and INTEGER for counters). The program then initializes the running total and counter of hot days. A FOR loop is constructed to iterate from 1 to 365. Inside the loop, an IF statement checks if the temperature is 30.0 or higher. If it is, the temperature is accumulated into Total and Count is incremented. After the loop, another IF statement checks whether Count is positive to prevent a division-by-zero error, calculating the average and printing the outputs accordingly.
評分準則
Total Marks: 9.37 - 2 Marks: Proper declarations for array Temperatures and variables with appropriate types - 2 Marks: Correct loop initialization and bounds (1 to 365) - 2 Marks: Correct conditional statement for checking temperatures >= 30.0 - 2 Marks: Correctly updating total sum and count within the loop - 1.37 Marks: Handling selection logic for when Count > 0, calculating average correctly, and outputting correct messages
題目 3 · Pseudocode Algorithms & Flowcharts
9.37 分
Consider the following pseudocode algorithm designed to perform numerical operations on positive integers A and B:
``` CONSTANT MAX_LIMIT = 50 DECLARE A, B, X, Y : INTEGER A <- 13 B <- 4 X <- A Y <- 0 REPEAT IF X >= B THEN X <- X - B Y <- Y + 1 ENDIF UNTIL X < B OR Y >= MAX_LIMIT OUTPUT \"Quotient: \", Y OUTPUT \"Remainder: \", X ```
Perform a dry run of the algorithm, tracing the values of variables X and Y at each iteration. State the final outputs, and describe the mathematical operations this algorithm performs.
查看答案詳解收起答案詳解
解題
At the start, A is 13, B is 4, X is 13, and Y is 0. Inside the REPEAT...UNTIL loop: - Loop 1: X (13) >= B (4) is true, so X becomes 13 - 4 = 9, and Y becomes 1. - Loop 2: X (9) >= B (4) is true, so X becomes 9 - 4 = 5, and Y becomes 2. - Loop 3: X (5) >= B (4) is true, so X becomes 5 - 4 = 1, and Y becomes 3. At the end of Loop 3, the termination condition is checked: X < B (1 < 4) is true, so the loop terminates. The final outputs are Quotient: 3 and Remainder: 1. This illustrates how integer division (DIV) and remainder modulo (MOD) are calculated via subtraction.
評分準則
Total Marks: 9.37 - 3 Marks: Accurate trace table showing states of X and Y for all three iterations - 2 Marks: Correct termination condition evaluation (loop stops when X = 1 and Y = 3) - 2 Marks: Correct identification of final outputs (Quotient = 3, Remainder = 1) - 2.37 Marks: Explaining that the algorithm executes integer division (A DIV B) and finds remainder (A MOD B) by subtracting
題目 4 · Pseudocode Algorithms & Flowcharts
9.37 分
A text file Sales.txt contains sales transaction data. Each line of the file contains a salesman ID (string) and the transaction amount (integer), separated by a comma (e.g., \"S102,450\").
Write a pseudocode algorithm that opens and reads Sales.txt, calculates the total sales amount of all transactions, and counts the number of transactions that exceed 500. After reading all records, the algorithm should output the total sales amount and the count of transactions exceeding 500.
Assume standard built-in functions: - STRING_TO_INT(s : STRING) RETURNS INTEGER - LENGTH(s : STRING) RETURNS INTEGER - MID(s : STRING, start : INTEGER, length : INTEGER) RETURNS STRING And file operations: - OPENFILE FOR READ - READFILE , - CLOSEFILE - EOF() which returns TRUE if the end of the file has been reached.
查看答案詳解收起答案詳解
解題
The algorithm begins by opening the file Sales.txt in READ mode. It then uses a WHILE NOT EOF loop to process each record line by line. To extract the transaction amount, it implements a helper loop that searches for the position of the comma separating the two fields. Once CommaPos is found, MID is utilized to slice the amount portion, which starts at CommaPos + 1 and runs to the end of the string. This substring is converted to an integer and accumulated into TotalSales. If the value exceeds 500, HighSalesCount is incremented. Finally, the file is closed, and the total and count are outputted.
評分準則
Total Marks: 9.37 - 1 Mark: Correctly opening and closing Sales.txt - 2 Marks: Implementing EOF loop correctly (WHILE NOT EOF) - 2 Marks: Logic for finding the comma separator in the text line - 2 Marks: Correctly slicing the amount substring and calling STRING_TO_INT - 2.37 Marks: Accumulating the total sales, maintaining the high sales count, and outputting the computed results
題目 5 · Pseudocode Algorithms & Flowcharts
9.37 分
A program contains a global 1D array Names of size 100 containing string values. Write a pseudocode procedure SortNames that performs an efficient ascending bubble sort on the array Names. Use a boolean flag Swapped to terminate the sorting process early if a pass is completed without any elements being swapped.
查看答案詳解收起答案詳解
解題
The procedure SortNames sorts the global array Names in ascending order. We initialize Limit to 99, since 100 elements require a maximum of 99 comparisons in the first pass. The REPEAT...UNTIL loop is controlled by the Swapped boolean flag and the Limit. In each pass, Swapped is reset to FALSE. The inner loop compares adjacent elements; if the element at index Inner is alphabetically greater than the element at Inner + 1, they are swapped using a temporary variable Temp, and Swapped is updated to TRUE. Limit is decremented by 1 after each pass because the largest elements naturally bubble to the end, optimizing the sort.
評分準則
Total Marks: 9.37 - 2 Marks: Correct procedure definition and local variable declarations - 2 Marks: Outer loop logic (using REPEAT...UNTIL or WHILE) controlled by a Swapped flag - 2 Marks: Inner loop iterating up to Limit to compare adjacent elements - 2 Marks: Correct comparison and swap using a temporary variable - 1.37 Marks: Decrementing Limit after each pass to optimize, and correct ENDPROCEDURE syntax
An array ClassList contains 50 elements of type StudentRecord, pre-sorted in ascending order of StudentID.
Write a pseudocode function BinarySearchStudent(SearchID : STRING) RETURNS INTEGER that performs a binary search on ClassList to look for a record with StudentID matching SearchID. If the student is found, return the index in the array; otherwise, return -1.
查看答案詳解收起答案詳解
解題
A binary search divides the search space in half during each iteration. Low is initialized to 1 and High is initialized to 50. In the loop, the midpoint Mid is calculated using integer division (DIV). The StudentID field of the element at ClassList[Mid] is accessed. If it matches SearchID, Mid is returned. If the ID at Mid is less than SearchID, the search boundaries are shifted by setting Low to Mid + 1. Otherwise, High is set to Mid - 1. If Low exceeds High, the loop terminates and the function returns -1.
評分準則
Total Marks: 9.37 - 2 Marks: Correct function header with parameter and return types - 2 Marks: Correct initialization of Low, High boundaries and correct loop condition (Low <= High) - 2 Marks: Calculation of Mid and correct dot-notation access to Record fields (ClassList[Mid].StudentID) - 2 Marks: Proper conditional branches to update Low and High correctly - 1.37 Marks: Returning Mid when found, -1 when not found, and correct ENDFUNCTION declaration
題目 7 · Pseudocode Algorithms & Flowcharts
9.37 分
Write a pseudocode function CompressString(InputStr : STRING) RETURNS STRING that compresses consecutive duplicate characters in a string of uppercase letters to a format of [count][character] (Run-Length Encoding). For example, if InputStr is \"AAABBC\", the function should return \"3A2B1C\".
The function first determines the length of InputStr. If it is empty, it returns an empty string. Otherwise, it initializes the result string Compressed to empty and Count to 1. A FOR loop iterates from 1 up to StrLen - 1. In each iteration, it compares the CurrentChar with the NextChar. If they are equal, the counter is incremented. If they differ, the algorithm appends the count (converted to a string) and the character to Compressed, then resets Count to 1. After the loop, the final group is appended using the last character. The compressed string is then returned.
評分準則
Total Marks: 9.37 - 2 Marks: Function signature, returns STRING, and handling of empty string input - 2 Marks: Loop from 1 to StrLen - 1 comparing current and next character correctly - 2 Marks: Incrementing count on match, resetting count to 1 and appending when characters change - 2 Marks: Converting counts using NUM_TO_STR and concatenating to form Compressed string - 1.37 Marks: Appending final character group after the loop terminates and returning Compressed
題目 8 · Pseudocode Algorithms & Flowcharts
9.37 分
A 2D array Grid has 10 rows and 10 columns, containing integer values. Write a pseudocode procedure FindMinPosition that searches the array Grid to find the minimum value.
The procedure must find and output: - The minimum value found - The row index and column index of all occurrences of this minimum value
Assume row and column indices start at 1 and end at 10.
查看答案詳解收起答案詳解
解題
The algorithm is designed to find the minimum value and report all coordinates where it occurs. First, MinVal is initialized to the value at Grid[1, 1]. A set of nested FOR loops iterates through all coordinates from (1, 1) to (10, 10). If any element is strictly smaller than MinVal, MinVal is updated. Once the minimum value is determined, the minimum is printed. Then, a second pass of nested loops is performed. Whenever Grid[Row, Col] matches MinVal, its row and column coordinates are printed. This handles cases where the minimum occurs multiple times.
評分準則
Total Marks: 9.37 - 2 Marks: Procedure header, declaration of variables (Row, Col, MinVal) as INTEGER - 2 Marks: Correctly initializing MinVal with the first element of the grid - 2 Marks: Using nested FOR loops to iterate through all 100 array cells to find the minimum - 2 Marks: Using a second set of nested loops to find and print all occurrences of MinVal - 1.37 Marks: Outputting correct row and column values and formatting
Paper 3 (A Level Advanced Theory)
Answer all questions. Show all working for numeric conversions.
An organization is assigned the IPv4 CIDR block 192.168.104.0/22. Work out the following details for this network: 1. The subnet mask in dotted-decimal format. 2. The total number of usable host addresses available in this subnet. 3. Show, using binary AND operations, whether the IP address 192.168.107.254 belongs to this subnet block.
查看答案詳解收起答案詳解
解題
1. A CIDR prefix of /22 means the first 22 bits of the subnet mask are 1s. In binary, this is 11111111.11111111.11111100.00000000. Converting each octet to decimal gives 255.255.252.0. 2. The number of host bits is 32 - 22 = 10 bits. The total number of addresses is 2^10 = 1024. Subtracting 2 for the network and broadcast addresses leaves 1022 usable host addresses. 3. To determine if 192.168.107.254 is in the subnet, perform a bitwise AND between the IP and the mask. IP Octet 3: 107 = 01101011 in binary. Mask Octet 3: 252 = 11111100 in binary. Bitwise AND: 01101011 AND 11111100 = 01101000, which is 104 in decimal. Since the resulting network prefix (192.168.104.0) matches the assigned network address, the IP address 192.168.107.254 belongs to this subnet block.
評分準則
Award marks as follows: - 2 marks for correct subnet mask (255.255.252.0) with working. - 2 marks for correct calculation of usable hosts (1022) showing the subtraction of 2. - 2.25 marks for showing the correct binary AND operation on the third octet and concluding that the IP belongs to the subnet.
Two positive floating-point numbers are represented in a 12-bit two's complement format, with an 8-bit mantissa and a 4-bit exponent. Number X: Mantissa = 0.1010000, Exponent = 0010 Number Y: Mantissa = 0.1100000, Exponent = 0001 Show the step-by-step working to add these two numbers, perform any necessary normalization, and state the final 12-bit binary result (8-bit mantissa followed by 4-bit exponent).
查看答案詳解收起答案詳解
解題
Step 1: Align exponents. The exponent of X is 0010 (2), and Y is 0001 (1). Shift the mantissa of Y right by 1 bit to match the larger exponent (2). Shifted Mantissa Y = 0.0110000. Step 2: Add the mantissas: 0.1010000 (X) + 0.0110000 (Y) = 1.0000000 Step 3: Normalize the result. Adding two positive numbers resulted in a value starting with 1, which represents an overflow in two's complement. Shift the mantissa right by 1 bit and insert the sign bit (0) at the MSB: Normalized Mantissa = 0.1000000. To compensate for the right shift, add 1 to the exponent: 0010 + 0001 = 0011 (3). Step 4: Combine mantissa and exponent: 0.1000000 and 0011 -> 010000000011.
評分準則
Award marks as follows: - 2 marks for correctly aligning the exponents (shifting Y's mantissa to 0.0110000). - 1.5 marks for adding the mantissas to get 1.0000000. - 1.5 marks for correctly identifying overflow, shifting right to 0.1000000, and incrementing the exponent to 0011. - 1.25 marks for the correct final 12-bit binary representation.
A RISC processor uses a 5-stage pipeline: Instruction Fetch (IF), Instruction Decode (ID), Execute (EX), Memory Access (MEM), and Write Back (WB). Consider this assembly code sequence: 1. ADD R1, R2, R3 2. SUB R4, R1, R5 3. AND R6, R7, R8 Assume there is no operand forwarding hardware, and registers can only be read in the clock cycle *after* they are written in the WB stage. Identify the pipeline hazard, state which instructions are affected, and calculate the total number of clock cycles needed to execute this sequence from the start of instruction 1 to the completion of instruction 3.
查看答案詳解收起答案詳解
解題
The hazard is a Data Hazard (specifically Read-After-Write, RAW) on register R1 because Instruction 2 needs R1 as an operand before Instruction 1 writes it back. Without forwarding, Instruction 1 writes R1 during the WB stage (Cycle 5). Instruction 2 can only decode and read R1 in Cycle 6. Pipeline timeline: Cycle 1: I1 (IF) Cycle 2: I1 (ID), I2 (IF) Cycle 3: I1 (EX), I2 (ID - stalled), I3 (IF - stalled) Cycle 4: I1 (MEM), I2 (ID - stalled), I3 (IF - stalled) Cycle 5: I1 (WB), I2 (ID - stalled), I3 (IF - stalled) Cycle 6: I2 (ID), I3 (IF) Cycle 7: I2 (EX), I3 (ID) Cycle 8: I2 (MEM), I3 (EX) Cycle 9: I2 (WB), I3 (MEM) Cycle 10: I3 (WB) Total cycles required is 10.
評分準則
Award marks as follows: - 1.25 marks for identifying the data hazard (RAW on register R1). - 2 marks for showing that the WB stage of Instruction 1 occurs in Cycle 5, delay stalling Instruction 2's ID stage until Cycle 6. - 2 marks for showing that the IF stage of Instruction 3 is stalled along with the ID stage of Instruction 2. - 1 mark for the correct final answer of 10 clock cycles.
Convert the following infix expression to Reverse Polish Notation (RPN): \((A + B) * (C - D / E)\) Then, show the step-by-step state of the evaluation stack when the resulting RPN expression is evaluated using the values: A = 5, B = 3, C = 10, D = 8, E = 2.
查看答案詳解收起答案詳解
解題
Step 1: Convert to RPN. (A + B) becomes: A B + (C - D / E) becomes: C D E / - Multiplying both sub-expressions: A B + C D E / - *
Award marks as follows: - 2.25 marks for correct RPN expression: A B + C D E / - *. - 2 marks for showing correct intermediate stack states for the first addition and subsequent pushes. - 2 marks for correctly evaluating the division, subtraction, and final multiplication to get 48.
Alice wants to send a secure, digitally signed document to Bob to guarantee authenticity and non-repudiation. Describe the step-by-step cryptographic process of how Alice generates the digital signature, how Bob decrypts and verifies the signature, and which keys are used by each party.
查看答案詳解收起答案詳解
解題
1. Alice passes the document through a hashing algorithm to generate a unique, fixed-size message digest (hash value). 2. Alice encrypts this message digest using her private key. This encrypted digest is the digital signature. 3. Alice sends both the original document and the digital signature to Bob. 4. Bob decrypts the digital signature using Alice's public key to retrieve the original message digest. 5. Bob independently hashes the received document using the same hashing algorithm to generate a new message digest. 6. Bob compares the decrypted message digest with his newly generated message digest. If they match, the signature is verified, confirming the document's integrity and authenticity.
評分準則
Award marks as follows: - 1.5 marks for explaining the generation of the message digest using a hashing algorithm. - 1.5 marks for stating Alice encrypts the hash with her private key to produce the digital signature. - 1.5 marks for explaining that Bob decrypts the signature using Alice's public key. - 1.75 marks for explaining the comparison of the decrypted hash with the newly computed hash of the received document.
An A* search algorithm is used to find the shortest path from node A to node E in a directed graph. The edge costs (g-costs) are: A->B = 2, A->C = 4, B->D = 5, C->D = 1, B->E = 10, D->E = 3. The heuristic estimates (h-costs) to goal node E are: A = 7, B = 6, C = 3, D = 2, E = 0. Trace the execution of the algorithm. For each step, show the contents of the Open List with their \(f(n) = g(n) + h(n)\) values, identify the node chosen for expansion, and write the final shortest path and its total cost.
查看答案詳解收起答案詳解
解題
Step 1: Initialize. Open List = {A (f=0+7=7)}, Closed List = {}. Step 2: Remove A from Open List. Expand A. - Successor B: g(B)=2, f(B)=2+6=8. - Successor C: g(C)=4, f(C)=4+3=7. Open List = {C (f=7), B (f=8)}, Closed List = {A}. Step 3: Remove C (lowest f-cost) from Open List. Expand C. - Successor D: g(D)=4+1=5, f(D)=5+2=7. Open List = {D (f=7), B (f=8)}, Closed List = {A, C}. Step 4: Remove D (lowest f-cost) from Open List. Expand D. - Successor E: g(E)=5+3=8, f(E)=8+0=8. Open List = {B (f=8), E (f=8)}, Closed List = {A, C, D}. Step 5: Remove E (goal reached with lowest cost). Stop search. Path is A -> C -> D -> E with total cost 8.
評分準則
Award marks as follows: - 2 marks for showing correct f-values for successors of A (B: f=8, C: f=7) and selecting C. - 1.5 marks for showing correct f-value for successor D (f=7) and selecting D. - 1.5 marks for showing correct f-value for successor E (f=8). - 1.25 marks for stating the correct final path (A -> C -> D -> E) and total cost of 8.
Analyze the time complexity of the following pseudocode. Express your answer in Big O notation in terms of \(n\) and show your derivation:
```pseudocode FUNCTION ProcessArray(Arr : ARRAY, n : INTEGER) RETURNS INTEGER DECLARE total : INTEGER total <- 0 FOR i <- 1 TO n FOR j <- 1 TO n total <- total + Helper(i) NEXT j NEXT i RETURN total ENDFUNCTION
FUNCTION Helper(x : INTEGER) RETURNS INTEGER DECLARE count : INTEGER count <- 0 WHILE x > 1 count <- count + 1 x <- x DIV 2 ENDWHILE RETURN count ENDFUNCTION ```
查看答案詳解收起答案詳解
解題
1. Analyze the `Helper(x)` function: The variable `x` is divided by 2 in each iteration of the `WHILE` loop until it is less than or equal to 1. This means the loop runs in logarithmic time with respect to its input, so its complexity is \(O(\log x)\). In the worst-case scenario within `ProcessArray`, `x` can be up to `n`, giving a complexity of \(O(\log n)\) for a single call. 2. Analyze the loops in `ProcessArray`: The outer loop runs `n` times (from 1 to `n`). The inner loop also runs `n` times (from 1 to `n`). Inside the inner loop, `Helper(i)` is called. 3. Combine the analysis: For each of the \(n\) iterations of the outer loop, the inner loop executes \(n\) times. In the worst case (when \(i \approx n\)), each call to `Helper(i)` takes \(O(\log n)\) time. Therefore, the overall worst-case complexity is: \(n \times n \times O(\log n) = O(n^2 \log n)\).
評分準則
Award marks as follows: - 2 marks for correctly identifying and justifying that the complexity of `Helper(x)` is \(O(\log x)\) or \(O(\log n)\) in the worst case. - 2 marks for analyzing that the nested loops without the helper take \(O(n^2)\) time. - 2.25 marks for multiplying the loop complexities with the helper function complexity to derive the final worst-case complexity of \(O(n^2 \log n)\).
Trace the execution of the query: `?- ancestor(john, ann).` Explain how backtracking and unification are used by the interpreter to resolve this query, and state the final output.
查看答案詳解收起答案詳解
解題
1. The query is `?- ancestor(john, ann).` 2. First, the interpreter tries Rule 1: `ancestor(X, Y) :- parent(X, Y).` Unifying `X = john`, `Y = ann` yields the goal `parent(john, ann)`. Since there is no such fact, this fail-matches. 3. The interpreter backtracks and tries Rule 2: `ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).` Unification gives `parent(john, Z), ancestor(Z, ann)`. 4. The interpreter searches for facts matching `parent(john, Z)`. The first match is `Z = mary`. 5. This generates a sub-goal: `ancestor(mary, ann)`. 6. To resolve `ancestor(mary, ann)`, it applies Rule 1, giving the goal `parent(mary, ann)`. 7. The fact `parent(mary, ann)` exists in the database. Thus, the sub-goal succeeds. 8. Since the sub-goal succeeds, the original query `ancestor(john, ann)` succeeds, returning 'Yes'.
評分準則
Award marks as follows: - 2 marks for explaining the failure of the first rule match (parent(john, ann)) and subsequent backtracking. - 2 marks for demonstrating how Z is unified with mary in the second rule to establish the sub-goal parent(john, mary) and ancestor(mary, ann). - 2.25 marks for evaluating ancestor(mary, ann) through Rule 1 (parent(mary, ann)), matching the fact, and outputting 'Yes'.
A real binary number is represented in normalized floating-point format using 16 bits: - 10 bits for the mantissa, stored in two's complement. - 6 bits for the exponent, stored in two's complement.
The binary representation is: Mantissa: 0110100000 Exponent: 111100
Convert this floating-point number into its denary equivalent. Show all steps of your working, including: 1. The conversion of the mantissa to a denary fraction. 2. The conversion of the exponent to a denary integer. 3. The final calculation to obtain the denary representation.
查看答案詳解收起答案詳解
解題
1. **Mantissa Conversion**: The mantissa is positive because the most significant bit is 0. Mantissa = 0110100000 This represents the binary fraction: \(0.1101_2 = 1 \times 2^{-1} + 1 \times 2^{-2} + 0 \times 2^{-3} + 1 \times 2^{-4}\) \(= 0.5 + 0.25 + 0.0625 = 0.8125\) (or \(13/16\))
2. **Exponent Conversion**: The exponent is negative because the most significant bit is 1. Exponent = 111100 In two's complement: - MSB value: \(-32\) - Remaining bits: \(16 + 8 + 4 = 28\) - Total = \(-32 + 28 = -4\) (Alternatively, inverting the bits of 111100 gives 000011, and adding 1 gives 000100, which is 4. Thus, the value is \(-4\).)
Maximum 6.25 marks total: - **1.5 marks**: Correctly converting the mantissa to its positive denary value of \(0.8125\) or \(13/16\). - **0.5 marks**: Correctly identifying that the mantissa is positive due to leading sign bit 0. - **1.5 marks**: Correctly identifying that the exponent is negative and calculating its value as \(-4\). - **0.75 marks**: Showing the formula/method of multiplying mantissa by \(2^{\text{exponent}}\). - **2.0 marks**: Providing the correct final answer of \(0.05078125\) or \(\frac{13}{256}\) with complete, clear working.
Simplify the following Boolean expression using Boolean algebra laws and De Morgan's laws. Show all steps in your simplification, stating the law(s) used at each major step.
\(X = A \cdot B + A \cdot (\overline{B + \overline{C}}) + B \cdot (A + \overline{C})\)
查看答案詳解收起答案詳解
解題
Step 1: Simplify the second term \(A \cdot (\overline{B + \overline{C}})\) using De Morgan's Law. \(\overline{B + \overline{C}} = \overline{B} \cdot \overline{\overline{C}} = \overline{B} \cdot C\) (Involution/Double Negation law) So, the second term becomes \(A \cdot \overline{B} \cdot C\).
Step 2: Expand the third term \(B \cdot (A + \overline{C})\) using the Distributive Law. \(B \cdot (A + \overline{C}) = B \cdot A + B \cdot \overline{C} = A \cdot B + B \cdot \overline{C}\)
Step 3: Combine all terms back into the expression. \(X = A \cdot B + A \cdot \overline{B} \cdot C + A \cdot B + B \cdot \overline{C}\)
Step 4: Use the Idempotent Law to simplify \(A \cdot B + A \cdot B\). \(X = A \cdot B + A \cdot \overline{B} \cdot C + B \cdot \overline{C}\)
Step 5: Factor out \(A\) from the first two terms using the Distributive Law. \(X = A \cdot (B + \overline{B} \cdot C) + B \cdot \overline{C}\)
Step 6: Simplify \(B + \overline{B} \cdot C\) using the Distributive/Redundancy Law (\(Y + \overline{Y}Z = Y + Z\)). \(B + \overline{B} \cdot C = B + C\) So, \(X = A \cdot (B + C) + B \cdot \overline{C} = A \cdot B + A \cdot C + B \cdot \overline{C}\)
Step 7: Simplify the expression further by removing the redundant consensus term \(A \cdot B\). We can rewrite \(A \cdot B\) as \(A \cdot B \cdot (C + \overline{C})\): \(X = A \cdot B \cdot (C + \overline{C}) + A \cdot C + B \cdot \overline{C}\) \(= A \cdot B \cdot C + A \cdot B \cdot \overline{C} + A \cdot C + B \cdot \overline{C}\) Group the terms: \(= (A \cdot B \cdot C + A \cdot C) + (A \cdot B \cdot \overline{C} + B \cdot \overline{C})\) Factor out \(A \cdot C\) and \(B \cdot \overline{C}\): \(= A \cdot C \cdot (B + 1) + B \cdot \overline{C} \times (A + 1)\) Since \(B + 1 = 1\) and \(A + 1 = 1\): \(= A \cdot C + B \cdot \overline{C}\)
評分準則
Maximum 6.25 marks total: - **1.25 marks**: Correctly applying De Morgan's law to simplify the second term to \(A \cdot \overline{B} \cdot C\). - **1.0 marks**: Correctly expanding the third term using the distributive law to \(A \cdot B + B \cdot \overline{C}\). - **1.0 marks**: Correctly using the Idempotent law to group \(A \cdot B + A \cdot B = A \cdot B\). - **1.0 marks**: Correctly applying distributive/redundancy rule to simplify \(A \cdot B + A \cdot \overline{B} \cdot C\) to \(A \cdot B + A \cdot C\). - **1.0 marks**: Correctly demonstrating the elimination of the redundant consensus term \(A \cdot B\). - **1.0 marks**: Providing the final correct simplified expression: \(A \cdot C + B \cdot \overline{C}\) (or equivalent standard notation).
An expression in Reverse Polish Notation (RPN) is processed by a compiler using a stack. The RPN expression to be evaluated is: `12 5 3 - * 8 2 / +`
Show the changing state of the stack as the expression is processed from left to right. Draw or write the state of the stack after each operator (`-`, `*`, `/`, `+`) is executed, and state the final evaluated result of the expression.
查看答案詳解收起答案詳解
解題
Tracing the evaluation of the expression `12 5 3 - * 8 2 / +` step-by-step:
1. Push `12`. Stack: `[12]` 2. Push `5`. Stack: `[12, 5]` 3. Push `3`. Stack: `[12, 5, 3]` 4. Operator `-` is met: - Pop `3` (right operand) and `5` (left operand). - Calculate \(5 - 3 = 2\). - Push result `2`. - Stack state after `-`: `[12, 2]` 5. Operator `*` is met: - Pop `2` and `12`. - Calculate \(12 \times 2 = 24\). - Push result `24`. - Stack state after `*`: `[24]` 6. Push `8`. Stack: `[24, 8]` 7. Push `2`. Stack: `[24, 8, 2]` 8. Operator `/` is met: - Pop `2` and `8`. - Calculate \(8 / 2 = 4\). - Push result `4`. - Stack state after `/`: `[24, 4]` 9. Operator `+` is met: - Pop `4` and `24`. - Calculate \(24 + 4 = 28\). - Push result `28`. - Stack state after `+`: `[28]`
The final evaluated result of the expression is 28.
評分準則
Maximum 6.25 marks total: - **1.25 marks**: Correctly showing the initial pushes and the state of the stack after the first operator `-` is executed: `[12, 2]`. - **1.25 marks**: Correctly showing the state of the stack after the second operator `*` is executed: `[24]`. - **1.25 marks**: Correctly showing the state of the stack after the third operator `/` is executed: `[24, 4]`. - **1.25 marks**: Correctly showing the state of the stack after the final operator `+` is executed: `[28]`. - **1.25 marks**: Providing the final correct result: `28`.
a) State the result(s) returned by the query: `?- can_take(alice, X).`
b) Write a new rule `is_heavy_workload(Course)` that is true if the course carries exactly 4 credits and has a prerequisite.
查看答案詳解收起答案詳解
解題
a) Tracing the query `?- can_take(alice, X).`: - From facts, `enrolled(alice, computer_science)`. Therefore, `Major = computer_science`. - From facts, courses under `computer_science` are `cs101` and `cs202`. - For `X = cs101`: - Checking the first `can_take` rule: `not(prerequisite(cs101, _))`. There is no prerequisite fact for `cs101`, so this is true. This yields the solution: `X = cs101`. - For `X = cs202`: - Checking the first `can_take` rule: `not(prerequisite(cs202, _))` is false because `prerequisite(cs202, cs101)` exists. - Checking the second `can_take` rule: `prerequisite(cs202, PreReq)` binds `PreReq = cs101`. Then `passed(alice, cs101)` is evaluated. Since `passed(alice, cs101)` is a fact, this is true. This yields the solution: `X = cs202`.
The query returns: `X = cs101` `X = cs202`
b) To define the rule `is_heavy_workload(Course)`: - Match a course that has 4 credits: `course(Course, _, 4)` - Ensure it has a prerequisite: `prerequisite(Course, _)` Combined rule: `is_heavy_workload(Course) :- course(Course, _, 4), prerequisite(Course, _).`
評分準則
Maximum 6.25 marks total: - **1.5 marks**: Correctly identifying `X = cs101` as a solution to the query. - **1.5 marks**: Correctly identifying `X = cs202` as a solution to the query. - **1.25 marks**: Explaining the Prolog logic execution/matching steps for either of the results. - **2.0 marks**: Writing a fully correct syntactic rule for `is_heavy_workload(Course)` (1 mark for matching course with exactly 4 credits, 1 mark for matching prerequisite existence).
Paper 4 (A Level Practical Programming)
Submit working source code and evidence documents. Do not use zip archives.
3 題目 · 75 分
題目 1 · Applied Programming Tasks
25 分
An transport company manages a fleet of vehicles. The company tracks regular vehicles and electric vehicles.
1. Create a new Python file named `Question1.py`.
2. Define a class `Vehicle` with the following private attributes: - `VehicleID` (String) - `Brand` (String) - `BasePrice` (Real)
The class must also have: - A constructor that takes `VehicleID`, `Brand`, and `BasePrice` as parameters to initialize the attributes. - Getters for all three attributes. - A method `CalculateTax()` that calculates and returns the tax as 10% of the `BasePrice`. [6 marks]
3. Define a subclass `ElectricVehicle` that inherits from `Vehicle`. It must have the following private attributes: - `BatteryCapacity` (Integer) - `RangeKM` (Integer)
The subclass must also have: - A constructor that takes `VehicleID`, `Brand`, `BasePrice`, `BatteryCapacity`, and `RangeKM` as parameters and initializes all attributes (using the parent constructor where appropriate). - Getters for `BatteryCapacity` and `RangeKM`. - A polymorphic override of the method `CalculateTax()` that calculates and returns the tax as 2% of the `BasePrice`. [6 marks]
4. In the main program area: - Set up a 1D array named `VehicleList` of size 30, with elements initialized to `None` (or null). - Write a function `ReadData()` that opens and reads data from a text file named `vehicles.txt`. Each vehicle's data is formatted over multiple lines. The first line of each record is either "VEHICLE" or "EV". This is followed by lines for the standard attributes, and (in the case of "EV") the battery capacity and range. - The function should instantiate the appropriate class objects and store them in the `VehicleList` array. - It should catch file-handling exceptions and return the total number of vehicles successfully loaded into the array. [8 marks]
5. Write a main function to: - Call `ReadData()`. - Output the total number of vehicles loaded. - Iterate through the loaded elements of `VehicleList` and display the ID, Brand, and calculated Tax of each vehicle. [5 marks]
Sample contents for `vehicles.txt`: EV EV-101 Tesla 45000.0 75 480 VEHICLE GAS-202 Toyota 25000.0 EV EV-303 Nissan 32000.0 40 270
查看答案詳解收起答案詳解
解題
The solution implements robust object-oriented patterns in Python as specified in the Cambridge 9618 syllabus.
1. **Base Class Vehicle**: Attributes are declared private using double leading underscores (`__`). Getters are implemented to retrieve private variables. The tax method multiplies base price by `0.10`. 2. **Derived Class ElectricVehicle**: Inherits from `Vehicle` using `super().__init__()`. Overrides the polymorphic `calculate_tax` method to return `0.02` of the parent's base price using `self.get_base_price()`. 3. **File Handling and Parsing**: Uses a try-except block to manage potential file I/O exceptions. It parses different numbers of lines dynamically depending on whether the record type header is `EV` or `VEHICLE`. 4. **Array Output**: Elements are printed from `VehicleList` up to the total loaded counter.
評分準則
### Marking Scheme (25 Marks Total)
#### Vehicle Class [6 Marks] - **1 Mark**: Private attributes correctly defined and initialized in constructor. - **1 Mark**: Getter for `VehicleID`. - **1 Mark**: Getter for `Brand`. - **1 Mark**: Getter for `BasePrice`. - **2 Marks**: `CalculateTax()` method implemented correctly returning 10% of base price.
#### ElectricVehicle Class [6 Marks] - **1 Mark**: Class inherits from `Vehicle`. - **1 Mark**: Constructor calls `super().__init__` with appropriate parent attributes. - **1 Mark**: Private subclass attributes `BatteryCapacity` and `RangeKM` initialized correctly. - **1 Mark**: Getters for subclass attributes defined. - **2 Marks**: Polymorphic method `CalculateTax()` correctly overridden to calculate 2% of base price.
#### ReadData Function [8 Marks] - **1 Mark**: Array initialized with 30 items. - **1 Mark**: Correct file open and close operations inside exception handler (try/except). - **1 Mark**: Loop to read each line until EOF or array limit reached. - **1 Mark**: Reads `VEHICLE` block (reads exactly 4 lines including type). - **1 Mark**: Reads `EV` block (reads exactly 6 lines including type). - **2 Marks**: Instantiate corresponding class object with typed variables and save to array. - **1 Mark**: Increments counter and returns loaded count.
#### Main Program Execution [5 Marks] - **1 Mark**: Calls `ReadData()` and saves count. - **1 Mark**: Displays total loaded count. - **1 Mark**: Loops through loaded array entries. - **2 Marks**: Prints output including ID, Brand, and Tax (formatted to 2 decimal places).
題目 2 · Applied Programming Tasks
25 分
A local inventory system requires a Binary Search Tree (BST) to organize unique Product Codes alphabetically.
1. Create a new Python file named `Question2.py`.
2. Define a class `Node` with the following public attributes: - `ProductCode` (String) - `LeftPointer` (Integer) - `RightPointer` (Integer)
The constructor must accept `ProductCode` as a parameter and initialize `LeftPointer` and `RightPointer` to -1. [4 marks]
3. Set up a global 1D array named `Tree` of size 15 of type `Node`. Initialize a global variable `RootPointer` to -1 and a global variable `FreePointer` to 0.
4. Write a procedure `InitialiseTree()` that links all nodes in `Tree` to form a free list. The `LeftPointer` of each node should point to the index of the next node, with the final node's `LeftPointer` set to -1. All `ProductCode` strings must be initialized to empty strings, and `RightPointer` values to -1. [6 marks]
5. Write a recursive procedure `InsertNode(CurrentPointer, NewNodeIndex)` which performs the following tasks: - Checks if the product code of the new node is alphabetically smaller than the product code at `CurrentPointer`. - If smaller, checks if `LeftPointer` of `CurrentPointer` is -1. If so, updates it to `NewNodeIndex`; otherwise, calls `InsertNode` recursively with `LeftPointer` as the new current index. - If larger or equal, checks if `RightPointer` of `CurrentPointer` is -1. If so, updates it to `NewNodeIndex`; otherwise, calls `InsertNode` recursively with `RightPointer` as the new current index. [8 marks]
6. Write a recursive procedure `InOrder(CurrentPointer)` that prints out the sorted `ProductCode` values stored in the tree in alphabetical order. [4 marks]
7. Write main program code to: - Call `InitialiseTree()`. - Write a function `AddProduct(NewCode)` that gets a node from the free list, sets its product code, and uses `InsertNode` to place it correctly within the BST. Update pointers appropriately. - Add the following test data codes: `"ORANGE"`, `"APPLE"`, `"PEACH"`, `"BANANA"`, `"MANGO"`. - Print the sorted order using `InOrder(RootPointer)`. [3 marks]
查看答案詳解收起答案詳解
解題
This implementation utilizes an array-based Binary Search Tree where pointers map directly to array indices.
1. **Initialization**: Linking the tree elements ahead of time allows for dynamic retrieval of available memory positions. The standard dynamic free list uses the left attribute of nodes to link sequentially from `0` to `14`. 2. **Recursive Insertion**: By referencing the class parameters inside `InsertNode()`, the recursion moves down the tree branches until finding a free pointer (`-1`) to attach the index of the newly parsed item. 3. **In-Order Traversal**: Standard depth-first LNR (Left, Node, Right) traversal recursively visits children, resulting in an ascending output of records.
評分準則
### Marking Scheme (25 Marks Total)
#### Node Class [4 Marks] - **1 Mark**: Attributes `ProductCode`, `LeftPointer`, and `RightPointer` defined. - **1 Mark**: Attributes initialized correctly in the constructor. - **2 Marks**: Constructor parameters set up correctly with default pointer values of -1.
#### Tree Initialization [6 Marks] - **1 Mark**: Global array of size 15 initialized with Node elements. - **1 Mark**: `RootPointer` initialized to -1. - **1 Mark**: `FreePointer` initialized to 0. - **2 Marks**: Loop links nodes `0` to `13` to next sequence point (`i + 1`) via `LeftPointer`. - **1 Mark**: Set final element's `LeftPointer` to -1.
#### In-Order Traversal [4 Marks] - **1 Mark**: Correct parameter input to function and check for empty node base-case (`!= -1`). - **1 Mark**: Recursive call to left child. - **1 Mark**: Outputting the current node's `ProductCode`. - **1 Mark**: Recursive call to right child.
#### Main and Add Method Integration [3 Marks] - **1 Mark**: Calls `InitialiseTree()`. - **1 Mark**: `AddProduct()` retrieves node from free list and updates `FreePointer` correctly. - **1 Mark**: Inserts all test data and displays accurate sorted alphabetized printouts.
題目 3 · Applied Programming Tasks
25 分
A processing server manages tasks queue using a Circular Queue.
1. Create a new Python file named `Question3.py`.
2. Define a class `TaskQueue` with the following private attributes: - `QueueArray` (1D Array of size 10, elements initialized to empty strings `""`) - `Head` (Integer, initialized to 0) - `Tail` (Integer, initialized to 0) - `NumItems` (Integer, initialized to 0)
The class must have the following public methods: - A constructor initializing the queue. - `Enqueue(TaskName)`: Adds `TaskName` to the queue. Returns `True` if successfully enqueued, and `False` if the queue is full. - `Dequeue()`: Removes and returns the task from the head of the queue. Returns `""` if the queue is empty. - Getter methods `GetHead()`, `GetNumItems()`, and `GetItemAt(Index)`. [12 marks]
3. Write a global recursive function `RecursiveSearch(QueueObj, CurrentIndex, Count, Target)` to search for a task in the queue. - `QueueObj` is the instance of `TaskQueue`. - `CurrentIndex` is the array position to inspect. - `Count` tracks how many elements have been evaluated. - The function should return the array index where the item was found. If the target is not found or the search has processed all elements (`Count == GetNumItems()`), return -1. [8 marks]
4. Write a main program to test your functions. Perform the following: - Instantiate an object of `TaskQueue`. - Enqueue five tasks in this sequence: `"Backup"`, `"Render"`, `"Compile"`, `"Update"`, `"Sync"`. - Dequeue the first task (`"Backup"`). - Search recursively for `"Compile"` using `RecursiveSearch` and print the returned index. - Search recursively for `"Backup"` and verify that it returns -1. [5 marks]
查看答案詳解收起答案詳解
解題
This solution sets up a robust circular queue.
1. **Circular Arithmetic**: Tail and head movements wrap around using `% 10`. 2. **Private Encapsulation**: Variable names use prefix `__` to ensure security scope. Getters allow standard reading operations. 3. **Recursive Execution**: Because search starts at the front header, we evaluate dynamically up to `num_items` depth without hardcoding linear array loops.
評分準則
### Marking Scheme (25 Marks Total)
#### TaskQueue Class Definition [12 Marks] - **1 Mark**: Private attributes declared correctly inside the constructor. - **1 Mark**: Queue array initialized with 10 empty strings. - **1 Mark**: `Enqueue` checks if queue is full. - **2 Marks**: `Enqueue` sets value and increments `Tail` circularly (e.g., `(Tail + 1) % 10`). - **1 Mark**: `Enqueue` increments `NumItems` counter and returns boolean values. - **1 Mark**: `Dequeue` checks if queue is empty. - **2 Marks**: `Dequeue` extracts, updates head circularly (e.g., `(Head + 1) % 10`), and decrements counter. - **3 Marks**: All three getter methods `GetHead()`, `GetNumItems()`, and `GetItemAt(Index)` return the correct private attributes.
#### RecursiveSearch Function [8 Marks] - **1 Mark**: Function signature contains all required input parameters. - **2 Marks**: Base case checks for processed iteration limits (`Count == NumItems`) returning -1. - **2 Marks**: Checks value of target with matching array value index and returns correct active index. - **2 Marks**: Calculates the modular next circular index step cleanly: `(CurrentIndex + 1) % 10`. - **1 Mark**: Correct recursive call incrementing `Count` parameter on execution.
#### Main Program Execution [5 Marks] - **1 Mark**: Instantiates `TaskQueue`. - **1 Mark**: Correctly enqueues the 5 tasks. - **1 Mark**: Calls dequeue method once. - **1 Mark**: Searches for "Compile" and outputs correctly returned index value (which should be 2). - **1 Mark**: Searches for "Backup" and outputs correctly returned value -1.
想知道自己有幾分把握？
Thinka 是 DSE 學生用的 AI 練習應用程式，有無限量練習題、即時自動批改和詳細解題步驟。逾 100,000 名學生用它確認自己真的識，而不只是「以為識」。