Cambridge A Level Computer Science 9618 — 2023 Oct/Nov Paper 3 · Variant 2

1 (a) Real numbers are stored in a computer using floating point representation with: • 10 bits for the mantissa • 6 bits for the exponent • two’s complement form for both the mantissa and the exponent. Write the normalised floating‑point representation of –96.75 in this system. Show your working. Mantissa Exponent Working ..................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... [3] (b) Explain why a binary representation is sometimes only an approximation to the real number it represents. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [3]

Mark scheme: Question Answer Marks 1(a) One mark per mark point (Max 1) 3 • conversion of −96.75 to binary e.g., positive 96.75, flip the bits + 1 to give 10011111.01 // –128 + 16 + 8 + 4 + 2 + 1 + 0.25 / ¼ seen One mark per mark point (Max 2) • correct mantissa • correct exponent Mantissa Exponent 1 0 0 1 1 1 1 1 0 1 0 0 0 1 1 1 1(b) One mark per mark point (Max 3) 3 MP1 Real numbers (can) have a fractional part (such as 1/3 and ½) / (such as 0.4 and 0.25) MP2 The fixed length of the storage means that you can’t store very large / very small numbers MP3 Binary numbers represent numbers based on powers of 2, with limited fractional representations such as 1/2, 1/4, 1/8, 1/16, etc. MP4 It isn’t possible to store all fractions with the level of precision provided by this system MP5 …the fractional part of the number is as close as possible within these constraints.

2 Describe what is meant by composite and non‑composite data types. Composite ........................................................................................................................................ .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... Non‑composite ................................................................................................................................. .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... [4]

Mark scheme: 2 One mark per mark point – composite (Max 2) 4 MP1 A (user defined) data type that is a collection of data that can consist of multiple elements MP2 …of different or the same data types MP3 …grouped under a single identifier. One mark per mark point – non-composite (Max 2) MP4 It can be defined without referencing another data type. MP5 It can be a primitive type available in a programming language, or a user- defined type.

3 The location of a record in a random file is determined using a hashing algorithm. A collision may occur during the process of adding a record. (a) Outline what is meant by the term collision in this context. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2] (b) Explain how a collision can be dealt with when writing records to a random file. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [3]

Mark scheme: 3(a) One mark per mark point (Max 2) 2 MP1 A collision is when the two values / data items in the key field for two records (pass through a hashing algorithm and) result in the same hash value MP2 …so the location identified (by the hashing algorithm) may already be in use // two records cannot occupy the same address. 3(b) One mark per mark point (Max 3) 3 MP1 A process of collision resolution is used MP2 Start at the original hashed storage space MP3 …go through the following spaces in a linear fashion MP4 …and store the data item in the first available slot. OR MP5 Search the overflow area MP6 …go through the following spaces in a linear fashion MP7 …and store the data item in the first available slot. OR MP8 Each storage space holds a reference to a collection / chain of items MP9 …which can be searched individually. MP10 The data item is stored in the first available space in this chain.

4 Complete the following paragraph about a protocol suite, using words from the given list. Some words are not used. BitTorrent circuit switching layered link list peer‑to‑peer queue stack star TCP/IP The protocols in a ............................................................................. determine the interconnectivity rules for a ............................................................................. network model such as the ............................................................................. model. [3]

Mark scheme: 4 One mark for each correct word (Max 3) 3 The protocols in a stack determine the interconnectivity rules for a layered network model such as the TCP/IP model.

5 (a) Outline the reasons why an operating system may need to use virtual memory. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2] (b) Explain the circumstances in which disk thrashing could occur. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [3]

Mark scheme: 5(a) One mark per mark point (Max 2) 2 MP1 Virtual memory is used when RAM is running low MP2 …such as when a computer is running many processes at once. MP3 Virtual memory may be used for efficient use of RAM / the processor MP4 …such as if data / programs are not immediately needed, they can be moved from RAM to virtual memory 5(b) One mark per mark point (Max 3) 3 MP1 Disk thrashing is a problem that may occur when frequent transfers between main memory and secondary memory take place // Disk thrashing is a problem that may occur when virtual memory is being used MP2 As main memory fills up, more pages need to be swapped in and out of secondary/virtual memory MP3 This swapping leads to a very high rate of hard disk head movements MP4 Eventually, more time is spent swapping the pages/data than processing the data.

6 (a) The Reverse Polish Notation (RPN) expression: a b * 2 / c d / * is to be evaluated where a = 20, b = 3, c = 10 and d = 5. Show the changing contents of the following stack as the RPN expression is evaluated. [4] (b) Explain how an expression stored in RPN can be evaluated. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [3]

Mark scheme: 6(a) One mark per ring (Max 4). 4 5 3 2 10 10 2 20 20 60 60 30 30 30 30 60 OR 20 3 60 2 30 10 5 2 60 20 60 30 10 30 30 6(b) One mark per mark point (Max 3) 3 MP1 The (RPN) expression is read from left to right, one item at a time MP2 Each element is checked to see if it as operator or a value MP3 Values are pushed onto a stack until an operator is found MP4 The operator is applied to the last two values on the stack and the result is pushed back onto the stack MP5 This repeats until a single value remains, which is the solution.

7 (a) This logic circuit represents the Boolean expression: X = A + B + C A B X C Complete this truth table for the given logic circuit. A B C X 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 [1] (b) Apply De Morgan’s laws to the expression: X = A + B + C X = ...................................................................................................................................... [1] (c) Simplify the following expression using Boolean algebra. Show all the stages in your simplification. T = X.Y.Z + X.Y.Z + X ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [3]

Mark scheme: 7(a) A B C X 1 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0 7(b) X= A.B.C 1 7(c) (Max 2) for correct working from points shown 3 (T =) X.Y.Z + X.Y.Z + X Distributive law (T=) X.Z.(Y + Y) + X Complement law (T=) X.Z.(1) + X Identity law (T=) X.Z + X Redundancy law (to get final answer) One mark for correct answer (T=) X + Z

8 Calculate the shortest distance between the Start and each of the destinations in the diagram using Dijkstra’s algorithm. Show your working and write your answers in the table provided. 4 A B 8 C 2 3 8 9 D 2 E 7 10 Start F Working ............................................................................................................................................ .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... Answers: A B C D E F [5]

Mark scheme: 8 One mark per mark point - working (Max 3) 5 May be seen on diagram or in working section MP1 Initialisation – setting Start to 0 MP2 …and the rest of the towns to MP3 Evidence to show values at nodes being updated MP4 Evidence to show ‘visited node(s)’ MP5 Evidence to show a correct calculation of at least one route MP6 Evidence to show more than one route has been calculated for at least one town Correct Answers (Max 2) Two marks for all six correct values One mark for four or five correct values. A B C D E F 8 12 19 14 16 10

9 (a) A stack Abstract Data Type (ADT) is to be implemented using pseudocode, with procedures to initialise it and to push new items onto the stack. A 1D array Stack stores the contents of the stack. (i) Study the pseudocode in part (a)(ii) and complete the table of identifiers by writing the missing data types and descriptions. Identifier Data type Description BasePointer TopPointer Stack REAL [2] (ii) Complete the pseudocode. CONSTANT MaxSize = 40 DECLARE BasePointer : INTEGER DECLARE TopPointer : INTEGER DECLARE Stack : ARRAY[1:40] OF REAL // initialisation of stack PROCEDURE Initialise() ................................................................................ 1 ................................................................................ 0 ENDPROCEDURE // push an item onto the stack PROCEDURE Push(NewItem : REAL) ................................................................................ MaxSize THEN .......................................................................................................... Stack[TopPointer] ............................................................. ENDIF ENDPROCEDURE [5] (b) Justify the use of a linked list instead of an array to implement a stack. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2] (c) Explain how a compiler makes use of a stack when translating recursive programming code. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [4]

Mark scheme: 9(a)(i) Two marks for all five empty boxes correct 2 One mark for any three or four empty boxes correct Identifier Data type Description BasePointer INTEGER Points to the bottom of the stack TopPointer INTEGER Points to the top of the stack Stack REAL List of decimal numbers stored in the stack 9(a)(ii) One mark for each correctly completed line (Max 5) 5 CONSTANT MaxSize = 40 DECLARE BasePointer : INTEGER DECLARE TopPointer : INTEGER DECLARE Stack : ARRAY[1:40] OF REAL // initialisation of stack PROCEDURE Initialise() BasePointer  1 TopPointer  0 ENDPROCEDURE // adding an item to the stack PROCEDURE Push(NewItem) IF TopPointer < MaxSize THEN TopPointer  TopPointer + 1 Stack[TopPointer]  NewItem ENDIF ENDPROCEDURE 9(b) One mark for linked list and one mark for array (Max 2) 2 Linked list MP1 A linked list is a dynamic data structure / not restricted in size MP2 Has greater freedom to expand or contract by adding or removing nodes as necessary MP3 Allows more efficient editing using pointers (instead of moving the data). Array MP4 An array is a static data structure1 generally fixed in size MP5 When the array is full, the stack cannot be extended any further. 9(c) One mark per mark point (Max 1) 4 MP1 The compiler must produce object code to One mark per mark point (Max 3) MP2 …push return addresses / values of local variables onto a stack MP3 …with each recursive call // … to set up winding MP4 …pop return addresses / values of local variables off the stack … MP5 …after the base case is reached // … to implement unwinding.

10 Describe the features of the SIMD and MISD computer architectures. SIMD ................................................................................................................................................ .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... MISD ................................................................................................................................................ .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... [4]

Mark scheme: 10 One mark per mark point – SIMD (Max 2) 4 MP1 Single Instruction, Multiple Data (architecture) // Performs the same operation on multiple different data streams simultaneously. MP2 The instructions can be performed sequentially, taking advantage of pipelining. MP3 Parallel computers with multiple processors. One mark per mark point – MISD (Max 2) MP4 Multiple Instruction, Single Data (architecture) // Performs different operations on the same data stream. MP5 Each processor works on the same data stream independently. MP6 Parallel computers with multiple processors.

11 A declarative programming language is used to represent some facts about people and their hobbies. 01 hobby(music). 02 hobby(caving). 03 hobby(climbing). 04 hobby(camping). 05 hobby(baking). 06 hobby(travelling). 07 person(toby). 08 person(natasha). 09 person(fatima). 10 person(joseph). 11 person(elijah). 12 person(nina). 13 enjoys(natasha, travelling). 14 enjoys(toby, climbing). 15 enjoys(nina, climbing). 16 enjoys(elijah, camping). 17 enjoys(fatima, baking). 18 enjoys(joseph, camping). 19 dislikes(toby, caving). These clauses have the meanings: Clause Meaning 01 Music is a hobby 07 Toby is a person 13 Natasha enjoys travelling 19 Toby dislikes caving (a) Carlos is a person who enjoys the hobby of cycling but does not like music. Write additional clauses to represent this information. 20 ............................................................................................................................................ 21 ............................................................................................................................................ 22 ............................................................................................................................................ 23 ............................................................................................................................................ [4] (b) Using the variable P, the goal: enjoys(P, camping) returns P = elijah, joseph Write the result returned by the goal: enjoys(P, climbing) P = .................................................................................................................................... [1] (c) N is a person who might enjoy H if H is a hobby and N does not dislike H. Write this as a rule. might_enjoy(N, H) IF ............................................................................................................................................ ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [4]

Mark scheme: 11(a) One mark for each correctly completed clause (Max 4) 4 20 person(carlos). 21 hobby(cycling). 22 enjoys(carlos, cycling). 23 dislikes(carlos, music). 11(b) P = toby, nina 1 11(c) One mark per mark point (Max 4) 4 • person(N) • hobby(H) • dislikes(N, H) • all logical operators correct with no additional code (see example answers) Example answers: might_enjoy(N, H) IF person(N) AND hobby(H) AND NOT dislikes(N, H) might_enjoy(N, H) IF NOT dislikes(N, H), person(N), hobby(H)

12 (a) Describe, with an example, what is meant by an exception. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [2] (b) A pseudocode algorithm searches for a customer record in a random file AccountRecord.dat. A user inputs the name of the customer. The records are stored using the user‑defined data type TAccount. TYPE TAccount DECLARE AccountNumber : INTEGER DECLARE Name : STRING DECLARE Address : STRING DECLARE Telephone : STRING ENDTYPE If the record is found, it is output, otherwise an error message is displayed. Complete the file handling pseudocode. DECLARE Customer : TAccount DECLARE Location : INTEGER DECLARE MaxSize : INTEGER DECLARE FoundFlag : BOOLEAN DECLARE SearchCustomer : STRING MaxSize 1000 OPENFILE ............................................................................................................... Location 1 ............................................................................................................... FALSE OUTPUT "Enter the customer’s name" ............................................................................................................... ................................................................................... AND Location <= MaxSize ................................... "AccountRecord.dat", ............................................ GETRECORD "AccountRecord.dat", Customer IF SearchCustomer = Customer.Name THEN OUTPUT "Customer found: " OUTPUT Customer // output customer record FoundFlag TRUE ENDIF Location Location + 1 ENDWHILE IF NOT FoundFlag THEN OUTPUT ".........................................................................................................." ENDIF [7]

Mark scheme: 12(a) One mark for description, for example: 2 An exception is an event that occurs during the execution of a program that disrupts the normal flow of instructions / causes the program to halt execution One mark for example: • Hardware failure // hard disk crash • Programming error // trying to access out-of-bounds array element // divide by zero error // runtime error • User error // typing incorrect filename / data type 12(b) One mark for each correctly completed blank (Max 7) 7 DECLARE Customer : TAccount DECLARE Location : INTEGER DECLARE MaxSize : INTEGER DECLARE: FoundFlag : BOOLEAN DECLARE SearchCustomer : STRING MaxSize  1000 OPENFILE "AccountRecord.dat" FOR RANDOM Location  1 FoundFlag  FALSE OUTPUT "Enter the customer’s name" INPUT SearchCustomer WHILE NOT FoundFlag AND Location <= MaxSize SEEK "AccountRecord.dat", Location GETRECORD "AccountRecord.dat", Customer IF SearchCustomer = Customer.Name THEN OUTPUT "Customer found: " OUTPUT Customer FoundFlag  TRUE ENDIF Location  Location + 1 ENDWHILE IF NOT FoundFlag THEN OUTPUT "Customer does not exist." ENDIF