OCR A Level Computer Science Algorithms and programming November 2020 question paper H446/02

Kira is creating a computer game where the user can play against the computer.

In each turn, each character can make one move from a selection of possible moves.

Kira uses a tree data structure shown in Fig. 1 to identify the range of possible moves the computer can make from starting position A. Each connection is a move, with each node representing the result of the move.

State what is meant by the term ‘abstraction’ and describe how Kira has used abstraction in her design of the tree.

State why the tree shown in Fig. 1 is not an example of a binary search tree.

State what type of pointers are used to store nodes I, F, J and H so they do not point to any other nodes.

Kira wants the program to traverse the tree to evaluate the range of possible moves. She is considering using a breadth-first traversal or a depth-first (post-order) traversal.

Show how a breadth-first traversal would traverse the tree shown in Fig. 1.

Kira wants to make some changes to the data that is stored in the tree structure shown in Fig. 1.

The move represented by node ‘E’ needs to be deleted.

Describe the steps an algorithm will follow to delete node ‘E’ from the tree.

The move represented by the node ‘K’ needs to be added. Node ‘K’ needs to be joined to node ‘G.’

Describe the steps the algorithm will follow to add node ‘K’ to the right of node ‘G’.

Kira could have used a graph data structure to represent the moves in her game.

Give two similarities and two differences between a tree and a graph data structure.

OCR-Tickets wants to sell tickets for their concerts, plays and other events online. A customer should be able to create an account and then be able to log into their account. Once logged in, customers should be able to carry out actions such as setting their preferences and purchase tickets.

OCR-Tickets have hired a software development company to create the system for them.

The system requirements have a number of features that mean they are solvable by computational methods, such as decomposition.

Explain why decomposition can help the development of the program.

* Discuss the need for concurrent processing in OCR-Ticket’s system and the benefits and drawbacks of using this.

Hugh has written a recursive function called thisFunction() using pseudocode.

The function DIV calculates integer division, e.g. 5 DIV 3 = 1

State the name of the standard algorithm thisFunction() performs.

Hugh could have written thisFunction() using iteration instead of recursion.

Compare two differences between recursion and iteration.

The recursive function thisFunction() is printed again here for your reference.

Rewrite the function thisFunction() so that it uses iteration instead of recursion.

You should write your answer using pseudocode or program code.

The following pseudocode procedure performs an insertion sort on the array parameter.

Explain why dataArray is passed by reference and not by value.

State whether the procedure insertionSort sorts the data into ascending or descending order and explain your choice.

* Two other sorting algorithms are merge sort and quick sort.

Compare the use of merge sort, quick sort and insertion sort on an array with a small number of elements, and on an array with a very large number of elements.

You should make reference to the time complexities of each algorithm using the Big O notation in your answer.

A fourth sorting algorithm is a bubble sort.

Describe how a bubble sort will sort an array of 10 elements.

A printer buffer is a storage area that holds the data, known as jobs, that are to be printed by a printer.

A simulation of the printer buffer uses a queue data structure to store jobs that are waiting to be printed. The queue is not circular.

The printer buffer is represented as a zero-indexed 1D array with the identifier buffer.

Fig. 2 shows the current contents of the queue buffer and its pointers.

State the purpose of the pointers queueHead and queueTail.

The array, buffer and pointer values are declared with global scope.

The function dequeue returns null if the array is empty, and the contents of the next element if not empty. The queue is not circular.

Write an algorithm, using pseudocode or program code, for the function dequeue()

The function enqueue returns-1 if there is no space at the end of the queue to add data, and returns 1 if the parameter was added to buffer. The array buffer contains a maximum of 100 elements.

Write an algorithm, using pseudocode or program code, for the function enqueue()

In the main program of the simulation the user is asked whether they want to add an item to the queue or remove an item.

If they choose to add an item they have to input the job name, and the function enqueue is called.

If they choose to remove an item, the function dequeue is called and the job name is output.

Appropriate messages are output if either action cannot be run because the queue is either empty or full.

Write, using pseudocode or program code, an algorithm for the main program of the simulation.

The queue is changed to make it a circular queue.

Describe how the functions enqueue and dequeue will need to be changed to allow buffer to work as a circular queue.

Some print jobs can have different priorities. The higher the priority the sooner the job needs to be printed.

Describe how the program could be changed to deal with different priorities.

Barney is writing a program to store data in a linked list. He is writing the initial program for a maximum of 10 data items.

Each node in the linked list has a data value and a pointer (to the next item).

A null pointer is stored with the value –1.

Describe the purpose of freeListPointer.

State the purpose of headPointer.

Barney wants the nodes to be stored as objects using object-oriented programming. He designs the following class.

The constructor assigns the parameters to the attributes to create an object.

The class node, uses get methods and set methods.

Describe one difference between get methods and set methods.

The function findNodePath() takes the data item to find in the linked list as a parameter and follows the pointers to find the required node.

The function returns the array indexes of all the nodes it visits and joins this to a suitable message stating whether the data was found or not found and then returns this as one string.

Describe how the function findNodePath() will search for the data item and return the required message.

The procedure printLinkedList() follows the pointers to print all of the elements in the linked list.

The procedure has a number of errors.

Identify the line of each error and write the corrected line.

Error 1 line number........

Error 1 correction........

Error 2 line number........

Error 2 correction........

Error 3 line number........

Error 3 correction........

Barney will use an Integrated Development Environment (IDE) to debug his program code.

Describe three features commonly found in IDEs that Barney could use to debug his program code.

* Barney would like his linked list to be part of a base program that is saved in a library. This means that it can be reused and changed by other programs.

Discuss the benefits of using different object-oriented techniques that Barney could use to achieve this.