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

Data in a computer program needs to be sorted.

Describe the steps a bubble sort will take to sort items into ascending order.

Darcie and Felix have both written a program that will perform a bubble sort to put these numbers into ascending order.

Darcie’s version will complete six passes. However, Felix’s version will only need to complete two passes.

Explain how Felix may have made his version more efficient than Darcie’s version.

A second type of sorting algorithm is an insertion sort.

Describe how an insertion sort can be used to put the following data into ascending order.

A third type of sorting algorithm is a quick sort.

The following quick sort algorithm is made up of two functions called partition() and quickSort(). The algorithm will sort an integer array into ascending numerical order.

Identify which of the two functions is recursive and give all of the line numbers where recursive calls are made.

Recursive function name........

Recursive call line numbers........

Identify the type of iteration used in the function partition().

Describe the role of the function partition() in the quick sort algorithm.

The algorithm needs to be changed to sort the integer array into descending numerical order.

Identify the line number that needs to be changed and write the amended line of code.

Amended line of code........

The quick sort is an example of a divide-and-conquer algorithm.

Describe what divide-and-conquer means.

2* A shopping website requires customers to create a username and password.

The usernames and passwords are stored securely in a file. The file contains the username and passwords for 50 million users which are sorted in alphabetical order by username.

The file can be searched using a linear search or a binary search.

The big-O complexities for a linear search and a binary search are given in the table:

Compare the use of a linear search and a binary search in this scenario.

You should include the following in your answer:

• the features and preconditions of a linear and binary search

• the benefits and drawbacks of each search in this scenario

• a conclusion justifying which search algorithm should be used in this scenario.

You should make reference to the big-O complexities in your answer.

The website collects data from customers’ activities once they log on. For example, the items they view and purchase. The company that owns the website would like to use data mining to improve their website and customer experience.

Describe what data mining means.

Explain how the company can make use of data mining to improve their website and customer experience.

A program is designed to use a stack data structure.

The current contents of part of the stack and its current pointer value are shown:

pointer = 2

Show the contents of the stack and its pointer value after the data items "t" and "s" are inserted in the order given.

The stack is stored using a 0-based 1-dimensional array called theStack with 20 elements.

The function push() stores its parameter into the next space in the stack if it is not full. The function returns true if it is successfully stored and returns false if the stack is full.

Complete the function push() using pseudocode or program code.

A pointer value of-1 indicates that the stack is empty.

The function pop() returns the next element in the stack. If the stack is empty it returns "false". The function updates the pointer value when appropriate.

Write the function pop() using pseudocode or program code.

A program is designed to reverse a set of data using the stack.

The main program takes 10 characters separately as input from the user and uses the function push() to insert these into the stack.

Once all 10 characters have been inserted into the stack, the program then uses the function pop() to output all 10 characters from the stack.

Write the main program to achieve this using pseudocode or program code.

Explain why this graph is a visualisation of the problem.

A user needs to travel from planet A to planet H. They need to travel the least expensive route.

Show how Dijkstra’s algorithm can be used on the directed graph shown in Fig. 5 to find the shortest path from start planet A to the end planet H.

You must state the nodes on the final path and the distance of this path. Show your working.

You may use the table to give your answer.

The A* algorithm can also be used to find the shortest path in a graph.

Describe how an A* algorithm uses heuristics to be an efficient algorithm.

A student is writing a program in a high-level programming language.

The student writes the program using an Integrated Development Environment (IDE).

Complete the table by identifying and describing three features of an IDE that the student can use to debug their program.

The program the student is developing includes both global and local variables.

Explain the difference between a global variable and a local variable.

Describe one drawback of using global variables in a program.

Describe one drawback of using local variables in a program.

A variable can be passed as a parameter into a function by value or by reference.

Describe what parameter passing by value means.

An algorithm is needed to count how many times each of the numbers from 1 to 9 appear in an array called myArray. Another array called checked is used to store each number found in myArray and the number of times it appears. For example, the contents of myArray are:

Based on these contents in myArray, the contents in checked would be:

–1 indicates an unused space in the array as the numbers 1, 4, 8 and 9 have not been found.

The student has written the following pseudocode for this program.

The pseudocode contains several errors.

Identify the line number of any four errors and write the corrected line for each error.

Error 1

Error 2

Error 3

Error 4

An ordered binary search tree contains the following data:

Add the following data items in the given order to the binary search tree above. 5 30 53 57 90

A balanced binary search tree has data consistently at each level, for example:

An unbalanced binary search tree is uneven, for example:

Describe the drawback of an unbalanced binary search tree when searching for a value.

A different binary search tree stores the following data:

Give the output that will be produced from a depth-first (post-order) traversal and a breadth-first traversal of this binary search tree.

Depth-first (post-order)........

A linked list data structure is designed using object-oriented programming.

The design includes two classes called node and linkedList.

Describe the features of a linked list data structure.

The class design for node is shown here.

new() is the constructor method. The constructor method takes a parameter and assigns this to the value attribute.

The method getNextNode() returns the attribute nextNode.

Write the method getNextNode() using pseudocode or program code.

The method setValue() takes an integer as a parameter and assigns this to the attribute value

Write the method setValue() using pseudocode or program code.

The class design for linkedList is shown here.

new() is the constructor method. The constructor initialises the attribute headNode to a null value.

Write the constructor method using pseudocode or program code.

The class design for node and linkedList are shown again here for your reference.

The method getValue() will return the value of a node. The method getNextNode() will return the next node to be accessed in the linked list.

The method outputList() traverses the linked list starting at the node headNode. The method joins the data in each node and returns it.

Complete the method outputList() using pseudocode or program code.

The method insertNode() will insert a new node into the linked list.

The method accepts an integer as a parameter, creates a new node with that data and inserts it into the linked list, e.g. insertNode(8) creates a node object with the data 8 and adds it to the linked list.

The program needs to store the following data items in the linked list in the order they are given: 10 25 39

The program then needs to output all of the data in the list using the appropriate method.

Write an algorithm using pseudocode or program code to:

• create a new linkedList object with the identifier createList

• insert each of the data items into the linked list (10, 25, 39)

• output the content of the linked list.

A new method is needed to remove a node from the linked list. The method needs to take the data to remove as a parameter and then find this data in the linked list before removing the node.

Describe the steps that this method will need to follow and the decisions that need to be made in the method to remove the correct node.

The program developer made use of computational methods when designing the object-oriented programming solution. One computational method is divide-and-conquer.

Identify three other computational methods that the program developer could have used.

* This program uses classes and objects to create a linked list.

An alternative method is creating a 2-dimensional array. In this design the first index stores the data and the second element stores the index of the next data item. Array elements not currently used are also linked together to form a chain of empty values to identify where the next data item can be inserted.

Compare the two different methods of creating a linked list that have been described.

You should include the following in your answer:

• the features of both methods including the reusability of program components

• benefits and drawbacks of both methods in this program

• a conclusion evaluating the efficiency of both methods when designing a program that needs

a linked list.