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

Exam Questions

1 hour14 questions
12 marks

State the name of each of the following computational thinking techniques.

Breaking a complex problem down into smaller problems.

Hiding or removing irrelevant details from a problem to reduce the complexity.

Did this page help you?

24 marks

The following table contains several definitions of terms that are used in Computer Science.

Letter

Definition

A

Cleaning up data entered by removing non-standard characters

B

Hiding or removing irrelevant details from a problem to reduce complexity

C

Checking that the user is allowed to access the program

D

Breaking a complex problem down into smaller problems

E

Repeating elements of a program

F

Converting one data type to another, for example converting an integer to a real number

Write the letter of the definition that matches each keyword in each space.

Keyword

Letter

Decomposition

Abstraction

Input sanitisation

Casting

Did this page help you?

3a1 mark

A list of valid discount codes is shown below.

[NIC12B, LOR11S, STU12M, VIC08E, KEI99M, WES56O, DAN34S]

State one reason why a binary search would not be able to be used with this data.

3b1 mark

Give the name of one searching algorithm that would be able to be used with this data.

Did this page help you?

1a3 marks

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

45

12

-99

100

-13

0

17

-27

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.

Seven numbers inside individual boxes: 45, 12, -99, 100, -13, 0, 17, and -27. The boxes are arranged in a horizontal line.
1b4 marks

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.

1c2 marks

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.

Did this page help you?

24 marks

A sample of data is shown in Fig. 4.

amber

house

kick

moose

orange

range

wind

zebra

Fig. 4

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

Did this page help you?

3a5 marks

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

Statement

True (✓)

False (✓)

The list of words is initially split into a sorted set and an unsorted set.

The insertion sort uses a divide stage and then a conquer stage.

The list of words must be in order before the insertion sort can start.

Each word is inserted into the correct place in the array, one by one.

The insertion sort will not work because the word “wall” appears twice.

3b4 marks

The sorted list of words is shown below.

flour

house

pumpkin

wall

wall

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

Did this page help you?

44 marks

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.

Computational thinking technique

How could it have been used?

Did this page help you?

54 marks

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

Did this page help you?

65 marks

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.

A table with seven columns labeled

Did this page help you?

7a2 marks

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.

7b1 mark

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

Did this page help you?

8a4 marks

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

8b2 marks

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

Did this page help you?

14 marks

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.

crime

bait

fright

victory

nibble

loose

Fig. 3

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

Did this page help you?

23 marks

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.

Purpose

Example

Did this page help you?

35 marks

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.

12

34

45

23

8

39

Fig. 1

Did this page help you?