10.4 Abstract Data Types – intro

AS Level · 3 questions found

What this topic covers

An ADT is a collection of data plus a set of operations on that data
Stack, queue and linked list as ADT examples
Key features of each; justify use for a given situation
Add, edit and delete data; implement stack/queue/linked list using arrays

Past paper questions

May/Jun 2024 Paper 2 v1 6 marks

Show mark scheme

3(a)

One mark per point:
1
The PS contains a null pointer
2
The PF points to the first element on the free list
3
All the nodes are on the free list

3(b) [6 marks]

Max 2 marks for 'Variables':
The two variables will be of type
Integer
The two variables will be used as
pointers / indexes
to the
arrays.
The values stored in the two variables will indicate
the first
element in each list
The first 1D array will be of type
String
The first 1D array will be used to
store the values // data items
// User IDs
The second 1D array will be of type
Integer
The second 1D array will be used to
store the pointers // point
to next item
Mark as follows:
One mark for
each
of the first three rows
One mark for
both
Array 1 rows
One mark for
both
Array 2 rows

May/Jun 2024 Paper 4 v1 3 marks

3 A program reads data from the user and stores the data that is valid in a linear queue. The queue is stored as a global 1D array, QueueData, of string values. The array needs space for 20 elements. The global variable QueueHead stores the index of the first element in the queue. The global variable QueueTail stores the index of the last element in the queue. (a) The main program initialises all the elements in QueueData to a suitable null value, QueueHead to −1 and QueueTail to −1. Write program code for the main program. Save your program as Question3_J24. Copy and paste the program code into part 3(a) in the evidence document. [1] (b) The function Enqueue() takes the data to insert into the queue as a parameter. If the queue is not full, it inserts the parameter in the queue, updates the appropriate pointer(s) and returns TRUE. If the queue is full, it returns FALSE. Write program code for Enqueue(). Save your program. Copy and paste the program code into part 3(b) in the evidence document. [4] (c) The function Dequeue() returns "false" if the queue is empty. If the queue is not empty, it returns the next item in the queue and updates the appropriate pointer(s). Write program code for Dequeue(). Save your program. Copy and paste the program code into part 3(c) in the evidence document. [3] (d) The string values to be stored in the queue are 7 characters long. The first 6 characters are digits and the 7th character is a check digit. The check digit is calculated from the first 6 digits using this algorithm: • multiply the digits in position 0, position 2 and position 4 by 1 • multiply the digits in position 1, position 3 and position 5 by 3 • calculate the sum of the products (add together the results from all of the multiplications) • divide the sum of the products by 10 and round the result down to the nearest integer to get the check digit • if the check digit equals 10 then it is replaced with 'X'. Example: Data is 954123 Character position 0 1 2 3 4 5 Digit 9 5 4 1 2 3 Multiplier 1 3 1 3 1 3 Product 9 15 4 3 2 9 Sum of products = 9 + 15 + 4 + 3 + 2 + 9 = 42 Divide sum of products by 10: 42 / 10 = 4 (rounded down) The check digit = 4. This is inserted into character position 6. The data including the check digit is: 9541234 A 7‑character string is valid if the 7th character matches the check digit for that data. For example, the data 9541235 is invalid because the 7th character (5) does not match the check digit for 954123. (i) The subroutine StoreItems() takes ten 7‑character strings as input from the user and uses the check digit to validate each input. Each valid input has the check digit removed and is stored in the queue using Enqueue(). An appropriate message is output if the item is inserted. An appropriate message is output if the queue is already full. Invalid inputs are not stored in the queue. The subroutine counts and outputs the number of invalid items that were entered. StoreItems() can be a procedure or a function as appropriate. Write program code for StoreItems(). Save your program. Copy and paste the program code into part 3(d)(i) in the evidence document. [6] (ii) Write program code to amend the main program to: • call StoreItems() • call Dequeue() • output a suitable message if the queue was empty • output the returned value if the queue was not empty. Save your program. Copy and paste the program code into part 3(d)(ii) in the evidence document. [1] (iii) Test the program with the following inputs in the order given: 999999X 1251484 5500212 0033585 9845788 6666666 3258746 8111022 7568557 0012353 Take a screenshot of the output(s). Save your program. Copy and paste the screenshot into part 3(d)(iii) in the evidence document. [2] BLANK PAGE BLANK PAGE Permission to reproduce items where third‑party owned material protected by copyright is included has been sought and cleared where possible. Every reasonable effort has been made by the publisher (UCLES) to trace copyright holders, but if any items requiring clearance have unwittingly been included, the publisher will be pleased to make amends at the earliest possible opportunity. To avoid the issue of disclosure of answer‑related information to candidates, all copyright acknowledgements are reproduced online in the Cambridge Assessment International Education Copyright Acknowledgements Booklet. This is produced for each series of examinations and is freely available to download at www.cambridgeinternational.org after the live examination series. Cambridge Assessment International Education is part of Cambridge Assessment. Cambridge Assessment is the brand name of the University of Cambridge BLANK PAGE

Show mark scheme

3(a) [1 mark]

1 mark each
QueueData
as 1D (string) array initialised to 20 null values
and
QueueHead
initialised to
-1
,
QueueTail
initialised to
-1
class Queue{
public static String[] QueueData = new String[20];
public static Integer QueueHead;
public static Integer QueueTail;
public static void main(String args[]){
for(Integer x = 0; x < 20; x++){
QueueData[x] = "";
}
QueueHead = -1;
QueueTail = -1;
}
VB.NET
Dim QueueData(0 To 20) As String
Dim QueueHead As Integer = -1
Dim QueueTail As Integer = -1
Sub Main(args As String())
For x = 0 To 19
QueueData(x) = ""
Next
End Sub
Python
global QueueData
global QueueHead
global QueueTail
QueueData = []
for x in range(0, 20):
QueueData.append("")
QueueHead = -1
QueueTail = -1

3(b)

Python
def Enqueue(DataToInsert):
global QueueData
global QueueHead
global QueueTail
if QueueTail == 19:
return False
elif QueueHead == -1:
QueueHead = 0
QueueTail = QueueTail + 1
QueueData.append(DataToInsert)
return True

3(c)

Python
def Dequeue():
global QueueData
global QueueHead
global QueueTail
if QueueHead < 0 or QueueHead > 20 or QueueHead > QueueTail:
return False
else:
QueueHead = QueueHead + 1
return QueueData[QueueHead-1]

3(d)(i)

Python
def StoreItems():
global QueueData
global QueueHead
global QueueTail
Count = 0
for X in range(0, 10):
Data = input("Enter data")
Total= int(Data[0]) + int(Data[1]) * 3 + int(Data[2]) + int(Data[3]) * 3 +
int(Data[4]) + int(Data[5]) * 3
Total = int(Total / 10)
if((Total == 10 and Data[6] == "X") or (Total == int(Data[6]))):
Result = Enqueue(Data[0:6])
if(Result == True):
print("Inserted item")
else:
print("Queue full")
else:
Count = Count + 1
print("There were", Count,"Invalid items")

3(d)(ii)

Python
QueueData = []
for x in range(0, 20):
QueueData.append("")
QueueHead = -1
QueueTail = -1
StoreItems()
Value = Dequeue()
if Value == False:
print("No data items")
else:
print("Item code", Value)

3(d)(iii) [2 marks]

1 mark each
Data input of 10 values
and
output a message saying there are 4 invalid items
999999 output

May/Jun 2024 Paper 4 v3 3 marks