Computational Thinking, Searching & Sorting Algorithms (OCR GCSE Computer Science)

A program stores the following list of positive and negative numbers. The numbers need sorting into ascending order using a merge sort.

The first step is to divide the list into individual lists of one number each. This has been done for you.

Complete the merge sort of the data by showing each step of the process.

Once the numbers are in order, a binary search can be run on the data.

Describe the steps a binary search will follow to look for a number in a sorted list.

A linear search could be used instead of a binary search.

Describe the steps a linear search would follow when searching for a number that is not in the given list.

A sample of data is shown in Fig. 4.

Fig. 4

Show the stages of a binary search to find the word zebra using the data shown in Fig. 4.

Tick (✓) one box in each row to identify whether each statement about the insertion sort is true or false.

The sorted list of words is shown below.

Explain how a binary search would be used to try to find whether the word “house” appears in this list.

Taylor has used computational thinking techniques to develop an algorithm.

Give two computational thinking techniques that Taylor could have used, describing how they could have been used.

The following names of students are stored in an array with the identifier studentnames.

studentnames = ["Rob", "Anna", "Huw", "Emma", "Patrice", "Iqbal"]

Describe the steps that a linear search would take to find Anna in studentnames

The names of students are sorted into ascending alphabetical order using an insertion sort.

Complete the following diagram to show the stages an insertion sort would take to complete this task.

Each row represents one pass of the insertion sort algorithm.

You may not need to use all empty rows.

Elliott plays football for OCR FC.

He wants to create a program to store the results of each football match they play and the names of the goal scorers.

Elliott wants individual players from the team to be able to submit this information.

Define what is meant by abstraction.

Give one example of how abstraction could be used when developing this program in part (a).

A library sorts their books based on a book code.

Show the steps that a merge sort would take to put the following list of book codes into ascending alphabetical order (from A to Z).

POE12 , BAC97 , FLY77 , JAV16 , TAL86 , AND18 , ZAR09 , HOP86

Explain one advantage of a merge sort compared to a bubble sort.

A program uses a file to store a list of words that can be used in a game.

A sample of this data is shown in Fig. 3.

Fig. 3

Show the stages of a bubble sort when applied to data shown in Fig. 3.

An insertion sort algorithm is used to sort a dataset of game scores from smallest to largest

game_scores = [101, 110, 130, 50, 66]

To perform an insertion sort, a count-controlled loop must be used.

Describe the purpose of the count-controlled loop and give an example of what the loop would look like.

Describe the steps involved in performing a bubble sort on the list in Fig. 1. Show the state of the list after each complete pass through the list.

Fig. 1