19.2 Recursion
A Level · 23 questions found
What this topic covers
Section titled “What this topic covers”- Essential features of recursion: base case, recursive call
- How recursion is expressed in a programming language
- Write and trace recursive algorithms; when recursion is beneficial
- What a compiler does to handle recursion: stacks and unwinding
Past paper questions
Section titled “Past paper questions”Describe when the use of recursion would be beneficial and give an example.
Description
Example 3 marks
Show mark scheme
11 [3 marks]
One mark per mark point ( Max 3 ) MP1 Recursion is beneficial for problems that can be broken down into smaller, repetitive problems MP2 … especially for problems that have many possible branches / are too complex for an iterative approach MP3 An example e.g. solving mathematical series, sorting a pile of documents, etc.
A program is written to perform different individual processes using arrays.
(a) A 1D array stores 10 integers.
(i) A recursive function RecursiveCount() takes three parameters: 6 marks
ArrayCopy, an array of integersNumberElements, the number of elements in the array of integersDataToFind, an integer data to find in the array.
The function counts and returns the number of times DataToFind is in ArrayCopy
The recursive algorithm:
returns
0if there are no elements inArrayCopycompares the first element in
ArrayCopywithDataToFindif the element matches, the function returns
1added to the return value from a recursive call (passing the array without the first element)if the element does not match, the function returns the return value from a recursive call (passing the array without the first element).
Write program code for RecursiveCount()
Save your program as Question3_N25 .
Copy and paste the program code into part 3(a)(i) in the evidence document.
(ii) The main program stores the following data in a 1D array of integers in the order given: 3 marks
0 5 1 2 5 9 9 6 5 0
The main program calls RecursiveCount() with the parameters:
0as the data to find10as the number of elementsthe array of 10 integers.
The return value is output.
Write program code for the main program.
Save your program.
Copy and paste the program code into part 3(a)(ii) in the evidence document.
(iii) Test your program. 1 mark
Take a screenshot of the output(s).
Save your program.
Copy and paste the screenshot(s) into part 3(a)(iii) in the evidence document.
(b) The program stores the following string. The string has four statements that are each terminated by a semi-colon ';'
"x=0;y=1;x=x+y;y++;"
(i) Write program code to amend the main program to store the string "x=0;y=1;x=x+y;y++;" in a local variable. 1 mark
Save your program.
Copy and paste the program code into part 3(b)(i) in the evidence document.
(ii) The function SplitData() splits a string parameter into four individual lines of code. 6 marks
The function creates an array of the strings where each line is stored in a new array element without the semi-colon.
The function returns the array of strings.
Do not use an inbuilt function to split the string.
Write program code for SplitData()
Save your program.
Copy and paste the program code into part 3(b)(ii) in the evidence document.
(iii) The main program needs to call SplitData() with the string from part 3(b)(i) . The main program then needs to output each element from the returned array on a new line. 2 marks
Write program code to amend the main program.
Save your program.
Copy and paste the program code into part 3(b)(iii) in the evidence document.
(iv) Test your program. 1 mark
Take a screenshot of the output(s).
Save your program.
Copy and paste the screenshot(s) into part 3(b)(iv) in the evidence document.
Show mark scheme
3(a)(i)
VB.NET Function RecursiveCount(DataToFind As Integer, ArrayCopy() As Integer, NumberElements As Integer) If NumberElements > 0 Then Dim NewArray(NumberElements - 1) As Integer For x = 1 To NumberElements - 1 NewArray(x - 1) = ArrayCopy(x) Next x If ArrayCopy(0) = DataToFind Then Return 1 + RecursiveCount(DataToFind, NewArray, NumberElements - 1) Else Return RecursiveCount(DataToFind, NewArray, NumberElements - 1) End If Else Return 0 End If End Function Python def RecursiveCount(DataToFind, ArrayCopy, NumberElements): if NumberElements > 0: NewArray = ArrayCopy[1:] if ArrayCopy[0] == DataToFind: return 1 + RecursiveCount(DataToFind, NewArray, NumberElements - 1) else: return RecursiveCount(DataToFind, NewArray, NumberElements - 1) else: return 0
3(a)(ii) [3 marks]
1 mark each • Storing the correct data in an array • Calling with the correct parameters RecursiveCount() • Outputting the return value Example program code Java Integer[] MyArray = new Integer[]{0, 5, 1, 2, 5, 9, 9, 6, 5, 0}; System.out.println(RecursiveCount(0, MyArray, 10)); VB.NET Dim MyArray() As Integer = {0, 5, 1, 2, 5, 9, 9, 6, 5, 0} Console.WriteLine(RecursiveCount(0, MyArray, 10)) Python MyArray = [0,5,1,2,5,9,9,6,5,0] print(RecursiveCount(0, MyArray, 10))
3(a)(iii) [1 mark]
1 mark for screenshot showing correct output of 2 Example
3(b)(i) [1 mark]
1 mark for storing the string in a variable Example program code Java String Code = "x=0;y=1;x=x+y;y++;"; VB.NET Dim Code As String = "x=0;y=1;x=x+y;y++;" Python Code = "x=0;y=1;x=x+y;y++;"
3(b)(ii)
Python def SplitData(DataString): SplitDataArray = [] Count = 0 for x in range(4): TempString = "" try: Character = DataString[Count] while Character != ";": TempString = TempString + (Character) Count += 1 Character = DataString[Count] SplitDataArray.append(TempString) except: print("No more characters") Count += 1 return SplitDataArray
3(b)(iii) [2 marks]
1 mark each • Calling with array as argument and storing/using return value SplitData() • Outputting each element of the returned array on a new line Example program code Java String Code = "x=0;y=1;x=x+y;y++;"; String[] SplitDataArray = new String[10]; SplitDataArray = SplitData(Code); for(Integer x = 0; x < 4; x++){ System.out.println(SplitDataArray[x]); } VB.NET Dim Code As String = "x=0;y=1;x=x+y;y++;" Dim SplitDataArray() As String = SplitData(Code) For x = 0 To 3 Console.WriteLine(SplitDataArray(x)) Next Python Code = "x=0;y=1;x=x+y;y++;" SplitDataArray = SplitData(Code) for x in range(4): print(SplitDataArray[x])
3(b)(iv) [1 mark]
1 mark for output x=0 y=1 x=x+y y++ Example
(b) A binary tree can be used to implement recursion. 2 marks
Identify one feature of an algorithm that makes it beneficial to use recursion. Give one example of an application that could use a recursive algorithm.
Feature
Example
Show mark scheme
11(a) [4 marks]
One mark per mark point MP1 Any two nodes added correctly with correct data (Aa, Mm, Ss, Xx) MP2 Remaining two nodes added with correct data (Aa, Mm, Ss, Xx) and all nodes with connecting arrows starting from correct pointer boxes MP3 Correct null pointers (0) added throughout MP4 … with no entries in other pointer boxes and all nodes correctly positioned and connected. Root pointer Pp Gg 0 Rr 0 Ss 0 Kk 0 Aa 0 0 Mm 0 0 Xx 0
11(b) [2 marks]
One mark for feature and one mark for example ( Max 2 ) • Recursion is beneficial for algorithms when a problem naturally breaks down into smaller versions of itself. • … such as calculating a factorial / mathematical series / Fibonacci / compound interest / tree traversal / evaluation of RPN expressions.
The recursive procedure Delete() is defined as follows:
PROCEDURE Delete(Index, Target) IF Numbers[Index] > 0 THEN IF Numbers[Index] >= Target THEN Numbers[Index] ← Numbers[Index + 1] ENDIF Index ← Index + 1 CALL Delete(Index, Target) ENDIF ENDPROCEDURE
An array Numbers is used to store a sorted data set of non-zero positive integers. Unused cells contain zero.
The contents of the array at the start of the algorithm are:
| Numbers | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | [10] |
| 2 | 3 | 7 | 11 | 15 | 17 | 19 | 23 | 0 | 0 |
Complete the trace table for the algorithm for the procedure call:
CALL Delete(1, 15)
| Numbers | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|
| Index | Target | [1] | [2] | [3] | [4] | [5] | [6] | [7] | [8] | [9] | [10] |
| 2 | 3 | 7 | 11 | 15 | 17 | 19 | 23 | 0 | 0 | ||
| 4 marks |
Show mark scheme
13 [23 marks]
One mark for each marking point MP1 Correct and columns Index Target MP2 Correct column Numbers[5] MP3 Correct and columns Numbers[6] Numbers[7] MP4 Correct column and no incorrect data added to any other of columns Numbers[8] Numbers Index Target [1] [2] [3] [4] [5] [6] 1 15 2 3 7 11 15 17 2 3 4 5 17 6 19 7 8 9
A program sorts an array of integers and searches the array for a particular value.
(a) The array of integers, NumberArray, stores the following data in the order given: 1 mark
100 85 644 22 15 8 1
The array is declared and initialised local to the main program.
Write program code to declare and initialise the array.
Save your program as Question3_J24 .
Copy and paste the program code into part 3(a) in the evidence document. (b) (i) The following recursive pseudocode function sorts the array into ascending order using 4 marks an insertion sort and returns the sorted array.
DECLARE LastItem : INTEGER
DECLARE CheckItem : INTEGER
DECLARE LoopAgain : BOOLEAN
FUNCTION RecursiveInsertion(IntegerArray : ARRAY[] OF INTEGER,
NumberElements : INTEGER) RETURNS ARRAY[] OF INTEGER
IF NumberElements <= 1 THEN
RETURN IntegerArray
ELSE
CALL RecursiveInsertion(IntegerArray, NumberElements - 1)
LastItem IntegerArray[NumberElements - 1]
CheckItem NumberElements - 2
ENDIF
LoopAgain TRUE
IF CheckItem < 0 THEN
LoopAgain FALSE
ELSE
IF IntegerArray[CheckItem] < LastItem THEN
LoopAgain FALSE
ENDIF
ENDIF
WHILE LoopAgain
IntegerArray[CheckItem + 1] IntegerArray[CheckItem]
CheckItem CheckItem - 1
IF CheckItem < 0 THEN
LoopAgain FALSE
ELSE
IF IntegerArray[CheckItem] < LastItem THEN
LoopAgain FALSE
ENDIF
ENDIF
ENDWHILE
IntegerArray[CheckItem + 1] LastItem
RETURN IntegerArray
ENDFUNCTION
Write the program code for the pseudocode function RecursiveInsertion() .
Save your program.
Copy and paste the program code into part 3(b)(i) in the evidence document.
(ii) Amend the main program to: 2 marks
call
RecursiveInsertion()with the initialised arrayNumberArrayand the number of elements as parametersoutput the word ‘Recursive’
output the content of the returned array.
Save your program.
Copy and paste the program code into part 3(b)(ii) in the evidence document.
(iii) Test your program. 1 mark
Take a screenshot of the output(s).
Save your program.
Copy and paste the screenshot into part 3(b)(iii) in the evidence document.
(c) The function RecursiveInsertion() can be changed to use iteration instead of recursion.
(i) Write program code for the function IterativeInsertion() to perform the same processes as RecursiveInsertion() but using iteration instead of recursion. 4 marks
Save your program.
Copy and paste the program code into part 3(c)(i) in the evidence document.
(ii) Write program code to amend the main program to also: 1 mark
call
IterativeInsertion()with the original initialised arrayNumberArrayoutput the word ‘iterative’
output the content of the returned array.
Save your program.
Copy and paste the program code into part 3(c)(ii) in the evidence document.
(iii) Test your program. 1 mark
Take a screenshot of the output(s).
Save your program.
Copy and paste the screenshot into part 3(c)(iii) in the evidence document.
(d) The recursive function BinarySearch() takes the parameters:
IntegerArray- an array of integersFirst- the index of the first array elementLast- the index of the last array elementToFind- an integer to search for in the array.
The function uses recursion to perform a binary search for ToFind in IntegerArray .
The function returns the index where ToFind is stored or returns −1 if ToFind is not in the
array.
(i) Write program code for the recursive function BinarySearch() . 6 marks
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: 2 marks
call
BinarySearch()with the sorted array and the integer 644 as the search valueoutput ‘Not found’ if 644 is not found in the array
output the index if 644 is found in the array.
Save your program.
Copy and paste the program code into part 3(d)(ii) in the evidence document.
(iii) Test your program. 1 mark
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 NumberArray declared (in main) with the 7 correct values in order (integer) 100 85 644 22 15 8 1 public static void main(String args[]){ Integer[] NumberArray = new Integer[7]; NumberArray[0] = 100; NumberArray[1] = 85; NumberArray[2] = 644; NumberArray[3] = 22; NumberArray[4] = 15; NumberArray[5] = 8; NumberArray[6] = 1; VB.NET Sub Main(args As String()) Dim NumberArray(7) As Integer NumberArray(0) = 100 NumberArray(1) = 85 NumberArray(2) = 644 NumberArray(3) = 22 NumberArray(4) = 15 NumberArray(5) = 8 NumberArray(6) = 1 EndSub Python NumberArray = [100, 85, 644, 22, 15, 8, 1]
3(b)(i)
LoopAgain = False End If End While IntegerArray(CheckItem + 1) = LastItem Return IntegerArray End Function Python def RecursiveInsertion(IntegerArray, NumberElements): if NumberElements <= 1: return IntegerArray RecursiveInsertion(IntegerArray,NumberElements - 1) LastItem = IntegerArray[NumberElements - 1] CheckItem = NumberElements - 2 LoopAgain = True if CheckItem < 0: LoopAgain = False elif IntegerArray[CheckItem] <= LastItem: LoopAgain = False while (LoopAgain): IntegerArray[CheckItem + 1] = IntegerArray[CheckItem] CheckItem = CheckItem - 1 if CheckItem < 0: LoopAgain = False elif IntegerArray[CheckItem] <= LastItem: LoopAgain = False IntegerArray[CheckItem + 1] = LastItem return IntegerArray
3(b)(ii) [2 marks]
1 mark each Calling RecursiveInsertion() with array and number of elements (7 or length) Outputting ‘recursive’ and then each element in returned array Integer[] SortedArray = new Integer[7]; SortedArray = RecursiveInsertion(NumberArray, 7); System.out.println("Recursive"); for(Integer x = 0; x < 7; x++){ System.out.println(SortedArray[x]); VB.NET SortedArray = RecursiveInsertion(NumberArray, 7) Console.WriteLine("Recursive") For x = 0 To 6 Console.WriteLine(SortedArray(x)) Next x Python SortedArray = RecursiveInsertion(NumberArray, len(NumberArray)) print("Recursive", SortedArray)
3(b)(iii) [1 mark]
1 mark for screenshot with: Recursive
3(c)(i)
Python def IterativeInsertion(IntegerArray, NumberElements): while NumberElements > 0: LastItem = IntegerArray[NumberElements - 1] CheckItem = NumberElements - 2 LoopAgain = True if CheckItem < 0: LoopAgain = False elif IntegerArray[CheckItem] <= LastItem: LoopAgain = False while(LoopAgain): IntegerArray[CheckItem + 1] = IntegerArray[CheckItem] CheckItem = CheckItem - 1 if CheckItem < 0: LoopAgain = False elif IntegerArray[CheckItem] <= LastItem: LoopAgain = False IntegerArray[CheckItem + 1] = LastItem NumberElements = NumberElements - 1 return IntegerArray
3(c)(ii) [1 mark]
1 mark each Calling IterativeInsertion() with original unsorted array and outputting ‘iterative’ and the content of the returned array Integer[] Sorted2Array = new Integer[7]; Sorted2Array = IterativeInsertion(NumberArray, 7); System.out.println("iterative"); for(Integer x = 0; x < 7; x++){ System.out.println(Sorted2Array[x]); VB.NET Sorted2Array = IterativeInsertion(NumberArray, 7) Console.WriteLine("iterative") For x = 0 To 6 Console.WriteLine(Sorted2Array(x)) Next x Python Sorted2Array = IterativeInsertion(NumberArray, len(NumberArray)) print("iterative", Sorted2Array)
3(c)(iii) [1 mark]
1 mark for Recursive 1 8 15 22 85 100 644 Iterative 1 8 15 22 85 100 644
3(d)(i)
Return -1 Else Middle = (Last + First) \ 2 If IntegerArray(Middle) = ToFind Then Return Middle ElseIf IntegerArray(Middle) > ToFind Then Return BinarySearch(IntegerArray, First, Middle - 1, ToFind) Else Return BinarySearch(IntegerArray, Middle + 1, Last, ToFind) End If End If End Function Python def BinarySearch(IntegerArray, First, Last, ToFind): if First > Last: return -1 else: Middle = int((Last + First) / 2) if IntegerArray[Middle] == ToFind: return Middle elif IntegerArray[Middle] > ToFind: return BinarySearch(IntegerArray, First, Middle - 1, ToFind) else: return BinarySearch(IntegerArray, Middle + 1, Last, ToFind)
3(d)(ii) [2 marks]
1 mark each Calling BinarySearch function with sorted array, 0, 6/len(array)–1, 644 as parameters Checking return value and outputting ‘Not found’ if –1 and index otherwise Position = BinarySearch(Sorted2Array, 0, 6, 644); if(Position == -1){ System.out.println("Not found"); }else{ System.out.println(Position); VB.NET Position = BinarySearch(Sorted2Array, 0, 6, 644) If Position = -1 Then Console.WriteLine("Not found") Console.WriteLine(Position) End If Python Position = BinarySearch(Sorted2Array, 0, len(NumberArray)-1, 644) if Position == -1: print("Not found") else: print(Position)
3(d)(iii) [1 mark]
1 mark for screenshot showing found in index 6 e.g.
(b) Justify the use of a linked list instead of an array to implement a stack. 2 marks
(c) Explain how a compiler makes use of a stack when translating recursive programming code. 4 marks
Show mark scheme
9(a)(i) [2 marks]
Two marks for all five empty boxes correct One mark for any three or four empty boxes correct Identifier Data type Description BasePointer INTEGER Points to the bottom of the stack TopPointer INTEGER Points to the top of the stack Stack REAL List of decimal numbers stored in the stack
9(a)(ii) [5 marks]
One mark for each correctly completed line ( Max 5 ) CONSTANT MaxSize = 40 DECLARE BasePointer : INTEGER DECLARE TopPointer : INTEGER DECLARE Stack : ARRAY[1:40] OF REAL // initialisation of stack PROCEDURE Initialise() BasePointer 1 TopPointer 0 ENDPROCEDURE // adding an item to the stack PROCEDURE Push(NewItem) IF TopPointer < MaxSize THEN TopPointer TopPointer + 1 Stack[TopPointer] NewItem ENDIF ENDPROCEDURE
9(b) [2 marks]
One mark for linked list and one mark for array ( Max 2 ) Linked list MP1 A linked list is a dynamic data structure / not restricted in size MP2 Has greater freedom to expand or contract by adding or removing nodes as necessary MP3 Allows more efficient editing using pointers (instead of moving the data). Array MP4 An array is a static data structure1 generally fixed in size MP5 When the array is full, the stack cannot be extended any further.
9(c) [4 marks]
One mark per mark point ( Max 1 ) MP1 The compiler must produce object code to One mark per mark point ( Max 3 ) MP2 …push return addresses / values of local variables onto a stack MP3 …with each recursive call // … to set up winding MP4 …pop return addresses / values of local variables off the stack … MP5 …after the base case is reached // … to implement unwinding.
This iterative pseudocode algorithm for the function IterativeVowels() takes a string as a
parameter and counts the number of lower-case vowels in this string.
The vowels are the letters a, e, i, o and u.
FUNCTION IterativeVowels(Value : STRING) RETURNS INTEGER
DECLARE Total : INTEGER
DECLARE LengthString : INTEGER
DECLARE FirstCharacter : CHAR
Total 0
# ←
LengthString LENGTH(Value)
# ←
FOR X 0 TO LengthString - 1
# ←
FirstCharacter MID(Value, 0, 1)
# ←
IF FirstCharacter = 'a' OR FirstCharacter = 'e' OR
FirstCharacter = 'i' OR FirstCharacter = 'o' OR
FirstCharacter = 'u' THEN
Total Total + 1
# ←
ENDIF
Value MID(Value, 1, LENGTH(Value)-1)
# ←
NEXT X
RETURN Total
ENDFUNCTION
The pseudocode function MID(X, Y, Z) returns Z number of characters from string X, starting
at the character in position Y . The first character in a string is in position 0, for example:
MID("computer", 0, 3) returns "com"
The pseudocode function LENGTH(X) returns the number of characters in the string X, for
example:
LENGTH("computer") returns 8
Show mark scheme
1(a)(i) [5 marks]
One mark each to max 5 • Function header (and end where appropriate) taking one string parameter • Calculating length of parameter string • Looping correct number of times • Checking the first character against all vowels • Accessing the remainder of the string • Remainder of function correct with nothing extra i.e. totalling, must match structure of given algorithm
FirstCharacter = Value.charAt(0); if(FirstCharacter == 'a' || FirstCharacter == 'e' || FirstCharacter =='i' || FirstCharacter == 'o' Total++; } Value = Value.substring(1, Value.length()); FirstCharacter = Left(Value, 1) If FirstCharacter = "a" Or FirstCharacter = "e" Or FirstCharacter = "i" Or FirstCharacter = "o" Or Total = Total + 1 End If Value = Right(Value, Len(Value) - 1)
FirstCharacter = Value[0] if FirstCharacter == 'a' or FirstCharacter == 'e' or FirstCharacter == 'i' or FirstCharacter == 'o' Total = Total + 1 Value = Value[1:len(Value)]
1(a)(ii) [2 marks]
One mark each • Calling the function with "house" • Outputting the return value Example program code: Java System.out.println(IterativeVowels("house")); VB.NET Console.WriteLine(IterativeVowels("house")) Python print(IterativeVowels("house"))
1(a)(iii) [1 mark]
One mark for screenshot outputting 3
1(b)(i) [6 marks]
One mark each • Recursive call • Function header (and end where appropriate) taking string parameter (returning integer where given) • Base case checking (length is 0) and returning 0 • Extracting first character and checking if a vowel … • … if it is a vowel, returning 1 + recursive call with 1 less character • … if not a vowel, return recursive call with 1 less character
return 0; FirstCharacter = Value.charAt(0); if(FirstCharacter == 'a' || FirstCharacter == 'e' || FirstCharacter =='i' || FirstCharacter == 'o' return 1 + RecursiveVowels(Value.substring(1, Value.length())); }else{ return RecursiveVowels(Value.substring(1, Value.length())); } Return 0 firstCharacter = Left(Value, 1) If firstCharacter = "a" Or firstCharacter = "e" Or firstCharacter = "i" Or firstCharacter = "o" Or Return 1 + RecursiveVowels(Right(Value, Len(Value) - 1)) Else Return RecursiveVowels(Right(Value, Len(Value) - 1))
End If return 0 FirstCharacter = Value[0] return 1 + RecursiveVowels(Value[1:len(Value)]) return RecursiveVowels(Value[1:len(Value)])
1(b)(ii) [1 mark]
One mark for calling recursive function with and outputting return value "imagine" Example program code: Java System.out.println(RecursiveVowels("imagine")); VB.NET Console.WriteLine(RecursiveVowels("imagine")) Python print(RecursiveVowels("imagine"))
1(b)(iii) [1 mark]
One mark for screenshot showing 4
An integer is said to be divisible by another integer if the result of the division is also an integer.
For example:
10 is divisible by 1, 2, 5 and 10:
10 ÷ 1 = 10
10 ÷ 2 = 5
10 ÷ 5 = 2
10 ÷ 10 = 1
10 is not divisible by 4:
- 10 ÷ 4 = 2.5
1, 2, 5 and 10 are said to be the divisors of 10.
The iterative function IterativeCalculate() totals all the divisors of its integer parameter and
returns this total.
Example 1: if the parameter is 10, the total will be 18 (1 + 2 + 5 + 10) . Example 2: if the parameter is 4, the total will be 7 (1 + 2 + 4) .
A pseudocode algorithm for IterativeCalculate() is shown.
FUNCTION IterativeCalculate(Number : INTEGER) RETURNS INTEGER
DECLARE Total : Integer
DECLARE ToFind : Integer
ToFind Number
# ←
Total 0
# ←
WHILE Number <> 0
IF ToFind MODULUS Number = 0 THEN
Total Total + Number
# ←
ENDIF
Number Number - 1
# ←
ENDWHILE
RETURN Total
ENDFUNCTION
The operator MODULUS calculates the remainder when one number is divided by another.
(a) (i) Write program code for IterativeCalculate() . 5 marks
Save your program as Question2_N23 .
Copy and paste the program code into part 2(a)(i) in the evidence document.
(ii) Write program code to call IterativeCalculate() with 10 as the parameter and output the return value. 2 marks
Save your program.
Copy and paste the program code into part 2(a)(ii) in the evidence document.
(iii) Test your program. 1 mark
Take a screenshot of the output.
Save your program.
Copy and paste the screenshot into part 2(a)(iii) in the evidence document.
(b) IterativeCalculate() has been rewritten as the recursive function RecursiveValue() .
A pseudocode algorithm for RecursiveValue() is given. The function is incomplete.
FUNCTION RecursiveValue(Number : INTEGER, ToFind : INTEGER)
RETURNS INTEGER
IF Number = ______ THEN
RETURN 0
ELSE
IF ToFind ______ Number = 0 THEN
RETURN ______ + RecursiveValue(Number - 1, ToFind)
ELSE
______ RecursiveValue(Number - 1, ______)
ENDIF
ENDIF
ENDFUNCTION
(i) Write program code for RecursiveValue() . 7 marks
Save your program.
Copy and paste the program code into part 2(b)(i) in the evidence document.
(ii) Write program code to call RecursiveValue() with 50 as the first parameter and 50 as the second parameter and output the return value. 1 mark
Save your program.
Copy and paste the program code into part 2(b)(ii) in the evidence document.
(iii) Test your program. 1 mark
Take a screenshot of the output.
Save your program.
Copy and paste the screenshot into part 2(b)(iii) in the evidence document.
Show mark scheme
2(a)(i)
Python def IterativeCalculate(Number): Total = 0 ToFind = Number while Number != 0: if ToFind % Number == 0: Total = Total + Number Number = Number - 1 return Total
2(a)(ii) [2 marks]
One mark each • Calling IterativeCalculate(10) • Outputting return value Example program code: Java System.out.println(IterativeCalculate(10)); VB.NET Sub Main(args As String()) Console.WriteLine(IterativeCalculate(10)) End Sub Python print(IterativeCalculate(10))
2(a)(iii) [1 mark]
One mark for screenshot showing 18
2(b)(i)
VB.NET Function RecursiveValue(Number As Integer, ToFind As Integer) If Number = 0 Then Return 0 Else If ToFind Mod Number = 0 Then Return Number + RecursiveValue(Number - 1, ToFind) Else Return RecursiveValue(Number - 1, ToFind) End If End If End Function Python def RecursiveValue(Number, ToFind): if Number == 0: return 0 else: if ToFind % Number == 0: return Number + RecursiveValue(Number - 1, ToFind) else: return RecursiveValue(Number - 1, ToFind)
2(b)(ii) [1 mark]
One mark for calling and outputting return value RecursiveValue(50,50) Example program code: Java System.out.println(RecursiveValue(50,50)); VB.NET Console.WriteLine(RecursiveValue(50,50)) Python print(RecursiveValue(50,50))
2(b)(iii) [1 mark]
One mark for screenshot showing 93
This iterative pseudocode algorithm for the function IterativeVowels() takes a string as a
parameter and counts the number of lower-case vowels in this string.
The vowels are the letters a, e, i, o and u.
FUNCTION IterativeVowels(Value : STRING) RETURNS INTEGER
DECLARE Total : INTEGER
DECLARE LengthString : INTEGER
DECLARE FirstCharacter : CHAR
Total 0
# ←
LengthString LENGTH(Value)
# ←
FOR X 0 TO LengthString - 1
# ←
FirstCharacter MID(Value, 0, 1)
# ←
IF FirstCharacter = 'a' OR FirstCharacter = 'e' OR
FirstCharacter = 'i' OR FirstCharacter = 'o' OR
FirstCharacter = 'u' THEN
Total Total + 1
# ←
ENDIF
Value MID(Value, 1, LENGTH(Value)-1)
# ←
NEXT X
RETURN Total
ENDFUNCTION
The pseudocode function MID(X, Y, Z) returns Z number of characters from string X, starting
at the character in position Y . The first character in a string is in position 0, for example:
MID("computer", 0, 3) returns "com"
The pseudocode function LENGTH(X) returns the number of characters in the string X, for
example:
LENGTH("computer") returns 8
Show mark scheme
1(a)(i) [5 marks]
One mark each to max 5 • Function header (and end where appropriate) taking one string parameter • Calculating length of parameter string • Looping correct number of times • Checking the first character against all vowels • Accessing the remainder of the string • Remainder of function correct with nothing extra i.e. totalling, must match structure of given algorithm
FirstCharacter = Value.charAt(0); if(FirstCharacter == 'a' || FirstCharacter == 'e' || FirstCharacter =='i' || FirstCharacter == 'o' Total++; } Value = Value.substring(1, Value.length()); FirstCharacter = Left(Value, 1) If FirstCharacter = "a" Or FirstCharacter = "e" Or FirstCharacter = "i" Or FirstCharacter = "o" Or Total = Total + 1 End If Value = Right(Value, Len(Value) - 1)
FirstCharacter = Value[0] if FirstCharacter == 'a' or FirstCharacter == 'e' or FirstCharacter == 'i' or FirstCharacter == 'o' Total = Total + 1 Value = Value[1:len(Value)]
1(a)(ii) [2 marks]
One mark each • Calling the function with "house" • Outputting the return value Example program code: Java System.out.println(IterativeVowels("house")); VB.NET Console.WriteLine(IterativeVowels("house")) Python print(IterativeVowels("house"))
1(a)(iii) [1 mark]
One mark for screenshot outputting 3
1(b)(i) [6 marks]
One mark each • Recursive call • Function header (and end where appropriate) taking string parameter (returning integer where given) • Base case checking (length is 0) and returning 0 • Extracting first character and checking if a vowel … • … if it is a vowel, returning 1 + recursive call with 1 less character • … if not a vowel, return recursive call with 1 less character
return 0; FirstCharacter = Value.charAt(0); if(FirstCharacter == 'a' || FirstCharacter == 'e' || FirstCharacter =='i' || FirstCharacter == 'o' return 1 + RecursiveVowels(Value.substring(1, Value.length())); }else{ return RecursiveVowels(Value.substring(1, Value.length())); } Return 0 firstCharacter = Left(Value, 1) If firstCharacter = "a" Or firstCharacter = "e" Or firstCharacter = "i" Or firstCharacter = "o" Or Return 1 + RecursiveVowels(Right(Value, Len(Value) - 1)) Else Return RecursiveVowels(Right(Value, Len(Value) - 1))
End If return 0 FirstCharacter = Value[0] return 1 + RecursiveVowels(Value[1:len(Value)]) return RecursiveVowels(Value[1:len(Value)])
1(b)(ii) [1 mark]
One mark for calling recursive function with and outputting return value "imagine" Example program code: Java System.out.println(RecursiveVowels("imagine")); VB.NET Console.WriteLine(RecursiveVowels("imagine")) Python print(RecursiveVowels("imagine"))
1(b)(iii) [1 mark]
One mark for screenshot showing 4
(b) A Fibonacci sequence is a series of numbers formed by adding together the two preceding numbers, for example: 5 marks
0, 1, 1, 2, …
This function calculates and returns values in the Fibonacci sequence and uses recursion.
FUNCTION Fib(Number : INTEGER) RETURNS INTEGER
IF Number <= 1 THEN
Result ← Number
ELSE
Result ← Fib(Number – 1) + Fib(Number – 2)
ENDIF
RETURN Result
ENDFUNCTION
Complete the trace table for the function when it is called as Fib(5) .
| Call number | Function call | Number | Result | Return value |
|---|---|---|---|---|
5 |
||||
Show mark scheme
12(a) [2 marks]
One mark per mark point ( Max 2 ) A process using a function or procedure defined in terms of itself / calls itself. A recursive process must have a base case (which is a way to return without making a recursive call) // terminating solution // concept of unwinding described There must (also) be a general case where the recursive call takes place.
12(b) [5 marks]
One mark per mark point ( Max 5 ) column correct Call number and columns correct Function call Number column down to base case (Winding) rows 1–6 correct Result column down from base case (Unwinding) rows 7–10 correct Result Return value column correct Number Result Call Function call Return number value 1 Fib(5) 5 Fib(4) + Fib(3) 2 Fib(4) 4 Fib(3) + Fib(2) 3 Fib(3) 3 Fib(2) + Fib(1) 4 Fib(2) 2 Fib(1) + Fib(0) 5 Fib(1) 1 1 1 6 Fib(0) 0 0 0 (4) Fib(2) 2 1 + 0 1 (3) Fib(3) 3 1 + 1 2 (2) Fib(4) 4 2 + 1 3 (1) Fib(5) 5 3 + 2 5
(b) A Fibonacci sequence is a series of numbers formed by adding together the two preceding numbers, for example: 5 marks
0, 1, 1, 2, …
This function calculates and returns values in the Fibonacci sequence and uses recursion.
FUNCTION Fib(Number : INTEGER) RETURNS INTEGER
IF Number <= 1 THEN
Result ← Number
ELSE
Result ← Fib(Number – 1) + Fib(Number – 2)
ENDIF
RETURN Result
ENDFUNCTION
Complete the trace table for the function when it is called as Fib(5) .
| Call number | Function call | Number | Result | Return value |
|---|---|---|---|---|
5 |
||||
Show mark scheme
12(a) [2 marks]
One mark per mark point ( Max 2 ) A process using a function or procedure defined in terms of itself / calls itself. A recursive process must have a base case (which is a way to return without making a recursive call) // terminating solution // concept of unwinding described There must (also) be a general case where the recursive call takes place.
12(b) [5 marks]
One mark per mark point ( Max 5 ) column correct Call number and columns correct Function call Number column down to base case (Winding) rows 1–6 correct Result column down from base case (Unwinding) rows 7–10 correct Result Return value column correct Number Result Call Function call Return number value 1 Fib(5) 5 Fib(4) + Fib(3) 2 Fib(4) 4 Fib(3) + Fib(2) 3 Fib(3) 3 Fib(2) + Fib(1) 4 Fib(2) 2 Fib(1) + Fib(0) 5 Fib(1) 1 1 1 6 Fib(0) 0 0 0 (4) Fib(2) 2 1 + 0 1 (3) Fib(3) 3 1 + 1 2 (2) Fib(4) 4 2 + 1 3 (1) Fib(5) 5 3 + 2 5
Show mark scheme
12(a) [6 marks]
One mark for each point ( Max 6 ) • Initialisation of upper bound • Test if upper bound is less than lower bound • Re-setting of mid value if current value is lower than the target • Re-setting of mid value if current value is higher than the target • Finding the value • Correct termination of loop Lower 0 Upper 99 Mid 0 Exit FALSE OUTPUT "Enter the name to be found " INPUT Target REPEAT IF Upper < Lower THEN OUTPUT Target, " does not exist" Exit TRUE ENDIF Mid Lower + (Upper – Lower + 1) DIV 2 IF Names[Mid] < Target THEN Lower Mid + 1 ENDIF IF Names[Mid] > Target THEN Upper Mid - 1 ENDIF IF Names[Mid] = Target THEN OUTPUT Target, " was found at location ", Mid Exit TRUE ENDIF UNTIL Exit // UNTIL Exit = TRUE
12(b)(i) [1 mark]
O(n)
12(b)(ii) [2 marks]
One mark for each point ( Max 2 ) • O(log n) is a time complexity that uses logarithmic time. • The time taken goes up linearly as the number of items rises exponentially • O(log n) is the worst case scenario (time complexity for a binary search).
Show mark scheme
12(a) [6 marks]
One mark for each point ( Max 6 ) • Initialisation of upper bound • Test if upper bound is less than lower bound • Re-setting of mid value if current value is lower than the target • Re-setting of mid value if current value is higher than the target • Finding the value • Correct termination of loop Lower 0 Upper 99 Mid 0 Exit FALSE OUTPUT "Enter the name to be found " INPUT Target REPEAT IF Upper < Lower THEN OUTPUT Target, " does not exist" Exit TRUE ENDIF Mid Lower + (Upper – Lower + 1) DIV 2 IF Names[Mid] < Target THEN Lower Mid + 1 ENDIF IF Names[Mid] > Target THEN Upper Mid - 1 ENDIF IF Names[Mid] = Target THEN OUTPUT Target, " was found at location ", Mid Exit TRUE ENDIF UNTIL Exit // UNTIL Exit = TRUE
12(b)(i) [1 mark]
O(n)
12(b)(ii) [2 marks]
One mark for each point ( Max 2 ) • O(log n) is a time complexity that uses logarithmic time. • The time taken goes up linearly as the number of items rises exponentially • O(log n) is the worst case scenario (time complexity for a binary search).
(a) The diagram shown represents an artificial neural network.
Layer 1 Hidden Layer 2
Layer 3
(i) State the reason for having multiple hidden layers in an artificial neural network. 1 mark
(ii) Explain how artificial neural networks enable machine learning. 4 marks
(b) Find the shortest path between the Home and School nodes using the A* algorithm. 5 marks 3 marks
Show your working in the table provided.
The first two rows in the table have been completed.
| Node | Cost from Home node (g) | Heuristic (h) | Total (f = g + h) |
|---|---|---|---|
| Home | 0 | 14 | 14 |
| A | 1 | 10 | 11 |
Final path 10 (a) State three essential features of recursion .
1
2
3
(b) Explain the reasons why a stack is a suitable Abstract Data Type (ADT) to implement recursion. 3 marks
(c) Identify two ADTs other than a stack. 2 marks
1
2
(d) The function StackFull() checks whether a stack is full. 5 marks
The function uses the variable TopOfStack to represent the pointer to the most recent
position used on the stack, and the variable Max to represent the maximum size of the stack.
Assume TopOfStack and Max are global variables.
FUNCTION StackFull() RETURNS BOOLEAN
IF TopOfStack = Max THEN
RETURN TRUE
ELSE
RETURN FALSE
ENDIF
ENDFUNCTION
An algorithm AddInteger is required to add a new integer data element to a stack.
The stack is implemented as an array ArrayStack .
The function AddInteger() calls StackFull() and returns an appropriate message.
Complete the pseudocode for the function AddInteger() .
FUNCTION AddInteger(NewInteger : INTEGER) RETURNS STRING
ENDFUNCTION
Show mark scheme
9(a)(i) [1 mark]
One mark for correct statement (Max 1) Enables deep learning to take place • Where the problem you are trying to solve has a higher level of • complexity it requires more layers to solve To enable the neural network to learn and make decisions on its own • To improve the accuracy of the result. •
9(a)(ii) [4 marks]
One mark for each correct marking point (Max 4) Artificial neural networks are intended to replicate the way human brains • work Weights / values are assigned for each connection between nodes • The data are input at the input layer and are passed into the system • They are analysed at each subsequent (hidden) layer where • characteristics are extracted / outputs are calculated … this process of training / learning is repeated many times to achieve • optimum outputs // reinforcement learning takes place Decisions can be made without being specifically programmed • The deep learning net will have created complex feature detectors • The output layer provides the results • Back propagation (of errors) will be used to correct any errors that have • been made.
9(b) [5 marks]
One mark for each correct calculation as follows (Max 4) Node B (from Home) (Line 3 in table) • Node C (from Home) (Line 4 in table) • Node B and Node E (from A) (Lines 5 and 6 in table) • Node F and Node School (from E) (Lines 7 and 8 in table) • Node School (from F) (Line 9 in table) • One mark for correct path (Max 1) : Home School • Node Cost from Home Heuristic Total Node (g) (h) (f = g + h) 1 Home 0 14 14 2 A 1 10 11 3 B 5 7 12 4 C 4 9 13 5 B 1 + 3 = 4 7 11 6 E 1 + 6 = 7 3 10 7 F 7 + 1 = 8 3 11 8 School 7 + 5 = 12 0 12 9 School 8 + 3 = 11 0 11 Final Path Home School
(a) The diagram shown represents an artificial neural network.
Layer 1 Hidden Layer 2
Layer 3
(i) State the reason for having multiple hidden layers in an artificial neural network. 1 mark
(ii) Explain how artificial neural networks enable machine learning. 4 marks
(b) Find the shortest path between the Home and School nodes using the A* algorithm. 5 marks 3 marks
Show your working in the table provided.
The first two rows in the table have been completed.
| Node | Cost from Home node (g) | Heuristic (h) | Total (f = g + h) |
|---|---|---|---|
| Home | 0 | 14 | 14 |
| A | 1 | 10 | 11 |
Final path 10 (a) State three essential features of recursion .
1
2
3
(b) Explain the reasons why a stack is a suitable Abstract Data Type (ADT) to implement recursion. 3 marks
(c) Identify two ADTs other than a stack. 2 marks
1
2
(d) The function StackFull() checks whether a stack is full. 5 marks
The function uses the variable TopOfStack to represent the pointer to the most recent
position used on the stack, and the variable Max to represent the maximum size of the stack.
Assume TopOfStack and Max are global variables.
FUNCTION StackFull() RETURNS BOOLEAN
IF TopOfStack = Max THEN
RETURN TRUE
ELSE
RETURN FALSE
ENDIF
ENDFUNCTION
An algorithm AddInteger is required to add a new integer data element to a stack.
The stack is implemented as an array ArrayStack .
The function AddInteger() calls StackFull() and returns an appropriate message.
Complete the pseudocode for the function AddInteger() .
FUNCTION AddInteger(NewInteger : INTEGER) RETURNS STRING
ENDFUNCTION
Show mark scheme
9(a)(i) [1 mark]
One mark for correct statement (Max 1) Enables deep learning to take place • Where the problem you are trying to solve has a higher level of • complexity it requires more layers to solve To enable the neural network to learn and make decisions on its own • To improve the accuracy of the result. •
9(a)(ii) [4 marks]
One mark for each correct marking point (Max 4) Artificial neural networks are intended to replicate the way human brains • work Weights / values are assigned for each connection between nodes • The data are input at the input layer and are passed into the system • They are analysed at each subsequent (hidden) layer where • characteristics are extracted / outputs are calculated … this process of training / learning is repeated many times to achieve • optimum outputs // reinforcement learning takes place Decisions can be made without being specifically programmed • The deep learning net will have created complex feature detectors • The output layer provides the results • Back propagation (of errors) will be used to correct any errors that have • been made.
9(b) [5 marks]
One mark for each correct calculation as follows (Max 4) Node B (from Home) (Line 3 in table) • Node C (from Home) (Line 4 in table) • Node B and Node E (from A) (Lines 5 and 6 in table) • Node F and Node School (from E) (Lines 7 and 8 in table) • Node School (from F) (Line 9 in table) • One mark for correct path (Max 1) : Home School • Node Cost from Home Heuristic Total Node (g) (h) (f = g + h) 1 Home 0 14 14 2 A 1 10 11 3 B 5 7 12 4 C 4 9 13 5 B 1 + 3 = 4 7 11 6 E 1 + 6 = 7 3 10 7 F 7 + 1 = 8 3 11 8 School 7 + 5 = 12 0 12 9 School 8 + 3 = 11 0 11 Final Path Home School
Study the following pseudocode for a recursive function.
FUNCTION Unknown(BYVAL X, BYVAL Y : INTEGER) RETURNS INTEGER
IF X < Y THEN
OUTPUT X + Y
RETURN (Unknown(X + 1, Y) * 2)
ELSE
IF X = Y THEN
RETURN 1
ELSE
OUTPUT X + Y
RETURN (Unknown(X - 1, Y) DIV 2)
ENDIF
ENDIF
ENDFUNCTION
The operator DIV returns the integer value after division e.g. 13 DIV 2 would give 6
(a) Write program code to declare the function Unknown() . 3 marks
Save your program as question 1 .
Copy and paste the program code into part 1(a) in the evidence document.
Show mark scheme
1(a) [3 marks]
1 mark per bullet point function with correct name and parameters • correct Div operator (or equivalent) used • code matches pseudocode • Example program code: Python def Unknown(X, Y): if X < Y: print(str(X + Y)) return Unknown(X + 1, Y) * 2 elif X == Y: return 1 else: print(str(X + Y)) return int(Unknown(X - 1, Y) / 2) VB.NET Function Unknown(X, Y) If X < Y Then Console.WriteLine(X + Y) Return Unknown(X + 1, Y) * 2 ElseIf X = Y Then Return 1 Else Console.WriteLine(X + Y) Return Unknown(X - 1, Y) \ 2 End If End Function Java public static Integer Unknown(Integer X, Integer Y){ if(X < Y){ System.out.println(X+Y); return Unknown(X + 1, Y) * 2; }else if(X == Y){ return 1; }else{ System.out.println(X + Y); Integer ReturnValue = Unknown(X-1,Y) / 2; return ReturnValue; } }
1(b)(i) [2 marks]
1 mark per bullet point Suitable output identifying parameters for each call • All three correct function calls … • …outputting the return value for each call • Example program code: Python print("10 and 15") print(str(Unknown(10, 15))) print("10 and 10") print(str(Unknown(10, 10))) print("15 and 10") print(str(Unknown(15, 10))) VB.NET Console.WriteLine("10 and 15") Console.WriteLine(Unknown(10, 15)) Console.WriteLine("10, 10") Console.WriteLine(Unknown(10, 10)) Console.WriteLine("15, 10") Console.WriteLine(Unknown(15, 10)) Java public static void main(String[] args){ System.out.println("10 and 15"); System.out.println(Unknown(10,15)); System.out.println("10 and 10"); System.out.println(Unknown(10, 10)); System.out.println("15 and 10"); System.out.println(Unknown(15, 10)); }
1(b)(ii) [7 marks]
1 mark for 1 function with correct output 1 mark for remaining 2 function calls with correct output For example: 10 and 15 25 26 27 28 29 32 10 and 10 1 15 and 10 25 24 23 22 21 0
1(c) [1 mark]
Java public static Integer IterativeUnknown(Integer X, Integer Y){ Integer Total = 1; while (X != Y){ System.out.println(X+Y); if(X<Y){ X = X + 1; Total = Total * 2; }else{ X = X - 1; Total = Total / 2; } } return Total; }
1(d)(i)
Calling function 3 times with correct Data and outputting Example program code: Python print("10 and 15") print(str(IterativeUnknown(10, 15))) print("10 and 10") print(str(IterativeUnknown(10, 10))) print("15 and 10") print(str(IterativeUnknown(15, 10))) VB.NET Console.WriteLine("10 and 15") Console.WriteLine(IterativeUnknown(10, 15)) Console.WriteLine("10, 10") Console.WriteLine(IterativeUnknown(10, 10)) Console.WriteLine("15, 10") Console.WriteLine(IterativeUnknown(15, 10)) Java System.out.println("10 and 15"); System.out.println(IterativeUnknown(10, 15)); System.out.println("10 and 10"); System.out.println(IterativeUnknown(10, 10)); System.out.println("15 and 10"); System.out.println(IterativeUnknown(15, 10));
1(d)(ii) [5 marks]
1 mark for screenshot showing correct output for both functions
Study the following pseudocode for a recursive function.
FUNCTION Unknown(BYVAL X, BYVAL Y : INTEGER) RETURNS INTEGER
IF X < Y THEN
OUTPUT X + Y
RETURN (Unknown(X + 1, Y) * 2)
ELSE
IF X = Y THEN
RETURN 1
ELSE
OUTPUT X + Y
RETURN (Unknown(X - 1, Y) DIV 2)
ENDIF
ENDIF
ENDFUNCTION
The operator DIV returns the integer value after division e.g. 13 DIV 2 would give 6
(a) Write program code to declare the function Unknown() . 3 marks
Save your program as question 1 .
Copy and paste the program code into part 1(a) in the evidence document.
Show mark scheme
1(a) [3 marks]
1 mark per bullet point function with correct name and parameters • correct Div operator (or equivalent) used • code matches pseudocode • Example program code: Python def Unknown(X, Y): if X < Y: print(str(X + Y)) return Unknown(X + 1, Y) * 2 elif X == Y: return 1 else: print(str(X + Y)) return int(Unknown(X - 1, Y) / 2) VB.NET Function Unknown(X, Y) If X < Y Then Console.WriteLine(X + Y) Return Unknown(X + 1, Y) * 2 ElseIf X = Y Then Return 1 Else Console.WriteLine(X + Y) Return Unknown(X - 1, Y) \ 2 End If End Function Java public static Integer Unknown(Integer X, Integer Y){ if(X < Y){ System.out.println(X+Y); return Unknown(X + 1, Y) * 2; }else if(X == Y){ return 1; }else{ System.out.println(X + Y); Integer ReturnValue = Unknown(X-1,Y) / 2; return ReturnValue; } }
1(b)(i) [2 marks]
1 mark per bullet point Suitable output identifying parameters for each call • All three correct function calls … • …outputting the return value for each call • Example program code: Python print("10 and 15") print(str(Unknown(10, 15))) print("10 and 10") print(str(Unknown(10, 10))) print("15 and 10") print(str(Unknown(15, 10))) VB.NET Console.WriteLine("10 and 15") Console.WriteLine(Unknown(10, 15)) Console.WriteLine("10, 10") Console.WriteLine(Unknown(10, 10)) Console.WriteLine("15, 10") Console.WriteLine(Unknown(15, 10)) Java public static void main(String[] args){ System.out.println("10 and 15"); System.out.println(Unknown(10,15)); System.out.println("10 and 10"); System.out.println(Unknown(10, 10)); System.out.println("15 and 10"); System.out.println(Unknown(15, 10)); }
1(b)(ii) [7 marks]
1 mark for 1 function with correct output 1 mark for remaining 2 function calls with correct output For example: 10 and 15 25 26 27 28 29 32 10 and 10 1 15 and 10 25 24 23 22 21 0
1(c) [1 mark]
Java public static Integer IterativeUnknown(Integer X, Integer Y){ Integer Total = 1; while (X != Y){ System.out.println(X+Y); if(X<Y){ X = X + 1; Total = Total * 2; }else{ X = X - 1; Total = Total / 2; } } return Total; }
1(d)(i)
Calling function 3 times with correct Data and outputting Example program code: Python print("10 and 15") print(str(IterativeUnknown(10, 15))) print("10 and 10") print(str(IterativeUnknown(10, 10))) print("15 and 10") print(str(IterativeUnknown(15, 10))) VB.NET Console.WriteLine("10 and 15") Console.WriteLine(IterativeUnknown(10, 15)) Console.WriteLine("10, 10") Console.WriteLine(IterativeUnknown(10, 10)) Console.WriteLine("15, 10") Console.WriteLine(IterativeUnknown(15, 10)) Java System.out.println("10 and 15"); System.out.println(IterativeUnknown(10, 15)); System.out.println("10 and 10"); System.out.println(IterativeUnknown(10, 10)); System.out.println("15 and 10"); System.out.println(IterativeUnknown(15, 10));
1(d)(ii) [5 marks]
1 mark for screenshot showing correct output for both functions
(a) Describe what is meant by an imperative (procedural) programming language. 2 marks 2 marks
(b) Describe what is meant by a declarative programming language. 4 marks
| (c) Identify the programming paradigm for eac | ch of these program code examples. |
|---|---|
| Program code example | Programming paradigm |
male(john).female(ethel).parent(john, ethel). |
|
FOR Counter = 1 TO 20 X = X * CounterNEXT Counter |
|
Start: LDD Counter INC ACC STO Counter |
|
public class Vehicle{ private speed; public Vehicle() { speed = 0; }} |
Show mark scheme
9(a)
One mark for each correct marking point (Max 2) Imperative languages use variables • … which are changed using (assignment) statements • … they rely on a method of repetition / iteration. • The statements provide a sequence of commands for the computer to • perform … in the order written / given • … each line of code changes something in the program run. •
9(b) [2 marks]
One mark for each correct marking point (Max 2) Instructs a program on what needs to be done instead of how to do it • ... using facts and rules • … using queries to satisfy goals. • Can be logical or functional • Logical - states a program as a set of logical relations • Functional – constructed by applying functions to arguments / uses a • mathematical style
9(c) [4 marks]
One mark for each correct programming paradigm (Max 4) Program code example Programming paradigm male(john). Declarative female(ethel). parent(john, ethel). FOR Counter = 1 TO 20 Procedural / imperative X = X * Counter NEXT Counter Start: LDD Counter Low-level / assembly INC ACC STO Counter public class Vehicle { private speed; public Vehicle() Object oriented / (OOP) { speed = 0; } }
(a) Describe what is meant by an imperative (procedural) programming language. 2 marks 2 marks
(b) Describe what is meant by a declarative programming language. 4 marks
| (c) Identify the programming paradigm for eac | ch of these program code examples. |
|---|---|
| Program code example | Programming paradigm |
male(john).female(ethel).parent(john, ethel). |
|
FOR Counter = 1 TO 20 X = X * CounterNEXT Counter |
|
Start: LDD Counter INC ACC STO Counter |
|
public class Vehicle{ private speed; public Vehicle() { speed = 0; }} |
Show mark scheme
9(a)
One mark for each correct marking point (Max 2) Imperative languages use variables • … which are changed using (assignment) statements • … they rely on a method of repetition / iteration. • The statements provide a sequence of commands for the computer to • perform … in the order written / given • … each line of code changes something in the program run. •
9(b) [2 marks]
One mark for each correct marking point (Max 2) Instructs a program on what needs to be done instead of how to do it • ... using facts and rules • … using queries to satisfy goals. • Can be logical or functional • Logical - states a program as a set of logical relations • Functional – constructed by applying functions to arguments / uses a • mathematical style
9(c) [4 marks]
One mark for each correct programming paradigm (Max 4) Program code example Programming paradigm male(john). Declarative female(ethel). parent(john, ethel). FOR Counter = 1 TO 20 Procedural / imperative X = X * Counter NEXT Counter Start: LDD Counter Low-level / assembly INC ACC STO Counter public class Vehicle { private speed; public Vehicle() Object oriented / (OOP) { speed = 0; } }
(a) Describe what is meant by an imperative (procedural) programming language. 2 marks 2 marks
(b) Describe what is meant by a declarative programming language. 4 marks
| (c) Identify the programming paradigm for eac | ch of these program code examples. |
|---|---|
| Program code example | Programming paradigm |
male(john).female(ethel).parent(john, ethel). |
|
FOR Counter = 1 TO 20 X = X * CounterNEXT Counter |
|
Start: LDD Counter INC ACC STO Counter |
|
public class Vehicle{ private speed; public Vehicle() { speed = 0; }} |
Show mark scheme
9(a)
One mark for each correct marking point (Max 2) Imperative languages use variables • … which are changed using (assignment) statements • … they rely on a method of repetition / iteration. • The statements provide a sequence of commands for the computer to • perform … in the order written / given • … each line of code changes something in the program run. •
9(b) [2 marks]
One mark for each correct marking point (Max 2) Instructs a program on what needs to be done instead of how to do it • ... using facts and rules • … using queries to satisfy goals. • Can be logical or functional • Logical - states a program as a set of logical relations • Functional – constructed by applying functions to arguments / uses a • mathematical style
9(c) [4 marks]
One mark for each correct programming paradigm (Max 4) Program code example Programming paradigm male(john). Declarative female(ethel). parent(john, ethel). FOR Counter = 1 TO 20 Procedural / imperative X = X * Counter NEXT Counter Start: LDD Counter Low-level / assembly INC ACC STO Counter public class Vehicle { private speed; public Vehicle() Object oriented / (OOP) { speed = 0; } }
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: