Cambridge A Level Computer Science 9618 — 2024 Oct/Nov Paper 3 · Variant 1

1 Numbers are stored in a computer using binary 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. (a) Calculate the normalised binary floating-point representation of +201.125 in this system. Show your working. Mantissa Exponent Working ..................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... [3] (b) Calculate the denary value of the given normalised binary floating-point number. Show your working. Mantissa Exponent 1 0 1 0 1 1 0 0 1 1 0 0 0 1 0 1 Working ..................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... Answer ...................................................................................................................................... [3]

Mark scheme: Question Answer Marks 1(a) One mark per mark point (Max 1) 3 • correct answer • statement regarding number losing precision/rounding error One mark per mark point for working (Max 2) • number converted to binary 201.125 = 11001001.001 // 128 + 64 + 8 + 1 + 0.125 / 1/8 seen • use of the exponent e.g. moving the binary point 8 places /  28. Mantissa Exponent 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1(b) One mark per mark point (Max 2) 3 • application of exponent to go from 1.010110011 to 101011.0011 // x 25 // movement of binary point 5 places seen • –32 + 8 + 2 + 1 + .125 + .0625 // –32 + 8 + 2 + 1 + 1/8 + 1/16 seen // –1 + ¼ + 1/16 + 1/32 + 1/256 + 1/512 // –1 + 179/512 // –333/512 One mark for correct answer (Max 1) • –20.8125 // –2013/16

2 Reduced Instruction Set Computers (RISC) is a type of processor. Identify four features of a RISC processor. 1 ....................................................................................................................................................... .......................................................................................................................................................... 2 ....................................................................................................................................................... .......................................................................................................................................................... 3 ....................................................................................................................................................... .......................................................................................................................................................... 4 ....................................................................................................................................................... .......................................................................................................................................................... [4]

Mark scheme: 2 One mark per mark point (Max 4) 4 MP1 low number of instruction formats //low number of instruction sets MP2 uses single-clock cycle instructions MP3 uses fixed length instructions MP4 uses many general-purpose registers MP5 works well with pipelining MP6 hard-wired control unit MP7 makes extensive use of RAM MP8 uses a low number of addressing modes MP9 the design emphasis is on the software.

3 (a) Describe circuit switching as a method of data transmission. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [3] (b) State one benefit and one drawback of circuit switching as a method of data transmission. Benefit ...................................................................................................................................... ................................................................................................................................................... Drawback .................................................................................................................................. ................................................................................................................................................... [2]

Mark scheme: 3(a) One mark per mark point (Max 3) 3 MP1 A dedicated circuit / channel is required MP2 The circuit is established before the transmission begins MP3 The circuit lasts for the whole of the transmission // The circuit is closed at the end of the transmission MP4 Data travels in a continuous stream along the same route MP5 Transmission is usually bidirectional. 3(b) One mark for a benefit (Max 1) 2 MP1 No need for data to be reassembled // data / frames arrive in the same order in which they were sent MP2 Suitable for real time transmission // fast data transfer rate MP3 The whole of the bandwidth is available One mark for a drawback (Max 1) MP4 No other transmission can use the same circuit when it is in use // Bandwidth can be wasted as it cannot be used by other messages MP5 Not secure // Can be intercepted as all data travelling along the same route MP6 If there is a problem with the route the transmission ends // No other route is available without first doing the setup MP7 The circuit is always there whether or not it’s being used MP8 Can take time to set up before transmission starts.

4 The TCP/IP protocol may be viewed as a stack that contains four layers: Application, Transport, Internet, Link. Describe how the layers of the TCP/IP protocol stack interact with each other. .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .......................................................................................................................................................... .................................................................................................................................................... [4]

Mark scheme: 4 One mark per mark point (Max 4) 4 MP1 Each layer can only accept input from the next higher layer or the next lower layer MP2 There is an interface between the adjacent layers which is the only interaction between layers MP3 Data is added to the headers as the frames/packets pass through the layers MP4 The interactions are carried out by installed software MP5 User interaction takes place at the highest/Application layer of the stack through protocols associated with that layer of the stack MP6 Direct access to hardware takes place at the lowest/Link layer of the stack.

5 (a) Explain what is meant by a hashing algorithm in the context of file access. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [3] (b) The use of a hashing algorithm can result in the same storage location being identified for more than one record. Outline two methods of overcoming this issue. 1 ................................................................................................................................................ ................................................................................................................................................... 2 ................................................................................................................................................ ................................................................................................................................................... [2]

Mark scheme: 5(a) One mark per mark point (Max 3) 3 MP1 A hashing algorithm is used in direct access methods on random and sequential files MP2 It is a mathematical formula MP3 … used to perform a calculation applied to the key field of the record being searched / stored MP4 The result of the calculation gives the address where the record should be found / stored. 5(b) One mark per mark point (Max 2) 2 MP1 The record is stored in the next free memory space after the one identified by the hashing algorithm // Use linear progression MP2 An overflow area is set up and the record is stored in the next free memory space in the overflow area.

6 (a) Describe the user-defined data type set. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [3] (b) Write pseudocode statements to declare the set data type, SymbolSet, to hold the following set of mathematical operators, using the variable Operators. + – * / ^ ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [4]

Mark scheme: 6(a) One mark per mark point (Max 3) 3 MP1 A set user-defined data type is a composite data type MP2 … which includes a list of unordered elements MP3 Set theory operations, such as intersection and union, can be applied to these elements MP4 A set data type includes the type of data/data type it uses as part of its definition MP5 All the elements are of the same data type. 6(b) One mark for each mark point (Max 4) 4 MP1 TYPE SymbolSet/Operators = MP2 SET OF CHAR MP3 DEFINE Operators/SymbolSet MP4 ('+', '–', '*', '/', '^') MP5 : SymbolSet/Operators Example answers TYPE SymbolSet = SET OF CHAR DEFINE Operators ('+', '–', '*', '/', '^') : SymbolSet TYPE Operators = SET OF CHAR DEFINE SymbolSet ('+', '–', '*', '/', '^') : Operators

7 The truth table for a logic circuit is shown. INPUT OUTPUT A B C D T 0 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 1 1 1 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 1 1 1 0 1 0 0 1 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 1 0 0 1 1 1 1 1 (a) Write the Boolean logic expression that corresponds to the given truth table as the sum-of-products. T = ............................................................................................................................................ ............................................................................................................................................. [3] (b) Complete the Karnaugh map (K-map) for the given truth table. AB CD 00 01 11 10 00 01 11 10 [2] (c) Draw loop(s) around appropriate group(s) in the K-map to produce an optimal sum-of-products. [2] (d) (i) Write the Boolean logic expression from your answer to part (c) as the simplified sum-of-products. T = ...................................................................................................................................... ..................................................................................................................................... [2] (ii) Use Boolean algebra to write your answer to part (d)(i) in its simplest form. T = ............................................................................................................................... [1]

Mark scheme: 7(a) One mark for every two correct products (Max 3) 3 (T =) A. B. C. D + A. B. C. D + A. B. C. D + A. B. C. D + A. B. C. D + A. B. C. D 7(b) Two marks if no errors present 2 One mark if one error present AB CD 00 01 11 10 00 0 0 0 0 01 1 0 1 1 11 1 0 1 1 10 0 0 0 0 7(c) One mark for each correct loop (Max 2) 2 AB CD 00 01 11 10 00 0 0 0 0 01 1 0 1 1 11 1 0 1 1 10 0 0 0 0 7(d)(i) One mark for each mark point (Max 2) 2 • Any correct Boolean term • Boolean terms and operator correct and no other terms present (T =) A. D + B. D // B. D. + A. D 7(d)(ii) One mark for simplest form (Max 1) 1 (T =) D. (A. B)

8 (a) Describe the process of segmentation for memory management. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [4] (b) Explain what is meant by disk thrashing. ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ................................................................................................................................................... ............................................................................................................................................. [3]

Mark scheme: 8(a) One mark per mark point (Max 4) 4 MP1 In segmented memory, the logical / virtual address space is broken into varying sized blocks called segments / sections. MP2 Each segment has a name and size. MP3 During execution segments from logical / virtual memory are loaded into physical memory. MP4 The address is specified by the user MP5 … it contains the segment name and offset value. MP6 Segments are numbered MP7 … and this number is used as an index in the segment map table. MP8 The offset value determines the size of the segment. MP9 A segment map table maps logical / virtual addresses to physical addresses / contains the segment number and offset. 8(b) One mark per mark point (Max 3) 3 MP1 Disk thrashing is a problem that may occur when virtual memory is being used. MP2 As the main memory fills up, more and more pages need to be swapped in and out of virtual memory. MP3 This swapping leads to a very high rate of hard disk access / excessive disk head movements. MP4 Moving a hard disk read/write head takes a relatively long time / long latency time. MP5 Eventually, more time is spent swapping pages than processing data thrash point, which can cause the program to freeze or not run.

9 A veterinary surgery wants to create a class for individual pets. Some of the attributes required in the class are listed in the table. Attribute Data type Description PetID STRING unique ID assigned at registration PetType STRING type of pet assigned at registration telephone number of owner assigned at OwnerTelephone STRING registration DateRegistered DATE date of registration (a) State one reason why the attributes would be declared as PRIVATE. ................................................................................................................................................... ............................................................................................................................................. [1] (b) Complete the class diagram for Pet, to include: • an attribute and data type for the name of the pet • an attribute and data type for the name of the owner • a method to create a Pet object and set attributes at the time of registration • a method to assign a pet ID • a method to assign the date of registration • a method to return the pet name • a method to return the owner’s telephone number. Pet PetID : STRING PetType : STRING OwnerTelephone : STRING DateRegistered : DATE .............................................................. : .............................................................. .............................................................. : .............................................................. ................................................................................................................................. ................................................................................................................................. ................................................................................................................................. ................................................................................................................................. ................................................................................................................................. [5]

Mark scheme: 9(a) To ensure that the attributes are only accessible using the class’s own methods/within the class. 1 9(b) One mark per mark point (Max 5) 5 MP1 Two correct attributes with sensible names and correct data types. MP2 Constructor present. MP3 Two correct setters with exact names and appropriate parameters and data types. MP4 Two correct getters with appropriate names. MP5 Name assigned to pet name getter matches the attribute. Pet PetID : STRING PetType : STRING OwnerTelephone : STRING DateRegistered : DATE PetName : STRING OwnerName : STRING Constructor() SetPetID(APetID : STRING) SetDateRegistered(RegDate : DATE) GetPetName() GetOwnerTelephone()

10 Several syntax diagrams are shown. letter operator A + E – I * O / U digit 0 Y 1 symbol # 2 $ 3 ? 4 & 5 @ 6 7 8 9 label letter digit digit equation label = label operator label (a) Complete the Backus-Naur Form (BNF) for the given syntax diagrams. <operator> ::= .................................................................................................................. ................................................................................................................................................... <label> ::= ......................................................................................................................... ................................................................................................................................................... <equation> ::= .................................................................................................................. ................................................................................................................................................... [4] (b) A new syntax rule, password, is required. It must begin with a letter or a symbol, followed by a digit and end with one or two symbols. (i) Draw a syntax diagram for password. [3] (ii) Write the BNF for password. ........................................................................................................................................... ........................................................................................................................................... ........................................................................................................................................... ..................................................................................................................................... [2]

Mark scheme: 10(a) One mark per mark point (Max 4) 4 • <operator> ::= + | – | * | / • <label> ::= <letter><digit>|<letter><digit><digit> • <equation> ::= <label> = • <label><operator><label> 10(b)(i) One mark per mark point (Max 3) 3 MP1 begin with either a letter or a symbol MP2 end with either one or two symbols MP3 digit and all other connections and label correct. password letter digit symbol symbol symbol 10(b)(ii) One mark per mark point (Max 2) 2 • <password> ::= <letter><digit><symbol>| • <letter><digit><symbol><symbol>|<symbol><digit><symbol>| <symbol><digit><symbol><symbol> <password> ::= <letter><digit><symbol>| <letter><digit><symbol><symbol>|<symbol><digit><symbol>| <symbol><digit><symbol><symbol> Alternative Answer One mark per mark point (Max 2) • All three lines correct • Any two lines correct <first> ::= <letter>|<symbol> <last> ::= <symbol>|<symbol><symbol> <password> ::= <first><digit><last>

11 The following diagram shows an ordered binary tree. Red Green Yellow Blue Orange Violet Indigo (a) A linked list of nodes is used to store the data. Each node consists of a left pointer, the data and a right pointer. –1 is used to represent a null pointer. Complete this linked list to represent the given binary tree. RootPtr LeftPtr Data RightPtr Red Green –1 Blue –1 [4] (b) A user-defined record structure is used to store the nodes of the linked list in part (a). Complete the diagram, using your answer for part (a). RootPtr Index LeftPtr Data RightPtr 0 0 Red 1 Green 2 Yellow 3 Blue 4 Orange 5 Indigo FreePtr 6 Violet 7 [4] (c) The linked list in part (a) is implemented using a 1D array of records. Each record contains a left pointer, data and a right pointer. The following pseudocode represents a function that searches for an element in the array of records BinTree. It returns the index of the record if the element is found, or it returns a null pointer if the element is not found. Complete the pseudocode for the function. FUNCTION SearchTree(Item : STRING) ........................................................................ NowPtr ......................................................................................................................... WHILE NowPtr <> -1 IF ..................................................................................................................... THEN NowPtr BinTree[NowPtr].LeftPtr ELSE IF BinTree[NowPtr].Data < Item THEN ......................................................................................................................... ELSE RETURN NowPtr ENDIF ENDIF ENDWHILE RETURN NowPtr ENDFUNCTION [4]

Mark scheme: 11(a) One mark per mark point (Max 4) 4 MP1 Four additional nodes with correct data values MP2 Correct null pointers in all added nodes (6) with no extra null pointers where the arrow points to the next node MP3 Correct arrows to represent pointers joining parent nodes to child nodes MP4 All nodes in correct order and no extra data added to pointers. RootPtr LeftPtr Data RightPtr Red Green Yellow -1 -1 Blue -1 Orange -1 -1 Indigo -1 -1 Violet -1 11(b) One mark per mark point (Max 4) 4 MP1 Correct Red and Green rows MP2 Correct Yellow and Blue rows MP3 Correct Orange, Indigo and Violet rows MP4 Correct FreePtr with blank row 7 RootPt RightPt Index LeftPtr Data r r 0 0 1 Red 2 1 3 Green 4 2 6 Yellow -1 3 -1 Blue -1 4 5 Orange -1 5 -1 Indigo -1 FreePt 6 -1 Violet -1 r 7 7 11(c) One mark for any correct row (Max 4) 4 FUNCTION SearchTree(Item : STRING) RETURNS INTEGER NowPtr  RootPtr WHILE NowPtr <> -1 IF BinTree[NowPtr].Data > Item THEN NowPtr  BinTree[NowPtr].LeftPtr ELSE IF BinTree[NowPtr].Data < Item THEN NowPtr  BinTree[NowPtr].RightPtr ELSE RETURN NowPtr ENDIF ENDIF ENDWHILE RETURN NowPtr ENDFUNCTION