Introduction to Abstract Data Types (ADT) — Paper 2 · A Level Computer Science 9618

6 The following diagram represents an Abstract Data Type (ADT) for a linked list. A C D E Ø The free list is as follows: Ø (a) Explain how a node containing data value B is added to the list in alphabetic sequence. … … … … … … … [4] (b) Describe how the linked list in part (a) may be implemented using variables and arrays. … … … … [2]

6 marks

Mark scheme: 6(a) One mark per point: 4 1 Check for a free node 2 Search for correct insertion point 3 Assign data value B to first node in free list / node pointed to by start pointer of free list 4 Pointer from A will be changed to point to node containing B (instead of C) 5 Pointer from B will be changed to point to node containing C 6 Start pointer in free list moved to point to next free node Note: max 4 marks 6(b) One mark per point: 2 • An array (1D) to store the data and a second array (1D) to store the pointers • An (integer) variable to hold the start pointer and an (integer) variable to store the next free pointer ALTERNATIVE: • Define a record type comprising a data element and a pointer and declare an array (1D) of this type • An integer variable to hold the start pointer and an integer variable to store the next free pointer

This question in 9618/21 May/June 2021

3 The following diagram represents an Abstract Data Type (ADT). A B Dolphin Cat Fish Elk (a) Identify this type of ADT. … [1] (b) Give the technical term for the item labelled A in the diagram. … [1] (c) Give the technical term for the item labelled B in the diagram. Explain the meaning of the value given to this item. Term … Meaning … … … [2] (d) Complete the diagram to show the ADT after the data has been sorted in alphabetical order. Dolphin Cat Fish Elk [2]

6 marks

Mark scheme: 3(a) Linked list 1 3(b) Start pointer 1 3(c) One mark for each: 2 Name: Null pointer Meaning: There are no further nodes in the list 3(d) 2 One mark for: • Start Pointer pointing to ‘Cat’ node • Remaining arrows: Cat → Dolphin → Elk → Fish

This question in 9618/22 May/June 2021

6 The following diagram represents an Abstract Data Type (ADT) for a linked list. A C D E Ø The free list is as follows: Ø (a) Explain how a node containing data value B is added to the list in alphabetic sequence. … … … … … … … [4] (b) Describe how the linked list in part (a) may be implemented using variables and arrays. … … … … [2]

6 marks

Mark scheme: 6(a) One mark per point: 4 1 Check for a free node 2 Search for correct insertion point 3 Assign data value B to first node in free list / node pointed to by start pointer of free list 4 Pointer from A will be changed to point to node containing B (instead of C) 5 Pointer from B will be changed to point to node containing C 6 Start pointer in free list moved to point to next free node Note: max 4 marks 6(b) One mark per point: 2 • An array (1D) to store the data and a second array (1D) to store the pointers • An (integer) variable to hold the start pointer and an (integer) variable to store the next free pointer ALTERNATIVE: • Define a record type comprising a data element and a pointer and declare an array (1D) of this type • An integer variable to hold the start pointer and an integer variable to store the next free pointer

This question in 9618/23 May/June 2021

3 (a) The diagram below represents a queue Abstract Data Type (ADT) that can hold a maximum of eight items. The operation of this queue may be summarised as follows: • The front of queue pointer points to the next item to be removed. • The end of queue pointer points to the last item added. • The queue is circular so that empty storage elements can be reused. 0 Frog Front of queue pointer 1 Cat 2 Fish 3 Elk End of queue pointer 4 5 6 7 (i) Describe how “Octopus” is added to the given queue. … … … … [2] (ii) Describe how the next item in the given queue is removed and stored in the variable AnimalName. … … … … [2] (iii) Describe the state of the queue when the front of queue and the end of queue pointers have the same value. … … [1] (b) Some operations are carried out on the original queue given in part (a). (i) The current state of the queue is: 0 Frog 1 Cat 2 Fish 3 Elk 4 5 6 7 Complete the diagram to show the state of the queue after the following operations: Add “Wasp”, “Bee” and “Mouse”, and then remove two data items. [3] (ii) The state of the queue after other operations are carried out is shown: 0 Frog 1 Cat 2 Fish 3 Elk Front of queue pointer 4 Wasp 5 Bee 6 Mouse End of queue pointer 7 Ant Complete the following diagram to show the state of the queue after the following operations: Remove one item, and then add “Dolphin” and “Shark”. 0 1 2 3 4 5 6 7 [2] (c) The queue is implemented using a 1D array. Describe the algorithm that should be used to modify the end of queue pointer when adding an item to the queue. Your algorithm should detect any potential error conditions. … … … … … … [3]

13 marks

Mark scheme: 3(a)(i) One mark per point: 2 • EoQ pointer will move to point to location 4 // incremented EoQ (by 1) • Data value "Octopus" will be stored in location pointed to be EoQ / location 4 3(a)(ii) One mark for each bullet 2 • Value "Frog" // value pointed to by FoQ / location 0 is assigned to variable AnimalName • FoQ pointer will move to point to location 1 / point to "Cat" // incremented FoQ (by 1) 0 Frog ← Front of queue pointer 1 Cat 2 Fish 3 Elk ← End of queue pointer 3(a)(iii) There is only one data item in the queue 1 3(b)(i) One mark for data values plus one mark for pointers 3 0 Frog 1 Cat 2 Fish ← Front of queue pointer 3 Elk 4 Wasp 5 Bee 6 Mouse ← End of queue pointer 7 One mark for each pointer One mark for three new data values 3(b)(ii) 2 0 Shark ← End of queue pointer 1 (Cat) 2 (Fish) 3 (Elk) 4 Wasp ← Front of queue pointer 5 Bee 6 Mouse 7 Dolphin One mark for BOTH pointers One mark for all data values as shown 3(c) One mark per point: 3 1 If incremented EoQ = FoQ then error condition: queue is full 2 Increment the EoQ 3 Manage wrap-around

This question in 9618/21 Oct/Nov 2021

3 (a) The diagram below represents a queue Abstract Data Type (ADT) that can hold a maximum of eight items. The operation of this queue may be summarised as follows: • The front of queue pointer points to the next item to be removed. • The end of queue pointer points to the last item added. • The queue is circular so that empty storage elements can be reused. 0 Frog Front of queue pointer 1 Cat 2 Fish 3 Elk End of queue pointer 4 5 6 7 (i) Describe how “Octopus” is added to the given queue. … … … … [2] (ii) Describe how the next item in the given queue is removed and stored in the variable AnimalName. … … … … [2] (iii) Describe the state of the queue when the front of queue and the end of queue pointers have the same value. … … [1] (b) Some operations are carried out on the original queue given in part (a). (i) The current state of the queue is: 0 Frog 1 Cat 2 Fish 3 Elk 4 5 6 7 Complete the diagram to show the state of the queue after the following operations: Add “Wasp”, “Bee” and “Mouse”, and then remove two data items. [3] (ii) The state of the queue after other operations are carried out is shown: 0 Frog 1 Cat 2 Fish 3 Elk Front of queue pointer 4 Wasp 5 Bee 6 Mouse End of queue pointer 7 Ant Complete the following diagram to show the state of the queue after the following operations: Remove one item, and then add “Dolphin” and “Shark”. 0 1 2 3 4 5 6 7 [2] (c) The queue is implemented using a 1D array. Describe the algorithm that should be used to modify the end of queue pointer when adding an item to the queue. Your algorithm should detect any potential error conditions. … … … … … … [3]

13 marks

Mark scheme: 3(a)(i) One mark per point: 2 • EoQ pointer will move to point to location 4 // incremented EoQ (by 1) • Data value "Octopus" will be stored in location pointed to be EoQ / location 4 3(a)(ii) One mark for each bullet 2 • Value "Frog" // value pointed to by FoQ / location 0 is assigned to variable AnimalName • FoQ pointer will move to point to location 1 / point to "Cat" // incremented FoQ (by 1) 0 Frog ← Front of queue pointer 1 Cat 2 Fish 3 Elk ← End of queue pointer 3(a)(iii) There is only one data item in the queue 1 3(b)(i) One mark for data values plus one mark for pointers 3 0 Frog 1 Cat 2 Fish ← Front of queue pointer 3 Elk 4 Wasp 5 Bee 6 Mouse ← End of queue pointer 7 One mark for each pointer One mark for three new data values 3(b)(ii) 2 0 Shark ← End of queue pointer 1 (Cat) 2 (Fish) 3 (Elk) 4 Wasp ← Front of queue pointer 5 Bee 6 Mouse 7 Dolphin One mark for BOTH pointers One mark for all data values as shown 3(c) One mark per point: 3 1 If incremented EoQ = FoQ then error condition: queue is full 2 Increment the EoQ 3 Manage wrap-around

This question in 9618/23 Oct/Nov 2021

4 A stack is created using a high-level language. Memory locations 200 to 207 are to be used to store the stack. The following diagram represents the current state of the stack. TopOfStack points to the last value added to the stack. Stack Pointer Memory Value location 200 201 202 203 'F' TopOfStack 204 'C' 205 'D' 206 'E' 207 'H' (a) Complete the following table by writing the answers. Answer The value that has been on the stack for the longest time. The memory location pointed to by TopOfStack if three POP operations are performed. [2] (b) The following diagram shows the current state of the stack: Stack Pointer Memory Value location 200 201 202 'W' TopOfStack 203 'Y' 204 'X' 205 'Z' 206 'N' 207 'P' The following operations are performed: POP POP PUSH 'A' PUSH 'B' POP PUSH 'C' PUSH 'D' Complete the diagram to show the state of the stack after the operations have been performed. Stack Pointer Memory Value location 200 201 202 203 204 205 206 207 [4]

6 marks

Mark scheme: 4(a) One mark per row 2 Answer The value that has been on the stack for the longest time. 'H' The memory location pointed to by TopOfStack if three 206 POP operations are performed. 4(b) 4 Stack Pointer Memory Value location 200 201 'D'  TopOfStack 202 'C' 203 'A' 204 'X' 205 'Z' 206 'N' 207 'P' One mark for: 1 TopOfStack pointing to 'D' 2 Value 'D' in 201 3 Values 'C' & 'A' in 202 and 203 4 Values 'X' to 'P' unchanged (204 to 207)

This question in 9618/21 May/June 2022

2 A system is being developed to help manage a car hire business. A customer may hire a car for a number of days. An abstract model needs to be produced. (a) Explain the process of abstraction and state four items of data that should be stored each time a car is hired. Explanation … … Item 1 … Item 2 … Item 3 … Item 4 … [3] (b) Identify two operations that would be required to process the car hire data. Operation 1 … … Operation 2 … … [2]

5 marks

Mark scheme: 2(a) One mark for Explanation: 3 • Abstraction is used to filter out information / data that is not necessary for the task Or the opposite: • To keep only information / data that is necessary for the task One mark for each TWO data items (not dependent on 'Explanation'): Items include: • Car details: ID, Car Registration, car type etc • Customer details: ID, name, address, licence details etc • Start date (of hire) • Return date / Number of days (of hire) • Cost of hire 2(b) One mark for each (Max 2) 2 Examples include: 1 Input customer details 2 Input car details 3 Input payment details 4 Create hire / start hire 5 Return car / end hire 6 Change / check car status (hired / available / written-off) 7 Cancel hire 8 Process payment / calculate hire cost

This question in 9618/21 Oct/Nov 2022

4 (a) The following diagram shows an Abstract Data Type (ADT) representation of an ordered linked list. The data item stored in each node is a single character. The data will be accessed in alphabetical order. The symbol Ø represents a null pointer. Start pointer 'C' 'J' 'L' Ø (i) Nodes with data 'A' and 'K' are added to the linked list. Nodes with data 'J' and 'L' are deleted. After the changes, the data items still need to be accessed in alphabetical order. Complete the diagram to show the new state of the linked list. Start pointer 'C' 'J' 'L' [4] (ii) The original data could have been stored in a 1D array in which each element stores a character. For example: 'C' 'J' 'L' Explain the advantages of making the changes described in part (a)(i) when the data is stored in the linked list instead of an array. … … … … [2] (iii) Explain the disadvantages of making the changes described in part (a)(i) when the data is stored in the linked list instead of an array. … … … … [2] (b) A program will store data using a linked list like the one shown in part (a). Explain how the linked list can be implemented. … … … … … … … … [4]

12 marks

Mark scheme: 4(a)(i) One mark for each: 4 1 Data A and K stored in new / existing nodes 2 Start pointer points to Node A 3 Node A points to Node C and Node C points to Node K 4 Node K contains Null Pointer 4(a)(ii) One mark per point: 2 1 Pointers determine the ordering of data // only the pointers need to be changed when data changed 2 Easier to add / delete data (to maintain correct sequence) in a linked list // description of moving data to maintain correct sequence when array used 4(a)(iii) One mark per point: 2 1 Need to store pointers as well as data 2 More complex (to setup / implement) 4(b) One mark per point (Max 4): 4 1 Declare two (1D) arrays 2 One for data, one for pointers 3 Elements from same index represent one node 4 Declare an integer / variable for StartPointer // explain its use 5 Define appropriate value for null pointer // explain its use 6 Declare an integer / variable for FreeList pointer // explain its use 7 Routines are needed to add / delete / search Alternative MP1, 2 and 3 for record-based implementation: 1 Define a record type with fields for data and pointer 2 Declare one (1D) array 3 ...of the defined record type

This question in 9618/21 Oct/Nov 2022

3 A stack is used in a program to store string data which needs to be accessed in several modules. (a) A stack is an example of an Abstract Data Type (ADT). Identify one other example of an ADT and describe its main features. Example … Features … … … … … … [3] (b) Explain how the stack can be implemented using an array. … … … … … … … … … … … … … … … [5] (c) A second stack is used in the program. The diagram below shows the initial state of this stack. Value X is at the top of the stack and was the last item added. Upper-case letters are used to represent different data values. Stack operations are performed in three groups as follows: Group 1: PUSH D PUSH E Group 2: POP POP POP Group 3: PUSH A PUSH B POP PUSH C Complete the diagram to show the state of the stack after each group of operations has been performed. Include the current stack pointer (SP) after each group. Memory Initial After After After location state Group 1 Group 2 Group 3 957 956 955 954 953 X ←SP 952 Y 951 Z 950 P [5]

13 marks

Mark scheme: 3(a) One mark for name, Max two for features (Max 3 in total) 3 Name: Queue Features: 1 Each queue element contains one data item 2 A Pointer to the front / start of the queue 3 A Pointer to the back / end of the queue 4 Data is added at back / end and removed from front / start // works on a FIFO basis 5 May be circular ALTERNATIVE: Name: Linked List Features: 1 Each node contains data and a pointer to the next node 2 A Pointer to the start of the list 3 Last node in the list has a null pointer 4 Data may be added / removed by manipulating pointers (not moving data) 5 Nodes are traversed in a specific sequence 6 Unused nodes are stored on a free list // a free-list pointer to the Free List 3(b) One mark per point (Max 5): 5 1 Declare a (1D) array of data type STRING 2 The number of elements in that array corresponds to the size of the required stack 3 Declare an integer / variable for StackPointer 4. Declare an integer / variable for the size of the stack // for the max value of StackPointer 5 Use the StackPointer as an index to the array 6 Pointers and variables initialised to indicate empty stack 7 Store each item on the stack as one array element / Each stack item maps to one array element 8 Attempt to describe Push and Pop operations 9 Push and Pop routines need to check for full or empty conditions 3(c) One mark for each: 5 1 Data 'After Group 1' (as shown, including blank cells) 2 Data 'After Group 2' (as shown, including blank cells) 3 Data 'After Group 3' (as shown, including blank cells) 4 SP 'After Group 1' pointing to location 955 5 Final two SPs pointing to locations 952 and 954

This question in 9618/22 Oct/Nov 2022

4 (a) A program contains a 1D array DataItem with 100 elements. State the one additional piece of information required before the array can be declared. … … [1] (b) A programmer decides to implement a queue Abstract Data Type (ADT) in order to store characters received from the keyboard. The queue will need to store at least 10 characters and will be implemented using an array. (i) Describe two operations that are typically required when implementing a queue. State the check that must be carried out before each operation can be completed. Operation 1 … … Check 1 … … Operation 2 … … Check 2 … … [4] (ii) Describe the declaration and initialisation of the variables and data structures used to implement the queue. … … … … … … … … … … … [5]

10 marks

Mark scheme: 4(a) The data type (of the item to be stored) 1 4(b)(i) Operation: Add an item / Enqueue 4 Check: There are unused elements in the array // The queue is not full Operation: Remove an item / Dequeue Check: There are items in the array // The queue is not empty One mark for reason and one mark for reason it could not be completed. 4(b)(ii) One mark per point (Max 5): 5 1 Declare a (1D) array of size >= 10 2 …of data type CHAR 3 Declare integer variable for FrontOfQueuePointer 4 Declare integer variable for EndOfQueuePointer 5 Initialise FrontOfQueuePointer and EndOfQueuePointer to represent an empty queue 6 Declare integer variable or NumberInQueue 7 Declare integer variable for SizeOfQueue to count / limit the max number of items allowed // Reference to mechanism for defining 'wrap' of circular queue 8 Initialise SizeOfQueue // Initialise NumberInQueue

This question in 9618/23 Oct/Nov 2022

3 A program stores data in a text file. When data is read from the file, it is placed in a queue. (a) The diagram below represents an Abstract Data Type (ADT) implementation of the queue. Each data item is stored in a separate location in the data structure. During initial design, the queue is limited to holding a maximum of 10 data items. The operation of this queue may be summarised as follows: • The Front of Queue Pointer points to the next data item to be removed. • The End of Queue Pointer points to the last data item added. • The queue is circular so that locations can be reused. 0 1 2 3 4 5 Red Front of Queue Pointer 6 Green 7 Blue 8 Pink End of Queue Pointer 9 (i) Describe how the data items Orange and Yellow are added to the queue shown in the diagram. … … … … … … … … [4] (ii) The following diagram shows the state of the queue after several operations have been performed. All queue locations have been used at least once. 0 D4 1 D3 End of Queue Pointer 2 D27 3 D8 4 D33 5 D17 Front of Queue Pointer 6 D2 7 D1 8 D45 9 D60 State the number of data items in the queue. … [1] (b) The design of the queue is completed and the number of locations is increased. A function AddToQueue() has been written. It takes a string as a parameter and adds this to the queue. The function will return TRUE if the string was added successfully. A procedure FileToQueue() will add each line from the file to the queue. This procedure will end when all lines have been added or when the queue is full. Describe the algorithm for procedure FileToQueue(). Do not use pseudocode in your answer. … … … … … … … … … … … [5]

10 marks

Mark scheme: 3(a)(i) One mark per point: 4 1 Check that the queue is not full 2 EoQ pointer will move to point to location 9 3 Data item Orange will be stored in location referenced by EoQ pointer 4 EoQ pointer will move to point to location 0 5 Data item Yellow will be stored in location referenced by EoQ pointer Note: max 4 marks 3(a)(ii) 7 1 3(b) One mark per bullet: 5 1 Open file in READ mode 2 Loop to EOF()// read / process all the lines in file 3 Loop will end when return value from AddToQueue() is FALSE / queue is full 4 Read a line from the file in a loop 5 Pass string to AddToQueue()// AddToQueue()is executed with line as parameter

This question in 9618/22 May/June 2023

3 A program processes data using a stack. The data is copied to a text file before the program ends. (a) The following diagram shows the current state of the stack. The operation of this stack may be summarised as follows: • The TopOfStack pointer points to the last item added to the stack. • The BottomOfStack pointer points to the first item on the stack. • The stack grows upwards when items are added. Stack Pointer Memory location Value 506 505 WWW TopOfStack 504 YYY 503 XXX 502 ZZZ 501 NNN 500 PPP BottomOfStack (i) An error will be generated if an attempt is made to POP a value when the stack is empty. State the maximum number of consecutive POP operations that could be performed on the stack shown above before an error is generated. … [1] (ii) The following operations are performed: 1. POP and store value in variable Data1 2. POP and store value in variable Data2 3. PUSH value AAA 4. PUSH value BBB 5. POP and discard value 6. POP and store value in variable Data2 Complete the diagram to show the state of the stack and the variables after the given operations have been performed. Stack Pointer Memory location Value 506 505 504 503 502 Variable Value 501 Data1 500 Data2 [4] (b) The data is copied to a text file before the program ends. (i) State an advantage of writing the data from the stack to a text file before the program ends. … … [1] (ii) A module SaveStack() will write the data from the stack to a text file. Express an algorithm for SaveStack() as five steps that could be used to produce pseudocode. Write the five steps. Step 1 … … Step 2 … … Step 3 … … Step 4 … … Step 5 … …

11 marks

Mark scheme: 3(a)(i) 6 1 3(a)(ii) 4 One mark for: MP1 Values 'BBB' and 'AAA' MP2 Values 'XXX' to 'PPP' (unchanged) MP3 Both pointers and labelled22 MP4 Values of both variables 3(b)(i) So that the data may be recovered / restored (the next time the program is 1 run) // the data is permanently saved / data is not lost when the program terminates 3(b)(ii) Max 5 marks 5 MP1 Open the text file in WRITE mode MP2 Check there is a value on the stack MP3 POP value …. MP4 Write value to the text file MP5 Repeat from Step 2 // loop referencing the stack items Alternative solution: Not using POP primitive MP1 Open the text file in WRITE mode MP2 Check there is a value on the stack MP3 Read value from ToS location MP4 Write the value to the text file – Must some attempt at ‘the value’ NOT ‘all the values’ MP5 Decrement ToS MP6 Repeat from step 2 // loop referencing the stack items

This question in 9618/23 May/June 2023