OCR A-Level Computer Science Algorithms and programming (02), June 2025: Question 3

17 marks · Medium difficulty · Algorithm / Pseudo-code

Demonstrate the operation of a stack, complete a push function, write a pop function, and write an algorithm using the stack to reverse 10 user-input characters.

Practise this question

Question

Question text

3 A program is designed to use a stack data structure.

The current contents of part of the stack and its current pointer value are shown:

2 "I"

1 "n"

0 "k"

pointer = 2

(a) Show the contents of the stack and its pointer value after the data items "t" and "s" are inserted in

the order given.

pointer = …

[2]

(b) The stack is stored using a 0-based 1-dimensional array called theStack with 20 elements.

The function push() stores its parameter into the next space in the stack if it is not full. The

function returns true if it is successfully stored and returns false if the stack is full.

Complete the function push() using pseudocode or program code.

function push(data)

if pointer == … then

return false

else

pointer = …

theStack[pointer] = …

endif

endfunction

[4]

The function pop() returns the next element in the stack. If the stack is empty it returns

"false". The function updates the pointer value when appropriate.

Write the function pop() using pseudocode or program code.

… [6]

(d) A program is designed to reverse a set of data using the stack.

The main program takes 10 characters separately as input from the user and uses the function

push() to insert these into the stack.

Once all 10 characters have been inserted into the stack, the program then uses the function

pop() to output all 10 characters from the stack.

Write the main program to achieve this using pseudocode or program code.

… [5]

Mark scheme

Show the mark scheme

3 (a) 1 mark for stack contents 2 Allow the absence of quotation marks around the

1 mark for pointer value values in the stack

Allow I or L if difficult to determine letter/case etc.

"s"

"t"

"I"

"n"

"k"

pointer = 4

3 (b) 1 mark for each completed statement to max 4 4 Allow len(theStack) – 1 or

theStack.length – 1 as equivalent to 19

function push(data)

if pointer == 19 then

return false

else

pointer = pointer + 1

theStack[pointer] = data

return true

endif

endfunction

3 (c) 1 mark each to max 6 12 6 BP1 ignore any parameters

• Function pop() declaration Allow equivalent check in BP2

• Checking if stack is empty … e.g. if pointer < 0

• …and returning "false"

• (otherwise) accessing the data at pointer BP3 is strictly dependent on MP2 being met

• Decrementing pointer before returning

• Returning the data accessed BP3 allow Boolean false instead of string "false"

e.g. Allow BP4 and BP5 to be in the opposite order

with appropriate logic.

function pop()

BP4 and BP6 can be combined

if pointer == -1

return "false" Allow reversal of logic and other equivalent

solutions e.g.

else

dataToReturn = theStack[pointer] function pop()

if pointer > -1

pointer = pointer – 1

pointer = pointer - 1

return dataToReturn return theStack[pointer+1]

endif else

return "false"

endfunction endif

endfunction

3 (d) 1 mark each to max 5 5 Award follow through if incorrect number of items

input/output

• Loop 10 times…

• …to take inputs… Loop constructs must be valid for MP2 i.e. a fully

• …calling push() with each value input working for or while loop or equivalent. If Python

• Calling pop() for each pushed value… syntax is used it must be clear that a for loop

• …and outputting each value in the correct order executes 10 times e.g. for i in range(0,10)

e.g.

for count = 0 to 9

push(input("Enter a string"))

next count

for count = 0 to 9

print(pop())

next count

How to answer it

Stack Data Structure: Implementation & Reversal Algorithm

What this question tests

This question assesses your understanding of the LIFO (Last In, First Out) Stack abstract data type implemented via a static 1D array. You are evaluated on: tracing pushes and pointer updates, handling boundary conditions (stack overflow and stack underflow), writing complete functions in pseudocode, and applying stack operations to solve a real-world problem (reversing a sequence).

Part (a) Tracing Stack Insertion & Pointer Updates

2 Marks

✅ Correct Answer

Insert "t" then "s":

5
4	"s"
3	"t"
2	"l"
1	"n"
0	"k"

pointer = 4

💡 Key Knowledge

A stack pointer points to the top item currently in the stack (here, 0-indexed).
When pushing, increment the pointer first, then store the item at that new index:
• Push "t": pointer becomes 3, store at index 3.
• Push "s": pointer becomes 4, store at index 4.

❌ Common Errors

Reversing insertion order (putting "s" at 3 and "t" at 4).
Leaving the pointer at 2 or writing 5 (pointing to next free space instead of current top).

🧠 Exam Technique

The mark scheme allows missing quotation marks around characters (e.g. writing s instead of "s" ), but always write them explicitly to be safe and accurate!

Mark Allocation:
• [1 mark] Correct stack contents with "t" at index 3 and "s" at index 4.
• [1 mark] Correct pointer value: pointer = 4 .

Part (b) Completing the push() Function

4 Marks

✅ Completed Code

function push(data) if pointer == 19 then return false else pointer = pointer + 1 theStack[pointer] = data return true endif endfunction

💡 Boundary Analysis (0-indexed Array)

The array has 20 elements, with indices 0 to 19 .

If pointer == 19 , the stack is full (stack overflow). Pushing another item is impossible, so it must return false .
Equivalents accepted: len(theStack) - 1 or theStack.length - 1 .

❌ Common Errors

Checking if pointer == 20 : This causes an Index Out of Range error on the next push when pointer increments to 20!
Forgetting to return true after successful insertion.
Assigning theStack[pointer] = "data" as a string literal instead of using the parameter data .

Mark Allocation:
• [1 mark] Overflow check condition ( 19 or equivalent).
• [1 mark] Increment pointer statement ( pointer + 1 ).
• [1 mark] Assign incoming argument ( data ) to theStack[pointer] .
• [1 mark] Returning success ( return true ).

Part (c) Writing the pop() Function

6 Marks

✅ Correct Implementation (Standard Approach)

function pop() if pointer == -1 then return "false" else dataToReturn = theStack[pointer] pointer = pointer - 1 return dataToReturn endif endfunction

🧠 Exam Technique: The Temporary Variable Trap

Notice the order of operations in the else branch:

Store element at current top into dataToReturn .
Decrement pointer ( pointer = pointer - 1 ).
Return dataToReturn .

If you decrement pointer first without saving the element, you will access the wrong index!

💡 Alternative Valid Logic

function pop() if pointer > -1 then pointer = pointer - 1 return theStack[pointer + 1] else return "false" endif endfunction

Decreasing first and returning theStack[pointer + 1] avoids needing a temporary variable and is awarded full marks.

❌ Pitfalls Examiner Notes

Underflow condition: Must check pointer == -1 or pointer < 0 . Checking pointer == 0 is wrong because index 0 holds a valid stack element!
Return string vs boolean: The prompt specified returning "false" . The mark scheme does allow Boolean false , but always follow stated types where possible.

Mark Allocation (1 mark each to max 6):
1. Function header/declaration ( function pop() ).
2. Checking if stack is empty ( pointer == -1 or < 0 ).
3. Returning "false" (strictly dependent on an empty check).
4. Accessing data at pointer position.
5. Decrementing pointer before returning.
6. Returning the accessed data item.

Part (d) Reversing 10 Characters Using the Stack

5 Marks

✅ Full Program Code

for count = 1 to 10 char = input("Enter a character: ") push(char) next count for count = 1 to 10 print(pop()) next count

Equivalent Python syntax accepted: for i in range(10): push(input()) followed by for i in range(10): print(pop()) .

💡 Why Stacks Naturally Reverse Data

Because stacks are LIFO (Last In, First Out):

The 1st item entered is at the bottom (index 0).
The 10th item entered is at the top (index 9).
Calling pop() retrieves items starting from the 10th down to the 1st, perfectly reversing the order.

❌ Common Errors

Interleaving push and pop: Putting pop() inside the same loop as push() . The characters must all be pushed first before popping starts.
Off-by-one loops: Writing for i in range(1, 10) in Python only runs 9 times, losing the loop mark.
Direct array manipulation: Writing to theStack[] directly instead of calling the required abstract methods push() and pop() .

Mark Allocation (1 mark each to max 5):
• [1 mark] Loop executing exactly 10 times for input.
• [1 mark] Taking user input inside the loop.
• [1 mark] Calling push() with each inputted value.
• [1 mark] Calling pop() for each pushed value (in a separate 10-iteration loop or equivalent).
• [1 mark] Outputting/printing each popped value in the correct reversed sequence.

Topics

1.4 Data types, data structures and algorithms · 2.2 Problem solving and programming · 2.3 Algorithms · 1.4.2 Data Structures · 2.2.1 Programming techniques · 2.3.1 Algorithms

Question and mark scheme from the OCR A-Level Computer Science examination, Algorithms and programming (02), June 2025. QuestionVault is an independent revision resource; questions remain the copyright of the awarding body.