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

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, and describe how.

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.

Show how a binary search will be used to find the number 10 in the following data set:

1  2  5  6  7  10  20

The student names for a team are stored in an array with the identifier theTeam

An example of the data in this array is shown:

A linear search function is used to find whether a student is in the team. The function:

• takes a student name as a parameter
• returns True if the student name is in the array
• returns False if the student name is not in the array

Complete the design of an algorithm for the linear search function.

function linearSearch(studentName)

    for count = 0 to …………….….....……………

        if theTeam[……………..…...…….………] == …………….….....…………… then

            return …………….….....……………

        endif

    next count

    return False

endfunction

A list of numbers is stored in the following order:

42, 17, 8, 31, 25, 14

Describe how the list would be sorted into ascending order using an insertion sort

You must show the list after passes 1, 2, 3 and 4, and then give the final sorted list

A list of words is stored in the following order:

grape, apple, cherry, banana, fig, date

Show how the list would be sorted into alphabetical order using an insertion sort

You must show the list after passes 1, 2, 3 and 4, and then give the final sorted list

A warehouse organises its inventory using product codes.

Show the steps that a merge sort would take to put the following list of product codes into ascending numerical order (from smallest to largest).

847 , 215 , 632 , 419 , 756 , 128 , 903 , 541

A library organises its book collection using reference numbers.

Show the steps that a bubble sort would take to put the following list of reference numbers into ascending numerical order (from smallest to largest).

523 , 187 , 412 , 695 , 234 , 876 , 341 , 158

A sports club records the scores of its members using player IDs.

Describe the steps that a bubble sort would take to put a list of player IDs into ascending numerical order (from smallest to largest).

742 , 315 , 628 , 891 , 456 , 203 , 567 , 134

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

Explain why the removal of geographical accuracy in a city bus map is a necessary form of abstraction for a computer

Justify the use of decomposition in a large-scale banking app, focusing on independent testing

Analyse how abstraction and decomposition help when designing an algorithm to solve a problem

A dataset of 1,000,000 items is unsorted.

Evaluate the effectiveness of using a binary search in this scenario

Explain a situation where a linear search would be more efficient than a binary search, even when the list is sorted

Explain why a merge sort is often preferred over a bubble sort when sorting a very large list, such as 10 million website users