Computational thinking and problem-solving

8(a) One mark for each correct marking point (Max 2) 2 • The initial order of the data • The number of data items to be sorted • The efficiency of the sorting algorithm © UCLES 2021 Page 8 of 10 8(b) One mark for each marking point (max 6) 6 MP1 Use of FOR loop to cycle through the whole year group MP2 Temporary storage of the score being ‘inserted’ MP3 Temporary storage of the corresponding name elements MP4 Use of WHILE loop with correct exit clause MP5 Moving of all three elements of data to next array elements MP6 Correct updating of counter variable MP7 Final insertion of all three data elements Example algorithm YearSize ← 249 FOR Student ← 2 to YearSize Temp1 ← Score[Student] Temp2 ← Name[Student,1] Temp3 ← Name[Student,2] Counter ← Student WHILE Counter > 1 AND Score[Counter - 1] < Temp1 Score[Counter] ← Score[Counter - 1] Name[Counter,1] ← Name[Counter - 1,1] Name[Counter,2] ← Name[Counter - 1,2] Counter ← Counter – 1 ENDWHILE Score[Counter] ← Temp1 Name[Counter,1] ← Temp2 Name[Counter,2] ← Temp3 NEXT Student Question Answer Marks

8(a) One mark for each correct marking point (Max 2) 2 • The initial order of the data • The number of data items to be sorted • The efficiency of the sorting algorithm © UCLES 2021 Page 8 of 10 8(b) One mark for each marking point (max 6) 6 MP1 Use of FOR loop to cycle through the whole year group MP2 Temporary storage of the score being ‘inserted’ MP3 Temporary storage of the corresponding name elements MP4 Use of WHILE loop with correct exit clause MP5 Moving of all three elements of data to next array elements MP6 Correct updating of counter variable MP7 Final insertion of all three data elements Example algorithm YearSize ← 249 FOR Student ← 2 to YearSize Temp1 ← Score[Student] Temp2 ← Name[Student,1] Temp3 ← Name[Student,2] Counter ← Student WHILE Counter > 1 AND Score[Counter - 1] < Temp1 Score[Counter] ← Score[Counter - 1] Name[Counter,1] ← Name[Counter - 1,1] Name[Counter,2] ← Name[Counter - 1,2] Counter ← Counter – 1 ENDWHILE Score[Counter] ← Temp1 Name[Counter,1] ← Temp2 Name[Counter,2] ← Temp3 NEXT Student Question Answer Marks

8(a) One mark for each correct marking point (Max 2) 2 • The initial order of the data • The number of data items to be sorted • The efficiency of the sorting algorithm © UCLES 2021 Page 8 of 10 8(b) One mark for each marking point (max 6) 6 MP1 Use of FOR loop to cycle through the whole year group MP2 Temporary storage of the score being ‘inserted’ MP3 Temporary storage of the corresponding name elements MP4 Use of WHILE loop with correct exit clause MP5 Moving of all three elements of data to next array elements MP6 Correct updating of counter variable MP7 Final insertion of all three data elements Example algorithm YearSize ← 249 FOR Student ← 2 to YearSize Temp1 ← Score[Student] Temp2 ← Name[Student,1] Temp3 ← Name[Student,2] Counter ← Student WHILE Counter > 1 AND Score[Counter - 1] < Temp1 Score[Counter] ← Score[Counter - 1] Name[Counter,1] ← Name[Counter - 1,1] Name[Counter,2] ← Name[Counter - 1,2] Counter ← Counter – 1 ENDWHILE Score[Counter] ← Temp1 Name[Counter,1] ← Temp2 Name[Counter,2] ← Temp3 NEXT Student Question Answer Marks

10(a) One mark for each correct marking point (Max 3) 3 • Must have a base case/stopping condition • Must have a general case • … which calls itself (recursively) // Defined in terms of itself • … which changes its state and moves towards the base case Unwinding can occur once the base case is reached. 10(b) One mark for each correct marking point (Max 3) 3 • A stack is a LIFO data structure • Each recursive call is pushed onto the stack • …. and is then popped as the function ends • Enables backtracking/unwinding … to maintain the required order. 10(c) One mark for each marking point (Max 2) 2 • Linked List • Queue Binary Tree 10(d) One mark for each marking point (Max 5) 5 • Checking if stack is full / empty using IF … THEN … (ELSE) … ENDIF • … correctly using StackFull() function • RETURN suitable message if stack is full • RETURN message if space available on stack • Incrementing TopOfStack pointer if space available • Assigning new data using correct NewInteger variable • … to correct the array element in ArrayStack[] array. Example algorithm FUNCTION AddInteger(NewInteger : INTEGER) RETURNS STRING IF StackFull() THEN RETURN "The stack is full" ELSE TopOfStack ← TopOfStack + 1 ArrayStack[TopOfStack] ← NewInteger RETURN "Item added" ENDIF ENDFUNCTION © UCLES 2021 Page 10 of 10

10(a) One mark for each correct marking point (Max 3) 3 • Must have a base case/stopping condition • Must have a general case • … which calls itself (recursively) // Defined in terms of itself • … which changes its state and moves towards the base case Unwinding can occur once the base case is reached. 10(b) One mark for each correct marking point (Max 3) 3 • A stack is a LIFO data structure • Each recursive call is pushed onto the stack • …. and is then popped as the function ends • Enables backtracking/unwinding … to maintain the required order. 10(c) One mark for each marking point (Max 2) 2 • Linked List • Queue Binary Tree 10(d) One mark for each marking point (Max 5) 5 • Checking if stack is full / empty using IF … THEN … (ELSE) … ENDIF • … correctly using StackFull() function • RETURN suitable message if stack is full • RETURN message if space available on stack • Incrementing TopOfStack pointer if space available • Assigning new data using correct NewInteger variable • … to correct the array element in ArrayStack[] array. Example algorithm FUNCTION AddInteger(NewInteger : INTEGER) RETURNS STRING IF StackFull() THEN RETURN "The stack is full" ELSE TopOfStack ← TopOfStack + 1 ArrayStack[TopOfStack] ← NewInteger RETURN "Item added" ENDIF ENDFUNCTION © UCLES 2021 Page 10 of 10

8(a) INTEGER 4

12(a) One mark for each point (Max 6) 6 • Initialisation of upper bound • Test if upper bound is less than lower bound • Re-setting of mid value if current value is lower than the target • Re-setting of mid value if current value is higher than the target • Finding the value • Correct termination of loop Lower  0 Upper  99 Mid  0 Exit  FALSE OUTPUT "Enter the name to be found " INPUT Target REPEAT IF Upper < Lower THEN OUTPUT Target, " does not exist" Exit  TRUE ENDIF Mid  Lower + (Upper – Lower + 1) DIV 2 IF Names[Mid] < Target THEN Lower  Mid + 1 ENDIF IF Names[Mid] > Target THEN Upper  Mid - 1 ENDIF IF Names[Mid] = Target THEN OUTPUT Target, " was found at location ", Mid Exit  TRUE ENDIF UNTIL Exit // UNTIL Exit = TRUE 12(b)(i) O(n) 1 © UCLES 2022 Page 14 of 15 12(b)(ii) One mark for each point (Max 2) 2 • O(log n) is a time complexity that uses logarithmic time. • The time taken goes up linearly as the number of items rises exponentially • O(log n) is the worst case scenario (time complexity for a binary search). © UCLES 2022 Page 15 of 15

11(a) One mark for each point 3 • Correct HeadPointer • Any three correct NextPointer • All six NextPointer correct HeadPointer 5 Index Flower NextPointer 1 Rose 0 2 Marigold 3 Foxglove 4 4 Iris 9 5 Daisy 3 6 Dahlia 7 Saxifrage 8 Lupin 1 9 Lily 8 10 Hydrangea © UCLES 2022 Page 15 of 16 11(b) One mark for each correct line 5 Pointer  HeadPointer Found  0 OUTPUT "Enter a flower name " INPUT FlowerName WHILE Pointer <> 0 IF Flower[Pointer] = FlowerName THEN Found  Pointer Pointer  0 ELSE Pointer  NextPointer[Pointer] ENDIF ENDWHILE IF Pointer = 0 THEN // IF Found <> 0 THEN OUTPUT Flower[Found], " is found" ELSE OUTPUT "The flower you wanted is not in the list" ENDIF 11(c) One mark for each point (Max 2) 2 • Include a free list pointer • …to reuse the unused space • …as a linked list of free space. © UCLES 2022 Page 16 of 16

12(a) One mark for each point (Max 6) 6 • Initialisation of upper bound • Test if upper bound is less than lower bound • Re-setting of mid value if current value is lower than the target • Re-setting of mid value if current value is higher than the target • Finding the value • Correct termination of loop Lower  0 Upper  99 Mid  0 Exit  FALSE OUTPUT "Enter the name to be found " INPUT Target REPEAT IF Upper < Lower THEN OUTPUT Target, " does not exist" Exit  TRUE ENDIF Mid  Lower + (Upper – Lower + 1) DIV 2 IF Names[Mid] < Target THEN Lower  Mid + 1 ENDIF IF Names[Mid] > Target THEN Upper  Mid - 1 ENDIF IF Names[Mid] = Target THEN OUTPUT Target, " was found at location ", Mid Exit  TRUE ENDIF UNTIL Exit // UNTIL Exit = TRUE 12(b)(i) O(n) 1 © UCLES 2022 Page 14 of 15 12(b)(ii) One mark for each point (Max 2) 2 • O(log n) is a time complexity that uses logarithmic time. • The time taken goes up linearly as the number of items rises exponentially • O(log n) is the worst case scenario (time complexity for a binary search). © UCLES 2022 Page 15 of 15

11(a) One mark per mark point (Max 3) 3  correctly defined constant  correctly defined array  three correctly defined integers CONSTANT MaxSize = 60 DECLARE Queue : ARRAY[1:60] OF STRING // DECLARE Queue : ARRAY[0:59] OF STRING // DECLARE Queue : ARRAY[1:MaxSize] OF STRING // DECLARE Queue : ARRAY[0:MaxSize - 1] OF STRING DECLARE FrontPointer : INTEGER DECLARE RearPointer : INTEGER DECLARE Length : INTEGER © UCLES 2023 Page 8 of 10 11(b) One mark for each correctly completed line (Max 4) 4 FUNCTION Dequeue RETURNS STRING DECLARE Item : STRING IF Length > 0 THEN Item  Queue[FrontPointer] FrontPointer  FrontPointer + 1 Length  Length – 1 IF Length = 0 THEN CALL Initialise // procedure to reset the pointers ELSE IF FrontPointer > MaxSize THEN FrontPointer  1 ENDIF ENDIF ELSE OUTPUT "The print queue was empty – error" Item  "" ENDIF RETURN Item ENDFUNCTION 11(c) One mark per mark point (Max 4) 4 MP1 (Two stacks are required) so that the second stack can reverse the order of the first stack. MP2 Stack 1 operates as the queue with the newest elements at the bottom. Stack 2 is empty. MP3 To add an element, pop all the elements from stack 1 and push onto stack 2. MP4 Push the new element onto either stack. MP5 Pop all the elements of stack 2 back onto stack 1. Question Answer Marks

12(a) One mark per mark point (Max 2) 2  A process using a function or procedure defined in terms of itself / calls itself.  A recursive process must have a base case (which is a way to return without making a recursive call) // terminating solution // concept of unwinding described  There must (also) be a general case where the recursive call takes place. © UCLES 2023 Page 9 of 10 12(b) One mark per mark point (Max 5) 5  Call number column correct  Function call and Number columns correct  Result column down to base case (Winding) rows 1–6 correct  Result column down from base case (Unwinding) rows 7–10 correct  Return value column correct Call Function call Number Result Return number value 1 Fib(5) 5 Fib(4) + Fib(3) 2 Fib(4) 4 Fib(3) + Fib(2) 3 Fib(3) 3 Fib(2) + Fib(1) 4 Fib(2) 2 Fib(1) + Fib(0) 5 Fib(1) 1 1 1 6 Fib(0) 0 0 0 (4) Fib(2) 2 1 + 0 1 (3) Fib(3) 3 1 + 1 2 (2) Fib(4) 4 2 + 1 3 (1) Fib(5) 5 3 + 2 5 © UCLES 2023 Page 10 of 10

11(a)(i) One mark for every two correct identifiers (Max 2) 2 Identifier Data type Description Queue STRING An array to store the contents of the queue. RearPointer INTEGER Points to the last term of the queue. Length INTEGER Indicates the number of items in the queue. FrontPointer INTEGER Points to the first term of the queue. 11(a)(ii) One mark for each correctly completed line (Max 5) 5 CONSTANT MaxLength = 50 DECLARE FrontPointer : INTEGER DECLARE RearPointer : INTEGER DECLARE Length : INTEGER DECLARE Queue : ARRAY[0:MaxLength – 1] OF STRING // Initialisation of queue PROCEDURE Initialise FrontPointer  -1 RearPointer  -1 Length  0 ENDPROCEDURE // Adding a new item to the queue PROCEDURE Enqueue(NewItem : STRING) IF Length < MaxLength THEN // IF Length <= MaxLength - 1 THEN RearPointer  RearPointer + 1 IF RearPointer > MaxLength – 1 THEN RearPointer  0 ENDIF Queue[RearPointer]  NewItem Length  Length + 1 ENDIF ENDPROCEDURE 11(b) One mark per mark point (Max 3) 3  Print jobs are expected to be actioned by the printer in the order they are received  … because the printer queue is a queue, the first job to be sent to the printer would be the first job printed.  If the printer queue was on a stack, the first job the printer received would not be printed until all the other jobs have been printed. © UCLES 2023 Page 12 of 12

11(a) One mark per mark point (Max 3) 3  correctly defined constant  correctly defined array  three correctly defined integers CONSTANT MaxSize = 60 DECLARE Queue : ARRAY[1:60] OF STRING // DECLARE Queue : ARRAY[0:59] OF STRING // DECLARE Queue : ARRAY[1:MaxSize] OF STRING // DECLARE Queue : ARRAY[0:MaxSize - 1] OF STRING DECLARE FrontPointer : INTEGER DECLARE RearPointer : INTEGER DECLARE Length : INTEGER © UCLES 2023 Page 8 of 10 11(b) One mark for each correctly completed line (Max 4) 4 FUNCTION Dequeue RETURNS STRING DECLARE Item : STRING IF Length > 0 THEN Item  Queue[FrontPointer] FrontPointer  FrontPointer + 1 Length  Length – 1 IF Length = 0 THEN CALL Initialise // procedure to reset the pointers ELSE IF FrontPointer > MaxSize THEN FrontPointer  1 ENDIF ENDIF ELSE OUTPUT "The print queue was empty – error" Item  "" ENDIF RETURN Item ENDFUNCTION 11(c) One mark per mark point (Max 4) 4 MP1 (Two stacks are required) so that the second stack can reverse the order of the first stack. MP2 Stack 1 operates as the queue with the newest elements at the bottom. Stack 2 is empty. MP3 To add an element, pop all the elements from stack 1 and push onto stack 2. MP4 Push the new element onto either stack. MP5 Pop all the elements of stack 2 back onto stack 1. Question Answer Marks

12(a) One mark per mark point (Max 2) 2  A process using a function or procedure defined in terms of itself / calls itself.  A recursive process must have a base case (which is a way to return without making a recursive call) // terminating solution // concept of unwinding described  There must (also) be a general case where the recursive call takes place. © UCLES 2023 Page 9 of 10 12(b) One mark per mark point (Max 5) 5  Call number column correct  Function call and Number columns correct  Result column down to base case (Winding) rows 1–6 correct  Result column down from base case (Unwinding) rows 7–10 correct  Return value column correct Call Function call Number Result Return number value 1 Fib(5) 5 Fib(4) + Fib(3) 2 Fib(4) 4 Fib(3) + Fib(2) 3 Fib(3) 3 Fib(2) + Fib(1) 4 Fib(2) 2 Fib(1) + Fib(0) 5 Fib(1) 1 1 1 6 Fib(0) 0 0 0 (4) Fib(2) 2 1 + 0 1 (3) Fib(3) 3 1 + 1 2 (2) Fib(4) 4 2 + 1 3 (1) Fib(5) 5 3 + 2 5 © UCLES 2023 Page 10 of 10

10(a) One mark per mark point (Max 3) 3 MP1 Correct constant declaration MP2 Two correct variable declarations MP3 Correct array declaration Example answer: CONSTANT Capacity = 25 DECLARE BasePointer : INTEGER DECLARE TopPointer : INTEGER DECLARE Stack : ARRAY[1:25] OF REAL 10(b) One mark for each correctly completed line (Max 5) 5 // popping an item from the stack FUNCTION Pop() RETURNS REAL DECLARE Item : REAL Item  0 IF TopPointer >= BasePointer THEN Item  Stack[TopPointer] TopPointer  TopPointer – 1 ELSE OUTPUT "The stack is empty – error" ENDIF RETURN Item ENDFUNCTION 10(c) One mark per mark point (Max 2) 2 MP1 A queue is a first in first out / FIFO data structure and a stack is a first in last out / FILO / LIFO data structure // Data is removed from a queue in the order it is received and removed from a stack in the reverse order to which it is received MP2 Both ADTs can vary in size / are of indeterminate length MP3 Data is popped and pushed (onto/from a stack) at the same end but it is enqueued and dequeued (to/from a queue) at different/opposite ends // a queue has two accessible ends and a stack has only one MP4 A stack has only one moveable pointer whereas a queue has two. Question Answer Marks

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 © UCLES 2023 Page 6 of 9 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. © UCLES 2023 Page 7 of 9

10(a) One mark per mark point (Max 3) 3 MP1 Correct constant declaration MP2 Two correct variable declarations MP3 Correct array declaration Example answer: CONSTANT Capacity = 25 DECLARE BasePointer : INTEGER DECLARE TopPointer : INTEGER DECLARE Stack : ARRAY[1:25] OF REAL 10(b) One mark for each correctly completed line (Max 5) 5 // popping an item from the stack FUNCTION Pop() RETURNS REAL DECLARE Item : REAL Item  0 IF TopPointer >= BasePointer THEN Item  Stack[TopPointer] TopPointer  TopPointer – 1 ELSE OUTPUT "The stack is empty – error" ENDIF RETURN Item ENDFUNCTION 10(c) One mark per mark point (Max 2) 2 MP1 A queue is a first in first out / FIFO data structure and a stack is a first in last out / FILO / LIFO data structure // Data is removed from a queue in the order it is received and removed from a stack in the reverse order to which it is received MP2 Both ADTs can vary in size / are of indeterminate length MP3 Data is popped and pushed (onto/from a stack) at the same end but it is enqueued and dequeued (to/from a queue) at different/opposite ends // a queue has two accessible ends and a stack has only one MP4 A stack has only one moveable pointer whereas a queue has two. Question Answer Marks

10(a) One mark 1 The elements are sorted according to the compare function / in ascending / descending order. 10(b) One mark for each correctly completed line (Max 5) 5 DECLARE Names : ARRAY[1:100000] OF STRING DECLARE TopOfList : INTEGER DECLARE EndOfList : INTEGER DECLARE CurrentItem : INTEGER DECLARE ToFind : STRING DECLARE Found : BOOLEAN DECLARE NotInList : BOOLEAN TopOfList  1 EndOfList  100000 OUTPUT "Which name do you wish to find? " INPUT ToFind Found  FALSE NotInList  FALSE WHILE Found = FALSE AND NotInList = FALSE CurrentItem  (TopOfList + EndOfList) DIV 2 IF ToFind = Names[CurrentItem]// Names[CurrentItem] = ToFind THEN Found  TRUE ELSE IF TopOfList >= EndOfList THEN NotInList  TRUE ELSE IF ToFind > Names[CurrentItem] THEN TopOfList  CurrentItem + 1 ELSE EndOfList  CurrentItem – 1 ENDIF ENDIF ENDIF ENDWHILE © Cambridge University Press & Assessment 2024 Page 12 of 14 10(b) IF Found = TRUE THEN OUTPUT "Item found at position ", CurrentItem, " in array" ELSE OUTPUT "Item not in array" ENDIF 10(c) One mark from 2 MP1 Big O for a binary search is O(Log n). 2 MP2 Big O notation is used to indicate the time/space complexity of an algorithm. One mark from MP3 The time taken to complete the search increases logarithmically as the number of search items increases linearly MP4 The time taken to complete the search increases linearly as the number of search items increases exponentially MP5 As the search field is repeatedly getting smaller, the number of comparisons made before the item is found, or the number of items runs out, is relatively small. © Cambridge University Press & Assessment 2024 Page 13 of 14

8(a) One mark for each correctly completed line (Max 4) 4 DECLARE Widgets : ARRAY[1:50000] OF STRING DECLARE TopOfList : INTEGER DECLARE EndOfList : INTEGER DECLARE Count : INTEGER DECLARE ToFind : STRING DECLARE Found : BOOLEAN DECLARE NotInList : BOOLEAN TopOfList  1 EndOfList  50000 OUTPUT "Enter the name of the item you wish to find " INPUT ToFind Found  FALSE NotInList  FALSE Count  TopOfList WHILE Found = FALSE AND NotInList = FALSE // Count <= EndOfList IF ToFind = Widgets[Count] // Widgets[Count] = ToFind THEN Found  TRUE ENDIF Count  Count + 1 IF Found = FALSE AND Count > EndOfList THEN NotInList  TRUE ENDIF ENDWHILE IF Found = TRUE THEN OUTPUT "Item found at position ", Count - 1, " in array" ELSE OUTPUT "Item not in array" ENDIF © Cambridge University Press & Assessment 2024 Page 10 of 14 8(b) Max 4 4 One mark per mark point (Max 3) MP1 Linear search sequentially checks each element of the array / list. MP2 … until the matching element is found, or the end of the array / list is reached. MP3 Binary search finds the mid-point of an array/list and determines which side contains the item to be found MP4 … it discards the half of the array/list not containing the search item // … it finds the position of a target value within an array / list by repeatedly halving the target search field. MP5 The binary search requires the elements to be sorted // The linear search does not require the elements to be sorted. MP6 The binary search will usually do many fewer comparisons of records/iterations against the target than a linear search before it finds its target. MP7 Linear search starts at the beginning of the array/list and binary search starts in the middle of the array/list. One mark per mark point (Max 2) MP8 Big O for binary search is O (Log n) 2 MP9 Big O for linear search is O (n) MP10 Big O notation is used to indicate the time / space complexity of an algorithm © Cambridge University Press & Assessment 2024 Page 11 of 14

10(a) One mark 1 The elements are sorted according to the compare function / in ascending / descending order. 10(b) One mark for each correctly completed line (Max 5) 5 DECLARE Names : ARRAY[1:100000] OF STRING DECLARE TopOfList : INTEGER DECLARE EndOfList : INTEGER DECLARE CurrentItem : INTEGER DECLARE ToFind : STRING DECLARE Found : BOOLEAN DECLARE NotInList : BOOLEAN TopOfList  1 EndOfList  100000 OUTPUT "Which name do you wish to find? " INPUT ToFind Found  FALSE NotInList  FALSE WHILE Found = FALSE AND NotInList = FALSE CurrentItem  (TopOfList + EndOfList) DIV 2 IF ToFind = Names[CurrentItem]// Names[CurrentItem] = ToFind THEN Found  TRUE ELSE IF TopOfList >= EndOfList THEN NotInList  TRUE ELSE IF ToFind > Names[CurrentItem] THEN TopOfList  CurrentItem + 1 ELSE EndOfList  CurrentItem – 1 ENDIF ENDIF ENDIF ENDWHILE © Cambridge University Press & Assessment 2024 Page 12 of 14 10(b) IF Found = TRUE THEN OUTPUT "Item found at position ", CurrentItem, " in array" ELSE OUTPUT "Item not in array" ENDIF 10(c) One mark from 2 MP1 Big O for a binary search is O(Log n). 2 MP2 Big O notation is used to indicate the time/space complexity of an algorithm. One mark from MP3 The time taken to complete the search increases logarithmically as the number of search items increases linearly MP4 The time taken to complete the search increases linearly as the number of search items increases exponentially MP5 As the search field is repeatedly getting smaller, the number of comparisons made before the item is found, or the number of items runs out, is relatively small. © Cambridge University Press & Assessment 2024 Page 13 of 14

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 © Cambridge University Press & Assessment 2024 Page 15 of 17 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 © Cambridge University Press & Assessment 2024 Page 16 of 17 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 © Cambridge University Press & Assessment 2024 Page 17 of 17

11(a) One mark per mark point (Max 4) 4 MP1 Five additional nodes with correct data values MP2 Correct null pointers in all nodes (7) – no extra null pointers where the arrow points to the next node MP3 Correct arrows to represent pointers joining parent nodes to child nodes – must come from the correct left or right pointer not the middle MP4 All nodes in correct order and no additional data in left/right pointer boxes. RootPtr LeftPtr Data RightPtr 25 4 -1 36 -1 1 -1 16 -1 64 -1 -1 9 -1 -1 49 -1 © Cambridge University Press & Assessment 2024 Page 13 of 15 11(b) First eight rows of table (Max 3) 4 Three marks for all eight correct rows Two marks for six or seven correct rows One mark for three, four or five correct rows Last row of table and FreePtr (Max 1) One mark for correct FreePtr with last row of table completely blank RootPt RightP Index LeftPtr Data r tr 0 0 1 25 2 1 3 4 4 2 -1 36 5 3 -1 1 -1 4 6 16 -1 5 7 64 -1 FreePt 6 -1 9 -1 r 8 7 -1 49 -1 8 © Cambridge University Press & Assessment 2024 Page 14 of 15 11(c) One mark for any correct row (Max 4) 4 FUNCTION SearchList(Item : INTEGER) RETURNS INTEGER NullPtr  -1 NowPtr  RootPtr WHILE NowPtr <> NullPtr IF LinkList[NowPtr].Data < Item THEN NowPtr  LinkList[NowPtr].RightPtr ELSE IF LinkList[NowPtr].Data > Item THEN NowPtr  LinkList[NowPtr].LeftPtr ELSE RETURN NowPtr ENDIF ENDIF ENDWHILE RETURN NullPtr ENDFUNCTION © Cambridge University Press & Assessment 2024 Page 15 of 15

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 © Cambridge University Press & Assessment 2024 Page 15 of 17 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 © Cambridge University Press & Assessment 2024 Page 16 of 17 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 © Cambridge University Press & Assessment 2024 Page 17 of 17

4(a) One mark per mark point 4 MP1 Any two nodes added correctly with correct data (6, 15, 41, 66) and arrows MP2 Remaining two nodes added with correct data (6, 15, 41, 66) and all nodes with connecting arrows starting from pointer boxes MP3 Correct null pointers (-1) added throughout MP4 … with no entries in other pointer boxes and all nodes correctly positioned and connected Root pointer Left pointer Data Right pointer 36 12 -1 40 -1 3 -1 15 -1 -1 41 -1 6 -1 -1 66 -1 © Cambridge University Press & Assessment 2025 Page 9 of 15 4(b) One mark per mark point 2 MP1 A technique used to solve problems using a function/procedure/subroutine that calls itself (general case) MP2 … until the terminating condition / base case is achieved, when no further recursive calls are made 4(c) One mark 1 • Stack Question Answer Marks

11(a) One mark per mark point 4 MP1 Any two nodes added correctly with correct data (Aa, Mm, Ss, Xx) MP2 Remaining two nodes added with correct data (Aa, Mm, Ss, Xx) and all nodes with connecting arrows starting from correct pointer boxes MP3 Correct null pointers (0) added throughout MP4 … with no entries in other pointer boxes and all nodes correctly positioned and connected. Root pointer Pp Gg 0 Rr 0 Aa 0 0 Kk 0 Ss 0 Mm 0 0 Xx 0 © Cambridge University Press & Assessment 2025 Page 10 of 12 11(b) One mark for feature and one mark for example (Max 2) 2 • Recursion is beneficial for algorithms when a problem naturally breaks down into smaller versions of itself. • … such as calculating a factorial / mathematical series / Fibonacci / compound interest / tree traversal / evaluation of RPN expressions. Question Answer Marks

12(a) One mark for any two correct ADTs (Max 1) 1 • Binary tree • Graph • Linked list • Queue • Stack 12(b) One mark for each marking point (Max 4) 4 MP1 Temporary assignment of the element being ‘inserted’ before inner loop MP2 Appropriate inner loop MP3 Check if current DataArray content is > Value MP4 Moving data to adjacent element as required MP5 Appropriate updating of Position variable MP6 Re-insertion of the element outside the inner loop Example algorithm FOR Index  2 to 1000 Value  DataArray[Index] Position  Index – 1 IF DataArray[Position] > Value THEN WHILE Position >= 1 AND DataArray[Position] > Value DataArray[Position + 1]  DataArray[Position] Position  Position – 1 ENDWHILE DataArray[Position + 1]  Value ENDIF NEXT Index 12(c) One mark for each marking point 2 MP1 The performance of a sorting routine should improve if the data is already partially sorted // The performance of a sorting routine is likely to be worse if the data is completely out of order MP2 The sort may take longer if the number of items to be sorted is larger // The sort may take less time if the number of items to be sorted is fewer. © Cambridge University Press & Assessment 2025 Page 15 of 16

13 One mark for each marking point 4 MP1 Correct Index and Target columns MP2 Correct Numbers[5] column MP3 Correct Numbers[6] and Numbers[7] columns MP4 Correct Numbers[8] column and no incorrect data added to any other of columns [1, 2, 3, 4, 9, 10] Numbers Index Target [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] 1 15 2 3 7 11 15 17 19 23 0 0 2 3 4 5 17 6 19 7 23 8 0 9 © Cambridge University Press & Assessment 2025 Page 16 of 16

9(a)(i) One mark for each correctly completed line (Max 5) 5 FUNCTION Pop() RETURNS STRING DECLARE DataItem : STRING DataItem  "" IF Top > –1 // Top >= Base THEN DataItem  StackArray[Top] Top  Top – 1 ELSE DataItem  "You cannot remove data; the stack is empty" ENDIF RETURN DataItem // StackArray[Top + 1] ENDFUNCTION © Cambridge University Press & Assessment 2025 Page 13 of 15 9(a)(ii) OUTPUT "The data removed from the stack is ", Pop() 1 9(b) One mark per mark point (Max 3) 3 MP1 A recursive algorithm must call itself / have a general case MP2 It must have a base case / have a stopping condition MP3 It must change its state and move towards the base case Question Answer Marks Guidance

12(a)(i) One mark for each correctly completed line (Max 4) 4 PROCEDURE Push(NewData : STRING) IF Top < Max – 1 THEN Top  Top + 1 StackArray[Top]  NewData ELSE OUTPUT "Stack full; new data cannot be added" ENDIF ENDPROCEDURE 12(a)(ii) One mark per mark point (Max 2) 2 MP1 Input with variable, with or without prompt MP2 Procedure call for Push with parameter used matching input variable Example answer INPUT MyData CALL Push(MyData) 12(b) One mark per mark point (Max 3) 3 MP1 Stacks store data in Last In First Out (LIFO) / First In Last Out (FILO) order MP2 Each time a recursive algorithm calls itself data is pushed onto the stack MP3 When the recursive algorithm reaches its base case / starts to unwind MP4 … data is popped from the stack in the reverse order to which it was pushed onto it. © Cambridge University Press & Assessment 2025 Page 17 of 17

10(a) One mark per mark point (Max 3) 3 MP1 Correct declaration of constant Maximum MP2 Both correctly declared integers MP3 Correct array declaration Example answer CONSTANT Maximum = 100 DECLARE Base : INTEGER DECLARE Top : INTEGER DECLARE StackArray : ARRAY[1:100] OF STRING 10(b) One mark per mark point (Max 3) 3 MP1 Correct procedure definition structure MP2 Base pointer with appropriate value (0 or 1) MP3 Top pointer with appropriate value (–1, 0, 1) Example answer PROCEDURE InitialiseStack() Base  0 Top  0 ENDPROCEDURE Question Answer Marks Guidance

11 One mark per mark point (Max 3) 3 MP1 Recursion is beneficial for problems that can be broken down into smaller, repetitive problems MP2 … especially for problems that have many possible branches / are too complex for an iterative approach MP3 An example e.g. solving mathematical series, sorting a pile of documents, etc. © Cambridge University Press & Assessment 2025 Page 13 of 16