10.4 Abstract Data Types – intro
AS Level · 39 questions found
What this topic covers
Section titled “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
Section titled “Past paper questions”A program uses a stack to hold up to 30 integer values. The stack is implemented using a global integer variable and a global 1D array.
The array is declared in pseudocode: DECLARE ThisStack : ARRAY[1:30] OF INTEGER
Stack design notes:
The global variable SP acts as a stack pointer. SP contains the array index of the last value pushed onto the stack.
If the stack is empty, then SP is assigned the value zero.
The first item added to the stack will be stored in ThisStack[1]
SP is incremented each time an item is added to the stack.
A function Pop() is written to remove an item from ThisStack. The function returns an item of type PopData which is defined in pseudocode:
TYPE PopData DECLARE Data : INTEGER DECLARE Exists : BOOLEAN ENDTYPE
The value removed from the stack is assigned to Data and Exists is set to TRUE. If it is not possible to remove a value from the stack, then Exists is set to FALSE
Complete the pseudocode for Pop()
FUNCTION Pop() RETURNS PopData
DECLARE ThisPop :
IF ______ THEN
PopData.Exists ______ // Stack is empty
ELSE
PopData.Data
PopData.Exists
SP
ENDIF
RETURN ThisPop
ENDFUNCTION 5 marks
Show mark scheme
3 [5 marks]
FUNCTION Pop() RETURNS PopData MP 2 DECLARE ThisPop : PopData MP 3 IF SP < 1 // SP = 0 THEN MP 1 PopData.Exists FALSE // Stack is empty ELSE MP 4 PopData.Data ThisStack[SP] MP 1 PopData.Exists TRUE MP 5 SP SP – 1 ENDIF RETURN ThisPop` ENDFUNCTION Mark as follows: MP 1 One mark for both assignments to ( and PopData.Exists FALSE ) TRUE MP 2, 3, 4 ,5 One mark for each of remaining four bold parts
A program stores integers in a stack. The stack is represented as a 1D array of 30 elements with
the identifier Stack
The global pointer TopOfStack stores the index of the last element inserted into the stack.
TopOfStack is initialised to –1
(a) Write program code to declare Stack, initialise each element in the array with a null value and declare and initialise TopOfStack Save your program as Question1_N25 . 2 marks
Copy and paste the program code into part 1(a) in the evidence document.
(b) The function Push() takes an integer parameter. If the stack is full, the function returns FALSE . If the stack is not full, the parameter is inserted into the stack, the pointer is updated and the function returns TRUE Write the program code for Push() Save your program. 4 marks
Copy and paste the program code into part 1(b) in the evidence document.
Show mark scheme
1(a) [2 marks]
1 mark each • (Global) 1D array initialised with 30 null values • (Global) initialised with TopofStack –1 Example program code Java public static Integer[] Stack = new Integer[30]; public static Integer TopOfStack; public static void main(String args[]){ for(Integer X = 0; X < 30; X++){ Stack[X] = null; } TopOfStack = -1; } VB.NET Dim Stack(29) As Integer Dim TopOfStack As Integer Sub Main(args As String()) For x = 0 To 29 Stack(x) = Nothing Next TopOfStack = -1 End Sub Python Stack = [None for x in range(30)] TopOfStack = -1
1(b)
Python def Push(DataToPush): global Stack global TopOfStack if TopOfStack < 29: TopOfStack = TopOfStack + 1 Stack[TopOfStack] = DataToPush return True else: return False
1(c)
Python def Pop(): global Stack global TopOfStack if TopOfStack == -1: return -999 else: DataReturn = Stack[TopOfStack] TopOfStack = TopOfStack - 1 return DataReturn
1(d) [4 marks]
1 mark each • Looping 40 times • Generating random number between 0 and 1000 inclusive inside the loop • Calling with each random number and storing/using return value … … if return value is Push() and breaking out of loop full Example program code Java for(Integer X = 0; X < 40; X++){ Pushed = Push(RandomNumber.nextInt(1001)); if(Pushed == false){ System.out.println("Stack full"); X = 40; } } VB.NET For x = 0 To 39 Pushed = Push(RandomNumber.Next(0, 1000)) If Pushed = False Then Console.WriteLine("Stack full") x = 40 End If Next Python for x in range(40): Pushed = Push(random.randint(0,1000)) if Pushed == False: print("Stack full") break
1(e)
VB.NET Sub FindValues() Dim Highest, Lowest As Integer Highest = Pop() Lowest = Highest Dim ReturnValue As Integer = Highest While ReturnValue <> -999 If ReturnValue > Highest Then Highest = ReturnValue End If If ReturnValue < Lowest Then Lowest = ReturnValue End If ReturnValue = Pop() End While Console.WriteLine("The highest value is " & Highest & " and the lowest value is " & Lowest) End Sub Python def FindValues(): Highest = Pop() Lowest = Highest ReturnValue = Lowest while(ReturnValue != -999): if ReturnValue > Highest: Highest = ReturnValue if ReturnValue < Lowest: Lowest = ReturnValue ReturnValue = Pop() print("The highest value is", Highest, "and the lowest value is", Lowest)
1(f)(i) [1 mark]
1 mark for calling FindValues() Example program code Java FindValues(); VB.NET FindValues() Python FindValues()
1(f)(ii) [1 mark]
1 mark for a screenshot of output showing Stack full output once Lowest value output in an appropriate message Highest value output in an appropriate message Lowest and Highest must be 0–1000 inclusive
A program reads string data from a text file into a linear queue and then compresses the data.
The queue is created using the global 1D array Queue . The queue can store up to 100 elements.
Each element is initialised to the empty string ""
The queue has two pointers that are global to the program:
QueueHeadthat points to the index of the first element in the queue, initialised to–1QueueTailthat points to the index of the last element in the queue, initialised to–1
The global variable NumberItems stores the number of elements stored in the queue, initialised
to 0
(a) Write program code to declare and initialise Queue, QueueHead, QueueTail and 2 marks
NumberItems
Save your program as Question2_N25 .
Copy and paste the program code into part 2(a) in the evidence document.
(b) The function Enqueue() takes a string as a parameter. The function checks if the queue is full, and returns Boolean FALSE if the queue is full. 5 marks
If the queue is not full, the parameter is inserted into the next position in Queue . The function
updates the appropriate pointer(s), updates NumberItems and then returns Boolean TRUE
Write program code for Enqueue()
Save your program.
Copy and paste the program code into part 2(b) in the evidence document.
(c) The function Dequeue() returns the string "False" if the queue is empty. 3 marks
If the queue is not empty, the function returns the next element in the queue. The function
updates the appropriate pointer(s) and updates NumberItems
Write program code for Dequeue()
Save your program.
Copy and paste the program code into part 2(c) in the evidence document.
(d) The text file BinaryData.txt stores individual binary digits, '1' and '0' . Each digit is on a new line. For example, the first line in the text file stores '1', the second line stores '1' The procedure ReadData() reads in each line from the text file BinaryData.txt and inserts it into the queue using the appropriate method. 5 marks
The procedure needs to work for a text file with any number of lines up to a maximum of 100.
Write program code for ReadData()
Save your program.
Copy and paste the program code into part 2(d) in the evidence document.
(e) The string data in the text file is compressed. 6 marks
The compression algorithm counts the number of times each binary digit appears consecutively, then stores the binary digit followed by the number of times it appears. The algorithm stores the compressed data in a single string.
For example, if the text file contains the data:
1
1
0
0
0
1
1
1
The compression algorithm will create the string "120313" because there are two '1' digits,
followed by three '0' digits, followed by three '1' digits.
The procedure Compress() uses Dequeue() to remove each element from the queue in
turn. The procedure then compresses the data following the compression algorithm described.
The new compressed string is stored in the global variable NewString
You can assume that one binary digit will never appear more than nine times consecutively in the sequence.
You can assume that there will always be at least one item in the queue.
Write program code for Compress()
Save your program.
Copy and paste the program code into part 2(e) in the evidence document.
(f) (i) Write program code for the main program to: 2 marks
call
ReadData()call
Compress()output the content of the compressed string.
Save your program.
Copy and paste the program code into part 2(f)(i) in the evidence document.
(ii) Test your program. 1 mark
Take a screenshot of the output(s).
Save your program.
Copy and paste the screenshot(s) into part 2(f)(ii) in the evidence document.
Show mark scheme
2(a)
Python global Queue, QueueHead, QueueTail, NumberItems Queue = [] for x in range(100): Queue.append("") QueueHead = -1 QueueTail = -1 NumberItems = 0
2(b)
VB.NET Function Enqueue(TheData) If QueueHead = -1 Then Queue(0) = TheData QueueHead = 0 QueueTail = 0 NumberItems += 1 Return True ElseIf QueueTail >= 99 Then Queue(QueueTail + 1) = TheData QueueTail += 1 NumberItems += 1 Return True Else Return False End If End Function Python def Enqueue(TheData): global Queue, QueueHead, QueueTail, NumberItems if(QueueHead == -1){ Queue[0] = TheData QueueHead = 0 QueueTail = 0 NumberItems +=1 return True elif QueueTail >= 99: Queue[QueueTail+1] = TheData QueueTail +=1 NumberItems +=1 return True else: return False
2(c)
Python def Dequeue(): global Queue, QueueHead, QueueTail, NumberItems if NumberItems == 0: return "False" else: ReturnData = Queue[QueueHead] QueueHead += 1 NumberItems -=1 return ReturnData
2(d)
VB.NET Sub ReadData() Dim ReturnValue As String Dim DataReader As New System.IO.StreamReader("BinaryData.txt") Dim FinishLoop As Boolean = True Do Until DataReader.EndOfStream Or FinishLoop = False ReturnValue = Enqueue(DataReader.ReadLine()) If ReturnValue = False Then FinishLoop = False End If Loop DataReader.Close() End Sub Python def ReadData(): TheFile = open("BinaryData.txt") for Line in TheFile: ReturnValue = Enqueue(Line.strip()) if ReturnValue == False: break TheFile.close()
2(e)
VB.NET Sub Compress() Dim First As String = Dequeue() Dim NewLine As String = "" Dim Count As Integer Dim NextChar As String While NumberItems > 0 And First <> "False" Count = 1 NextChar = Dequeue() While NextChar = First Count += 1 First = NextChar NextChar = Dequeue() End While NewLine = First & Count NewString = NewString & NewLine First = NextChar End While Python def Compress(): global NewString First = Dequeue() NewString = "" while NumberItems > 0 and First != "False": Count = 1 NextChar = Dequeue() while NextChar == First: Count += 1 First = NextChar NextChar = Dequeue() NewLine = First + str(Count) NewString = NewString + NewLine First = NextChar
2(f)(i)
Python NewString = "" Queue = [] for x in range(100): Queue.append("") QueueHead = -1 QueueTail = -1 NumberItems = 0 ReadData() Compress() print(NewString)
2(f)(ii) [1 mark]
1 mark for screenshot showing output Example
Stacks and queues are both abstract data types.
A stack uses a top-of-stack pointer to indicate the location of the last item added to the stack.
A queue uses two pointers:
a front pointer to indicate the location of the next item to be removed from the queue
a rear pointer to indicate the location of the next item to be added to the queue.
A queue can be used to reverse the items stored on a stack.
For example, if a stack contains six items:
Initial state of the stack:
top-of-stack pointer
item 6
item 5
item 4
item 3
item 2
item 1
Final state of the stack when the items have been reversed:
top-of-stack pointer
item 1
item 2
item 3
item 4
item 5
item 6
Describe how the queue could be used to reverse the items that are currently stored on the stack.
Your description must include how the pointers are used in both the stack and queue.
Assume:
The stack initially contains an unknown number of items.
The queue can store all the items currently stored on the stack.
The queue is initially empty.
7 marks
Show mark scheme
5 [7 marks]
Pop an item off the stack Update Stack pointer Add it to the queue Update Rear pointer Repeat until the stack is empty Remove an item from the queue Update Front pointer Push it onto the stack Update the Stack pointer Repeat until the queue is empty
Two arrays Data and Pointer are accessed by the procedure Place()
Data and Pointer are both global arrays of type INTEGER
The contents of these two arrays are shown:
Data Pointer
1 1018 1 7
2 1007 2 3
3 1010 3 1
4 1056 4 6
5 1092 5 -1
6 1062 6 5
7 1034 7 4
8 0 8 9
9 0 9 10
10 0 10 -1
Study the pseudocode:
PROCEDURE Place(Value : INTEGER, Start : INTEGER, Unused : INTEGER) DECLARE New, Current, Last : INTEGER CONSTANT NullPointer = -1 New Unused Last NullPointer Current Start WHILE Current <> NullPointer AND Data[Current] < Value Last Current Current Pointer[Current] ENDWHILE Pointer[New] Pointer[Last] Pointer[Last] New Data[New] Value ENDPROCEDURE
(a) (i) Complete the trace table below by dry running the procedure Place() when it is called by the statement: 4 marks
CALL Place(1043, 2, 8)
| Value | Start | Unused | New | Last | Current |
|---|---|---|---|---|---|
(ii) Complete the diagram showing the contents of the global arrays Data and Pointer after the procedure Place() has run to completion when called as shown in part (a)(i). 3 marks
Data Pointer
1 1018 1
2 1007 2
3 1010 3
4 1056 4
5 1092 5
6 1062 6
7 1034 7
8 8
9 9
10 10
(b) The operation carried out by procedure Place() together with the arrays form part of the implementation of an Abstract Data Type (ADT). 2 marks
Identify the ADT and state the operation carried out by procedure Place()
Show mark scheme
6(a)(i) [4 marks]
Value Start Unused New Last Current 1043 2 8 8 –1 2 Region 1 2 3 Region 2 3 1 Region 3 1 7 7 4 Region 4 Award 1 mark per region
6(a)(ii) [3 marks]
Data Pointer 1018 7 1 1 1007 3 2 2 1010 1 3 3 1056 6 4 4 1092 –1 5 5 1062 5 6 6 1034 8 7 7 1043 4 8 8 0 10 9 9 0 –1 10 10 Mark as follows: 1 mark for global array row 8 containing the value 1043 Data 1 mark for global array row 7 containing the value 8 and row 8 Pointer containing the value 4 1 mark for all other rows in both arrays
6(b) [2 marks]
Example answer: The ADT is a linked list and the procedure inserts / add a new node / Place() value into it / the linked list Mark as follows:
- 1 mark for identifying the ADT as a linked list
- 1 mark for identifying operation as inserting / adding a value / node into a linked list
A programmer uses a number of Abstract Data Types (ADT) in the programs that she is developing.
(a) A stack using memory locations 400 to 409 is used in one program.
The diagram represents the current state of the stack.
A variable TopOfStack pointer indicates the last value added to the stack.
Stack
Memory Value location
409
408
407
406
405
404
403 'P' TopOfStack
402 'X'
401 'D'
400 'B'
(i) Complete the answer column in the following table: 2 marks
| Answer | |
|---|---|
| the memory location of the value that has been on the stack for the longest time |
|
| the number of consecutive push operations that will result in the TopOfStack variable containing 409 |
Show mark scheme
2 MP2 6
2(a)(ii) [3 marks]
Stack Memory Value location 409 TopOfStack 408 'Y' 407 'Z' 406 ‘C’ 405 ‘F’ 404 ‘K’ 403 ‘B’ 3 402 ‘S’ 401 ‘R’ 400 ‘D’ MP1 pointing to 'Y' and value 'Y' in location 408 TopOfStack MP2 Values 'C' and 'Z' in 406 and 407 MP3 Values 'D' to 'F' unchanged in 400 to 405 and 409 is empty
2(b)(i) [3 marks]
Index Data Pointer 0 "Neptune" 2 MP3 1 "Jupiter" 4 2 "Saturn" 5 3 "Earth" 1 MP1 4 "Mercury" 0 5 "Uranus" -1 MP2 MP1 Earth pointer 1 MP2 Uranus pointer -1 MP3 Other four correct pointers
2(b)(ii) [1 mark]
3
2(c) [2 marks]
MP1 First value added to queue is the first value removed // FIFO // LILO MP2 Two pointers needed to indicate the start and end of the queue MP3 May behave as a circular queue MP4 Manipulated using / operations // by enqueue() dequeue() description Max 2
(a) An array is an Abstract Data Type (ADT). 1 mark
Identify two other ADTs.
1
2
(b) A 1D array DataArray holds up to 1000 elements of type integer and needs to be sorted in ascending order. 4 marks
Write the pseudocode for an insertion sort to sort the array into ascending order.
Use the identifiers from the table in your algorithm.
You do not need to declare any arrays or variables for this algorithm. You may assume this has already been done.
| Identifier | Data type | Description |
|---|---|---|
| Index | INTEGER | counter for outer loop |
| Position | INTEGER | counter for inner loop – insertion position |
| DataArray | INTEGER | 1D array to store up to 1000 integers |
| Value | INTEGER | value to insert |
The first line has been written for you.
FOR Index ← 2 to 1000
(c) Describe two ways in which the performance of a sort routine is affected by the data to be sorted. 2 marks
1
2
Show mark scheme
12(a) [1 mark]
One mark for any two correct ADTs ( Max 1 ) • Binary tree • Graph • Linked list • Queue • Stack
12(b) [4 marks]
One mark for each marking point ( Max 4 ) MP1 Temporary assignment of the element being ‘inserted’ before inner loop MP2 Appropriate inner loop MP3 Check if current content is > DataArray Value MP4 Moving data to adjacent element as required MP5 Appropriate updating of variable Position 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) [2 marks]
One mark for each marking point 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.
A program stores positive integers in a circular queue.
The queue is stored as a global 1D array of 20 integers with the identifier Queue . Each index is
initialised with the data –1
The global variable HeadPointer, initialised to –1, points to the first element in the queue.
The global variable TailPointer, initialised to –1, points to the last element in the queue.
The global variable NumberItems, initialised to 0, stores the number of items in the queue.
(a) Write program code to declare and initialise Queue, HeadPointer, TailPointer and 2 marks
NumberItems
Save your program as Question1_J25 .
Copy and paste the program code into part 1(a) in the evidence document.
(b) The function Enqueue() : 6 marks
takes an integer as a parameter
checks if the queue is full
returns
FALSEif the queue is fullstores the parameter in the next position in the queue and returns
TRUEif the queue is not fullupdates the appropriate pointers and
NumberItems
Write program code for Enqueue()
Save your program.
Copy and paste the program code into part 1(b) in the evidence document.
Show mark scheme
1(a) [2 marks]
1 mark each • (global) Declaration of 1D array , 20 elements initialised with Queue –1 • (global) and initialised to , HeadPointer TailPointer –1 NumberItems
Queue[X] = -1;
1(b) [6 marks]
1 mark each • Function header (and close) taking 1 (integer) parameter and returning a Boolean value in all cases • Checking if queue is full ( ) and returning NumberItems = 20 FALSE • Checking if queue is empty ( ) then and updating NumberItems = 0 TailPointer • Incrementing and in appropriate place … TailPointer NumberItems • … looping back to 0 for if at end of structure TailPointer • Storing parameter in (after increment) and returning Queue[TailPointer]
Return False TailPointer = 0 HeadPointer = 0 Queue(TailPointer) = InputData
TailPointer = TailPointer + 1 If TailPointer = 20 Then TailPointer = 0 End If Queue(TailPointer) = InputData return false; TailPointer = 0; HeadPointer = 0; Queue[TailPointer] = InputData; TailPointer++; if(TailPointer == 20){ TailPointer = 0; } Queue[TailPointer] = InputData;
1(c) [3 marks]
1 mark each • Calling with 1 to 25 (inclusive) in order Enqueue() • … storing/using return value in selection …outputting with integer Successful integer correctly Console.WriteLine(x & "Successful " ) Console.WriteLine(x & "Unsuccessful ") System.out.println(X + "Successful "); System.out.println(X + "Unsuccessful ");
1(d) [6 marks]
1 mark each • header (and close) and checking if queue is empty ( Dequeue() NumberItems = 0 • Returning data at HeadPointer • Incrementing … HeadPointer • … and catching if = 20 to return to 0 • Decrementing NumberItems • Resetting and when queue is empty HeadPointer TailPointer
Return -1 ReturnValue = Queue(HeadPointer) HeadPointer = HeadPointer + 1 If HeadPointer >= 20 Then HeadPointer = 0 End If NumberItems = NumberItems – 1 If NumberItems = 0 Then HeadPointer = -1 TailPointer = -1
End If Return ReturnValue return -1; ReturnValue = Queue[HeadPointer]; HeadPointer++; if(HeadPointer >= 20){ HeadPointer = 0; } NumberItems--; if(NumberItems == 0){ HeadPointer = -1; TailPointer = -1; } return ReturnValue;
1(e)(i) [2 marks]
1 mark each • Calling twice Dequeue() • … outputting return value from both calls
1(e)(ii) [1 mark]
1 mark for output showing: • 1 to 20 with Successful 21 to 25 with Unsuccessful 1 and 2 output
A program reads data from a text file and stores it in a stack. The stack Stack is stored as a 1D
array of up to 20 elements. The pointer TopOfStack stores the index of the last element stored in
the stack.
(a) Stack is a global array of strings with all elements initialised to "-1" TopOfStack is a global variable initialised to –1 Write program code to declare and initialise Stack and TopOfStack Save your program as Question1_J25 . 2 marks
Copy and paste the program code into part 1(a) in the evidence document.
(b) The function Push() takes a string parameter and attempts to store it on the stack. 4 marks
The function returns –1 if the stack is full.
The function returns 1 if the parameter is successfully pushed onto the stack.
Write program code for Push()
Save your program.
Copy and paste the program code into part 1(b) in the evidence document.
Show mark scheme
1(a) [2 marks]
1 mark each • (Global) as 1D array (of strings) with 20 elements initialised to string Stack • (Global) initialised to TopOfStack –1 for(Integer X = 0; X < 20; X++){ Stack[X] = "-1"; } TopOfStack = -1;
1(b) [1 mark]
1 mark each • function header (and end where appropriate) taking one (string) parameter Push • Checking if stack is full and returning integer –1 • (Otherwise) Incrementing TopOfStack • Storing parameter in the incremented the stack at and returning integer TopOfStack if (TopOfStack == 19){ return -1; }else{ TopOfStack++; Stack[TopOfStack] = Data; return 1; }
1(c) [4 marks]
1 mark each • Function header (and end where appropriate) and returning a value in all cases. • Checking if stack is empty and returning string "–1" • (Otherwise) Decrementing TopOfStack • Returning element in stack at before is decremented TopOfStack TopOfStack if (TopOfStack == -1){ return "-1"; }else{ String ReturnValue = Stack[TopOfStack]; TopOfStack--; return ReturnValue; }
1(d) [6 marks]
1 mark each • Procedure header (and end where appropriate) taking one (string) parameter • Opening the file with the filename parameter and closing the file in an appropriate place • Looping through to end of file and reading in each line ... • … calling once with each read in value … Push() • … if any return value from is integer outputting Push() –1 "Stack full" • Exception handling for opening and reading from file with appropriate catch and output Integer ReturnValue; try{ FileReader f = new FileReader(FileName); try{ BufferedReader Reader = new BufferedReader(f); String Line= Reader.readLine(); Line = Line.replace("\n",""); while (Line != null){ Line = Line.replace("\n",""); ReturnValue = Push(Line); if (ReturnValue == -1){ System.out.println("Stack full"); } Line = Reader.readLine(); } Reader.close(); }catch(IOException ex){} }catch(FileNotFoundException e){ System.out.println("File not found"); }
1(e) [7 marks]
1 mark for: • function header (and end where appropriate) Calculate() • Looping until the stack is empty • Calling repeatedly within loop and storing/using return value Pop() • … working out if return value from call is an operator or a number / alternating between operator and number Pop() • Select to determine if the operator is +, -, /, * or ^ and attempt the matching calculation • … performing correct calculation using operator, number • … updating total from previous loops and returning this final value Double Total = Double.parseDouble(Pop()); String ReturnValue = ""; String LastOperator = ""; Boolean OperatorFlag = true; Integer TheData = 0; while(ReturnValue != "-1"){ ReturnValue = Pop(); if(OperatorFlag == false){ TheData = Integer.parseInt(ReturnValue); if(LastOperator.compareTo("+")==0){ Total = Total + TheData; }else if(LastOperator.compareTo("-")==0){ Total = Total - TheData; }else if(LastOperator.compareTo("*")==0){ Total = Total * TheData; }else if(LastOperator.compareTo("/")==0){ Total = Total / TheData; }else if(LastOperator.compareTo("^")==0){ Total = Math.pow(Total, TheData); } OperatorFlag = true;
}else{ LastOperator = ReturnValue; OperatorFlag = false; } } return Total;
1(f)(i) [2 marks]
1 mark each • Taking a filename as input and calling with input ReadData() • Calling and outputting the return value Calculate()
1(f)(ii) [2 marks]
1 mark for screenshot showing input of and output of 131 StackData.txt 1 mark for screenshot showing input of and output of 320 SecondStack.txt
A program reads data from a text file and stores it in a queue. The linear queue Queue is stored as
a 1D array of up to 50 elements. The queue has the following pointers:
HeadPointer- this stores the index of the first element in the queue, initialised to–1TailPointer- this stores the index of the last element in the queue, initialised to–1
(a) Queue is a global array of 50 integers with all elements initialised to –1 in the main program. 3 marks
The two pointers are declared as global variables and initialised to –1
Write program code to declare and initialise Queue, HeadPointer and TailPointer
Save your program as Question1_J25 .
Copy and paste the program code into part 1(a) in the evidence document.
(b) The function Enqueue() : 6 marks
takes an integer parameter to store in the next position in the queue
returns
FALSEif the queue is full and the parameter cannot be stored in the queuereturns
TRUEif the parameter is stored in the queueupdates the pointers where appropriate.
Write program code for Enqueue()
Save your program.
Copy and paste the program code into part 1(b) in the evidence document.
Show mark scheme
1(a) [3 marks]
1 mark each • (Global) array with 50 integer elements … Queue • … all initialised to –1 • (Global) and initialised with HeadPointer TailPointer –1
Queue(x) = -1
1(b) [6 marks]
1 mark each • Function header (and end) taking one (integer) parameter Enqueue() • Checking if is full … Queue • …returning if full and if not full FALSE TRUE • (Otherwise) storing data item at (check incrementing) TailPointer + 1 • Incrementing TailPointer • Checking if this is the first element and incrementing/storing 0 in HeadPointer
TailPointer = TailPointer + 1 Queue(TailPointer) = DataValue If HeadPointer = -1 Then HeadPointer = 0 End If Return True Return False
1(c) [5 marks]
1 mark each • Function header (and close) and returning appropriate value in all cases. Dequeue() • Checking if queue is empty … • … and returning if empty –1 • Accessing and returning element at (before Queue[HeadPointer] HeadPointer • Incrementing HeadPointer
ReturnValue = Queue(HeadPointer) HeadPointer = HeadPointer + 1 Return ReturnValue Return -1
1(d) [6 marks]
1 mark each • header (and end) and opening the file to read and closing file in appropriate place CreateQueue() • Looping until end of file • Reading in each/all lines (and converting to integer and removing new line) • … calling once with each value … Enqueue() • … checking return value and outputting if full (can output once or many times) "Queue full" • Exception try, catch with appropriate output. All file access within try
Dim FileReader As New System.IO.StreamReader("QueueData.txt") While Not FileReader.EndOfStream ReadData = FileReader.ReadLine() ReturnValue = Enqueue(ReadData) If ReturnValue = False Then Console.WriteLine("Queue full") End If End While FileReader.Close() Console.WriteLine("Cannot open or read file")
1(e)(i) [5 marks]
1 mark each • Calling CreateQueue() • Calling and storing/using return value … Dequeue() • … repeatedly until return value is –1 • … adding together all return values to create a total within the loop … • … outputting the total
Total = Total + ReturnValue
1(e)(ii) [1 mark]
1 mark for screenshot showing 3059
A program uses a stack to hold up to 60 numeric values. The stack is implemented using two integer variables and a 1D array.
The array is declared in pseudocode as shown:
DECLARE ThisStack : ARRAY[1:60] OF REAL
The stack operates as follows:
Global variable SP acts as a stack pointer that points to the next available stack location. The value of SP represents an array index.
Global variable OnStack represents the number of values currently on the stack.
The stack grows upwards from array element index 1.
(a) (i) Give the initial values that should be assigned to the two variables. 1 mark
SP
OnStack
(ii) Explain why it is not necessary to initialise the array elements before the stack is used. 2 marks
(b) A function to add a value to ThisStack is expressed in pseudocode as shown. 4 marks
The function will return a value to indicate whether the operation was successful or not.
Complete the pseudocode by filling in the gaps.
FUNCTION Push(ThisValue : REAL) RETURNS BOOLEAN
DECLARE ReturnValue : BOOLEAN
IF ______ THEN
RETURN ______ // stack is already full
ENDIF
______ ThisValue
SP
OnStack OnStack + 1
RETURN TRUE
ENDFUNCTION
Show mark scheme
3(a)(i) [1 mark]
: 1 SP : 0 OnStack One mark for both correct values
3(a)(ii) [2 marks]
MP1 Unused values cannot be popped / taken off the stack // initialised values would never be used / unused elements cannot be accessed MP2 ... until a value has first been pushed / written // overwrites previous value
3(b) [4 marks]
Example solution: FUNCTION Push(ThisValue : REAL) RETURNS BOOLEAN DECLARE ReturnValue : BOOLEAN IF OnStack = 60 / >59 // SP = 61 / SP > 60 // outside the range 1 to 60 SP THEN RETURN FALSE // Stack is already full ENDIF ThisStack[SP] ThisValue SP SP + 1 OnStack OnStack + 1 RETURN TRUE ENDFUNCTION1 Mark as follows: One mark per gap
The implementation of a linked list uses an integer variable and a 1D array List of type Node.
Record type Node is declared in pseudocode as follows:
TYPE Node DECLARE Data : STRING DECLARE Pointer : INTEGER ENDTYPE
The array List is declared in pseudocode as follows:
DECLARE List : ARRAY[1:200] OF Node
The linked list will operate as follows:
Integer variable HeadPointer will store the array index for the first node in the linked list.
The Pointer field of a node contains the index value of the next array element (the next node) in the linked list.
The value 0 is used as a null pointer.
(a) (i) State why the value 0 has been selected as the null pointer. 1 mark
(ii) Give the range of valid values that could be assigned to variable HeadPointer. 1 mark
Show mark scheme
3(a)(i) [1 mark]
0 is not a valid array / index value // No 0 element in the array th List
3(a)(ii) [1 mark]
to 0 200
3(b) [4 marks]
Mark as follows: MP1 Use of variable as array index and initialisation to 1 / to first element of array MP2 Loop for 199 / 200 iterations MP3 Assign Index+1 to each pointer field in a loop MP4 Assign 0 to 200 pointer field th
3(c) [4 marks]
One mark per step: MP1 Assign to / Current Pointer // Identify HeadPointer ThisPointer first node using headpointer MP2 Loop the following until value is 0 (zero) / null pointer ThisPointer reached MP3 … Output data (field) from array element at index // ThisPointer Output data (field) of the current node / array element MP4 … Assign pointer field from current array element / index / to / Current Pointer // Assign pointer field from current ThisPointer node to / Current Pointer ThisPointer
A linear queue data structure is designed using a record structure.
The record structure Queue has the following fields:
QueueArray, a 1D array of up to 100 integer valuesHeadpointer, a variable that stores the index of the first data item inQueueArrayTailpointer, a variable that stores the index of the next free location inQueueArray.
(a) Write program code to declare the record structure Queue and its fields. 3 marks
If your programming language does not support record structures, a class can be declared instead.
If you are writing in Python, use comments to declare the appropriate data types.
Save your program as Question2_N24 .
Copy and paste the program code into part 2(a) in the evidence document.
(b) The main program creates a new Queue record with the identifier TheQueue . The head pointer is initialised to –1. The tail pointer is initialised to 0. Each element in the array is initialised with –1. 3 marks
Write program code for the main program.
Save your program.
Copy and paste the program code into part 2(b) in the evidence document.
(c) The pseudocode function Enqueue() inserts an integer value into the queue. 5 marks
The function is incomplete. There are three incomplete statements.
FUNCTION Enqueue(BYREF AQueue : Queue, BYVAL TheData : INTEGER)
RETURNS INTEGER
IF AQueue.Headpointer = -1 THEN
AQueue.QueueArray[AQueue.Tailpointer]
←
AQueue.Headpointer 0
# ←
AQueue.Tailpointer AQueue.Tailpointer + 1
# ←
RETURN 1
ELSE
IF AQueue.Tailpointer > ______ THEN
RETURN -1
ELSE
AQueue.QueueArray[AQueue.Tailpointer] TheData
# ←
AQueue.Tailpointer AQueue.Tailpointer
←
RETURN 1
ENDIF
ENDIF
ENDFUNCTION
Write program code for Enqueue() .
Save your program.
Copy and paste the program code into part 2(c) in the evidence document.
(d) The function ReturnAllData() accesses TheQueue . It concatenates all the integer values that have been inserted into the queue’s array, starting from the value stored at HeadPointer, with a space between each integer value. The string of concatenated values is returned. 3 marks
None of the integer values are removed from the queue.
Write program code for ReturnAllData() .
Save your program.
Copy and paste the program code into part 2(d) in the evidence document. (e) (i) The main program asks the user to enter 10 integers with values of 0 or greater. It reads 5 marks each input repeatedly until a valid number is entered.
All 10 valid inputs are added to the queue, using Enqueue() .
If the value returned from Enqueue() is –1, a message is output to state that the queue
is full, otherwise a message is output to state that the item has been added to the queue.
The function ReturnAllData() is called once all 10 integers have been entered and
the return value from the function call is output.
Amend the main program to perform these actions.
Save your program.
Copy and paste the program code into part 2(e)(i) in the evidence document.
(ii) Test your program with the following inputs in the order given: 2 marks
10 9 –1 8 7 6 5 4 3 2 1
Take a screenshot of the output.
Save your program.
Copy and paste the screenshot into part 2(e)(ii) in the evidence document.
(f) The function Dequeue() accesses TheQueue . The function returns –1 if the queue is empty. 4 marks
If the queue is not empty, the function returns the next item in the queue and updates the relevant pointer(s).
The data is not replaced or deleted from the queue.
Write program code for Dequeue() .
Save your program.
Copy and paste the program code into part 2(f) in the evidence document.
(g) (i) The main program calls Dequeue() twice, and each time it either outputs ‘Queue empty’ 3 marks
if there is no data in the queue or outputs the return value.
The main program then calls ReturnAllData() a second time.
Amend the main program.
Save your program.
Copy and paste the program code into part 2(g)(i) in the evidence document.
(ii) Test your program with the following inputs in the order given: 1 mark
10 9 8 7 6 5 4 3 2 1
Take a screenshot of the output.
Save your program.
Copy and paste the screenshot into part 2(g)(ii) in the evidence document.
Show mark scheme
2(a) [3 marks]
1 mark each to max • Record structure or class with constructor (and end where appropriate) … Queue • … containing a 1D array of (100) integers QueueArray • … containing and as integers HeadPointer TailPointer e.g. Python class Queue: def init(self): self.QueueArray = [] HeadPointer = 0 #integer TailPointer = 0 #integer for x in range(0, 100): self.QueueArray.append(-1) VB.NET Structure Queue Dim QueueArray() As Integer Dim HeadPointer As Integer Dim TailPointer As Integer End Structure Java class queue{ private static Integer[] QueueArray = new Integer[100]; private static Integer HeadPointer; private static Integer TailPointer; public queue(){ } }
2(b)
HeadPointer = -1; TailPointer = 0; for(Integer x = 0; x < 100; x++){ QueueArray[x] = -1; } } } public static void main(String args[]){ queue TheQueue = new queue(); }
2(c)
Java public static Integer Enqueue(Integer TheData){ if(GetHeadPointer() == -1){ SetData(TheData); SetHeadPointer(0); SetTailPointer(GetTailPointer() + 1); return 1; }else if(GetTailPointer() > 99){ return -1; }else{ SetData(TheData); SetTailPointer(GetTailPointer() + 1); return 1; } }
2(d)
VB.NET Function ReturnAllData(AQueue As Queue) Dim Temp As String = "" For X = AQueue.HeadPointer To AQueue.TailPointer - 1 Temp = Temp & AQueue.QueueArray(X).ToString() & " " Next X Return Temp End Function Java public static String ReturnAllData(){ String Temp = ""; Integer Counter = 0; for(int X = HeadPointer; X < TailPointer; X++){ Temp = Temp + Integer.toString(QueueArray[X]) + " "; } return Temp; }
2(e)(i)
End While ReturnValue = Enqueue(TheQueue, DataInput) If ReturnValue = 2 Then Console.WriteLine("Queue full") Else Console.WriteLine("Item inserted") End If Next Console.WriteLine(ReturnAllData(TheQueue)) Java Boolean Continue = true; Integer DataInput = -1; Scanner scanner = new Scanner(System.in); Integer ReturnValue; for(Integer x = 0; x < 10; x++){ Continue = true; while(Continue == true){ System.out.println("Enter an integer that is 0 or more"); DataInput = Integer.parseInt(scanner.nextLine()); if(DataInput > -1){ Continue = false; } } ReturnValue = Enqueue(DataInput); if(ReturnValue == -1){ System.out.println("Queue full"); }else{ System.out.println("Item inserted"); } } System.out.println(ReturnAllData());
2(e)(ii) [2 marks]
1 mark for each • All values input and 10 messages ‘Inserted’ (i.e. –1 is not inserted) • Screenshot show 10 9 8 7 6 5 4 3 2 1 on one line with a space between each number e.g.
2(f)
VB.NET Function Dequeue(ByRef AQueue As Queue) If AQueue.HeadPointer = 100 or AQueue.HeadPointer = -1 or AQueue.HeadPointer = AQueue.TailPointer Then Return -1 Else Dim Temp As Integer = AQueue.QueueArray(AQueue.HeadPointer) AQueue.HeadPointer += 1 Return Temp End If End Function Java public static Integer Dequeue(){ if(GetHeadPointer() = 100 || GetTailpointer() == -1 || GetHeadPointer() == GetTailpointer()){ return -1; }else{ Integer Temp = GetData(GetHeadPointer()); SetHeadPointer(GetHeadPointer() + 1); return Temp; } }
2(g)(i)
If ReturnValue = -1 Then Console.WriteLine("Queue empty") Else Console.WriteLine(ReturnValue, " is returned") End If Console.WriteLine(ReturnAllData(TheQueue)) Java ReturnValue = Dequeue(); if(ReturnValue == -1){ System.out.println("Queue empty"); }else{ System.out.println(ReturnValue + " is returned"); } ReturnValue = Dequeue(); if(ReturnValue == -1){ System.out.println("Queue empty"); }else{ System.out.println(ReturnValue + " is returned"); } ReturnAllData(TheQueue);
2(g)(ii) [1 mark]
1 mark each • Screenshot shows the input of 10 9 8 7 6 5 4 3 2 1 Output for 10 returned Output for 9 is returned e.g.
The diagram shows an Abstract Data Type (ADT) representation of a linked list after data items have been added.
PS is the start pointer.
PF is the free list pointer.
Labels Df, Dc, Db and Dy represent the data items of nodes in the list.
Labels Fg, Fh, Fm and Fw represent the data items of nodes in the free list.
The symbol Ø represents a null pointer.
PS
Dc Db Dy Ø
Fh Fm Fw Ø
PF
Df
Fg
(a) Describe the linked list immediately after initialisation, before any data items are added. 3 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
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. 1 mark
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.
(b) The function Enqueue() takes the data to insert into the queue as a parameter. 4 marks
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.
(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). 3 marks
Write program code for Dequeue() .
Save your program.
Copy and paste the program code into part 3(c) in the evidence document.
(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. 6 marks
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.
(ii) Write program code to amend the main program to: 1 mark
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.
(iii) Test the program with the following inputs in the order given: 2 marks
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.
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
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. 1 mark
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.
(b) The function Enqueue() takes the data to insert into the queue as a parameter. 4 marks
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.
(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). 3 marks
Write program code for Dequeue() .
Save your program.
Copy and paste the program code into part 3(c) in the evidence document.
(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. 6 marks
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.
(ii) Write program code to amend the main program to: 1 mark
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.
(iii) Test the program with the following inputs in the order given: 2 marks
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.
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
A class of students are developing a program to send data between computers. Many computers are connected together to form a wired network. Serial ports are used to connect one computer to another.
Each computer:
is assigned a unique three-digit ID
has three ports, each identified by an integer value
is connected to between one and three other computers.
Data is sent as individual message strings. Each string contains the destination ID (the ID of the computer that is to receive the message) followed by the data:
<DestinationID><Data>
Messages may pass through several computers on the way to their destination. When a message arrives at a computer, that is not the destination, the program needs to forward it on to another computer using one of its serial ports.
The port to use is obtained from information that is stored in an array RouteTable .
RouteTable is a global 2D array of integers. It is declared in pseudocode as follows:
DECLARE RouteTable : ARRAY[1:6,1:3] OF INTEGER
The values in the first two columns of RouteTable define a range of ID values.
Column 3 gives the corresponding port number to use when forwarding the message to a computer
with an ID within this range.
For example, the contents of RouteTable could be:
| Column 1 | Column 2 | Column 3 |
|---|---|---|
100 |
199 |
1 |
200 |
259 |
2 |
| −1 | <undefined> |
<undefined> |
260 |
399 |
2 |
400 |
599 |
3 |
600 |
999 |
1 |
In this example, a message that arrives with a DestinationID of "283" will be forwarded using
port 2.
Row 3 in the example shows an unused row. These may occur anywhere. Unused rows have the column 1 element set to −1. The value of unused elements in the other two columns is undefined.
The programmer has defined the first program module as follows:
| Module | Description |
|---|---|
GetPort() |
• takes a DestinationID as a parameter of type string• searches for the range corresponding to the DestinationID in the array • returns the port number, or returns −1 if no corresponding range is found |
(a) Write pseudocode for module GetPort() . 7 marks
Assume DestinationID contains a valid three-digit string.
(b) Copies of the same program will run on each computer. The program contains a global variable MyID of type string, which contains the unique ID of the computer in which the program is running. 7 marks
When messages are received, they are placed on one of two stacks. Stack 1 is used for messages that have reached their destination and stack 2 is used for messages that will be forwarded on to another computer.
Additional modules are defined:
| Module | Description |
|---|---|
StackMsg()(already written) |
• takes two parameters: ○ a string representing a message ○ an integer representing the stack number • adds the message to the required stack • returns TRUE if the message is added to the required stack,otherwise returns FALSE |
ProcessMsg() |
• takes a message as a parameter of type string • ignores any message with a zero-length data field • extract the DestinationID from the message• checks whether the DestinationID is this computer orwhether the message is to be forwarded • uses StackMsg() to add the message to the appropriatestack • outputs an error if the message could not be added to the stack |
Write pseudocode for module ProcessMsg() .
Module StackMsg() must be used.
(c) The program contains a module GetFile() which receives text files sent from another computer.
Lines from the file are sent one at a time. Each message contains one line and ProcessMsg()
from part (b) adds each message as it is received onto stack 1.
Module GetFile() removes messages from stack 1 and writes the data to a text file.
There is a problem. Under certain circumstances, the received file does not appear as expected.
Assume that while a file is being received ProcessMsg() receives only messages containing
lines from the file.
(i) Describe the circumstances and explain the problem. 3 marks
Circumstances
Explanation
(ii) Suggest a more appropriate Abstract Data Type that could be used to store the messages that would not have the same problem. 1 mark
Show mark scheme
8(a)
Port RouteTable[1, 3] END IF IF RouteTable[2, 1] <> -1 AND RouteTable[2, 1] >= DNum AND __ RouteTable[2, 2] <= DNum THEN Port RouteTable[2, 3] END IF IF RouteTable[3, 1] <> -1 AND RouteTable[3, 1] >= DNum AND __ RouteTable[3, 2] <= DNum THEN Port RouteTable[3, 3] END IF IF RouteTable[4, 1] <> -1 AND RouteTable[4, 1] >= DNum AND __ RouteTable[4, 2] <= DNum THEN Port RouteTable[4, 3] END IF IF RouteTable[5, 1] <> -1 AND RouteTable[5, 1] >= DNum AND __ RouteTable[5, 2] <= DNum THEN Port RouteTable[5, 3] END IF IF RouteTable[6, 1] <> -1 AND RouteTable[6, 1] >= DNum AND __ RouteTable[6, 2] <= DNum THEN Port RouteTable[6, 3] END IF RETURN Port ENDFUNCTION Mark as follows Max 7 : 1 Function heading and ending including parameter and return type 2 Convert parameter to a number 3 Skip all unused elements 4 Attempt to check one range 5 Check two ranges with destination correctly 6 Check all ranges with destination correctly 7 Store port value if destination matched 8 Return port value including -1 if no match found
8(b) [7 marks]
Example solution PROCEDURE ProcessMsg(ThisMsg : STRING) DECLARE ThisDest : STRING DECLARE Response : BOOLEAN DECLARE StackNum : INTEGER IF LENGTH(ThisMsg) >= 4 THEN ThisDest LEFT(ThisMsg, 3) IF ThisDest = MyID THEN // It's for this computer StackNum 1 ELSE StackNum 2 ENDIF Response StackMsg(ThisMsg, StackNum) IF Response = FALSE THEN OUTPUT "Message discarded - no room on stack" ENDIF ENDIF ENDPROCEDURE Mark as follows:
- Ignore message if data field is empty
- Extract from ThisDest ThisMsg
- Test if destination is this computer
- Attempt to use StackMsg()
Fully correct use of for both cases / stacks StackMsg() 6. Test return value for both cases StackMsg() 7. Following a reasonable attempt at MP6 output warning if StackMsg() returns FALSE
8(c)(i) [3 marks]
One mark per point Max 3 marks: Decide on scenario and mark accordingly. Scenario one : • If more than one line is / all lines are stored on the stack (before line(s) are removed) • The stack operates as a FILO device // Last item added to stack will be in first item out • So lines in the file appear out of sequence Scenario two: • Stack is Full • Not all lines can be stored on the stack • so resulting file will not contain all the original lines Scenario three: • (All) the data in a line read can’t be stored on the stack • Stack elements have not been allocated enough memory • so only part of each line is stored in the file Scenario four: • Stack is empty • The stack is being read faster than it is being written to • so blank lines may be inserted into the file
8(c)(ii) [1 mark]
Queue
Show mark scheme
3(a)(i)
One mark for structure Structure: Record One mark for each point Advantage: A set of data / all data related to one customer of different types is held under a single identifier/entity
3(a)(ii) [5 marks]
A (1D) array of records // An array of the given type could be used One mark per underlined word
3(b) [6 marks]
One mark for reference to each: 1 Reference to the use of constants or variables for the two threshold values of 10 and 100 // Input amount spent (by customer and store in a numeric variable) 2 Work out one band that amount maps to 3 Work out all bands that amount maps to 4 Calculate rounded value of amount / whole number part of amount 5 Calculate the points by multiplying the (rounded) amount by the appropriate value for appropriate band /all bands 6 Output the number of points Note: Max 5 from available points Function Replace(OldString : STRING, Char1, Char2 :
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.
Show mark scheme
3(a)(i)
One mark per point: 1 Check that the queue is not full 2 pointer will move to point to location 9 EoQ 3 Data item Orange will be stored in location referenced by EoQ pointer 4 pointer will move to point to location 0 EoQ 5 Data item Yellow will be stored in location referenced by EoQ pointer Note: max 4 marks
3(a)(ii) [5 marks]
7
3(b) [6 marks]
One mark per bullet: 1 Open file in mode READ 2 Loop to // read / process all the lines in file EOF() 3 Loop will end when return value from is / queue AddToQueue() FALSE is full 4 Read a line from the file in a loop 5 Pass string to // is executed with AddToQueue() AddToQueue() line as parameter Function GetNum(ThisString : STRING, ThisChar : CHAR)
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
TopOfStackpointer points to the last item added to the stack.The
BottomOfStackpointer points to the first item on the stack.The stack grows upwards when items are added.
| Stack | |
|---|---|
| Memory location | Value |
| 506 | |
| 505 | WWW |
| 504 | YYY |
| 503 | XXX |
| 502 | ZZZ |
| 501 | NNN |
| 500 | PPP |
(i) An error will be generated if an attempt is made to POP a value when the stack is empty. 1 mark
State the maximum number of consecutive POP operations that could be performed on the stack shown above before an error is generated.
(ii) The following operations are performed:
- POP and store value in variable
Data1 - POP and store value in variable
Data2 - PUSH value AAA
- PUSH value BBB
- POP and discard value
- POP and store value in variable
Data2
Show mark scheme
3(a)(i) [4 marks]
6
3(a)(ii) [1 mark]
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) [5 marks]
So that the data may be recovered / restored (the next time the program is run) // the data is permanently saved / data is not lost when the program terminates
3(b)(ii) [6 marks]
Max 5 marks 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 FUNCTION MakeString(Count : INTEGER, AChar : CHAR)
(b) Complete the following pseudocode for the function Dequeue to remove the front item from the queue. 4 marks
FUNCTION Dequeue RETURNS STRING
DECLARE Item : STRING
______ > 0 THEN
Item ←
IF Length = 0 THEN
CALL Initialise // reset the pointers
ELSE
IF FrontPointer > MaxSize THEN
______ ← 1
ENDIF
ENDIF
ELSE
OUTPUT "The print queue was empty – error!"
Item ← ""
ENDIF
RETURN Item
ENDFUNCTION
(c) Explain how a new element can be added to the queue if it is implemented using two stacks. 4 marks 2 marks
12 (a) Describe what is meant by recursion.
Show mark scheme
11(a) [4 marks]
One mark per mark point ( Max 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
11(b) [4 marks]
One mark for each correctly completed line ( Max 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 ) 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.
(b) Complete the Karnaugh map (K‑map) for the given truth table. 2 marks
AB
CD
(c) Draw loop(s) around appropriate group(s) in the K‑map to produce an optimal sum‑of‑products. 2 marks
(d) Write the Boolean logic expression from your answer to part (c) as a simplified sum‑of‑products. 2 marks
Z =
(e) Use Boolean algebra to give your answer to part (d) in its simplest form. 1 mark
Z = [1]
10 (a) State one category of machine learning.
(b) Calculate the path that takes the shortest time to travel from the Begin node to the End node, using the A* algorithm. 5 marks 2 marks
Show your working in the table provided.
The first two rows have already been completed.
| Start node | Destination node |
Cost from start node (g) |
Heuristic (h) |
Total (f = g + h) |
|---|---|---|---|---|
| Begin | Begin | 0 | 12 | 12 |
| Begin | A | 5 | 8 | 13 |
Final path 11 (a) The pseudocode shown represents a queue Abstract Data Type (ADT) with procedures for initialisation and to add new items. It is incomplete.
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
______ 0
ENDPROCEDURE
// adding a new item to the queue
PROCEDURE Enqueue(NewItem : STRING)
IF ______ THEN
RearPointer
IF RearPointer > MaxLength – 1 THEN
RearPointer 0
ENDIF
Length Length + 1
ENDIF
ENDPROCEDURE
| (i) Study the pseudoc | code and insert th | he identifiers to complete this table. |
|---|---|---|
| Identifier | Data type | Description |
STRING |
An array to store the contents of the queue. | |
INTEGER |
Points to the last item of the queue. | |
INTEGER |
Indicates the number of items in the queue. | |
INTEGER |
Points to the first item of the queue. |
(ii) Complete the given pseudocode. [5]
(b) Explain the reasons why a queue ADT works better than a stack ADT in organising print jobs. 3 marks
Show mark scheme
11(a)(i) [5 marks]
One mark for every two correct identifiers (Max 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 ) 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) [3 marks]
One mark per mark point ( Max 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.
(b) Complete the following pseudocode for the function Dequeue to remove the front item from the queue. 4 marks
FUNCTION Dequeue RETURNS STRING
DECLARE Item : STRING
______ > 0 THEN
Item ←
IF Length = 0 THEN
CALL Initialise // reset the pointers
ELSE
IF FrontPointer > MaxSize THEN
______ ← 1
ENDIF
ENDIF
ELSE
OUTPUT "The print queue was empty – error!"
Item ← ""
ENDIF
RETURN Item
ENDFUNCTION
(c) Explain how a new element can be added to the queue if it is implemented using two stacks. 4 marks 2 marks
12 (a) Describe what is meant by recursion.
Show mark scheme
11(a) [4 marks]
One mark per mark point ( Max 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
11(b) [4 marks]
One mark for each correctly completed line ( Max 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 ) 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.
A 1D array Data of type integer contains 200 elements. Each element has a unique value.
An algorithm is required to search for the largest value and output it.
Describe the steps that the algorithm should perform.
Do not include pseudocode statements in your answer. 5 marks
Show mark scheme
3 [5 marks]
One mark per point ( Max 5 ): 1 Declare a variable / an integer Max 2 Assign value of first / any element to Max 3 Set up a loop to repeat 200 times / from start to end of array 4 Use the loop counter as the array index 5 If value of current element is greater than ... Max 6 ...then assign value to Max 7 After the loop, Output Max
A binary tree consists of nodes. Each node has 3 integer values: a left pointer, data and a right pointer.
The binary tree is stored using a global 2D array.
The pseudocode declaration for the array is:
DECLARE ArrayNodes : ARRAY[0:19, 0:2] OF INTEGER
For example:
ArrayNodes[0, 0]stores the left pointer for the first node.ArrayNodes[0, 1]stores the data for the first node.ArrayNodes[0, 2]stores the right pointer for the first node.
–1 indicates a null pointer, or null data.
(a) Write program code to: 3 marks
declare the global 2D array
ArrayNodesinitialise all 3 integer values to
–1for each node.
Save your program as Question3_N22 .
Copy and paste the program code into part 3(a) in the evidence document.
(b) The binary tree stores the following values: 2 marks
| Left pointer | Data | Right pointer |
|---|---|---|
| 1 | 20 | 5 |
| 2 | 15 | –1 |
| –1 | 3 | 3 |
| –1 | 9 | 4 |
| –1 | 10 | –1 |
| –1 | 58 | –1 |
| –1 | –1 | –1 |
FreeNode stores the index of the first free element in the array, initialised to 6.
RootPointer stores the index of the first node in the tree, initialised to 0.
Amend your program by writing program code to store the given data in ArrayNodes and
initialise the free node and root node pointers.
Save your program.
Copy and paste the program code into part 3(b) in the evidence document.
(c) The following recursive pseudocode function searches the binary tree for a given value. If the value is found, the function must return the index of the value. If the value is not found, the function must return –1. 5 marks
The function is incomplete. There are four incomplete statements.
FUNCTION SearchValue(Root : INTEGER,
ValueToFind : INTEGER) RETURNS INTEGER
IF Root = –1 THEN
RETURN –1
ELSE
IF ArrayNodes[Root, 1] = ValueToFind THEN
RETURN
ELSE
IF ArrayNodes[Root, 1] = –1 THEN
RETURN –1
ENDIF
ENDIF
ENDIF
IF ArrayNodes[Root, 1] ______ ValueToFind THEN
RETURN SearchValue(ArrayNodes[ ______ , 0], ValueToFind)
ENDIF
IF ArrayNodes[Root, ______ ] < ValueToFind THEN
RETURN SearchValue(ArrayNodes[Root, 2], ValueToFind)
ENDIF
ENDFUNCTION
Write program code for the function SearchValue() .
Save your program.
Copy and paste the program code into part 3(c) in the evidence document.
(d) A post order traversal performs the following operation: 7 marks
visit the left node
visit the right node
output the root.
For example, in the following tree, the output would be: 3 9 25 60 50
An outline of the PostOrder() procedure is:
If left node is not empty, make a recursive call with the left node as the root.
If right node is not empty, make a recursive call with the right node as the root.
Output the current root node.
The procedure PostOrder() takes the root node as a parameter.
Write program code for the procedure PostOrder() .
Save your program.
Copy and paste the program code into part 3(d) in the evidence document. (e) (i) Amend the main program by writing program code to: 3 marks
call the function
SearchValue()to find the position of the number 15 in the treeuse the result from
SearchValue()to output either the index of the value if found, or an appropriate message to state that the value was not foundcall the procedure
PostOrder().
Save your program.
Copy and paste the program code into part 3(e)(i) in the evidence document.
(ii) Test your program. 1 mark
Take a screenshot to show the output.
Copy and paste the screenshot into part 3(e)(ii) in the evidence document.
Show mark scheme
3(a) [3 marks]
1 mark per point: • Declaring (global) 2D array ArrayNodes • looping through all 20 3 elements of array … • …. storing −1 in each element Example program code: Java public static Integer[][] ArrayNodes = new Integer[20][3]; for(Integer X = 0; X<20; X++){ for(Integer Y = 0; Y<3; Y++){ ArrayNodes[X][Y] = -1 }} Python ArrayNodes = [] for x in range(0, 20): ArrayNodes.append([-1, -1, -1]) VB.NET Dim ArrayNodes(19, 2) As Integer Sub main() For X = 0 To 19 For Y = 0 To 2 ArrayNodes(X, Y) = -1 Next Next End Sub
3(b)
VB.NET ArrayNodes(0, 0) = 1 ArrayNodes(0, 1) = 20 ArrayNodes(0, 2) = 5 ArrayNodes(1, 0) = 2 ArrayNodes(1, 1) = 15 ArrayNodes(1, 2) = -1 ArrayNodes(2, 0) = -1 ArrayNodes(2, 1) = 3 ArrayNodes(2, 2) = 3 ArrayNodes(3, 0) = -1 ArrayNodes(3, 1) = 9 ArrayNodes(3, 2) = 4 ArrayNodes(4, 0) = -1 ArrayNodes(4, 1) = 10 ArrayNodes(4, 2) = -1 ArrayNodes(5, 0) = -1 ArrayNodes(5, 1) = 58 ArrayNodes(5, 2) = -1 Dim FreeNode As Integer = 6 Dim RootPointer As Integer = 0
3(c)
Java public static Integer SearchValue(Integer Root, Integer ValueToFind){ if(Root == -1){ return -1; }else if(ArrayNodes[Root][1] == ValueToFind){; return Root ; }else if(ArrayNodes[Root][1] == -1){ return -1; } if(ArrayNodes[Root][1]
ValueToFind){ return(SearchValue(ArrayNodes[ Root ][0], ValueToFind)); } if(ArrayNodes[Root][ 1 ] < ValueToFind){ return(SearchValue(ArrayNodes[Root][2], ValueToFind)); } return -1; } VB.NET Function SearchValue(ByVal Root, ByVal ValueToFind) If ArrayNodes(Root, 1) = ValueToFind Then Return Root ElseIf ArrayNodes(Root, 1) = -1 Then Return -1 End If If ArrayNodes(Root, 1)
ValueToFind Then Return SearchValue(ArrayNodes( Root , 0), ValueToFind) End If If ArrayNodes(Root, 1 ) < ValueToFind Then Return SearchValue(ArrayNodes(Root, 2), ValueToFind) End If Return -1 End Function
3(d) [7 marks]
1 mark per point ( Max 7 ): • (procedure) header (and end where appropriate) with one parameter (root node or index of root node) and at least one recursive call • checking if left node is −1 … • … if not recursive call with parameter as ArrayNodes[RootNode[0]] • checking if right node is −1 … • …if not recursive call with parameter as ArrayNodes[RootNode[2]] • outputting the element at the parameter RootNode[] • all 3 in the correct order Example program code: Python def PostOrder(RootNode): if RootNode[0] != -1: PostOrder(ArrayNodes[RootNode[0]]) if RootNode[2] != -1: PostOrder(ArrayNodes[RootNode[2]]) print(str(RootNode[1])) Java public static void PostOrder(Integer[] RootNode){ if(RootNode[0] != -1){ PostOrder(ArrayNodes[RootNode[0]]); } if(RootNode[2] != -1){ PostOrder(ArrayNodes[RootNode[2]]); } System.out.println(RootNode[1]); } VB.NET Sub PostOrder(RootNode() As Integer) Dim TempArray(2) As Integer If RootNode(0) <> -1 Then TempArray(0) = ArrayNodes(RootNode(0), 0) TempArray(1) = ArrayNodes(RootNode(0), 1) TempArray(2) = ArrayNodes(RootNode(0), 2) PostOrder(TempArray) End If If RootNode(2) <> -1 Then TempArray(0) = ArrayNodes(RootNode(2), 0) TempArray(1) = ArrayNodes(RootNode(2), 1) TempArray(2) = ArrayNodes(RootNode(2), 2) PostOrder(TempArray) End If Console.WriteLine(RootNode(1)) End Sub
3(e)(i) [3 marks]
1 mark per point: • calling with 15 and as a parameter … SearchValue() rootPointer • … if return value
-1 output returned index and if return value = -1 output not found Both as appropriate messages • Calling with as a PostOrder() ArrayNodes[RootPointer] parameter Example program code: Python ReturnValue = SearchValue(RootPointer, 15) if ReturnValue == -1: print("Not found") else: print("Found at " + str(ReturnValue)) PostOrder(ArrayNodes[RootPointer]) Java Integer ReturnValue = SearchValue(RootPointer, 15); if(ReturnValue == -1){ System.out.println("Not found"); } else { System.out.println("Found at " + ReturnValue); } PostOrder(ArrayNodes[RootPointer]); VB.NET Dim returnvalue As Integer = SearchValue(RootPointer, 15) If returnvalue = -1 Then Console.WriteLine("Not found") Else Console.WriteLine("Found at " & returnvalue) End If Console.WriteLine("Post order") Dim TempArray(2) As Integer TempArray(0) = ArrayNodes(RootPointer, 0) TempArray(1) = ArrayNodes(RootPointer, 1) TempArray(2) = ArrayNodes(RootPointer, 2) PostOrder(TempArray)
3(e)(ii) [1 mark]
Screenshot with result as shown, for example:
A program uses a linear queue to store up to 100 integers.
(a) A 1D array, Queue, is used to store the data. The head pointer points to the first number stored in the queue and the tail pointer points to the next free space in the queue. 3 marks
Write program code to:
declare the global array
Queuedeclare the global variable head pointer and assign an appropriate initial value
declare the global variable tail pointer and assign an appropriate initial value.
Save your program as Question3_N22 .
Copy and paste the program code into part 3(a) in the evidence document.
(b) The function Enqueue() takes an integer value as a parameter and stores it in the queue. It returns TRUE if the value was successfully stored and FALSE otherwise. 6 marks
Write program code for the function Enqueue() .
Save your program.
Copy and paste the program code into part 3(b) in the evidence document.
(c) The main program uses the Enqueue() function to store the numbers 1 to 20 (inclusive) 4 marks
in the queue, in ascending numerical order. The program should output ‘Successful’ if all numbers are successfully enqueued, and ‘Unsuccessful’ otherwise.
Amend the main program by writing program code to perform this task.
Save your program.
Copy and paste the program code into part 3(c) in the evidence document.
(d) The following iterative pseudocode function calculates the total of all the values stored in the queue. 6 marks
FUNCTION IterativeOutput(Start: INTEGER) RETURNS INTEGER
DECLARE Total : INTEGER
Total 0
# ←
FOR Count Start - 1 TO HeadPointer STEP -1
# ←
Total Total + Queue[Count]
# ←
NEXT Count
RETURN Total
ENDFUNCTION
Rewrite the function as a recursive function using program code.
Save your program.
Copy and paste the program code into part 3(d) in the evidence document.
(e) The main program calls the recursive function from part 3(d) and outputs the value returned.
(i) Amend the main program by writing program code to perform this task. 1 mark
Save your program.
Copy and paste the program code into part 3(e)(i) in the evidence document.
(ii) Test your program. 1 mark
Take a screenshot to show the output.
Copy and paste the screenshot into part 3(e)(ii) in the evidence document.
Show mark scheme
3(a) [3 marks]
1 mark per point: • 1D array with 100 (Integer) spaces • head pointer declared initialised to appropriate value e.g. −1 • tail pointer declared initialised to 0 Example program code: Java public Integer[] queue = new Integer[100]; public Integer HeadPointer = -1; public Integer TailPointer = 0; Python Queue = [-1 for I in range(100)] #Integer HeadPointer = -1 TailPointer = 0 VB.NET Dim Queue(0 To 99) As Integer Dim HeadPointer As Integer = -1 Dim TailPointer As Integer = 0
3(b) [6 marks]
1 mark per point: • Function header (and close where appropriate) with integer parameter • Checking if queue full and returning false • If not full adding parameter to queue at tail pointer … • … incrementing tail pointer (after adding to queue) • … and returning true • Changing head pointer to 0 if this is the first element in array Example program code: Java public Boolean Enqueue(Integer Data){ if(TailPointer < 100){ if(HeadPointer == -1){ HeadPointer = 0; } Queue[TailPointer] = Data; TailPointer = TailPointer + 1; return true; } return false; } Python def Enqueue(Data): global Queue global TailPointer if(TailPointer < 100): if HeadPointer == -1: HeadPointer = 0 Queue[TailPointer] = Data TailPointer = TailPointer + 1 return True return False VB.NET Function Enqueue(Data) If TailPointer < 100 Then If HeadPointer = -1 Then HeadPointer = 0 End If Queue(TailPointer) = data TailPointer = TailPointer + 1 Return True End If Return False End Function
3(c) [4 marks]
1 mark per point: • Looping 20 times • … using with each number 1 to 20 in ascending numerical Enqueue() order… • … and storing/using the return value • … based on return value, outputting "Successful" and "Unsuccessful" if all numbers are added Example program code: Java public static void main(String[] args){ Boolean success = false; for(Integer count = 1; count <= 20; count++){ success = enqueue(count); } if(success == false){ System.Out.Println("Unsuccessful ") else{ System.Out.Println("Successful ") } } Python Success = False for Count in range(1, 21): Success = Enqueue(Count) if(Success == False): print("Unsuccessful") else: print("Successful") VB.NET Dim Success As Boolean For Count = 1 To 20 Success = Enqueue(Count) Next If Success = False THEN Console.WriteLine("Unsuccessful") ELSE Console.WriteLine("Successful") ENDIF
3(d) [6 marks]
1 mark per point: • function call (and end where appropriate) taking a parameter • checking if at start of queue//20 … • …returning the last value in the queue • (otherwise) adding return value to a total // adding value in queue before recursive call and using this in the recursive call … • recursive call with Start/pointer −1 • returning the final total Example program code: Java public static Integer RecursiveOutput(Integer Start){ if(Start == 0){ return Queue[Start]; }else{ return Queue[Start] + RecursiveOutput(Start -1); }} Python def RecursiveOutput(Start): if(Start == 0): return Queue[Start] else: return Queue[Start] + RecursiveOutput(Start - 1) VB.NET Function RecursiveOutput(ByVal Start) If (Start = 0) Then Return Queue(Start) Else Return Queue(Start) + RecursiveOutput(Start - 1) End If End Function
3(e)(i) [1 mark]
1 mark for calling function and outputting return value. Example program code: Java System.out.println(RecursiveOutput(TailPointer-1)); Python print(str(RecursiveOutput(TailPointer - 1))) VB.NET Console.WriteLine(RecursiveOutput(TailPointer - 1))
3(e)(ii) [1 mark]
1 mark for screenshot showing 210, for example:
A binary tree consists of nodes. Each node has 3 integer values: a left pointer, data and a right pointer.
The binary tree is stored using a global 2D array.
The pseudocode declaration for the array is:
DECLARE ArrayNodes : ARRAY[0:19, 0:2] OF INTEGER
For example:
ArrayNodes[0, 0]stores the left pointer for the first node.ArrayNodes[0, 1]stores the data for the first node.ArrayNodes[0, 2]stores the right pointer for the first node.
–1 indicates a null pointer, or null data.
(a) Write program code to: 3 marks
declare the global 2D array
ArrayNodesinitialise all 3 integer values to
–1for each node.
Save your program as Question3_N22 .
Copy and paste the program code into part 3(a) in the evidence document.
(b) The binary tree stores the following values: 2 marks
| Left pointer | Data | Right pointer |
|---|---|---|
| 1 | 20 | 5 |
| 2 | 15 | –1 |
| –1 | 3 | 3 |
| –1 | 9 | 4 |
| –1 | 10 | –1 |
| –1 | 58 | –1 |
| –1 | –1 | –1 |
FreeNode stores the index of the first free element in the array, initialised to 6.
RootPointer stores the index of the first node in the tree, initialised to 0.
Amend your program by writing program code to store the given data in ArrayNodes and
initialise the free node and root node pointers.
Save your program.
Copy and paste the program code into part 3(b) in the evidence document.
(c) The following recursive pseudocode function searches the binary tree for a given value. If the value is found, the function must return the index of the value. If the value is not found, the function must return –1. 5 marks
The function is incomplete. There are four incomplete statements.
FUNCTION SearchValue(Root : INTEGER,
ValueToFind : INTEGER) RETURNS INTEGER
IF Root = –1 THEN
RETURN –1
ELSE
IF ArrayNodes[Root, 1] = ValueToFind THEN
RETURN
ELSE
IF ArrayNodes[Root, 1] = –1 THEN
RETURN –1
ENDIF
ENDIF
ENDIF
IF ArrayNodes[Root, 1] ______ ValueToFind THEN
RETURN SearchValue(ArrayNodes[ ______ , 0], ValueToFind)
ENDIF
IF ArrayNodes[Root, ______ ] < ValueToFind THEN
RETURN SearchValue(ArrayNodes[Root, 2], ValueToFind)
ENDIF
ENDFUNCTION
Write program code for the function SearchValue() .
Save your program.
Copy and paste the program code into part 3(c) in the evidence document.
(d) A post order traversal performs the following operation: 7 marks
visit the left node
visit the right node
output the root.
For example, in the following tree, the output would be: 3 9 25 60 50
An outline of the PostOrder() procedure is:
If left node is not empty, make a recursive call with the left node as the root.
If right node is not empty, make a recursive call with the right node as the root.
Output the current root node.
The procedure PostOrder() takes the root node as a parameter.
Write program code for the procedure PostOrder() .
Save your program.
Copy and paste the program code into part 3(d) in the evidence document. (e) (i) Amend the main program by writing program code to: 3 marks
call the function
SearchValue()to find the position of the number 15 in the treeuse the result from
SearchValue()to output either the index of the value if found, or an appropriate message to state that the value was not foundcall the procedure
PostOrder().
Save your program.
Copy and paste the program code into part 3(e)(i) in the evidence document.
(ii) Test your program. 1 mark
Take a screenshot to show the output.
Copy and paste the screenshot into part 3(e)(ii) in the evidence document.
Show mark scheme
3(a) [3 marks]
1 mark per point: • Declaring (global) 2D array ArrayNodes • looping through all 20 3 elements of array … • …. storing −1 in each element Example program code: Java public static Integer[][] ArrayNodes = new Integer[20][3]; for(Integer X = 0; X<20; X++){ for(Integer Y = 0; Y<3; Y++){ ArrayNodes[X][Y] = -1 }} Python ArrayNodes = [] for x in range(0, 20): ArrayNodes.append([-1, -1, -1]) VB.NET Dim ArrayNodes(19, 2) As Integer Sub main() For X = 0 To 19 For Y = 0 To 2 ArrayNodes(X, Y) = -1 Next Next End Sub
3(b)
VB.NET ArrayNodes(0, 0) = 1 ArrayNodes(0, 1) = 20 ArrayNodes(0, 2) = 5 ArrayNodes(1, 0) = 2 ArrayNodes(1, 1) = 15 ArrayNodes(1, 2) = -1 ArrayNodes(2, 0) = -1 ArrayNodes(2, 1) = 3 ArrayNodes(2, 2) = 3 ArrayNodes(3, 0) = -1 ArrayNodes(3, 1) = 9 ArrayNodes(3, 2) = 4 ArrayNodes(4, 0) = -1 ArrayNodes(4, 1) = 10 ArrayNodes(4, 2) = -1 ArrayNodes(5, 0) = -1 ArrayNodes(5, 1) = 58 ArrayNodes(5, 2) = -1 Dim FreeNode As Integer = 6 Dim RootPointer As Integer = 0
3(c)
Java public static Integer SearchValue(Integer Root, Integer ValueToFind){ if(Root == -1){ return -1; }else if(ArrayNodes[Root][1] == ValueToFind){; return Root ; }else if(ArrayNodes[Root][1] == -1){ return -1; } if(ArrayNodes[Root][1]
ValueToFind){ return(SearchValue(ArrayNodes[ Root ][0], ValueToFind)); } if(ArrayNodes[Root][ 1 ] < ValueToFind){ return(SearchValue(ArrayNodes[Root][2], ValueToFind)); } return -1; } VB.NET Function SearchValue(ByVal Root, ByVal ValueToFind) If ArrayNodes(Root, 1) = ValueToFind Then Return Root ElseIf ArrayNodes(Root, 1) = -1 Then Return -1 End If If ArrayNodes(Root, 1)
ValueToFind Then Return SearchValue(ArrayNodes( Root , 0), ValueToFind) End If If ArrayNodes(Root, 1 ) < ValueToFind Then Return SearchValue(ArrayNodes(Root, 2), ValueToFind) End If Return -1 End Function
3(d) [7 marks]
1 mark per point ( Max 7 ): • (procedure) header (and end where appropriate) with one parameter (root node or index of root node) and at least one recursive call • checking if left node is −1 … • … if not recursive call with parameter as ArrayNodes[RootNode[0]] • checking if right node is −1 … • …if not recursive call with parameter as ArrayNodes[RootNode[2]] • outputting the element at the parameter RootNode[] • all 3 in the correct order Example program code: Python def PostOrder(RootNode): if RootNode[0] != -1: PostOrder(ArrayNodes[RootNode[0]]) if RootNode[2] != -1: PostOrder(ArrayNodes[RootNode[2]]) print(str(RootNode[1])) Java public static void PostOrder(Integer[] RootNode){ if(RootNode[0] != -1){ PostOrder(ArrayNodes[RootNode[0]]); } if(RootNode[2] != -1){ PostOrder(ArrayNodes[RootNode[2]]); } System.out.println(RootNode[1]); } VB.NET Sub PostOrder(RootNode() As Integer) Dim TempArray(2) As Integer If RootNode(0) <> -1 Then TempArray(0) = ArrayNodes(RootNode(0), 0) TempArray(1) = ArrayNodes(RootNode(0), 1) TempArray(2) = ArrayNodes(RootNode(0), 2) PostOrder(TempArray) End If If RootNode(2) <> -1 Then TempArray(0) = ArrayNodes(RootNode(2), 0) TempArray(1) = ArrayNodes(RootNode(2), 1) TempArray(2) = ArrayNodes(RootNode(2), 2) PostOrder(TempArray) End If Console.WriteLine(RootNode(1)) End Sub
3(e)(i) [3 marks]
1 mark per point: • calling with 15 and as a parameter … SearchValue() rootPointer • … if return value
-1 output returned index and if return value = -1 output not found Both as appropriate messages • Calling with as a PostOrder() ArrayNodes[RootPointer] parameter Example program code: Python ReturnValue = SearchValue(RootPointer, 15) if ReturnValue == -1: print("Not found") else: print("Found at " + str(ReturnValue)) PostOrder(ArrayNodes[RootPointer]) Java Integer ReturnValue = SearchValue(RootPointer, 15); if(ReturnValue == -1){ System.out.println("Not found"); } else { System.out.println("Found at " + ReturnValue); } PostOrder(ArrayNodes[RootPointer]); VB.NET Dim returnvalue As Integer = SearchValue(RootPointer, 15) If returnvalue = -1 Then Console.WriteLine("Not found") Else Console.WriteLine("Found at " & returnvalue) End If Console.WriteLine("Post order") Dim TempArray(2) As Integer TempArray(0) = ArrayNodes(RootPointer, 0) TempArray(1) = ArrayNodes(RootPointer, 1) TempArray(2) = ArrayNodes(RootPointer, 2) PostOrder(TempArray)
3(e)(ii) [1 mark]
Screenshot with result as shown, for example:
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 location |
Value |
|---|---|
| 200 | |
| 201 | |
| 202 | |
| 203 | 'F' |
| 204 | 'C' |
| 205 | 'D' |
| 206 | 'E' |
| 207 | 'H' |
(a) Complete the following table by writing the answers. 2 marks
| Answer | |
|---|---|
| The value that has been on the stack for the longest time. | |
The memory location pointed to byTopOfStack ifthree POPoperations are performed. |
Show mark scheme
4(a) [4 marks]
One mark per row The value that has been on the stack for the longest time. 'H' The memory location pointed to by if three TopOfStack 206 POP operations are performed.
4(b) [6 marks]
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 pointing to 'D' TopOfStack 2 Value 'D' in 201 3 Values 'C' & 'A' in 202 and 203 4 Values 'X' to 'P' unchanged (204 to 207)
A program uses a circular queue to store strings. The queue is created as a 1D array, QueueArray,
with 10 string items.
The following data is stored about the queue:
the head pointer initialised to 0
the tail pointer initialised to 0
the number of items in the queue initialised to 0.
(a) Declare the array, head pointer, tail pointer and number of items. 2 marks
If you are writing in Python, include attribute declarations using comments.
Save your program as Question3_J2022 .
Copy and paste the program code into part 3(a) in the evidence document.
(b) The function Enqueue is written in pseudocode. The function adds DataToAdd to the queue. 7 marks
It returns FALSE if the queue is full and returns TRUE if the item is added.
The function is incomplete, there are five incomplete statements.
FUNCTION Enqueue(BYREF QueueArray[] : STRING, BYREF HeadPointer : INTEGER,
BYREF TailPointer : INTEGER, NumberItems : INTEGER,
DataToAdd : STRING) RETURNS BOOLEAN
IF NumberItems = …………………………………… THEN
RETURN ……………………………………
ENDIF
QueueArray[ …………………………………… ] DataToAdd
←
IF TailPointer >= 9 THEN
TailPointer ……………………………………
←
ELSE
TailPointer TailPointer + 1
# ←
ENDIF
NumberItems NumberItems ……………………………………
←
RETURN TRUE
ENDFUNCTION
Write program code for the function Enqueue() .
Save your program.
Copy and paste the program code into part 3(b) in the evidence document.
(c) The function Dequeue() returns "FALSE" if the queue is empty, or it returns the next data item in the queue. 6 marks
Write program code for the function Dequeue() .
Save your program.
Copy and paste the program code into part 3(c) in the evidence document. (d) (i) Amend the main program to: 5 marks
take as input 11 string values from the user
use the
Enqueue()function to add each element to the queueoutput an appropriate message to state whether each addition was successful, or not
call
Dequeue()function twice and output the return value each time.
Save your program.
Copy and paste the program code into part 3(d)(i) in the evidence document.
(ii) Test your program with the input data: 1 mark
"A" "B" "C" "D" "E" "F" "G" "H" "I" "J" "K"
Take a screenshot to show the output.
Copy and paste the screenshot into part 3(d)(ii) in the evidence document.
Show mark scheme
3(a) [2 marks]
1 mark per mark point Declaring variables: head pointer, tail pointer and number of items all initialised as 0 (integer) QueueArray declared as 1D array as string with 10 elements Example program code: public static void main(String[] args){ String[] QueueArray = new String[10]; Integer QueueHeadPointer = 0; Integer QueueTailPointer = 0; Integer NumberOfItems = 0; Python QueueArray = ['','','','','','','','','',''] #string QueueHeadPointer = 0 #integer QueueTailPointer = 0 #integer NumberOfItems = 0 #integer VB.NET Sub Main() Dim QueueArray(0 To 9) As String Dim QueueHeadPointer As Integer = 0 Dim QueueTailPointer As Integer = 0 Dim NumberOfItems As Integer = 0 End Sub
3(b)
Python def Enqueue(Queue, Head, Tail, NumItems, InputData): if NumItems >= 10: return (False, Queue, Head, Tail, NumItems) Queue[Tail] = InputData if Tail >= 9: Tail = 0 else: Tail = Tail + 1 NumItems = NumItems + 1 return (True, Queue, Head, Tail, NumItems) VB.NET Function Enqueue(ByRef Queue() As String, ByRef Head As Integer, ByRef Tail As Integer, ByRef NumItems As Integer, ByRef InputData As String) If NumItems = 10 Then Return False End If Queue(Tail) = InputData If Tail >= 9 Then Tail = 0 Else Tail = Tail + 1
3(c)
VB.NET Function Dequeue(ByRef QueueArray() As String, ByRef QueueHeadPointer As Integer, ByRef QueueTailpointer As Integer, ByRef NumberOfItems As Integer) If NumberOfItems = 0 Then Return "False" Else Dim ReturnValue = QueueArray(QueueHeadPointer) QueueHeadPointer = QueueHeadPointer + 1 If QueueHeadPointer >= 9 Then QueueHeadPointer = 0 End If NumberOfItems = NumberOfItems - 1 Return ReturnValue End If End Function
3(d)(i)
Python for x in range(0, 11): InputString = input("Enter a string") ReturnValue, QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems = Enqueue(QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems, InputString) if ReturnValue == True: print("Successful") else: print("Unsuccessful") ReturnValue, QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems = Dequeue(QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems) print(ReturnValue) ReturnValue, QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems = Dequeue(QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems) print(ReturnValue) VB.NET For x = 0 To 10 Console.WriteLine("Enter a string") InputString = Console.ReadLine If(Enqueue(QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems, InputString)) Console.WriteLine("Successful") Else Console.WriteLine("Unsuccessful") End If Console.WriteLine(Dequeue) Console.WriteLine(Dequeue)
3(d)(ii) [1 mark]
1 mark for showing inputs and outputs: A – J input and successful. K input and unsuccessful. Output: A, B
A programmer is designing a computer game that uses a set of cards.
Each card has a number and a colour. The cards are saved in the text file CardValues.txt
| The program has a class named Card. The class has the following attributes and methods. Card | |
|---|---|
Card |
Card |
| Number : INTEGER Colour : STRING |
The number of the card The colour of the card |
| Constructor() GetNumber() GetColour() |
Takes two values as parameters and sets them to the private attributes Returns the number of the card Returns the colour of the card |
(a) The constructor takes the number and colour of the card as parameters and sets them to the private attributes. 5 marks
Write program code to declare the class Card and its constructor. Do not write any other methods.
Use your programming language appropriate constructor.
All attributes should be private. If you are writing in Python, include attribute declarations using comments.
Save your program as Question3_J22 .
Copy and paste the program code into part 3(a) in the evidence document.
(b) The two get methods return the associated attribute. 3 marks
Write program code for the get methods GetNumber() and GetColour() .
Save your program.
Copy and paste the program code into part 3(b) in the evidence document.
(c) The text file CardValues.txt stores the data for 30 cards, in the order: number, colour. 7 marks
For example, the first card in the text file:
1 is the number
red is the colour.
A 1D array of type Card is declared to store all the cards read in from CardValues.txt
Write the main program to:
declare an array of type Card with 30 elements
read in the data for the 30 cards from CardValues.txt and assign each to the array.
Save your program.
Copy and paste the program code into part 3(c) in the evidence document.
(d) The program needs to allow all players (maximum of 5) to select 4 cards from the 30 available. 6 marks
A card can only be selected once, so the program needs to record which cards have already been selected.
The function, ChooseCard() :
takes as input an integer to represent an array index from 1 to 30
validates that the value is between 1 and 30 inclusive
checks if the card is available (it has not already been selected)
loops until an available card is selected
returns the index of the card if it is available.
Amend the program to store which cards have already been selected and write program code for the function ChooseCard() .
Save your program.
Copy and paste the program code into part 3(d) in the evidence document.
(e) The main program needs to allow one player to select all their 4 cards.
(i) Amend the main program to: 5 marks
create an array, Player1, for player 1 of type Card
ask player 1 to input 4 integers using the function from part 3(d)
store the cards in Player1
output the number and colour of the 4 cards in Player1 .
Save your program.
Copy and paste the program code into part 3(e)(i) in the evidence document.
(ii) Test your program with the following test data: 1 mark
Test 1: 1 5 9 10
Test 2: 2 2 3 4 4 5
Take a screenshot to show the output.
Copy and paste the screenshot into part 3(e)(ii) in the evidence document.
Show mark scheme
3(a)
import java.util.Scanner; import java.io.*; class Card{ private Integer Number; private String Colour; public Card(Integer pNumber, String pColour){ Number = pNumber; Colour = pColour; public static void main(String args[]){
3(b) [3 marks]
1 mark per mark point 1 get method header (and close where appropriate) with no parameter … … returning attribute 2nd correct get method Example program code: VB.NET Function GetNumber() Return Number End Function Function GetColour() Return Colour End Function Python def GetNumber(self): return self.__Number def GetColour(self): return self.__Colour public Integer GetNumber(){ return Number; } public String GetColour(){ return Colour; }
3(c)
catch(FileNotFoundException ex){ System.out.println("No file found"); } catch(IOException ex){ System.out.println("No file found"); }
3(d)
public static Boolean[] NumbersChosen = new Boolean[30]; public Integer chooseCard (){ Boolean flagContinue = true; Integer CardSelected = -1; while(flagContinue){ System.out.println("Select a Card from 1 to 30"); Scanner scanner = new Scanner(System.in); CardSelected = Integer.parseInt(scanner.nextLine()); if(CardSelected < 1 || CardSelected > 30){ System.out.println("Number must be between 1 and 30"); }else if(NumbersChosen[CardSelected - 1]){ System.out.println("Already taken"); }else{ System.out.println("Valid"); flagContinue = false; } } NumbersChosen[CardSelected - 1] = true; return CardSelected - 1;
3(e)(i)
Card[] Player1 = new Card[5]; for(Integer x = 0; x < 5; x++){ Player1[x] = CardArray[ChooseCard()]; for(Integer x = 0; x < 5; x++){ System.out.println(Player1[x].GetColour()); System.out.println(Player1[x].GetNumber());
3(e)(ii)
Test 2 e.g.
A program uses a circular queue to store strings. The queue is created as a 1D array, QueueArray,
with 10 string items.
The following data is stored about the queue:
the head pointer initialised to 0
the tail pointer initialised to 0
the number of items in the queue initialised to 0.
(a) Declare the array, head pointer, tail pointer and number of items. 2 marks
If you are writing in Python, include attribute declarations using comments.
Save your program as Question3_J2022 .
Copy and paste the program code into part 3(a) in the evidence document.
(b) The function Enqueue is written in pseudocode. The function adds DataToAdd to the queue. 7 marks
It returns FALSE if the queue is full and returns TRUE if the item is added.
The function is incomplete, there are five incomplete statements.
FUNCTION Enqueue(BYREF QueueArray[] : STRING, BYREF HeadPointer : INTEGER,
BYREF TailPointer : INTEGER, NumberItems : INTEGER,
DataToAdd : STRING) RETURNS BOOLEAN
IF NumberItems = …………………………………… THEN
RETURN ……………………………………
ENDIF
QueueArray[ …………………………………… ] DataToAdd
←
IF TailPointer >= 9 THEN
TailPointer ……………………………………
←
ELSE
TailPointer TailPointer + 1
# ←
ENDIF
NumberItems NumberItems ……………………………………
←
RETURN TRUE
ENDFUNCTION
Write program code for the function Enqueue() .
Save your program.
Copy and paste the program code into part 3(b) in the evidence document.
(c) The function Dequeue() returns "FALSE" if the queue is empty, or it returns the next data item in the queue. 6 marks
Write program code for the function Dequeue() .
Save your program.
Copy and paste the program code into part 3(c) in the evidence document. (d) (i) Amend the main program to: 5 marks
take as input 11 string values from the user
use the
Enqueue()function to add each element to the queueoutput an appropriate message to state whether each addition was successful, or not
call
Dequeue()function twice and output the return value each time.
Save your program.
Copy and paste the program code into part 3(d)(i) in the evidence document.
(ii) Test your program with the input data: 1 mark
"A" "B" "C" "D" "E" "F" "G" "H" "I" "J" "K"
Take a screenshot to show the output.
Copy and paste the screenshot into part 3(d)(ii) in the evidence document.
Show mark scheme
3(a) [2 marks]
1 mark per mark point Declaring variables: head pointer, tail pointer and number of items all initialised as 0 (integer) QueueArray declared as 1D array as string with 10 elements Example program code: public static void main(String[] args){ String[] QueueArray = new String[10]; Integer QueueHeadPointer = 0; Integer QueueTailPointer = 0; Integer NumberOfItems = 0; Python QueueArray = ['','','','','','','','','',''] #string QueueHeadPointer = 0 #integer QueueTailPointer = 0 #integer NumberOfItems = 0 #integer VB.NET Sub Main() Dim QueueArray(0 To 9) As String Dim QueueHeadPointer As Integer = 0 Dim QueueTailPointer As Integer = 0 Dim NumberOfItems As Integer = 0 End Sub
3(b)
Python def Enqueue(Queue, Head, Tail, NumItems, InputData): if NumItems >= 10: return (False, Queue, Head, Tail, NumItems) Queue[Tail] = InputData if Tail >= 9: Tail = 0 else: Tail = Tail + 1 NumItems = NumItems + 1 return (True, Queue, Head, Tail, NumItems) VB.NET Function Enqueue(ByRef Queue() As String, ByRef Head As Integer, ByRef Tail As Integer, ByRef NumItems As Integer, ByRef InputData As String) If NumItems = 10 Then Return False End If Queue(Tail) = InputData If Tail >= 9 Then Tail = 0 Else Tail = Tail + 1
3(c)
VB.NET Function Dequeue(ByRef QueueArray() As String, ByRef QueueHeadPointer As Integer, ByRef QueueTailpointer As Integer, ByRef NumberOfItems As Integer) If NumberOfItems = 0 Then Return "False" Else Dim ReturnValue = QueueArray(QueueHeadPointer) QueueHeadPointer = QueueHeadPointer + 1 If QueueHeadPointer >= 9 Then QueueHeadPointer = 0 End If NumberOfItems = NumberOfItems - 1 Return ReturnValue End If End Function
3(d)(i)
Python for x in range(0, 11): InputString = input("Enter a string") ReturnValue, QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems = Enqueue(QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems, InputString) if ReturnValue == True: print("Successful") else: print("Unsuccessful") ReturnValue, QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems = Dequeue(QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems) print(ReturnValue) ReturnValue, QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems = Dequeue(QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems) print(ReturnValue) VB.NET For x = 0 To 10 Console.WriteLine("Enter a string") InputString = Console.ReadLine If(Enqueue(QueueArray, QueueHeadPointer, QueueTailPointer, NumberOfItems, InputString)) Console.WriteLine("Successful") Else Console.WriteLine("Unsuccessful") End If Console.WriteLine(Dequeue) Console.WriteLine(Dequeue)
3(d)(ii) [1 mark]
1 mark for showing inputs and outputs: A – J input and successful. K input and unsuccessful. Output: A, B
(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 |
|---|---|
| 1 | Cat |
| 2 | Fish |
| 3 | Elk |
| 4 | |
| 5 | |
| 6 | |
| 7 |
(i) Describe how “Octopus” is added to the given queue. 2 marks
(ii) Describe how the next item in the given queue is removed and stored in the variable AnimalName . 2 marks
(iii) Describe the state of the queue when the front of queue and the end of queue pointers have the same value. 1 mark
(b) Some operations are carried out on the original queue given in part (a) .
(i) The current state of the queue is: 3 marks
| 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.
(ii) The state of the queue after other operations are carried out is shown: 2 marks
| 0 | Frog |
|---|---|
| 1 | Cat |
| 2 | Fish |
| 3 | Elk |
| 4 | Wasp |
| 5 | Bee |
| 6 | Mouse |
| 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 |
(c) The queue is implemented using a 1D array. 3 marks
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.
Show mark scheme
3(a)(i) [2 marks]
One mark per point: pointer will move to point to location 4 // incremented (by 1) • EoQ EoQ Data value "Octopus" will be stored in location pointed to be / • EoQ location 4
3(a)(ii) [2 marks]
One mark for each bullet Value "Frog" // value pointed to by / location 0 is assigned to variable • FoQ AnimalName pointer will move to point to location 1 / point to "Cat" // incremented • FoQ (by 1) FoQ 0 Frog Front of queue pointer ← 1 Cat 2 Fish End of queue pointer ← 3 Elk
3(a)(iii) [3 marks]
There is only one data item in the queue
3(b)(i)
One mark for data values plus one mark for pointers 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) [3 marks]
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) [4 marks]
One mark per point: 1 If incremented
then error condition: queue is full EoQ FoQ 2 Increment the EoQ 3 Manage wrap-around
(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 |
|---|---|
| 1 | Cat |
| 2 | Fish |
| 3 | Elk |
| 4 | |
| 5 | |
| 6 | |
| 7 |
(i) Describe how “Octopus” is added to the given queue. 2 marks
(ii) Describe how the next item in the given queue is removed and stored in the variable AnimalName . 2 marks
(iii) Describe the state of the queue when the front of queue and the end of queue pointers have the same value. 1 mark
(b) Some operations are carried out on the original queue given in part (a) .
(i) The current state of the queue is: 3 marks
| 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.
(ii) The state of the queue after other operations are carried out is shown: 2 marks
| 0 | Frog |
|---|---|
| 1 | Cat |
| 2 | Fish |
| 3 | Elk |
| 4 | Wasp |
| 5 | Bee |
| 6 | Mouse |
| 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 |
(c) The queue is implemented using a 1D array. 3 marks
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.
Show mark scheme
3(a)(i) [2 marks]
One mark per point: pointer will move to point to location 4 // incremented (by 1) • EoQ EoQ Data value "Octopus" will be stored in location pointed to be / • EoQ location 4
3(a)(ii) [2 marks]
One mark for each bullet Value "Frog" // value pointed to by / location 0 is assigned to variable • FoQ AnimalName pointer will move to point to location 1 / point to "Cat" // incremented • FoQ (by 1) FoQ 0 Frog Front of queue pointer ← 1 Cat 2 Fish End of queue pointer ← 3 Elk
3(a)(iii) [3 marks]
There is only one data item in the queue
3(b)(i)
One mark for data values plus one mark for pointers 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) [3 marks]
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) [4 marks]
One mark per point: 1 If incremented
then error condition: queue is full EoQ FoQ 2 Increment the EoQ 3 Manage wrap-around
The following diagram represents an Abstract Data Type (ADT) for a linked list.
A
The free list is as follows:
C D E Ø
(a) Explain how a node containing data value B is added to the list in alphabetic sequence. 4 marks
(b) Describe how the linked list in part (a) may be implemented using variables and arrays. 2 marks
Show mark scheme
6(a) [2 marks]
One mark per point: 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) [7 marks]
One mark per point: 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
The following diagram represents an Abstract Data Type (ADT).
A
B
Dolphin
(a) Identify this type of ADT. 1 mark
Cat Fish Elk
(b) Give the technical term for the item labelled A in the diagram. 1 mark
(c) Give the technical term for the item labelled B in the diagram. 2 marks
Explain the meaning of the value given to this item.
Term
Meaning
(d) Complete the diagram to show the ADT after the data has been sorted in alphabetical order. 2 marks
Dolphin Cat Fish Elk
Show mark scheme
3(a) [1 mark]
Linked list
3(b) [2 marks]
Start pointer
3(c)
One mark for each: Name: Null pointer Meaning: There are no further nodes in the list
3(d) [6 marks]
One mark for: Start Pointer pointing to ‘Cat’ node • Remaining arrows: Cat Dolphin Elk Fish • → → →
The following diagram represents an Abstract Data Type (ADT) for a linked list.
A
The free list is as follows:
C D E Ø
(a) Explain how a node containing data value B is added to the list in alphabetic sequence. 4 marks
(b) Describe how the linked list in part (a) may be implemented using variables and arrays. 2 marks
Show mark scheme
6(a) [2 marks]
One mark per point: 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) [7 marks]
One mark per point: 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
An unordered linked list uses a 1D array to store the data.
Each item in the linked list is of a record type, node, with a field data and a field nextNode .
The current contents of the linked list are:
| data | nextNode |
|---|---|
1 |
1 |
5 |
4 |
6 |
7 |
7 |
-1 |
2 |
2 |
0 |
6 |
0 |
8 |
56 |
3 |
0 |
9 |
0 |
-1 |
(a) The following is pseudocode for the record type node . 2 marks
TYPE node
DECLARE data : INTEGER
DECLARE nextNode : INTEGER
ENDTYPE
Write program code to declare the record type node .
Save your program as question1 .
Copy and paste the program code into part 1(a) in the evidence document.
Show mark scheme
1(a) [2 marks]
1 mark per bullet point Declaring record/class with name node… …declaring data and next node (both as Integers) Example code: Visual Basic Structure node Dim Data As Integer Dim nextNode As Integer End Structure Python class node: def init(self, theData, nextNodeNumber): self. Data = theData self.nextNode = nextNodeNumber class node{ private Integer Data; private Integer nextNode; public node(Integer dataP, Integer nextNodeP){ this.Data = dataP; this.nextNode = nextNodeP;
1(b)
Python linkedList = [node(1,1),node(5,4),node(6,7),node(7,-1),node(2,2),node(0,6), node(0,8),node(56,3),node(0,9),node(0,-1)] startPointer = 0 emptyList = 5 public static void main(String[] args){ node[] linkedList = new node[10]; linkedList[0] = new node(1,1); linkedList[1] = new node(5, 4); linkedList[2] = new node(6, 7); linkedList[3] = new node(7,-1); linkedList[4] = new node(2,2); linkedList[5] = new node(0,6); linkedList[6] = new node(0,8); linkedList[7] = new node(56, 3); linkedList[8] = new node(0,9); linkedList[9] = new node(0,-1); Integer startPointer = 0; Integer emptyList = 5;
1(c)(i) [6 marks]
1 mark per bullet point Procedure outputNodes … …taking linked list and start pointer as parameters Looping until nextNode/pointer is –1 Outputting the node data in the correct order, i.e. following pointers Updating pointer to current node ’ s nextNode Using the correct record/class field/properties throughout Example code: Visual Basic Sub outputNodes(ByRef linkedList, ByVal currentPointer) While (currentPointer <> -1) Console.WriteLine(linkedList(currentPointer).data) currentPointer = linkedList(currentPointer).nextNode End While End Sub Python def outputNodes(linkedList, currentPointer): while(currentPointer != -1): print(str(linkedList[currentPointer].data)) currentPointer = linkedList[currentPointer].nextNode public static void outputNodes(node[] linkedList, Integer currentPointer){ while(currentPointer != -1){ System.out.println(linkedList[currentPointer].data); currentPointer = linkedList[currentPointer].nextNode;
1(c)(ii) [1 mark]
Screenshot showing:
1(d)(i)
public static Boolean addNode(node[] linkedList, Integer currentPointer, Integer emptyList){ Integer dataToAdd; Integer previousPointer; node newNode; Scanner in = new Scanner(System.in); System.out.println("Enter the data to add"); dataToAdd = in.nextInt(); if(emptyList < 0 || emptyList > 9){ return false; }else{ newNode = new node(dataToAdd, -1); linkedList[emptyList] = newNode; previousPointer = 0; while(currentPointer != -1){ previousPointer = currentPointer; currentPointer = linkedList[currentPointer].nextNode; } linkedList[previousPointer].nextNode = emptyList; emptyList = linkedList[emptyList].nextNode; return true; }
1(d)(ii)
linkedList[9] = new node(-1,-1); Integer startPointer = 0; Integer emptyList = 5; outputNodes(linkedList, startPointer); Boolean returnValue; returnValue = addNode(linkedList, startPointer, emptyList); if (returnValue == true){ System.out.println("Item successfully added"); }else{ System.out.println("Item not added, list full"); } outputNodes(linkedList, startPointer);
1(d)(iii) [1 mark]
1 mark for screenshot showing : Linked list output 5 input Message saying Successfully added or equivalent Linked list output with 5 at the end. Example:
An unordered linked list uses a 1D array to store the data.
Each item in the linked list is of a record type, node, with a field data and a field nextNode .
The current contents of the linked list are:
| data | nextNode |
|---|---|
1 |
1 |
5 |
4 |
6 |
7 |
7 |
-1 |
2 |
2 |
0 |
6 |
0 |
8 |
56 |
3 |
0 |
9 |
0 |
-1 |
(a) The following is pseudocode for the record type node . 2 marks
TYPE node
DECLARE data : INTEGER
DECLARE nextNode : INTEGER
ENDTYPE
Write program code to declare the record type node .
Save your program as question1 .
Copy and paste the program code into part 1(a) in the evidence document.
Show mark scheme
1(a) [2 marks]
1 mark per bullet point Declaring record/class with name node… …declaring data and next node (both as Integers) Example code: Visual Basic Structure node Dim Data As Integer Dim nextNode As Integer End Structure Python class node: def init(self, theData, nextNodeNumber): self. Data = theData self.nextNode = nextNodeNumber class node{ private Integer Data; private Integer nextNode; public node(Integer dataP, Integer nextNodeP){ this.Data = dataP; this.nextNode = nextNodeP;
1(b)
Python linkedList = [node(1,1),node(5,4),node(6,7),node(7,-1),node(2,2),node(0,6), node(0,8),node(56,3),node(0,9),node(0,-1)] startPointer = 0 emptyList = 5 public static void main(String[] args){ node[] linkedList = new node[10]; linkedList[0] = new node(1,1); linkedList[1] = new node(5, 4); linkedList[2] = new node(6, 7); linkedList[3] = new node(7,-1); linkedList[4] = new node(2,2); linkedList[5] = new node(0,6); linkedList[6] = new node(0,8); linkedList[7] = new node(56, 3); linkedList[8] = new node(0,9); linkedList[9] = new node(0,-1); Integer startPointer = 0; Integer emptyList = 5;
1(c)(i) [6 marks]
1 mark per bullet point Procedure outputNodes … …taking linked list and start pointer as parameters Looping until nextNode/pointer is –1 Outputting the node data in the correct order, i.e. following pointers Updating pointer to current node ’ s nextNode Using the correct record/class field/properties throughout Example code: Visual Basic Sub outputNodes(ByRef linkedList, ByVal currentPointer) While (currentPointer <> -1) Console.WriteLine(linkedList(currentPointer).data) currentPointer = linkedList(currentPointer).nextNode End While End Sub Python def outputNodes(linkedList, currentPointer): while(currentPointer != -1): print(str(linkedList[currentPointer].data)) currentPointer = linkedList[currentPointer].nextNode public static void outputNodes(node[] linkedList, Integer currentPointer){ while(currentPointer != -1){ System.out.println(linkedList[currentPointer].data); currentPointer = linkedList[currentPointer].nextNode;
1(c)(ii) [1 mark]
Screenshot showing:
1(d)(i)
public static Boolean addNode(node[] linkedList, Integer currentPointer, Integer emptyList){ Integer dataToAdd; Integer previousPointer; node newNode; Scanner in = new Scanner(System.in); System.out.println("Enter the data to add"); dataToAdd = in.nextInt(); if(emptyList < 0 || emptyList > 9){ return false; }else{ newNode = new node(dataToAdd, -1); linkedList[emptyList] = newNode; previousPointer = 0; while(currentPointer != -1){ previousPointer = currentPointer; currentPointer = linkedList[currentPointer].nextNode; } linkedList[previousPointer].nextNode = emptyList; emptyList = linkedList[emptyList].nextNode; return true; }
1(d)(ii)
linkedList[9] = new node(-1,-1); Integer startPointer = 0; Integer emptyList = 5; outputNodes(linkedList, startPointer); Boolean returnValue; returnValue = addNode(linkedList, startPointer, emptyList); if (returnValue == true){ System.out.println("Item successfully added"); }else{ System.out.println("Item not added, list full"); } outputNodes(linkedList, startPointer);
1(d)(iii) [1 mark]
1 mark for screenshot showing : Linked list output 5 input Message saying Successfully added or equivalent Linked list output with 5 at the end. Example:
An unordered linked list uses a 1D array to store the data.
Each item in the linked list is of a record type, node, with a field data and a field nextNode .
The current contents of the linked list are:
| data | nextNode |
|---|---|
1 |
1 |
5 |
4 |
6 |
7 |
7 |
-1 |
2 |
2 |
0 |
6 |
0 |
8 |
56 |
3 |
0 |
9 |
0 |
-1 |
(a) The following is pseudocode for the record type node . 2 marks
TYPE node
DECLARE data : INTEGER
DECLARE nextNode : INTEGER
ENDTYPE
Write program code to declare the record type node .
Save your program as question1 .
Copy and paste the program code into part 1(a) in the evidence document.
Show mark scheme
1(a) [2 marks]
1 mark per bullet point Declaring record/class with name node… …declaring data and next node (both as Integers) Example code: Visual Basic Structure node Dim Data As Integer Dim nextNode As Integer End Structure Python class node: def init(self, theData, nextNodeNumber): self. Data = theData self.nextNode = nextNodeNumber class node{ private Integer Data; private Integer nextNode; public node(Integer dataP, Integer nextNodeP){ this.Data = dataP; this.nextNode = nextNodeP;
1(b)
Python linkedList = [node(1,1),node(5,4),node(6,7),node(7,-1),node(2,2),node(0,6), node(0,8),node(56,3),node(0,9),node(0,-1)] startPointer = 0 emptyList = 5 public static void main(String[] args){ node[] linkedList = new node[10]; linkedList[0] = new node(1,1); linkedList[1] = new node(5, 4); linkedList[2] = new node(6, 7); linkedList[3] = new node(7,-1); linkedList[4] = new node(2,2); linkedList[5] = new node(0,6); linkedList[6] = new node(0,8); linkedList[7] = new node(56, 3); linkedList[8] = new node(0,9); linkedList[9] = new node(0,-1); Integer startPointer = 0; Integer emptyList = 5;
1(c)(i) [6 marks]
1 mark per bullet point Procedure outputNodes … …taking linked list and start pointer as parameters Looping until nextNode/pointer is –1 Outputting the node data in the correct order, i.e. following pointers Updating pointer to current node ’ s nextNode Using the correct record/class field/properties throughout Example code: Visual Basic Sub outputNodes(ByRef linkedList, ByVal currentPointer) While (currentPointer <> -1) Console.WriteLine(linkedList(currentPointer).data) currentPointer = linkedList(currentPointer).nextNode End While End Sub Python def outputNodes(linkedList, currentPointer): while(currentPointer != -1): print(str(linkedList[currentPointer].data)) currentPointer = linkedList[currentPointer].nextNode public static void outputNodes(node[] linkedList, Integer currentPointer){ while(currentPointer != -1){ System.out.println(linkedList[currentPointer].data); currentPointer = linkedList[currentPointer].nextNode;
1(c)(ii) [1 mark]
Screenshot showing:
1(d)(i)
public static Boolean addNode(node[] linkedList, Integer currentPointer, Integer emptyList){ Integer dataToAdd; Integer previousPointer; node newNode; Scanner in = new Scanner(System.in); System.out.println("Enter the data to add"); dataToAdd = in.nextInt(); if(emptyList < 0 || emptyList > 9){ return false; }else{ newNode = new node(dataToAdd, -1); linkedList[emptyList] = newNode; previousPointer = 0; while(currentPointer != -1){ previousPointer = currentPointer; currentPointer = linkedList[currentPointer].nextNode; } linkedList[previousPointer].nextNode = emptyList; emptyList = linkedList[emptyList].nextNode; return true; }
1(d)(ii)
linkedList[9] = new node(-1,-1); Integer startPointer = 0; Integer emptyList = 5; outputNodes(linkedList, startPointer); Boolean returnValue; returnValue = addNode(linkedList, startPointer, emptyList); if (returnValue == true){ System.out.println("Item successfully added"); }else{ System.out.println("Item not added, list full"); } outputNodes(linkedList, startPointer);
1(d)(iii) [1 mark]
1 mark for screenshot showing : Linked list output 5 input Message saying Successfully added or equivalent Linked list output with 5 at the end. Example: