Keeping only the details that are needed and ignoring the rest
What is the name for working out the steps needed to solve a problem, in the correct order, precisely enough that a computer can follow them?
Algorithmic thinking
What is meant by an algorithm?
A sequence of steps that solves a problem
Which term describes a set of techniques for understanding a problem and working out a solution that a computer can carry out?
Computational thinking
What is meant by a sub-problem?
A smaller part of a larger problem that can be solved and tested on its own
A programmer tests a first version of a solution, then improves the problem definition and the solution step by step. What is this called?
Refining the problem
Computational thinking is used to define a problem. What does this mean?
Working out exactly what has to be solved
What does decomposition mean in computational thinking?
Breaking a large problem into smaller sub-problems
A chess program stores each piece as a single letter and the board as an 8 by 8 grid. What is being done here?
Real objects are being represented by simpler models
A team splits a large program into parts so that different people can write each part. Which principle of computational thinking is being used?
Decomposition
A programmer lists the steps of a solution and decides the order they must be carried out in. Which principle of computational thinking is being used?
Algorithmic thinking
A sat nav needs to work out a route. Which detail about a road is not needed and so would be left out?
The colours of the houses along the road
Why must every step of an algorithm be written precisely?
A processor follows each instruction exactly and cannot guess what was meant
What is a benefit of decomposition when solving a large problem?
Each part is simpler to understand, write and test
Why does abstraction make a problem easier to solve?
The solution is simpler and there is less to design and program
A quiz program asks ten questions and adds one to the score for each correct answer. Which step is carried out once, before the repeat begins?
Setting the score to zero
A sub-problem is still too large to solve easily on its own. What should be done next?
Break it down into smaller sub-problems
A programmer writes the steps for making a slice of toast as: take the bread from the bag, put it in the toaster, wait until it pops up, push the lever down. What is wrong with this solution?
The steps are not in the correct order
Which term describes the flowchart symbol with rounded ends that marks where an algorithm starts and finishes?
Terminal
What is meant by an input/output symbol in a flowchart?
A parallelogram used for input and output steps
Which term describes the diamond shaped symbol that holds a question with exactly two labelled exits?
Decision
What is meant by a process symbol in a flowchart?
A rectangle used for a calculation or an assignment
Which term describes the symbol that runs a separate named flowchart and is drawn as a rectangle with an extra vertical line just inside each side?
Sub program
What is meant by iteration in a flowchart?
Steps that repeat because an arrow leads back up
Which term describes the arrow that joins one symbol to the next in a flowchart?
Line
What is a flowchart?
A diagram of the steps of an algorithm, joined by arrows
Which flowchart symbol should contain a step such as total = total + price?
Process
How many exits must each decision symbol in a flowchart have?
Exactly two, both labelled
A flowchart sets count to 1. While count is 5 or less it outputs count and then adds 1 to count. How many numbers are output?
5
A flowchart inputs a length, inputs a width, multiplies them and outputs the result. What does the flowchart do?
Calculates the area of a rectangle
A flowchart repeats a group of steps until the user types the correct password. What type of iteration is this?
Condition-controlled
Why might a programmer replace a group of boxes in a flowchart with one sub program symbol?
To keep a large flowchart small and easier to read
A flowchart grades a mark by checking mark >= 70 and then mark >= 50. What would go wrong if the two checks were swapped?
A mark of 85 would be graded Merit
A flowchart outputs the numbers 1 to 10 using a counter that starts at 1 and increases by 1 each time round. Which Python code matches?
for count in range(1, 11): print(count)
A flowchart outputs 1, 2, 3 and so on forever. What is the most likely mistake in the flowchart?
The counter is never increased inside the loop
A flowchart checks the condition temperature < 20 before each repeat, and an arrow leads back up to the decision. Which Python statement matches this loop?
while temperature < 20
A flowchart shows the step INPUT length inside a rectangle. Which change makes this step correct?
Use a parallelogram, the input/output symbol
In a flowchart, one decision sits inside the Yes path of another decision. What does this show?
Selection nested inside selection
A flowchart contains the same four boxes, in the same order, three times. What is the best way to refine it?
Put the boxes inside a loop that repeats three times
A flowchart keeps inputting numbers until the user enters 0, and outputs each number that is not 0. The user enters 4, 6 and 0. Which numbers are output?
4 and 6
A flowchart inputs a number, then keeps inputting more numbers and compares each one with the value stored, replacing the stored value whenever the new number is larger. What does this flowchart do?
Finds the largest number entered
What is meant by a linear search?
An algorithm that compares the value being looked for with each item in turn, starting at the first item
What is meant by a binary search?
An algorithm that checks the middle item of a sorted list, then throws away the half that cannot hold the value
What is the name for a condition that must already be met before an algorithm can be used, such as the data being in order before a certain search can be carried out?
Pre-requisite
What is meant by mid in a binary search?
The position of the middle item of the part of the list that is still being searched
Which term describes one check in which a search algorithm compares the value it is looking for with a single item in a list?
Comparison
What is meant by a sorted list?
A list in which the items are arranged in numerical or alphabetical order
In a binary search, what do the variables low and high hold?
The positions of the first and last items of the part of the list still being searched
What is the main purpose of a search algorithm?
To find whether an item is in a list and where it is
What is a pre-requisite of a binary search that a linear search does not have?
The list must already be sorted into order
A linear search is used to find 30 in the list 5, 12, 18, 24, 30, 36, 42. How many comparisons are made before 30 is found?
5
A linear search compares every item in a list and finds no match. What does this mean?
The item being searched for is not in the list
A binary search is used on the sorted list 4, 9, 15, 22, 28, 31 (positions 0 to 5). Which item is compared first?
15
In a binary search, the item being looked for is larger than the middle item. What happens next?
The middle item and everything before it are discarded
A binary search is looking for a value that is not in the list. How does the search finish?
When low becomes greater than high, so there is nothing left
Why does a binary search usually make fewer comparisons than a linear search on a large sorted list?
Each comparison removes half of the items still to be checked
A search uses low, high and mid, sets mid to (low + high) // 2 and moves low or high past mid. Which search is this?
Binary search
A list of names is stored in no particular order and will be searched once. Which search is the better choice?
A linear search, because the list is not sorted
A binary search is used on the sorted list 1, 3, 5, 7, 9, 11, 13, 17, 23, 29 (positions 0 to 9) to find 23. How many comparisons are made before 23 is found?
3
A binary search is used on the sorted list 1, 8, 16, 17, 18, 19, 25 (positions 0 to 6) to look for 20. How many comparisons are made before the search stops?
3
A program searches a list using a single index that starts at 0 and goes up by 1 each time round a loop, comparing the item at that index with the value it wants until the item is found or the end of the list is reached. Which search is the program using?
Linear search
A binary search is used on the sorted list butterscotch, chocolate, mint, strawberry, vanilla (positions 0 to 4) to look for chocolate. Which item is compared second?
Butterscotch
In search algorithms, what is the usual name for the value that the algorithm is trying to find in a list?
Target
A linear search is used to find 50 in the list 5, 12, 18, 24, 30, 36, 42. How many comparisons are made before the search finishes?
7
A programmer adds a new score to the end of a sorted list but does not sort the list again. Why might a binary search now give the wrong result?
The list is no longer fully sorted, so the search could discard the half that actually contains the value
Which term describes an algorithm that puts a list of items into order by comparing each neighbouring pair in turn, swapping them when they are in the wrong order, and repeating until a complete run makes no swaps?
Bubble sort
What is meant by 'merge sort'?
A sorting algorithm that repeatedly divides a list into smaller sub-lists until each holds one item, then combines them back together in order
What is meant by 'insertion sort'?
A sorting algorithm that takes each item in turn and inserts it into its correct position among the items already sorted, shifting larger items one place to the right
What is the name for a single complete run through a list in which every neighbouring pair of items is compared once?
A pass
Which term describes arranging the items of a list so that the smallest value comes first and the largest value comes last?
Ascending order
What is meant by a swap in a sorting algorithm?
Two items change places in the list
What is meant by a sub-list in a merge sort?
A smaller list made by dividing the original list into parts
When does a bubble sort know that the list has been sorted?
After a whole pass is made with no swaps
The list 5, 3, 8, 1 is sorted into ascending order with a bubble sort. What is the list after the first pass?
3, 5, 1, 8
In the code for a bubble sort, what is the swapped flag used for?
It shows that a pass made no swaps so the sort stops
In a merge sort, what is done to the list before the merging begins?
It is split until every sub-list holds one item
The list 6, 2, 5, 1 is sorted with a merge sort. What are the sub-lists after the first merging step?
2, 6 and 1, 5
The list 9, 4, 7, 2 is sorted into ascending order with an insertion sort. What is the list once 7 has been inserted?
4, 7, 9, 2
Which statement about the three standard sorting algorithms is correct?
Merge sort is usually quicker on large lists but needs extra memory
During the merge step of a merge sort, which item is copied into the result list next?
The smaller of the two front items is copied next
A programmer wants to sort an unsorted list of numbers using one of the three standard sorting algorithms. What has to be done to the list before the sort can start?
Nothing, the sort can start with the items in any order
Which sorting algorithm does this code use?
Insertion sort
The list 4, 9, 1, 6 is sorted into descending order using a bubble sort. What is the list after the first pass?
9, 4, 6, 1
Why does a bubble sort finish quickly when a list is already nearly in order?
Only a few passes are needed before one makes no swaps
During the merge of two sorted lists, one list runs out of items before the other. What happens to the items that are left?
They are copied straight to the end of the result list
After the first pass of a bubble sort that is putting a list into ascending order, which item is certain to be in its final position?
The largest item, at the end of the list
The words pear, apple, lemon, banana are sorted into ascending alphabetical order using an insertion sort. What is the list once lemon has been inserted?
Apple, lemon, pear, banana
What is meant by a pre-requisite of an algorithm?
A condition that must already be true before the algorithm can be used
Which sorting algorithm does this code use?
Bubble sort
Which sorting algorithm uses this code?
Merge sort
Which term describes the data that a program is given to work with, such as a value typed by a user or a record read from a file?
Input
What is meant by a process?
Work done on data, such as a calculation or a comparison
Which term describes something a program sends out, such as text shown on screen, a printed document, a sound or a signal that turns a device on or off?
Output
What is meant by a prompt?
A message displayed to the user that asks them to enter some data
Which term describes a device that measures a physical quantity such as temperature, light or movement and passes readings into a program?
Sensor
What is meant by a running total?
A value that builds up in a variable as each new item of data is added to it