A Level Computer Science: Procedural Programming — Practice Questions

These are original questions written for Marlbridge, for revision and practice on this content. They are not reproduced past-paper questions, and they do not replicate the exam’s exact structure, question count or mark tariffs — examination boards hold copyright in their own papers. Use these alongside the official past papers available free from your board.

Related: Procedural Programming revision notes

A note on pseudocode. The specification’s own exams ask candidates to trace pseudocode, not write it — where a question asks you to write an algorithm, it must be written as a program in your own chosen language. The worked answers below are given in pseudocode purely for language-neutral illustration, not because that is the form the real exam requires.

---

Section A

1. Define algorithm and state two ways of representing one. [3]

2. Explain what is meant by decomposition and abstraction. [2]

Section B

3. Compare linear search and binary search.

(a) Describe how each works. [4] (b) (A-level only — section 3.13.5, Unit 4; the AS searching sub-section states Big O comparisons are not required at AS.) State the time complexity of each in Big O notation. [2] (c) State the precondition for binary search and explain why it is required. [3]

4. Write a program, in your chosen language, for a bubble sort of an array of integers into ascending order. [6]

5. Explain two ways bubble sort can be optimised, and state why it is still unsuitable for large data sets. [5]

6. Explain the benefits of a modular, top-down approach to program design, giving three points. [6]

7. Trace the following for input n = 4 and state the output:

result = 1
FOR i = 1 TO n
    result = result * i
ENDFOR
OUTPUT result

[3]

---

Section C

8. A program uses both procedures and functions, and passes parameters in different ways.

(a) Distinguish between a procedure and a function. [2]

(b) Distinguish between passing a parameter by value and by reference, and explain why passing by value is generally preferred. [3]

9. (A-level only — section 3.9.4.2, Unit 3; not assessed at AS.) A recursive function calculates factorial(n).

(a) Write a program, in your chosen language, for a recursive factorial function, clearly identifying the base case and the general case. [4]

(b) Explain what happens on the call stack when factorial(3) is called, and why a missing base case causes a stack overflow. [3]

10. A programmer is choosing between a stack, a queue, a static array and a dynamic list for different tasks.

(a) Distinguish between a stack and a queue in terms of the order in which elements are removed. [2]

(b) State one advantage and one disadvantage of a dynamic data structure compared with a static one. [2]

---

Answers

1. An algorithm is a finite, ordered sequence of unambiguous steps that solves a problem [1]. It can be represented as pseudocode [1] or as a flowchart (also structured English or a program) [1].

2. Decomposition — breaking a large problem into smaller, more manageable sub-problems that can be solved separately [1]. Abstraction — removing unnecessary detail so that only the features relevant to the problem remain [1].

3. (a) Linear search — examine each element in turn from the start until the target is found or the end is reached [1] [1]. Binary search — examine the middle element; if it is not the target, discard the half that cannot contain it and repeat on the remaining half [1] [1]. (b) Linear: O(n) [1]. Binary: O(log n) [1]. (c) The list must be sorted [1]. Binary search works by deciding which half to discard based on whether the target is greater or less than the middle element [1]; that decision is only valid if the elements are in order — on an unsorted list it would discard the half containing the target [1].

4.

n = number of elements in arr
FOR i = 0 TO n - 2
    swapped = FALSE
    FOR j = 0 TO n - 2 - i
        IF arr[j] > arr[j+1] THEN
            temp = arr[j]
            arr[j] = arr[j+1]
            arr[j+1] = temp
            swapped = TRUE
        ENDIF
    ENDFOR
    IF swapped = FALSE THEN
        EXIT FOR
    ENDIF
ENDFOR

Outer loop [1]; inner loop with correct bounds [1]; comparison of adjacent elements [1]; correct three-line swap using a temporary variable [1]; swapped flag set [1]; early exit when no swaps occur [1].

5. A swapped flag — if a complete pass makes no swaps, the list is already sorted and the algorithm can stop, so a list that is already or nearly sorted finishes after very few passes [1] [1]. Reducing the inner loop bound by one each pass — after pass i, the last i elements are already in their final positions, so re-comparing them is wasted work [1] [1]. It remains unsuitable for large data sets because, on unsorted data, the number of comparisons still grows with roughly the square of the number of items, so doubling the data about quadruples the work — merge sort is far faster on large lists, at the cost of extra memory [1]. (At A-level you would express this as O(n²) against O(n log n); Big O is not required at AS.)

6. Any three, 2 marks each: each module can be written and tested independently, so errors are localised and easier to find [1] [1]; several programmers can work on different modules simultaneously, shortening development time [1] [1]; modules can be reused in other programs, saving effort [1] [1]; the program is easier to read and maintain, since each module has a single clear purpose [1] [1].

7. i = 1: result = 1 [1]; i = 2: result = 2; i = 3: result = 6 [1]; i = 4: result = 24 [1]. This computes n factorial.

8. (a) A procedure performs a task but returns no value [1]; a function returns a value [1].

(b) By value passes a copy of the argument, so the original is unaffected [1]; by reference passes the address, so the original can be changed [1]. Passing by value is generally preferred because it prevents side effects, where one subroutine unintentionally alters data another part of the program depends on [1].

9. (a)

FUNCTION factorial(n)
    IF n = 0 THEN
        RETURN 1
    ELSE
        RETURN n * factorial(n - 1)
    ENDIF
END FUNCTION

Base case: n = 0 returns 1 [2]. General case: n × factorial(n − 1), which moves progressively closer to the base case [2].

(b) Each call is placed on the call stack with its own local variables and return address, so factorial(3) calls factorial(2), which calls factorial(1), which calls factorial(0), stacking three unfinished calls before any of them can return [2]. Without a base case, the recursion never stops adding calls to the stack, eventually exhausting available memory and causing a stack overflow [1].

10. (a) A stack is LIFO (last in, first out) — the most recently added element is removed first [1]; a queue is FIFO (first in, first out) — the earliest added element is removed first [1].

(b) Advantage: a dynamic structure grows and shrinks as the program runs, so it uses only the memory it needs and cannot overflow a fixed size [1]. Disadvantage: memory must be allocated at run time, which is slower, and the structure’s size is not known in advance, so it can grow until memory runs out [1].

---

Where marks are usually lost

• Omitting the temporary variable in a swap, which loses one of the values.
• Getting the inner loop bound wrong and reading past the end of the array.
• Stating O(n log n) for binary search.
• Forgetting that binary search requires a sorted list.
• Omitting the base case when writing a recursive function.
• Confusing a stack’s LIFO order with a queue’s FIFO order.