A-LevelComputer ScienceData types and structures9618/42 · May/June 2022 · Q125 Marks

A program needs to use a stack data structure. The stack can store up to 10 integer elements. A 1D array StackData is used to store the stack globally. The global variable StackPointer points to the next available space in the stack and is initialised to 0.

(a)Write program code to declare the array and pointer as global data structures. Initialise the pointer to 0.[3]
(b)Write a procedure to output all 10 elements in the stack and the value of StackPointer.[3]
(c)The function Push() takes an integer parameter and returns FALSE if the stack is full. If the stack is not full, it puts the parameter value on the stack, updates the relevant pointer and returns TRUE. Write program code for the function Push().[6]
(d)(i)Edit the main program to test the Push() function. The main program needs to: • allow the user to enter 11 numbers and attempt to add these to the stack • output an appropriate message when a number is added to the stack • output an appropriate message when a number is not added to the stack if it is full • output the contents of the stack after attempting to add all 11 numbers.[5]
(d)(ii)Test your program from part 1(d)(i) with the following 11 inputs: 11 12 13 14 15 16 17 18 19 20 21 Take a screenshot to show the output.[1]
(e)(i)The function Pop() returns -1 if the stack is empty. If the stack is not empty, it returns the element at the top of the stack and updates the relevant pointer. Write program code for the function Pop().[5]
(e)(ii)After the code you wrote in the main program for part 1(d)(i), add program code to: • remove two elements from the stack using Pop () • output the updated contents of the stack. Test your program and take a screenshot to show the output.[2]

Mark scheme

Marking points from the official mark scheme (May/June 2022). The mark or mark type is shown in brackets.

[3] 1 mark per mark point • declaring array StackData and pointer StackPointer as (global data structures) • StackData has 10 integer elements • StackPointer initialised to 0
[3] 1 mark per mark point • procedure header with sensible identifier (and end where appropriate) • outputting StackPointer • outputting all 10 elements in array
[6] 1 mark per mark point • function Push () taking an integer parameter • checking if stack is full ... • ...and returning FALSE • (if not full) storing parameter to stack at StackPointer ... • ...incrementing StackPointer • ...returning TRUE
[5] 1 mark per mark point • Inputting 11 numbers ... • ...calling Push () with each number input as a parameter ... • .outputting appropriate message if TRUE returned • .outputting appropriate message if FALSE returned • Calling their output procedure after all 11 additions
[1] 1 mark for inputting all 11 numbers, message for first 10 saying added (11 to 20), message stating 11th number stating stack full. Full array contents output (11 12 13 14 15 16 17 18 19 20). e.g.
[5] 1 mark per mark point • Pop () function header (and close where appropriate) and returning a number in all possible situations • checking if stack is empty (StackPointer is 0) and returning -1 • (otherwise) accessing the item at the top of the stack ... • ...decrementing the stack pointer • .returning the item removed
[2] 1 mark per mark point • output of before removed with 11 inputs • output of stack (after, this could be 11–20, 11–18, or 11–18 then 'null' 'null's) e.g.