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

The temperatures of an ocean are input into a computer system. They are recorded, and will be accessed, in the order in which they arrive. The data for one week is shown:

5, 5.5, 5, 6, 7, 6.5, 6

The data is to be stored in a data structure. The programmer stores the data in a queue.

Explain why a queue is used instead of a stack.

The data is processed. After processing, the value for the first day is stored as 0. The value for each following day is stored as an increase, or decrease, from the first day.

For example: if the first day was 7, the second was 6 and the third was 9, after processing it would be stored as 0, –1, 2.

The queue uses dequeue() to return the first element of the queue.

dequeue() is a function.

Explain why dequeue() is a function, not a procedure.

The contents of processedData are shown.

The data needs to be sorted into ascending order.

Explain how a bubble sort algorithm sorts data. Use the current contents of processedData in your explanation.

A program needs to store the names of plants that are in a garden, so they can be easily found and accessed in alphabetical order.

The data is stored in a tree structure. Part of the tree is shown.

State the type of tree shown in Fig. 2.1.

Show the output of a breadth-first traversal of the tree shown in Fig. 2.1.

Explain how backtracking is used in a depth-first (post-order) traversal. Use the tree in Fig. 2.1 in your explanation.

The elements in the tree in Fig. 2.1 are read into a linked list producing an alphabetised list.

Complete the following table to show the linked list for the data.

A new plant, Lavender, needs adding to the linked list. The linked list needs to retain its alphabetical order.

Complete the table to show the linked list after Lavender is added.

Hosta needs removing from the linked list.

Explain how a data item is removed from a linked list. Use the removal of Hosta in your answer.

The linked list is stored as a 2D array with the identifier plantList. The index of the first element of the linked list is stored in the identifier firstElement.

All contents of the linked list need to be output in alphabetical order.

Write an algorithm to follow the pointers to output the contents of the linked list in alphabetical order.

Add comments to explain your code.

A recursive function, GCD, is given in pseudocode.

The function uses branching.

Identify the type of branching statement used in the function.

Explain the difference between branching and iteration.

Identify the two parameters in the function.

1

2.

State whether the parameters should be passed by value, or by reference. Justify your answer.

Describe the arithmetic operation of MOD. Use an example in your answer.

Trace the recursive function when it is called by the statement GCD(250, 20). Give the final value returned.

Final return value:.

The function has been rewritten using iteration instead of recursion.

State one benefit and one drawback of using iteration instead of recursion.

Benefit.

Drawback.

Complete the missing statements in this iterative version of the function.

Mabel is a software engineer. She is writing a computer game for a client. In the game the main character has to avoid their enemies. This becomes more difficult as the levels of the game increase.

Mabel uses decomposition to design the program.

Explain how decomposition can aid the design of this program.

The computer game allows a user to select a character (e.g. name, gender). They can then choose a level for the game (easy, normal, challenging). The user controls their character by moving it left or right. The character can jump using space bar as an input. If the character touches one of the enemies then it loses a life. The character has to make it to the end of the level without losing all their lives.

The game is designed in a modular way.

One sub-procedure will handle the user input.

Describe three other sub-procedures Mabel could create for the given game description.

Describe the decision that the program will need to make within the user input sub- procedure and the result of this decision.

Define pipelining and give an example of how it could be applied in the program.

*Mabel has been told that true programmers write programs in a text editor, and do not use IDEs. Mabel does not agree with this statement.

Discuss the use of an IDE in the development of this program.

A 1-dimensional array stores the following data:

The array needs sorting into descending order.

Describe how a merge sort would sort the given array into descending order.

An insertion sort can be used to sort the array instead of a merge sort.

Explain why an insertion sort might use less memory than a merge sort.

6* Benedict runs a social networking website. He has been told he should use data mining to help him enhance and improve his website.

Evaluate the use of data mining to help Benedict enhance and improve his social networking website.

The programmer will use abstraction to produce the program interface to represent the garden.

Give two different examples of how abstraction has been used to produce the layout of the garden.

Explain the need for abstraction in the production of this program.

The user needs to input data into the program to set up their garden layout.

Identify three pieces of data that the user may input into this program.

The program is to be built using object oriented programming.

All items that can be added to the garden are declared as instances of the class GardenItem

The class has the following attributes:

The constructor method sets the attributes to values that are passed as parameters.

Write pseudocode or program code to declare the class GardenItem and its constructor. All attributes should be private and initialised through the constructor (e.g. daisies =

new GardenItem("Flowerbed",2,1)

The trees in the garden layouts are defined by the class Tree. This class inherits from GardenItem.

The class Tree has the additional attributes: height, sun, shade.

If sun is true then the tree can grow in full sun, if it is false then it cannot.

If shade is true then the tree can grow in full shade, if it is false then it cannot.

The length and width of a tree are the same. Only one value for these measurements is passed to the constructor.

Write an algorithm, using pseudocode or program code, to declare the class Tree Declare all attributes as private.

The Common Oak is a type of tree. It has a maximum height, length and width of 40 m. It can grow in sun and shade.

Write a statement, using pseudocode or program code, to declare an instance of tree for the Common Oak. Give the object the identifier firstTree.

The classes GardenItem and Tree use get and set methods to access and alter their private attributes.

Write the get method getItemName and set method setItemName for class GardenItem. The set method takes the new value as a parameter.

Do not write any other methods, or re-declare the class.

* The programmer is designing the program to make use of caching and re-useable components.

Explain and evaluate the use of caching and re-useable components in the design of the garden program.