References only, not question text. Open Official paper ↗ where Cambridge publishes the paper,
or see the official Cambridge past-papers page; for other papers, ask your
school. “Paper 42” means Paper 4, variant 2.
Practice questions
Original questions written by HomiLabs in the style of the exam, with answers and mark schemes. They are not
Cambridge past paper questions and have not been reviewed by Cambridge. Try each one before opening the answer.
Q1BNF & syntax diagrams · Core · Paper 3 style · 6 marks
A set of rules in Backus-Naur Form (BNF) is:<digit> ::= 0|1|2|3|4|5|6|7|8|9<letter> ::= A|B|C|D|E<code> ::= <letter><letter><digit> | <letter><digit><digit>
(a)For each string, state whether it is a valid <code> and give a reason if it is not.(i) AB7 (ii) C99 (iii) AF3 (iv) B5[4]
(b)Write a new rule <longcode> that is a <code> followed by one or two <digit>s.[2]
Show answer
(a) (i) Valid (ii) Valid (iii) Invalid – F is not a <letter> (only A to E). (iv) Invalid – only two characters; a <code> needs three.
B1: uses <code> followed by <digit>; B1: both alternatives separated by |.
Q2BNF & syntax diagrams · Core · Paper 3 style · 5 marks
(a)State the meaning of each symbol used in BNF.(i) ::=(ii) |(iii) < > around a word[3]
(b)Explain why the syntax of a programming language is defined using a formal notation such as BNF or syntax diagrams.[2]
Show answer
(a) (i) 'is defined as' (ii) 'or' – separates alternatives (iii) encloses a non-terminal (a syntactic element defined by another rule)
1 mark each.
(b) It gives a precise, unambiguous definition of which statements are valid, so the compiler writer can build the syntax analyser from it and programmers know exactly what is allowed.
1 mark each: unambiguous / precise definition of the grammar; used by the compiler in syntax analysis / to check statements are valid.
Q3BNF & syntax diagrams · Standard · Paper 3 style · 5 marks
The following BNF rules define an integer:<digit> ::= 0|1|2|3|4|5|6|7|8|9<integer> ::= <digit> | <digit><integer>
(a)Explain why the rule for <integer> is recursive and why recursion is needed here.[2]
(b)Write a BNF rule for <signed> which is an <integer> with an optional + or − sign in front.[2]
(c)Write a BNF rule for <decimal> which is a <signed> followed by a decimal point and then an <integer>, for example −12.05.[1]
Show answer
(a) <integer> is defined in terms of itself (<digit><integer>); this allows an integer of any number of digits to be defined with a single finite rule.
1 mark each: rule refers to itself; allows unlimited / any length of digits.
B1: three alternatives; B1: correct use of <integer> and the signs.
(c) <decimal> ::= <signed>.<integer>
B1.
Q4BNF & syntax diagrams · Standard · Paper 3 style · 6 marks
In a small scripting language, an identifier must start with a letter. It can then be followed by any number of letters, digits or underscore (_) characters.
(a)Write BNF rules to define an <identifier> for this language. You may use <letter> and <digit>, which are already defined.[3]
(b)State whether each of the following is a valid <identifier>.(i) score_2 (ii) 2ndPlace (iii) total[3]
B1: <char> (or equivalent) defined with letter, digit and underscore; B1: identifier begins with a <letter> (base case); B1: recursion allowing any number of further characters.
(b) (i) Valid (ii) Invalid – starts with a digit (iii) Valid
1 mark each.
Q5BNF & syntax diagrams · Standard · Paper 3 style · 5 marks
A syntax diagram for <pin> is described as follows.• The path enters a box labelled <symbol>.• It then enters a box labelled <digit>.• After <digit> there is a loop that can return to the start of the <digit> box any number of times, or the path can leave to the end.A second syntax diagram shows <symbol> as a choice between two terminals: # and *.
(a)Write the BNF rules that are equivalent to the syntax diagrams. You may use <digit>, which is already defined.[4]
(b)Explain why the string ##42 is not a valid <pin>.[1]
(a)For each statement, state whether it is a valid <assignment>. If it is invalid, give the reason.(i) X=Y+3(ii) Z=4*X-Y(iii) 3=X+Y(iv) Y=X+(v) X=12[5]
(b)Modify the rule for <operand> so that it can be a <variable> or an integer of one or more digits. You may define a new rule.[2]
Show answer
(a) (i) Valid (ii) Valid (iii) Invalid – the left side must be a <variable>. (iv) Invalid – an <operator> must be followed by an <expression>. (v) Invalid – an <operand> can only be a single digit.
(c) The parser checks that the sequence of tokens produced by lexical analysis matches the grammar rules (e.g. builds a parse tree); if a statement cannot be derived from the rules, a syntax error is reported.
1 mark each: tokens checked against the grammar / BNF rules; error reported when they do not match / parse tree built.
Q8BNF & syntax diagrams · Challenge · Paper 3 style · 8 marks
A warehouse in Karachi uses product codes that have:• two upper-case letters, then• a hyphen '-', then• a whole number that does not start with 0 (one or more digits), then• optionally, the letter X at the end.For example: KH-7, PK-3005X.
(a)Write BNF rules to define a <product> code. You may use <letter> (any upper-case letter A–Z) and <digit> (0–9), which are already defined.[5]
(b)State whether each code is valid and, if not, why.(i) KH-0123 (ii) PK-7X (iii) LH-45XX[3]
1 mark each: <nonzero> defined; recursive rule for any number of digits; number starts with a non-zero digit; two letters then hyphen; optional X suffix shown as an alternative.
(b) (i) Invalid – the number starts with 0. (ii) Valid. (iii) Invalid – only one X is allowed at the end.
1 mark each.
Q9BNF & syntax diagrams · Challenge · Paper 3 style · 7 marks
An email system for a university in Lahore only accepts addresses in this form:• a username of one or more lower-case letters, then• '@', then• a domain of one or more lower-case letters, then• '.', then• the ending pk or com.For example, sana@nuhs.pk.
(a)Write BNF rules for <address>. You may use <lower>, which is any single lower-case letter a–z.[4]
(b)The format is extended so that the part after @ may contain several words separated by dots before the ending, for example sana@mail.uni.edu.pk. Write the new or changed rules.[3]
M1: operands pushed in order; M1: + pops 3 and 2 and pushes 5; M1: * gives 30, 4 pushed; A1: − gives 26 (30 − 4, correct order).
(b) 6 * (2 + 3) − 4
B1.
Q13Reverse Polish notation · Standard · Paper 3 style · 4 marks
(a)Convert each RPN expression into infix form, using brackets only where they are needed.(i) a b c * + d /(ii) x y z + * w −[4]
Show answer
(a) (i) (a + b * c) / d (ii) x * (y + z) − w
2 marks each: B1 correct operands/operators, B1 brackets in the right place.
Q14Reverse Polish notation · Standard · Paper 3 style · 6 marks
(a)Give two reasons why compilers and interpreters convert arithmetic expressions into RPN.[2]
(b)Describe how a stack is used to evaluate an expression in RPN.[4]
Show answer
(a) No brackets are needed; operator precedence does not have to be considered during evaluation; the expression can be evaluated in a single left-to-right pass using a stack.
1 mark each for any two.
(b) The expression is read from left to right. Each operand is pushed onto the stack. When an operator is read, the top two items are popped, the operator is applied (second popped item operator first popped item), and the result is pushed back. At the end, the single item left on the stack is the result.
1 mark each: read left to right; operands pushed; operator pops two items and pushes result; order of operands (e.g. for − and /); final value on stack is the answer.
Q15Reverse Polish notation · Standard · Paper 3 style · 5 marks
(a)Show the contents of the stack after each symbol of w x y * z − + is processed, when w = 4, x = 5, y = 6 and z = 10, and state the result.[4]
Q16Reverse Polish notation · Standard · Paper 3 style · 5 marks
A binary expression tree has root node *.• The left child of * is +, whose children are a (left) and b (right).• The right child of * is −, whose left child is c and whose right child is /.• The children of / are d (left) and e (right).
(a)Write the RPN form of the expression represented by the tree.[2]
(b)Write the infix form of the expression.[2]
(c)Name the tree traversal that produces RPN.[1]
Show answer
(a) a b + c d e / − *
M1: post-order traversal used; A1: correct.
(b) (a + b) * (c − d / e)
B1 each bracketed part correct.
(c) Post-order traversal
B1.
Q17Reverse Polish notation · Challenge · Paper 3 style · 7 marks
(a)Convert the infix expression a − b / (c + d) * e into RPN.[2]
(b)Evaluate your RPN expression when a = 20, b = 12, c = 1, d = 2 and e = 3. Show the stack after each step.[4]
(c)State the maximum number of items on the stack during the evaluation.[1]
Q19Process scheduling & interrupts · Core · Paper 3 style · 4 marks
(a)Name the three process states.[1]
(b)Describe the conditions that cause a process to move:(i) from running to ready(ii) from running to blocked(iii) from blocked to ready[3]
Show answer
(a) Running, ready, blocked (waiting)
B1: all three.
(b) (i) Its time slice ends or a higher-priority process needs the processor (it is pre-empted). (ii) It must wait for an event such as input/output to finish. (iii) The event it was waiting for (e.g. the I/O) has completed.
1 mark each.
Q20Process scheduling & interrupts · Standard · Paper 3 style · 6 marks
Four processes all arrive at time 0 and need the following processor (burst) times: P1 8 ms, P2 4 ms, P3 9 ms, P4 5 ms.
(a)Calculate the average waiting time if the processes are run in the order P1, P2, P3, P4 using first come first served (FCFS).[2]
(b)Calculate the average waiting time using shortest job first (SJF).[2]
M1: order P2, P4, P1, P3 with waits 0, 4, 9, 17; A1: 30 ÷ 4 = 7.5 ms.
(c) Long processes may wait a very long time (starvation) if short jobs keep arriving; also the burst time must be known or estimated in advance.
1 mark point, 1 mark explanation.
Q21Process scheduling & interrupts · Standard · Paper 3 style · 7 marks
Three processes, A (7 ms), B (4 ms) and C (2 ms), arrive at time 0 in the order A, B, C. They are scheduled using round robin with a time slice (quantum) of 3 ms. Ignore the time taken to switch processes.
(a)Give the order in which the processes use the processor, with the start and end time of each time slice.[3]
(b)State the time at which each process finishes, and calculate the average waiting time. Give your answer to 2 decimal places.[3]
(c)Explain why round robin is suitable for an interactive system with many users.[1]
Show answer
(a) A 0–3, B 3–6, C 6–8, A 8–11, B 11–12, A 12–13
M1: first round A, B, C; M1: C finishes at 8 (only 2 ms needed); A1: correct remaining slices.
(b) A 13 ms, B 12 ms, C 8 ms; average waiting time 6.67 ms
B1: finish times; M1: waits A 6, B 8, C 6 (finish − burst); A1: 20 ÷ 3 = 6.67 ms.
(c) Every process gets a share of processor time regularly, so no user waits long for a response.
B1.
Q22Process scheduling & interrupts · Standard · Paper 3 style · 6 marks
(a)Describe what happens when an interrupt is received by the processor.[4]
(b)Explain how the kernel acts as an interrupt handler in a multitasking system.[2]
Show answer
(a) At the end of the current fetch-execute cycle the processor checks for interrupts. If the interrupt has a higher priority than the current task, the contents of the registers (PC and others) are saved, e.g. on a stack / in the process control block. The kernel identifies the source and calls the matching interrupt service routine (ISR). When the ISR finishes, the saved register contents are restored and the interrupted process continues (or the scheduler picks another process).
1 mark each, max 4: checked at end of F-E cycle; priority compared; registers/context saved; ISR identified and executed; context restored / process resumes.
(b) The kernel receives every interrupt, including timer interrupts that mark the end of a time slice; it saves the current process's state and passes control to the scheduler or the correct ISR, then resumes a process.
1 mark each: kernel handles all interrupts (e.g. timer interrupt for time slicing); saves state and transfers control to scheduler/ISR.
Q23Process scheduling & interrupts · Standard · Paper 3 style · 4 marks
(a)Explain why an operating system uses process scheduling.[3]
(b)State the purpose of the low-level scheduler.[1]
Show answer
(a) To allow multitasking, so several processes appear to run at the same time; to keep the processor as busy as possible (for example running another process while one waits for I/O); to share processor time fairly and give each user an acceptable response time; to make sure higher-priority processes are dealt with first.
1 mark each, max 3.
(b) It decides which process in the ready state is moved into the running state (given the processor) next.
B1.
Q24Process scheduling & interrupts · Challenge · Paper 3 style · 6 marks
A process table shows four processes:Process | Arrival time (ms) | Burst time (ms)P1 | 0 | 7P2 | 2 | 4P3 | 4 | 1P4 | 5 | 4Ignore the time taken to switch between processes.
(a)Using shortest remaining time (SRT) scheduling, give the order in which the processes run, with start and end times.[4]
Q25Process scheduling & interrupts · Challenge · Paper 3 style · 6 marks
(a)Explain the difference between pre-emptive and non-pre-emptive scheduling.[2]
(b)Classify each of FCFS, round robin, SJF and SRT as pre-emptive or non-pre-emptive.[2]
(c)A hospital monitoring system in Islamabad runs one process that reads patient heart-rate sensors and several less urgent processes. Explain which kind of scheduling should be used.[2]
Show answer
(a) Pre-emptive: the OS can stop a running process (e.g. when its time slice ends or a higher-priority process arrives) and move it to the ready state. Non-pre-emptive: once a process has the processor, it keeps it until it finishes or blocks.
(c) Pre-emptive (priority-based) scheduling, so the sensor process can interrupt less urgent processes immediately when it needs the processor; a delay in reacting to a heart-rate alarm could be dangerous.
1 mark: pre-emptive with priority; 1 mark: justification in context.
Q26Compilation stages · Core · Paper 3 style · 5 marks
(a)Describe what happens during lexical analysis.[3]
(b)State two items of information about an identifier that are stored in the symbol table.[2]
Show answer
(a) Comments and unnecessary white space are removed; the source code is split into tokens (keywords, identifiers, operators, literals); keywords and operators are replaced by token codes; identifiers are entered into the symbol table; some errors (e.g. invalid identifiers) are reported.
1 mark each, max 3.
(b) Any two of: its name, data type, scope (local/global), memory address / location, whether it is a variable, constant or procedure, its value for a constant.
1 mark each.
Q27Compilation stages · Standard · Paper 3 style · 5 marks
A compiler is about to generate code for this fragment:FOR Index ← 1 TO 1000 Rate ← 0.17 Temp ← Price[Index] + 1 Tax[Index] ← Price[Index] * RateNEXT IndexOUTPUT Price[1000] * RateTemp is not used anywhere else in the program.
(a)Rewrite the code in an optimised form that produces the same result.[3]
(b)State two benefits of code optimisation.[2]
Show answer
(a)Rate ← 0.17FOR Index ← 1 TO 1000 Tax[Index] ← Price[Index] * RateNEXT IndexOUTPUT Price[1000] * Rate
M1: assignment Rate ← 0.17 moved out of the loop (loop-invariant code); M1: the unused assignment Temp ← Price[Index] + 1 removed; A1: rest of code unchanged so the result is the same (accept OUTPUT Tax[1000], which reuses the value already calculated).
(b) The program runs faster (fewer instructions executed); it uses less memory / produces smaller object code.
1 mark each.
Q28Compilation stages · Challenge · Paper 3 style · 7 marks
A compiler translates the statement:Total ← Total + Price * 2
(a)State the number of tokens in the statement and list them.[2]
(b)Describe what happens to this statement during syntax analysis.[3]
(c)Describe what happens during code generation.[2]
Show answer
(a) 7 tokens: Total, ←, Total, +, Price, *, 2
B1: 7; B1: list correct.
(b) The parser checks the sequence of tokens against the grammar rules of the language (e.g. defined in BNF); it builds a parse tree showing that * is applied before +; if the statement does not match the rules, a syntax error is reported. The expression may also be converted to RPN, e.g. Total Price 2 * +.
1 mark each, max 3: tokens checked against grammar; parse tree; precedence shown; errors reported; conversion to RPN with correct form.
(c) The compiler produces object (machine) code for the statement, e.g. loading Price, multiplying by 2, adding Total and storing the result in Total, using the memory addresses held in the symbol table.
1 mark each: object/machine code produced; uses addresses from symbol table / sequence of instructions for the operations.
Q29Memory management & virtual memory · Standard · Paper 3 style · 6 marks
(a)Explain the difference between paging and segmentation.[3]
(b)Describe how virtual memory allows a program larger than the available RAM to run.[3]
Show answer
(a) In paging, memory is divided into fixed-size blocks: processes are split into pages that are all the same size, which are placed into page frames of the same size. In segmentation, a process is divided into logical segments (e.g. a procedure or a data area) of different sizes. Paging is a physical division set by the OS; segmentation follows the logical structure of the program.
1 mark each, max 3: pages fixed size, matched to page frames; segments variable size; segments based on logical units of the program; page table / segment map table used to translate addresses.
(b) Part of secondary storage is used as if it were main memory. Only the pages of the program currently needed are kept in RAM; other pages are stored on disk. When a page that is not in RAM is needed, a page fault occurs and the page is swapped in, replacing a page that is copied out to disk.
1 mark each, max 3: secondary storage used as extension of RAM; only needed pages in RAM; pages swapped in/out as needed; page table records where each page is.
Q30Memory management & virtual memory · Challenge · Paper 3 style · 8 marks
A computer has 3 page frames available for a process, all empty at the start. The process requests pages in this order:7, 2, 3, 7, 4, 2, 5, 7, 2
(a)Show the contents of the frames after each page request using first-in first-out (FIFO) page replacement, and state the total number of page faults.[4]
(b)Explain what is meant by disk thrashing and why it happens.[3]
M1: first three requests fill frames; M1: correct replacements of the oldest page; M1: hits identified at the 4th and 6th requests; A1: 7 faults.
(b) Disk thrashing is when the computer spends more time swapping pages between RAM and disk than executing processes. It happens when too many processes are running or RAM is too small, so pages are swapped out and almost immediately needed again; the disk is constantly busy and performance falls sharply.
1 mark each: excessive swapping of pages in and out; pages swapped out are soon needed again; little useful processing done / performance drops (high disk activity).
(c) Install more RAM, or run fewer programs at the same time (reduce the number of active processes).
B1.
Similar questions
Questions that test the same subtopic in different years, grouped so you can work on one skill at a time.
References only: find each question in its paper (official link where available, otherwise through your school).
