8.1 Algorithms (OCR A Level Computer Science): Exam Questions

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

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

Explain why a quicksort is known as a divide and conquer algorithm.

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

01 procedure insertionSort(dataArray:byRef)

02  for i = 1 to dataArray.Length - 1

03   temp = dataArray[i]

04   tempPos = i – 1

05   exit = false

06   while tempPos >= 0 and exit == false

07    if dataArray[tempPos] < temp then

08     dataArray[tempPos + 1] = dataArray[tempPos]

09     tempPos = tempPos - 1

10    else

11     exit = true

12    endif

13   endwhile

14   dataArray[tempPos + 1] = temp

15  next i

16 endprocedure

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

A fourth sorting algorithm is a bubble sort.

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

This bubble sort algorithm is written to sort numberArray into ascending numerical order.

Complete this bubble sort algorithm.

One section of numberArray is shown here.

A second sorting algorithm that could be used to sort this data is a merge sort.

Show how a merge sort will sort this section of the array numberArray into ascending numerical order.

Fig. 5 shows a graph data structure representing a small section of a parcel delivery network. Each node represents an address where deliveries need to be made. The edges show the possible routes and distances between these deliveries.

Give a similarity and difference between the performance of Dijkstra’s algorithm and the performance of A* algorithm.

The pseudocode function binarySearch() performs a binary search on the array dataArray that is passed as a parameter. The function returns the array index of searchValue within the array, and -1 if it is not in the array.

The pseudocode binary search algorithm is incomplete.

Complete the algorithm by filling in the missing statements.

The tables below show possible Big O complexities for the worst-case space, best-case space and average time for search algorithms.

Tick the worst-case space complexity for a binary and linear search

Tick the best-case space complexity for a binary and linear search.

Tick the average time complexity for a binary and linear search.

A one dimensional array holds data that needs to be sorted.

Describe how a quicksort would sort data into ascending order.

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.

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.

A tree is one example of a data structure.

A graph is another type of data structure.

An example graph is shown in Fig. 1.

Show how Dijkstra’s algorithm can be used on the graph shown in Fig. 1 to find the shortest path from start node A to end node G.

You must state the nodes on the final path and the distance of this path. Show your working.

You may use the table below to give your answer.

Final path: ...............................................

Distance: ................................................

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 an example of a sorting algorithm is insertion sort.

The number of values stored in an array numberArray is 10.

Compare the use of bubble, merge and insertion sorts on the array numberArray.

You should include the following in your answer:

• how each algorithm works

• the Big O complexities for each algorithm

• the suitability of each algorithm for sorting the 10 values.

Fig. 5 shows a graph data structure representing a small section of a parcel delivery network. Each node represents an address where deliveries need to be made. The edges show the possible routes and distances between these deliveries.

Show how Dijkstra’s algorithm can be used on the graph shown in Fig. 5 to find the shortest path from the start node A and the end node H.

You should state the nodes on the final path and the overall distance. Show your working.

You may choose to use the table below to give your answer.

Some of the characters in a game will move and interact independently. Taylor is going to use graphs to plan the movements that each character can take within the game.

DancerGold is one character. The graph shown in Fig. 1 shows the possible movements that DancerGold can make.

DancerGold’s starting state is represented by node A. DancerGold can take any of the paths to reach the end state represented by node G.

The number on each path represents the number of seconds each movement takes.

The number in bold below each node is the heuristic value from A.

Perform an A* algorithm on the graph shown in Fig. 1 to find the shortest path from the starting node to the end node.

Show your working, the nodes visited and the distance.

You may choose to use the table below to give your answer.