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

A tree is one example of a data structure.

Give two characteristics of a tree data structure.

The following data is entered into a binary search tree.

22 13 5 36 55 14 8

Draw the binary search tree when the given data is entered in the order given.

Describe how a leaf node is deleted from a binary search tree.

Describe how a binary search tree can be searched for a value.

Identify the order that the nodes will be visited in a depth-first (post-order) traversal of this binary search tree.

Explain how backtracking is used in depth-first (post-order) traversals.

2* A company needs a new computer program that will create schedules for delivery drivers. It will need to identify a possible order that the drivers can deliver items and possible routes they could take.

Discuss how programmers could make use of problem recognition and problem decomposition when designing this system.

You should include the following in your answer:

• a description of both problem recognition and decomposition

• how each method can be used when designing the solution

• the benefits of using each method when designing the solution.

A program stores data in a linked list.

The current contents of the linked list are shown in Fig. 3, along with the linked list pointers.

State the purpose of headPointer and freeListPointer in the linked list shown in Fig. 3.

State the meaning of the pointers with the value NULL in the linked list shown in Fig. 3.

A procedure outputs the data in the linked list shown in Fig. 3 from the first item in the list, to the last item.

Give the output from the procedure.

A new item needs to be added to the linked list.

Describe how a new item is added to a linked list.

The function findNode will search the linked list and return either the position of the node that contains the data item, or-1 if the data item is not found.

The data held in a node at location x can be accessed with linkedList[x].data. The pointer of the node at location x can be accessed with linkedList[x].pointer.

Complete the function, using pseudocode or program code.

A programmer has designed a program that includes a reusable program component.

The reusable program component is a function called isInteger(). This will take a string as an argument and then check that each digit is between 0 and 9. For example if 103 is input, it will check that the digits 1, 0 and 3 are each between 0 and 9.

The asc() function returns the ASCII value of each digit. For example asc("1") returns 49.

The ASCII value for 0 is 48. The ASCII value for 9 is 57.

Identify one identifier used in the function isInteger().

Give the line number where the branching (selection) construct starts in the function isInteger().

Give the line number where the iteration construct starts in the function isInteger()

Describe the purpose of the following lines in the function isInteger().

Line 03........

Line 04........

Line 09........

Give two reasons why reusable program components are used in programs.

A recursive pseudocode function, recursiveAlgorithm(), is shown.

Describe the key features of a recursive algorithm.

You may refer to the function, recursiveAlgorithm() in your answer.

Trace the recursive function, recursiveAlgorithm(), and give the final return value when called with recursiveAlgorithm(10). You may choose to use the table below to give your answer.

Final return value........

7* (a) A program designer needs to decide on an algorithm to use from a choice of three. The table shows the worst-case Big O complexities for each algorithm.

The program will be used to analyse data that can range from 2 items to 2 billion items.

Compare the use of all three algorithms and suggest which the programmer should use.

You should include the following in your answer:

• the meaning of constant, logarithmic, linear and exponential complexity

• how well each algorithm scales as the amount of data increases

• which algorithm is the most suitable for the given task.

The program designer is investigating the use of concurrent processing.

Describe what is meant by the term ‘concurrent processing’.

Give two benefits of using concurrent processing.

The programmer needs to use a merge sort in one part of the problem to sort items in ascending order.

Describe how a merge sort works.

Give one benefit and one drawback of the programmer using a merge sort instead of a bubble sort.

The programmer uses an Integrated Development Environment (IDE).

Complete the table by identifying and describing three IDE features that can help the programmer to develop, or debug a program.

A program is being designed that will allow a user to log into an account on a website using a username and password.

Identify two possible inputs and one output this program will need.

Identify two possible sub-procedures that could be used in this program.

A text-based computer game allows a user to dig for treasure on an island. The island is designed as a grid with 10 rows and 20 columns to store the treasure. Each square is given an x and y coordinate. Some of the squares in the grid store the name of a treasure object. Each treasure object has a value, e.g. 100 and a level, e.g. "Bronze."

The computer game makes use of abstraction.

Describe what is meant by the term abstraction and give an example of how abstraction can be used in the treasure game.

Give three benefits of using abstraction when writing a program.

The treasure game is being programmed using an object-oriented paradigm.

A class, Treasure, is used to store the treasure objects.

The design for the Treasure class, its attributes and methods is shown here.

The constructor method takes a value as an integer, e.g. 100, and a level, e.g. "bronze", as parameters and assigns these to the attributes.

Write pseudocode or program code to declare the class Treasure.

You should define the attributes and constructor method in your answer.

You do not need to write the get methods.

The get method getLevel() will return the appropriate attribute.

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

Describe the object-oriented programming technique being used in part 9(b)(ii).

A class, Board, is used to store the 10 row (x coordinate) by 20 column (y coordinate) grid.

The design for the Board class, its attributes and methods is shown here.

The constructor initialises each space in the grid to a treasure object with value as-1 and level as an empty string.

Complete the following pseudocode for the constructor method.

A procedure, guessGrid():

• takes a Board object as a parameter

• accepts the row (x) and column (y) coordinates from the user

• outputs "No treasure" if there is no treasure found at the coordinate (level is an empty string)

• if there is treasure at that coordinate, it outputs the level and the value of the treasure in an appropriate message.

Write the procedure guessGrid() using either pseudocode or program code.

Describe two benefits of using an object-oriented paradigm rather than a procedural paradigm.

* The main program initialises a new instance of Board. The programmer is considering declaring this as a global variable or as a local variable and then passing this into the subroutines that control the game.

Compare the use of variables and parameters in this game.

You should include the following in your answer:

• what is meant by a local variable and global variable

• how local and global variables can be used in this program

• the use of passing parameters by value and by reference.