Flashcards · 9618 · A Level Topic 19

Computational thinking and Problem-solving (A Level) flashcards

10 cards on A Level Topic 19, subtopics 19.1 to 19.2. Pick a subtopic or study them all.

Study mode needs JavaScript. Every card is listed below, so you can still cover the answers and test yourself.

All 10 cards

For a quick read-through or printing. Cover the right-hand side to test yourself.

How does a binary search work, and what does it need?: The data must be sorted. Compare the item with the middle element; discard the half that cannot contain it; repeat on the remaining half until found or no items remain.
How does an insertion sort work?: Take each element in turn from the second onwards and move it back through the sorted part of the list until it is in the correct position.
What is Big O notation?: A way of describing how the time (or memory) an algorithm needs grows as the size of the input, n, grows, using the worst case.
What are the time complexities of linear search, binary search and bubble sort?: Linear search: O(n). Binary search: O(log n). Bubble sort and insertion sort: O(n²).
How do you add a value to a binary search tree?: Start at the root; go left if the value is smaller than the node, right if larger; repeat until an empty position is reached and add the new node there.

What is recursion?: A subroutine that is defined in terms of itself: it calls itself with a smaller version of the problem.
What are the essential features of a recursive subroutine?: A base case that stops the recursion, a general case that calls itself, and each call moving closer to the base case.
How does a compiler implement recursion?: Each call pushes a stack frame (return address, parameters, local variables) onto the call stack; when a call ends its frame is popped and control returns, unwinding the stack.
What happens if a recursive subroutine has no reachable base case?: It keeps calling itself until the call stack runs out of memory: a stack overflow.
Write a recursive factorial function in 9618 pseudocode.: FUNCTION Factorial(n : INTEGER) RETURNS INTEGER IF n = 0 THEN RETURN 1 ELSE RETURN n * Factorial(n - 1) ENDIF ENDFUNCTION