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

A programmer needs to sort an array of numeric data using an insertion sort.

The following, incomplete, algorithm performs an insertion sort.

Complete the algorithm.

Show how an insertion sort would sort the following data:

Using Big-O notation state the best case complexity of insertion sort.

Explain what your answer to part (b)(i) means.

(c*) The number of data items in the array is continually increasing.

Insertion sort has a worst case time complexity of O(n²) and space complexity of O(1).

An alternative sorting algorithm that could be used is bubble sort which also has a worst case time complexity of O(n²) and space complexity of O(1).

Briefly outline how the bubble sort algorithm works. Discuss the relationship between the complexities and the two sorting algorithms and justify which of the two algorithms is best

suited to sorting the array.

A programmer is developing an ordering system for a fast food restaurant. When a member of staff inputs an order, it is added to a linked list for completion by the chefs.

Explain why a linked list is being used for the ordering system.

Order 158 has been made, and needs adding to the end of the linked list.

Add the order, 158, to the linked list as shown in Fig. 2.1. Show the contents of the linked list in the following table.

Order 159 has been made. This order has a high priority and needs to be the second order in the linked list. Add the order, 159, to the original linked list as shown in Fig. 2.1. Show the contents of the linked list in the following table.

The linked list is implemented using a 2D array, theOrders:

• Row 0 stores orderNo

• Row 1 stores next

The data now stored in theOrders is shown in Fig. 2.2.

The following algorithm is written:

Outline why nodeNo does not need to be stored in the array.

Complete the trace table for procedure x, for the data shown in Fig. 2.2.

Describe the purpose of procedure x.

A new order, 190, is to be added to theOrders. It needs to be the third element in the list. The current contents of the array are repeated here for reference:

Describe how the new order, 190, can be added to the array, so the linked list is read in the correct order, without rearranging the array elements.

The user needs to be able to search for, and find, a specific order number.

State an appropriate search algorithm that could be used, and justify your choice against an alternative Search algorithm.

Appropriate Search Algorithm........

The programmer is writing the program using an IDE.

Identify three features of an IDE that the programmer would use when writing the code and describe how the features benefit the programmer.

(f*) The programmer is considering using concurrent programming.

Discuss how concurrent programming can be applied to the food ordering system and the

benefits and limitations of doing so.

An encryption routine reads a line of text from a file, reverses the order of the characters in the string and subtracts 10 from the ASCII value of each letter, then saves the new string into the same file.

The program is split into sub-procedures. Three sub-procedures are described as follows:

• Read string from file

• Push each character of the string onto a stack

• Read and encrypt each character message

Identify one further sub-procedure that could be used in the program.

Describe two advantages of splitting the problem into sub-procedures.

A function, readMessage:

• takes the file name as a parameter

• reads and returns the line of text

Complete the pseudocode algorithm for readMessage:

A function, push, can be used to add a character to a stack. For example:

theStack.push("H")

places the character H onto the stack, theStack.

A procedure, pushToStack, takes a string as a parameter and pushes each character of the message onto the stack, messageStack.

Complete the procedure below.

Add comments to explain how your code works.

procedure pushToStack(message)

endprocedure

Describe the steps that the program would have to take in order to encrypt the characters stored in the stack, and save them in a single variable.

Identify the data structure shown in Fig. 4.1.

The programmer is considering using a depth-first (post-order) traversal, or a breadth-first traversal to find the path between node A and node X.

Explain the difference between a depth-first (post-order) and breadth-first traversal.

Show how a depth-first (post-order) traversal would find the path between node A and node X for the structure shown in Fig. 4.1.

Explain how you used backtracking in your answer to part (b)(ii).

A recursive function, calculate, is shown below:

Identify the lines where recursion is used.

Trace the algorithm, showing the steps and result when the following line is run:

print(calculate(4,10))

Re-write the function so it uses iteration instead of recursion.

A software developer is creating a Virtual Pet game.

The user can choose the type of animal they would like as their pet, give it a name and then they are responsible for caring for that animal. The user will need to feed, play with, and educate their pet.

The aim is to keep the animal alive and happy, for example if the animal is not fed over a set period of time then the pet will die.

• The game tells the user how hungry or bored the animal is as a percentage (%) and the animal’s intelligence is ranked as a number between 0 and 150 (inclusive).

• Hunger and boredom increase by 1% with every tick of a timer.

• When the feed option is selected, hunger is reduced to 0.

• When the play option is selected, bored is reduced to 0.

• When the read option is selected, the intelligence is increased by 0.6% of its current value.

An example of the game is shown:

Fig. 1.1

Identify three inputs that the user will have to enter to start, and/or play the game.

The developer is using decomposition to design the game.

Describe the process of decomposition.

The developer needs to write procedures for the options play and read. Each of the options changes its corresponding value, and outputs the results to the screen.

Write a procedure, using pseudocode, to reset bored and output the new value in an appropriate message.

Write a procedure, using pseudocode, to increase intelligence by 0.6% and output the new intelligence in an appropriate message.

The developer is extending the game to allow users to have multiple pets of different types. The developer has written a class, Pet.

The attributes and methods in the class are described in the table:

Part of the class declaration is given:

Write a line of code that creates a new instance of Pet for a Tiger called “Springy”.

The method outputGreeting for the superclass is written as follows:

A class is needed for Tiger. The class needs to:

• inherit the methods and attributes from pet

• in the constructor, set type to Tiger, intelligence to 10, hunger to 50 and bored to 10

• extend the method outputGreeting, by outputting an additional line that says “I like to eat meat and roar”

Write, using pseudocode, the class Tiger.

(e*) The developer made use of abstraction when creating the Virtual Pet game.

Discuss the need for and purpose of abstraction and how abstraction will be used in the

development of the game.

The developer is storing the user’s pets in a 1-dimensional array. At each timer interval, the array is searched, using a linear search, to check if any pets’ hunger or bored values are greater than 90%. If they are, an alert is displayed to the user.

State the complexity of searching the pets in Big-O notation.

A given computer takes 4 milliseconds (ms) to search an array of 20 pets. Calculate an estimate of how long the computer will take to search an array of 100 pets.

Show your working.