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

A program stores entered data in a binary search tree.

The current contents of the tree are shown:

Complete the diagram to show the contents of the tree after the following data is added:

England, Scotland, Wales, Australia

Show the order of the nodes visited in a breadth first traversal on the following tree.

A pseudocode algorithm is written to search the tree to determine if the data item “Sweden” is in the tree.

The function currentNode.left()returns the node positioned to the left of currentNode

Complete the algorithm.

The algorithm needs to be used in different scenarios, with a range of different trees.

Identify two preconditions needed of a tree for this algorithm to work.

A company merger is joining five e-commerce retailers under one company, OCRRetail. Each retailer has a different sales system and OCRRetail wants to develop one computer system that can be used by all the retailers.

Mary’s software development company has been employed to analyse and design a solution for the company.

Two computational methods (techniques used to solve a problem using computational thinking) that Mary will use are problem recognition and decomposition.

State what is meant by problem recognition and decomposition.

State one additional computational method.

Mary plans to use data mining to generate information about OCRRetail’s customers. Mary will use this information to benefit the company.

Define the term ‘data mining’.

Identify two pieces of information that data mining could provide OCRRetail about sales, and state how OCRRetail could make use of this information.

Mary has developed the program and is considering using performance modelling before installing the system.

Define the term ‘performance modelling’.

Identify one way performance modelling could be used to test the new system.

Mary created the program as a series of sub-programs that can be reused.

Describe one benefit of Mary creating reusable program components.

The graph in Fig. 3 is a visualisation of the problem.

Identify one difference between a graph and a tree.

Explain how the graph is an abstraction of the problem.

Identify two advantages of using a visualisation such as the one shown in Fig. 3.

Demonstrate how Dijkstra’s algorithm would find the shortest path to the solution in Fig. 3.

* The creator of the puzzle has been told that the A* algorithm is more efficient at finding the shortest path because it uses heuristics.

Compare the performance of Dijkstra’s algorithm and the A* search algorithm, making reference to heuristics, to find the shortest path to the problem.

A recursive function, generate, is shown.

Trace the algorithm to show the value returned when generate(7) is called. Show each step of your working.

The parameter, num1, is passed by value.

Explain why the parameter was passed by value instead of by reference.

* Parameters can be used to reduce the use of global variables.

Compare the use of parameters to global variables in recursive functions.

A student called Jason writes a recursive algorithm. The recursive algorithm uses more memory than if Jason had written it as an iterative algorithm.

Explain why the recursive algorithm uses more memory than the iterative algorithm.

A computer program stores data input on a stack named dataItems. The stack has two sub-programs to add and remove data items from the stack. The stack is implemented as a 1D array, dataArray.

The current contents of dataItems are shown:

The main program asks a user to push or pop an item from the stack. If the user chooses ‘push’, the data item is added to the stack. If the user chooses “pop”, the next item is removed from the stack, multiplied by 3 and output.

The main program is shown:

Before the sub-programs, push() and pop(), can add or remove items from the stack, a selection statement is used to decide if each action is possible.

Describe the decision that needs to be made in each sub-program and how this impacts the next process.

The algorithm does not work when the user enters "PUSH" or "Push". The algorithm needs to be changed in order to accept these inputs.

Identify the line number to be changed and state the change that should be made.

The stack is implemented as a 1D array, dataArray.

Describe how a 1D array can be set up and used to push and pop items as a stack.

As an array, the data in dataArray is sorted and then searched for a specific value.

The data in dataArray is sorted into ascending order using an insertion sort.

The current contents of dataArray are shown:

Show the steps of an insertion sort on the current contents of the array dataArray.

The array dataArray can now be searched using a binary search.

Describe the stages of a binary search on an array of size n.

The array has 50 items.

The function, searchItem(), performs a linear search for a data item.

Rewrite the function using a while loop.

Kamran is writing a program to manipulate the data for a set of items.

For each item, the program needs to store:

• Item name (e.g. Box)

• Cost (e.g. 22.58)

• Date of arrival (e.g. 1/5/2018)

• Transferred (e.g. true)

The items are added to a queue for processing.

The queue is defined as a class, itemQueue.

The head attribute points to the first element in the queue. The tail attribute points to the next available space in the queue. The numItems attribute states how many items are currently in the queue.

The data about the items can be stored using either a record structure, or as objects of a class.

Explain the similarities and differences between a record and a class.

Kamran chooses to use a record structure to store the data about the items.

Record structures may be declared using the following syntax:

Complete the pseudocode to declare a record called items.

New records may be created using the following syntax:

Write a programming statement to create a new item, using the identifier ‘box1’, with the item name “Box”, the cost 22.58, date of arrival 1/5/2018 and transferred true.

The array, theItems, stores the items in the queue. When the tail of the queue exceeds the last element in the array, it adds a new item to the first element if it is vacant.

For example, in the following queue, the next item to be added would be placed at index 0.

Define the term ‘queue’.

The attributes in itemQueue are all declared as private.

Explain how a private attribute improves the integrity of the data.

The constructor method creates a new instance of itemQueue and sets the head, tail and numItems attributes to 0.

Write an algorithm, using pseudocode or program code, for the constructor including the initialisation for all attributes.

The enqueue method:

takes as a parameter the item to insert in the queue

checks if the queue is full

reports an error and returns false if the queue is full

does the following if the queue is not full: o adds the item to the array at the tail position and adjusts the pointer(s) o returns true

The attribute numItems stores the number of items currently in the queue.

Write an algorithm, using pseudocode or program code, for the enqueue method.

Write a programming statement to declare an instance of itemQueue called myItems

Write a procedure, insertItems(), to ask the user to input the data for an item. The item is then added to the queue myItems. The user is continually asked to input data items until the queue is full.

When the main program ends, the items and the queue no longer exist.

Describe how Kamran could amend the program to make sure the items and queue still exist and are used the next time the program is run.

* Kamran wants to expand the program to allow it to handle up to 100,000,000 items and to allow him to search for data about items. Kamran is worried that the increase in the number of items will cause a decrease in the performance of the program. He decides to investigate the benefits of caching and concurrent processing.

Evaluate the use of caching and concurrent processing in this scenario and make a recommendation to Kamran.