OCR A Level Computer Science Algorithms and programming June 2022 question paper H446/02

A computer program stores data in an array named words.

The data in the array needs to be searched for a value that the user inputs.

One example of a searching algorithm is a binary search.

Identify the precondition for a binary search.

A second example of a searching algorithm is a linear search.

Describe how a linear search works.

The array words is defined as a global variable and contains these values:

The pseudocode function useWords() here uses the global array words.

The number of words in the array words is passed as a parameter.

Identify two variables in the function useWords().

numberOfWords is a parameter passed by value.

Describe the difference between passing a parameter by value and by reference.

Rewrite the function useWords() to use a while loop instead of a for loop.

The function header and close have been written for you.

Write your answer using pseudocode or program code.

function useWords(numberOfWords: byVal)

endfunction

Give one benefit and one drawback of declaring the array as a global variable instead of a local variable.

Describe one feature of an Integrated Development Environment (IDE) that can be used to help write the program and one feature that can be used to help test the program.

Functions and procedures are reusable components.

Give two benefits of writing a program with reusable components.

A computer program is being written to store data about students.

Fig. 2 shows a binary search tree that stores data about students.

Each student is represented by their ID number. The current contents of the binary search tree are:

Fig. 2

Identify the root node in the binary tree shown in Fig. 2.

Identify two leaf nodes in the binary tree shown in Fig. 2.

Four more students are added to the binary search tree shown in Fig. 2 in this order:

1420 2050 2780 2600

Complete the binary search tree here by adding the new students to it.

* A programmer would like to traverse the binary search tree shown in Fig. 2.

Compare the use of a breadth-first traversal and a depth-first (post-order) traversal on the binary search tree.

You should include the following in your answer:

• how each traversal works

• the order of the return values for each traversal.

A bubble sort will sort an array of 50 integer values called numberArray.

State why the integer values are stored in an array instead of separate variables.

This bubble sort algorithm is written to sort numberArray into ascending numerical order.

Complete this bubble sort algorithm.

One section of numberArray is shown here.

A second sorting algorithm that could be used to sort this data is a merge sort.

Show how a merge sort will sort this section of the array numberArray into ascending numerical order.

* Another sorting algorithm is insertion sort.

The number of values stored in the array numberArray has been reduced to 10.

Compare the use of bubble, merge and insertion sorts on the array numberArray.

You should include the following in your answer:

• how each algorithm works

• the Big O complexities for each algorithm

• the suitability of each algorithm for sorting the 10 values.

A programmer is developing an aeroplane simulator. The user will sit in a cockpit and the simulated environment will be displayed on screens around them.

The programmer uses computational methods to design a solution for the program.

Complete the table by writing a definition for each computational method.

Give three potential differences between the abstracted aeroplane simulator and reality.

Identify two reasons why abstraction is used when designing a solution to the problem.

Describe how caching can be used in the aeroplane simulator.

State one way a directed graph is different to an undirected graph.

State one way a graph data structure is different to a tree data structure.

Give one reason why the graph is a visualisation of the problem.

Give a similarity and difference between the performance of Dijkstra’s algorithm and the performance of A* algorithm.

State why performance modelling is used to test a system.

Describe how performance modelling can be used in the delivery system.

A card game uses a set of 52 standard playing cards. There are four suits; hearts, diamonds, clubs and spades. Each suit has a card with a number from; 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13.

The card game randomly gives 2 players 7 cards each. The unallocated cards become known as the deck.

The players then take it in turns to turn over a card. A valid move is a card of the same suit or the same number as the last card played.

The winner is the first player to play all of their cards.

One component of the game is checking if a move is valid.

Identify three other components of the game.

A function, checkValid(), takes the card the player has selected, and the last card played as parameters.

It returns true if the player’s move is valid and returns false if the player’s move is not valid.

State the reason why checkValid() is a function and not a procedure.

The programmer will use a branching (selection) construct to make decisions.

Describe the decisions that will be made in the checkValid() function and how these change the return values.

The cards are held in the 2D array cards. The first index stores the card number and the second index stores the suit, both as strings.

Write a pseudocode statement or program code to declare the array cards.

A program uses the recursive function calculate(). The function is written in pseudocode.

Give the line number in the algorithm calculate() where a recursive call is made.

State two features of any recursive algorithm.

Trace the recursive function calculate() and give the final return value, when the following function call is run:

calculate(5)

You may choose to use the table below to give your answer.

Give the pseudocode function call that would return 55 from the recursive function calculate().

A computer uses a stack data structure, implemented using an array, to store numbers entered by the user.

The array is zero based and has 100 locations.

State the purpose of pointerValue.

The stack is programmed as an object using object-oriented programming. The design for the class, its attributes and methods are shown:

The method pop() returns the next value in the stack, or –1 if the stack is empty.

Complete the pseudocode method pop().

The method push() accepts an integer as a parameter and adds it to the top of the stack unless the stack is already full.

If the push is successful the method returns true.

If the push is unsuccessful due to the stack being full the method returns false.

Write the method push() using either pseudocode or program code.

The main program initialises a new object of type stack with the identifier mathsStack

Write pseudocode or program code to declare the object.

The main program needs to:

• take numbers as input from the user

• push them onto the stack mathsStack until the stack is full

• output an appropriate message if the stack is full.

Complete the pseudocode algorithm to meet these requirements.

The main program also needs to:

• remove one item from the stack at a time and add this to a total

• output the total every time an item is removed

• stop removing items when either the stack is empty, or 20 items have been removed.

Write pseudocode or program code to meet these requirements.

The program is amended to include the use of several queue data structures.

Describe how an array can be used to implement a queue data structure.

* Discuss the use of object-oriented programming and procedural programming to create and manipulate the queue data structures.

You should include the following in your answer:

• the features of object-oriented programming

• the features of procedural programming

• the benefits of using object-oriented instead of procedural programming when creating several queue structures.