Unit 7: Data Structures
(AS Content)
Marks: /42
Answer all the questions.
1. Data structures may be described as static or dynamic.
(i) State the meaning of the term static.
[1]
(ii) State one type of data structure that is always considered to be static.
[1]
(iii) State the meaning of the term dynamic.
[1]
(iv) Give one disadvantage of using a dynamic data structure.
[1]
© OCR 2019. You may photocopy this page.
PhysicsAndMathsTutor.com
2(a). The organisers of an international football competition are planning to use a large electronic score board to
display information to spectators in the stadium. The board can display three lines of text of 15 characters each.
The program stores the text to be displayed in an array called Board, so that
Board(1,1) contains the letter in the top left corner of the display board
Board(3,15) contains the letter in the bottom right corner of the display board.
A module in the program updates the display every time the contents of this array are changed.
State the identifier, number of dimensions and most appropriate data type of the array Board.
Identifier _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
Number of dimensions _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
Most appropriate data type _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
[3]
(b). The program contains a module which clears the display using a routine to insert a space in each element of the
array using the following algorithm.
Complete this algorithm by filling in the blanks.
[3]
© OCR 2019. You may photocopy this page.
PhysicsAndMathsTutor.com
3. A stack, in shared memory, is being used to pass a single variable length ASCII string between two sub-
systems. The string is placed in the stack one character at a time in reverse order with the last byte holding the
number of characters pushed i.e. the text “SILVER” would be held in the stack as:
Use pseudocode to write a procedure that will take a text string passed to it and push it to the stack in the format
defined above. You may assume any given input will fit in the stack.
[6]
© OCR 2019. You may photocopy this page.
PhysicsAndMathsTutor.com
4(a). A program stores a queue of mathematical questions to be asked to a user. The questions are asked in the order
they are added. Once a question has been asked it cannot be asked again. New questions are continually added
to the end of the queue.
The program will use a non-circular queue, questions, (implemented using an array) to store the questions.
The pointer, head, stores the index of the first element in the queue.
The pointer, tail, stores the index of the last element in the queue.
Fig. 4.1 shows an example of the data in the queue. head is currently 0, tail is currently 4.
“2*3” “1+4” “3–1” “10/2” “3+6”
Fig. 4.1
(i) Show the contents of the queue shown in Fig. 4.1, after the following code is run.
add("6+1")
[2]
(ii) State the values stored in head and tail after the code in part (i) has run.
head
tail
[2]
© OCR 2019. You may photocopy this page.
PhysicsAndMathsTutor.com
(b). Complete the following algorithm, to ask the user to input a new question and then either add it to the queue, or
report that the queue is full.
procedure add()
maxElements = 10
endprocedure [4]
(c). Describe why a queue is a suitable structure for this program.
[3]
© OCR 2019. You may photocopy this page.
PhysicsAndMathsTutor.com
(d). Complete the following algorithm, to remove, and output, the first element in the queue.
procedure remove()
endprocedure
[4]
© OCR 2019. You may photocopy this page.
PhysicsAndMathsTutor.com
5(a). Four in a Row is a game where two players drop coloured discs into a grid, with the aim to get four of their own
colour in a row.
Each player is given a set of coloured discs, red (R) or yellow (Y). The players take it in turns to drop their disc
into a column in the grid. The disc drops down to the lowest available space in that column.
(i) * The programmer is writing a new version of the game, where each player removes one disc from the
bottom row of the grid before a new move is made.
In the example below, player R removes one disc from column 2 (Before) and places one in column 4
(After).
© OCR 2019. You may photocopy this page.
PhysicsAndMathsTutor.com
The programmer has to decide whether to continue to use a 2D array, or produce an array of queues.
Evaluate the use of a 2D array versus an array of queues to perform this action.
[9]
(ii) Explain why a stack would not be an appropriate data structure for this revised game.
[2]
END OF QUESTION PAPER
© OCR 2019. You may photocopy this page.
PhysicsAndMathsTutor.com
Question Answer/Indicative content Marks Guidance
1 i Size is fixed when structure created / size 1
cannot change during processing Examiner's Comments
These four questions were marked as a
group. These questions were good
differentiators and allowed for a clear
distinction between candidates. The more
able got four marks the majority managed
two marks.
ii array 1
iii Size can change during processing 1
iv Storage required is unknown initially / more 1
difficult to program Examiner's Comments
These four questions were marked as a
group. These questions were good
differentiators and allowed for a clear
distinction between candidates. The more
able got four marks the majority managed
two marks.
Total 4
2 a Identifier: Board / board 3 Allow suitable name
Number of dimensions: 2 Allow 2D
Most appropriate data type: Character / Do not except alphanumeric
String
Examiner's Comments
Generally well answered, the most
common error was with the dimensions
where candidates gave (3, 15) or 45 as the
answer.
b In order 3 cao
Examiner's Comments
15
Column This question was well answered with most
Row candidates gaining full marks
Total 6
© OCR 2019. You may photocopy this page.
PhysicsAndMathsTutor.com
Question Answer/Indicative content Marks Guidance
3 String length calculated (1) 6 Allow StackPtr to be used instead of i
Correct number of characters from in loop, as we would not expect them to
passed string taken ... (1) know that some compilers do not always
... in reverse order (1) increment “loop counter” when they exit
Characters placed in stack in correct loops (i.e. loop counter on exit is
order (1) undefined)
String length placed in stack at correct
point (1) Accept candidates using built-in stack
Meaningful variable names used (1) methods e.g.
(AO2.1) stack.push(word.substring(i,1))
Example program Do not penalise for syntax errors if the
logic can clearly be followed.
Max 6 mark
Examiner's Comments
Many of the same comments regarding
pseudocode as in 4b once again applied in
4d. An encouraging number of able
candidates produced quite elegant
solutions.
Total 6
© OCR 2019. You may photocopy this page.
PhysicsAndMathsTutor.com
Question Answer/Indicative content Marks Guidance
4 a i "6+1" in the correct box. [1] 2
Speech marks present [1] AO2.1
(2)
"2*3" "1+4" "3-1" "10/2" "3+6" "6+1"
Examiner's Comment:
Many candidates would have scored well
on this question if they understood that a
queue is FIFO. Those who did not
understand the basic properties of a queue
struggled with the question.
ii 1 mark for head, 1 for tail 2
head = 0 [1] AO2.1
tail = 5 [1] (2)
Examiner's Comment:
Many candidates would have scored well
on this question if they understood that a
queue is FIFO. Those who did not
understand the basic properties of a queue
struggled with the question.
© OCR 2019. You may photocopy this page.
PhysicsAndMathsTutor.com
Question Answer/Indicative content Marks Guidance
b 1 mark for pseudocode / code that meets 4
each bullet
Input a question [1] AO3.2
Check if tail is full and outputs (4)
message / reports error [1]
Increment tail [1]
Adds question to tail of questions
[1]
e.g.
Examiner's Comment:
Again, the use of pseudocode posed
problems for many candidates. Those who
had a wider programming experience were
apparent from the well-crafted solutions.
Those who gained credit generally gained
two marks for understanding how the
pointers were updated and how data was
added / removed. Fewer scored full marks
by also performing error checking.
c 1 mark per bullet to max 3 3
e.g. AO1.2
A queue is First In First Out (FIFO) [1] (2)
The questions are retrieved in the AO2.1
order they are stored [1] (1)
Questions can be added to the end [1]
Dynamic structure… [1]
…expands to take more questions [1]
Examiner's Comment:
Many candidates understood that a queue
was a FIFO structure, but fewer could then
go on to explain in context why this would
then be a suitable data structure for the
problem in context.
© OCR 2019. You may photocopy this page.
PhysicsAndMathsTutor.com
Question Answer/Indicative content Marks Guidance
d 1 mark for pseudocode/code that meets 4
each bullet
Checking if queue is empty [1] AO3.2
…outputting message/reporting (4)
error [1]
Outputting element in questions at
index head [1]
Increment head [1]
e.g.
Examiner's Comment:
Again, the use of pseudocode posed
problems for many candidates. Those who
had a wider programming experience were
apparent from the well-crafted solutions.
Those who gained credit generally gained
two marks for understanding how the
pointers were updated and how data was
added/removed. Fewer scored full marks
by also performing error checking.
Total 15
© OCR 2019. You may photocopy this page.
PhysicsAndMathsTutor.com
Question Answer/Indicative content Marks Guidance
5 i Mark Band 3 – High level 9 AO1: Knowledge and Understanding
(7–9 marks) Indicative content
The candidate demonstrates a thorough
knowledge and understanding of queues Arrays are static (size cannot change)
and arrays; the material is generally Queues are dynamic (size can change)
accurate and detailed. Queues use pointers to identify the first
The candidate is able to apply their element (to be removed)
knowledge and understanding directly and
consistently to the context provided. AO2: Application
Evidence / examples will be explicitly
relevant to the explanation. Array will need all elements to be
There is a well-developed line of reasoning moved ‘down 1’ each time a disc is
which is clear and logically structured. The removed
information presented is relevant and Queue will allow the front element to
substantiated. be taken out and then the pointer will
move
Mark Band 2 – Mid level Algorithms for queues can be more
(4–6 marks) complex, especially as the language
The candidate demonstrates reasonable may use an array to implement the
knoledge and understanding of queues queue
and arrays; the material is generally
accurate but at times underdeveloped. AO3: Evaluation
The candidate is able to apply their Candidates will need to evaluate the
knowledge and understanding directly to benefits and drawbacks of using queues
the context provided although one or two and arrays and suggest an appropriate
opportunities are missed. Evidence / solution
examples are for the most part implicitly e.g.
relevant to the explanation.
The candidate provides a reasonable Size does not need to change (Static is
discussion, the majority of which is needed as grid is fixed size) so that
focused. Evaluative comments are, for the benefit of queues is not necessary
most part appropriate, although one or two Programmer has already written a
opportunities for development are missed. program using arrays, may be less
There is a line of reasoning presented with time consuming to edit it for arrays
some structure. The information presented Language may need a queue to be
is in the most part relevant and supported programmed in an array, therefore an
by some evidence. array may be more straight forward to
use
Mark Band 1 – Low Level Queue does not need to move all
(1–3 marks) elements each time a counter is
The candidate demonstrates a basic removed, only pointers change
knowledge of queues and arrays with
limited understanding shown; the material
is basic and contains some inaccuracies.
The candidates makes a limited attempt to
apply acquired knowledge and
understanding to the context provided.
The candidate provides a limited
discussion which is narrow in focus.
© OCR 2019. You may photocopy this page.
PhysicsAndMathsTutor.com
Question Answer/Indicative content Marks Guidance
Judgements if made are weak and
unsubstantiated.
The information is basic and comunicated
in an unstructured way. The information is
supported by limited evidence and the
relationship to the evidence may not be
clear.
0 marks
No attempt to answer the question or
response is not worthy of credit.
ii Max 2 2
Stack is last-in-first-out (1)
This game the first-in needs to be first-
out (1)
Total 11
© OCR 2019. You may photocopy this page.
PhysicsAndMathsTutor.com
