Problem Solving and Programming - Worksheets, Questions and Revision
10 original exam-style questions - 8 pages of questions with a full mark scheme - free printable PDF.
Problem Solving and Programming revision guideWrite-in editionMore A Level Computer Science practiceMock exams
This topic is chapter 4 of A Level Computer Science Topic Workbook 2 and chapter 12 of A Level Computer Science 10-Minute Tests.
2.2 Problem Solving and Programming
CASE OF grade
"A" : bonus <- 50
"B" : bonus <- 30
"C" : bonus <- 10
OTHERWISE : bonus <- 0CASE OF grade
"A" : bonus = 50
"B" : bonus <- 30
OTHERWISE : bonus <- 0ENDCASEIdentify the error in this code and state how to fix it.(2)
Test1 Test2 Test3 Test4
Student1: 55 62 70 48
Student2: 80 75 90 85
Student3: 40 55 60 65
total <- 0
FOR row <- 1 TO 3
FOR col <- 1 TO 4
total <- total + scores[row, col]
NEXT col
NEXT row
OUTPUT totalComplete the trace table below, showing the cumulative value of total after each row is fully processed, and state the final value output.
After row 1: total = ___
After row 2: total = ___
After row 3: total = ___(4)
PROCEDURE DoubleValue(BYREF x : INTEGER)
x <- x * 2
ENDPROCEDURE
FUNCTION AddFive(y : INTEGER) RETURNS INTEGER
y <- y + 5
RETURN y
ENDFUNCTION
num1 <- 10
num2 <- 10num2 <- AddFive(num2) OUTPUT num1 OUTPUT num2
list = [3, 8, 15, 19, 24, 31, 42, 50]
The function below performs a binary search for a target value:
FUNCTION BinarySearch(list : ARRAY[1:8] OF INTEGER, target : INTEGER) RETURNS INTEGER
lower <- 1
upper <- 8
WHILE lower <= upper
mid <- (lower + upper) DIV 2
IF list[mid] = target THEN
RETURN mid
ELSE IF list[mid] < target THEN
lower <- mid + 1
ELSE
upper <- mid - 1
ENDIF
ENDWHILE
RETURN -1
ENDFUNCTIONBinarySearch(list, 24) is called.
Start: [8, 3, 6, 1]
After pass 1: [___] , swaps = ___
After pass 2: [___] , swaps = ___
After pass 3: [___] , swaps = ___
After pass 4: [___] , swaps = ___(4)
Push(5), Push(9), Pop(), Push(3), Push(7), Pop()
Complete a trace table showing the value of top and the contents of the stack after each operation.(5)
FUNCTION Mystery(n : INTEGER) RETURNS INTEGER
IF n = 1 THEN
RETURN 1
ELSE
RETURN n * Mystery(n - 1)
ENDIF
ENDFUNCTIONQuestion 1
- (a) bonus = 30, caoB1
- (a) Answer: 30
- (b) IF grade = "A" THEN bonus <- 50M1
- (b) nested ELSE IF grade = "B" THEN bonus <- 30M1
- (b) nested ELSE IF grade = "C" THEN bonus <- 10M1
- (b) final ELSE bonus <- 0, with all IF structures correctly closed with ENDIF; any correct logic, ignore minor syntaxA1
- (b) Answer:
IF grade = "A" THEN bonus <- 50 ELSE IF grade = "B" THEN bonus <- 30 ELSE IF grade = "C" THEN bonus <- 10 ELSE bonus <- 0 ENDIF ENDIF ENDIF - (c) identifies benefit, e.g. CASE is more readable/easier to follow when testing many discrete values of the same variable, oeB1
- (c) expands the point, e.g. avoids deeply nested IF statements, which are harder to trace, maintain and debug, oeB1
- (c) Answer: CASE is clearer than deeply nested IF statements when checking several discrete values of one variable, reducing the chance of logic errors.
- (d) identifies that the "A" branch uses "=" instead of the assignment operatorB1
- (d) states the correction: bonus <- 50B1
- (d) Answer: The line "A" : bonus = 50 uses "=" (comparison) instead of "<-" (assignment); it should read "A" : bonus <- 50
Question 2
- (a) correct 2D array syntax with bounds [1:3, 1:4], oe equivalent boundsB1
- (a) correct data type OF INTEGERB1
- (a) Answer: DECLARE scores : ARRAY[1:3, 1:4] OF INTEGER
- (b) total <- 0 initialised before the loopM1
- (b) FOR col <- 1 TO 4 loopM1
- (b) total <- total + scores[2, col] inside the loop, correctly indexing row 2M1
- (b) average <- total / 4 and OUTPUT average, correct value 82.5; any correct logic, ignore minor syntaxA1
- (b) Answer:
total <- 0 FOR col <- 1 TO 4 total <- total + scores[2, col] NEXT col average <- total / 4 OUTPUT average
Output = 82.5 - (c) after row 1: total = 235B1
- (c) after row 2: total = 565B1
- (c) after row 3: total = 785B1
- (c) final OUTPUT value = 785, caoB1
- (c) Answer: 785
- (d) 90, caoB1
- (d) Answer: 90
Question 3
- (a) checks LEN(code) = 7 and sets valid to false if notM1
- (a) checks position 3 equals "-" using MID(code, 3, 1)M1
- (a) loop/checks over positions 1-2, confirming each is a letter (e.g. using ASC ranges for "A" to "Z")M1
- (a) loop/checks over positions 4-7, confirming each is a digit (e.g. using ASC ranges for "0" to "9")M1
- (a) correct use of MID to extract each character being testedM1
- (a) returns a single BOOLEAN value combining all checks correctly; any correct logic, ignore minor syntaxA1
- (a) Answer:
FUNCTION ValidateCode(code : STRING) RETURNS BOOLEAN valid <- true IF LEN(code) <> 7 THEN valid <- false ELSE IF MID(code, 3, 1) <> "-" THEN valid <- false ENDIF FOR i <- 1 TO 2 letter <- MID(code, i, 1) IF (ASC(letter) < ASC("A")) OR (ASC(letter) > ASC("Z")) THEN valid <- false ENDIF NEXT i FOR i <- 4 TO 7 digit <- MID(code, i, 1) IF (ASC(digit) < ASC("0")) OR (ASC(digit) > ASC("9")) THEN valid <- false ENDIF NEXT i ENDIF RETURN valid ENDFUNCTION - (b) "1234", caoB1
- (b) Answer: "1234"
- (c) "AB", caoB1
- (c) Answer: "AB"
- (d) validation only checks that data conforms to a set of format rules (length, character types, hyphen position), oeB1
- (d) it does not check the data represents a real/correct product, e.g. "ZZ-9999" could pass validation without being an actual issued code, oeB1
- (d) Answer: Validation checks the code's format, not whether it corresponds to a real product; a well-formatted but invented code would still pass.
Question 4
- (a) num1 = 20B1
- (a) num2 = 15B1
- (a) Answer: num1 = 20, num2 = 15
- (b) passing by reference passes the memory address/reference of the actual variable into the subroutine, oeB1
- (b) so changes made to the parameter (x <- x * 2) directly change the original variable, num1, giving 20, oeB1
- (b) passing by value copies the value of the argument into a new, separate local variable, oeB1
- (b) so changes to y inside AddFive do not directly change num2; num2 only changes because the returned value is explicitly assigned back to it, oeB1
- (b) Answer: By reference links the parameter directly to the caller's variable, so DoubleValue permanently changes num1. By value copies the data, so AddFive cannot change num2 directly; num2 is only updated because its new value is returned and reassigned.
- (c) correct FUNCTION header with a by-value parameter (no BYREF) and RETURNS INTEGERM1
- (c) correct calculation, e.g. RETURN x * 2 or result <- x * 2M1
- (c) correct RETURN statement, and the original argument is not modified since the parameter is passed by value; any correct logic, ignore minor syntaxA1
- (c) Answer:
FUNCTION DoubleValueFunc(x : INTEGER) RETURNS INTEGER RETURN x * 2 ENDFUNCTION - (d) a procedure is appropriate when the subroutine performs an action (e.g. output, or modifying data via reference parameters) and does not need to return a single value, oeB1
- (d) Answer: Procedures are used when no value needs to be returned, e.g. the subroutine only needs to perform an action or modify parameters passed by reference.
Question 5
- (a) iteration 1: lower=1, upper=8, mid=4, list[4]=19; 19<24 so lower becomes 5B1
- (a) iteration 2: lower=5, upper=8, mid=6, list[6]=31; 31>24 so upper becomes 5B1
- (a) iteration 3: lower=5, upper=5, mid=5, list[5]=24; match foundB1
- (a) correct comparison/decision applied at each step (equal / less than / greater than target)B1
- (a) final index returned = 5, caoB1
- (a) Answer: Index 5 (list[5] = 24)
- (b) 3, caoB1
- (b) Answer: 3
- (c) binary search relies on the data being sorted so that comparing the middle value with the target tells you which half to discard, oeB1
- (c) on unsorted data this less-than/greater-than comparison is not reliable, so a whole half of the array could be discarded even though it contains the target, oeB1
- (c) Answer: Binary search assumes ordering to eliminate half the search space each time; on unsorted data that assumption fails and the target could be discarded incorrectly.
- (d) O(log n)B1
- (d) explains that binary search halves the search space at each step, whereas linear search may check every item, oeB1
- (d) as n grows very large, log n grows far more slowly than n, so binary search needs far fewer comparisons in the worst case, oeB1
- (d) Answer: O(log n); it is faster than O(n) linear search for large n because each comparison eliminates half the remaining data rather than checking one item at a time.
- (e) loop through each index of the array, e.g. FOR i <- 1 TO 8M1
- (e) compares list[i] to target and returns i as soon as a match is foundM1
- (e) returns -1 after the loop completes with no match found; any correct logic, ignore minor syntaxA1
- (e) Answer:
FUNCTION LinearSearch(list : ARRAY[1:8] OF INTEGER, target : INTEGER) RETURNS INTEGER FOR i <- 1 TO 8 IF list[i] = target THEN RETURN i ENDIF NEXT i RETURN -1 ENDFUNCTION
Question 6
- (a) pass 1: [3, 6, 1, 8], swaps = 3B1
- (a) pass 2: [3, 1, 6, 8], swaps = 1B1
- (a) pass 3: [1, 3, 6, 8], swaps = 1B1
- (a) pass 4: [1, 3, 6, 8], swaps = 0 (array already sorted)B1
- (a) Answer: Sorted array: [1, 3, 6, 8]
- (b) use a boolean flag (e.g. swapped) that is reset to false at the start of each pass, oeB1
- (b) if no swaps occur during a full pass, the flag stays false, meaning the array is fully sorted, so the algorithm can stop early instead of running further unnecessary passes, oeB1
- (b) Answer: Use a flag that records whether any swap occurred in a pass; if a whole pass completes with no swaps, the array is sorted and the algorithm can terminate early.
- (c) outer loop controlled by a swapped flag, e.g. WHILE swapped = trueM1
- (c) swapped is reset to false at the start of each passM1
- (c) inner FOR loop comparing each pair of adjacent elements, e.g. FOR j <- 1 TO n - 1M1
- (c) correct swap of arr[j] and arr[j+1] using a temporary variable when arr[j] > arr[j+1]M1
- (c) swapped is set to true whenever a swap occursM1
- (c) algorithm correctly terminates once a full pass makes no swaps; any correct logic, ignore minor syntaxA1
- (c) Answer:
PROCEDURE BubbleSort(BYREF arr : ARRAY[1:n] OF INTEGER, n : INTEGER) DECLARE i, j, temp : INTEGER DECLARE swapped : BOOLEAN swapped <- true WHILE swapped = true swapped <- false FOR j <- 1 TO n - 1 IF arr[j] > arr[j + 1] THEN temp <- arr[j] arr[j] <- arr[j + 1] arr[j + 1] <- temp swapped <- true ENDIF NEXT j ENDWHILE ENDPROCEDURE - (d) O(n2)B1
- (d) Answer: O(n2)
Question 7
- (a) Push (add data)B1
- (a) Pop (remove data)B1
- (a) Answer: Push and Pop
- (b) Push(5): top=1, stack=[5]B1
- (b) Push(9): top=2, stack=[5,9]B1
- (b) Pop() returns 9: top=1, stack=[5]B1
- (b) Push(3) then Push(7): top=3, stack=[5,3,7]B1
- (b) Pop() returns 7: top=2, stack=[5,3] (final state)B1
- (b) Answer: Final state: top = 2, stack contents [5, 3]
- (c) a stack is LIFO (last in, first out), oeB1
- (c) each opening bracket is pushed onto the stack, and each closing bracket should match (pop) the most recently pushed, still-unmatched opening bracket, oeB1
- (c) if the stack is empty at the end (and never needed to pop from empty) the brackets are balanced; a queue's FIFO order would not correctly match the most recent unmatched bracket, oeB1
- (c) Answer: A stack's LIFO behaviour naturally matches each closing bracket with the most recently opened, still-unclosed bracket; a FIFO queue would match brackets in the wrong order.
- (d) any valid example, e.g. a print queue, a task/process scheduling queue, a keyboard input bufferB1
- (d) Answer: Example: a print queue, where documents are printed in the order they were sent.
Question 8
- (a) n factorial (n!), for positive integer nB1
- (a) Answer: n factorial
- (b) Mystery(4) calls Mystery(3), which calls Mystery(2), which calls Mystery(1), correctly shown in sequenceB1
- (b) Mystery(1) is the base case (n=1) and returns 1B1
- (b) Mystery(2) returns 2 * 1 = 2B1
- (b) Mystery(3) returns 3 * 2 = 6B1
- (b) Mystery(4) returns 4 * 6 = 24, caoB1
- (b) Answer: Mystery(4) = 24
- (c) the base case is n = 1, but starting from n = 0 and repeatedly subtracting 1 gives 0, -1, -2, ... which never exactly equals 1, oeB1
- (c) so the base case is never reached and the function calls itself indefinitely (infinite recursion), oeB1
- (c) each call uses memory on the call stack; because the recursion never stops, this is called a stack overflowB1
- (c) Answer: Because n decreases past 1 without ever equalling it, the base case (n=1) is never reached, causing infinite recursion and a stack overflow.
- (d) result initialised to 1 before the loopM1
- (d) FOR loop iterating from 1 to n (e.g. FOR i <- 1 TO n)M1
- (d) result <- result * i inside the loopM1
- (d) correct RETURN result after the loop; any correct logic, ignore minor syntaxA1
- (d) Answer:
FUNCTION MysteryIterative(n : INTEGER) RETURNS INTEGER result <- 1 FOR i <- 1 TO n result <- result * i NEXT i RETURN result ENDFUNCTION
Question 9
- (a) correct place values used (128,64,32,16,8,4,2,1) with correct bits identifiedM1
- (a) 10110011, caoA1
- (a) Answer: 10110011
- (b) splits into two 4-bit nibbles: 1011 and 0011M1
- (b) B3, caoA1
- (b) Answer: B3
- (c) recognises the MSB is 1, so the number is negativeM1
- (c) correctly inverts the bits and adds 1 (00010110 + 1 = 00010111), or uses correct negative place-value weightingM1
- (c) -23, caoA1
- (c) Answer: -23
- (d) 01111111 represents the largest positive value storable in 8-bit two's complement (127), oeB1
- (d) binary addition gives 10000000, but with two's complement this bit pattern represents -128, oeB1
- (d) the result of adding two positive numbers has incorrectly become negative because there are not enough bits to store the true result (128), which is overflow, oeB1
- (d) Answer: 01111111 + 00000001 = 10000000, which as two's complement represents -128, not the correct positive result (128); this incorrect sign change is overflow, caused by the result exceeding the range that 8 bits can represent.
- (e) 256 (28)B1
- (e) Answer: 256
Question 10
- (a) total and count20 initialised to 0 before the loopM1
- (a) FOR loop running exactly 10 timesM1
- (a) INPUT temp inside the loopM1
- (a) running total correctly updated (total <- total + temp)M1
- (a) correct selection test (temp > 20) and count20 incremented when trueM1
- (a) count20 correctly output after the loopM1
- (a) average correctly calculated as total / 10M1
- (a) correct test for whether the average is a whole number (e.g. total MOD 10 = 0) with an appropriate message output in both cases; any correct logic, ignore minor syntaxA1
- (a) Answer:
total <- 0 count20 <- 0 FOR i <- 1 TO 10 INPUT temp total <- total + temp IF temp > 20 THEN count20 <- count20 + 1 ENDIF NEXT i OUTPUT "Days above 20 degrees: ", count20 average <- total / 10 IF total MOD 10 = 0 THEN OUTPUT "The average is a whole number: ", average ELSE OUTPUT "The average is not a whole number: ", average ENDIF - (b) normal data: any value clearly within range, e.g. 15 (should be accepted)B1
- (b) boundary data: a value exactly on a limit, e.g. 50 or -50 (should be accepted)B1
- (b) erroneous data: a value outside the range or wrong type, e.g. 75 or "hot" (should be rejected)B1
- (b) Answer: Normal: 15. Boundary: 50 (or -50). Erroneous: 75 (or a non-numeric value such as "hot").
- (c) boundary values test the exact edges of the accepted range, which is where off-by-one errors (e.g. using < instead of ≤) are most likely to occur, oeB1
- (c) testing values exactly on the limit confirms whether the validation correctly accepts (or rejects) them as intended by the specification, oeB1
- (c) Answer: Boundary values check that the comparison operators (≤, ≥) are correct at the exact edges of the valid range, where logic errors such as excluding a valid limit value are most likely.
Mark your answers
Check answers without an account. Some answers can be checked automatically; use the mark scheme to mark the rest.