1.4.2 Data Structures Exam Questions
Paper 1 · Computer Systems · 21 past paper questions · 60 marks
Exam questions for 1.4.2 Data structures
21 OCR past paper questions (60 marks) with mark schemes
Answer each question, reveal the mark scheme, then award yourself marks. Scores and answers are saved in this browser so you can see which topics need more work.
Download Questions & Mark Scheme (PDF)Past paper questions
- Question 1H446/01 · June 20242 marks
Fig. 8 shows a binary search tree that contains the names of different towns in Ireland. The binary search tree is held in a 2-dimensional array called towns with 8 rows and 3 columns. Write a line of program code or pseudocode to declare the array towns.
Fig. 8 Show mark scheme
array towns(8,3) or string towns[][] = new string [8][3] or array towns [8][3] as string (2 marks - 1 for array type, 1 for correct dimensions)Mark yourself: how many marks did you get?/ 2 - Question 2H446/01 · June 20244 marks
Fig. 8 shows a binary search tree that contains the names of different towns in Ireland. The binary search tree is held in a 2-dimensional array called towns with 8 rows and 3 columns. In the 2-dimensional array towns: • the first column contains a pointer to the left side • the second column contains the data • the third column contains a pointer to the right side. Leaf nodes have the pointer null. Complete the table showing the contents of the towns array to store the binary search tree shown in Fig. 8.
Fig. 8 Left Data Right 0 Sligo 1 Dublin 2 Cork 3 Waterford 4 Galway 5 Limerick 6 Tralee 7 Dundalk Show mark scheme
1 mark for each pair of rows completed correctly (rows 0 and 1, rows 2 and 3, rows 4 and 5, rows 6 and 7). Allow -1 or Ø for null. Follow through if 0 or a blank is used as null after the first error. (4 marks)Left Data Right 0 1 Sligo 3 1 2 Dublin 4 2 null Cork null 3 6 Waterford null 4 7 Galway 5 5 null Limerick null 6 null Tralee null 7 null Dundalk null Mark yourself: how many marks did you get?/ 4 - Question 3H446/01 · June 20232 marks
Describe one difference between a stack and a queue.
Show mark scheme
Stack is LIFO/FILO, Queue is FIFO/LILO Stack uses one pointer (for head), Queue uses two pointers (head and tail) Stack data popped/pushed from top, Queue data dequeued from front and enqueued to back (2 marks - mark in pairs)Mark yourself: how many marks did you get?/ 2 - Question 4H446/01 · June 20232 marks
Describe one difference between an array and a list.
Show mark scheme
Array is of fixed/defined size/static, List size can be changed/dynamic Array holds data of single data type, List can hold data of multiple/different types (2 marks - 1 per bullet)Mark yourself: how many marks did you get?/ 2 - Question 5H446/01 · June 20231 mark
State how a tuple is different to a list.
Show mark scheme
A tuple cannot be changed at runtime / a tuple is immutable (1 mark)Mark yourself: how many marks did you get?/ 1 - Question 6H446/01 · June 20233 marks
Describe how the second item in a linked list would be accessed using pointer values.
Show mark scheme
Go to the first position indicated by the start pointer From the first position, read the next pointer value Follow this pointer value and access the data item (3 marks - 1 per bullet)Mark yourself: how many marks did you get?/ 3 - Question 7H446/014 marks
Describe how an array can be used to store and access data in a stack data structure.
Show mark scheme
(Stack) Pointer points to the last element added/top of stack New data is added to the pointer position, check for overflow Pointer is then incremented Data is removed from pointer position, check for underflow Pointer is then decremented Elements accessed through Push() and Pop() methods (4 marks - 1 per bullet, max 4)Mark yourself: how many marks did you get?/ 4 - Question 8H446/011 mark
Tick one box that describes how a queue operates: Last In First Out or First In First Out.
Show mark scheme
First In First Out (1 mark)Mark yourself: how many marks did you get?/ 1 - Question 9H446/014 marks
A stack is stored in an array called items. The variable top holds the index of the item at the top of the stack, and is 0 when the stack is empty. Write a pseudocode function pop() that removes and returns the item at the top of the stack, returning -1 if the stack is empty.
Show mark scheme
if top == 0 then return -1 else item = items[top] top = top - 1 return item (4 marks - 1 per bullet) Example: function pop() { if top == 0 then return -1 else item = items[top] top = top - 1 return item endif endfunctionMark yourself: how many marks did you get?/ 4 - Question 10H446/02 · June 20221 mark
State one way a directed graph is different to an undirected graph.
Show mark scheme
In directed, arcs/edges may only go in 1 direction / in undirected arcs/edges can go in both directions (1 mark)Mark yourself: how many marks did you get?/ 1 - Question 11H446/02 · June 20221 mark
State one way a graph data structure is different to a tree data structure.
Show mark scheme
More than one path is allowed in a graph / Graphs do not have a root node Graphs can be weighted / Graphs can have loops/cycles Tree is 1-directional whereas graph is 2-directional (1 mark for any valid point)Mark yourself: how many marks did you get?/ 1 - Question 12H446/013 marks
Describe how a linear search could be used to find the first available appointment in a 2D array.
Show mark scheme
To start from the beginning/first booking slot Search each slot in order/sequentially Search until the first empty slot is found (3 marks - 1 per bullet)Mark yourself: how many marks did you get?/ 3 - Question 13H446/01 · June 20211 mark
A business uses an array with the identifier wNames to store workers' names. A variable with the identifier top is used to store the index of the last element to be added to the array, which is also the element which will next be removed. State the name of the type of data structure described above.
0 1 2 3 4 5 6 Kirstie Martyn Louise Alex Anna wNames 4 top Show mark scheme
Stack (1 mark)Mark yourself: how many marks did you get?/ 1 - Question 14H446/01 · June 20214 marks
A business uses an array with the identifier wNames to store workers' names. A variable with the identifier top is used to store the index of the last element to be added to the array, which is also the element which will next be removed. Using pseudocode, write an algorithm that allows the user to enter a name which is then pushed onto the data structure above, checking first that the data structure is not full.
0 1 2 3 4 5 6 Kirstie Martyn Louise Alex Anna wNames 4 top Show mark scheme
Input name from user Check if stack is full (e.g. top <= max) If not full, update top pointer Correctly push name to index referenced by top (4 marks - 1 per bullet) Example: new = input("enter a name") if top <= 5 then top = top + 1 wNames[top] = new endifMark yourself: how many marks did you get?/ 4 - Question 15H446/01 · June 20212 marks
Compare the efficiency of a binary search tree to a linked list when searching for data.
Show mark scheme
Binary tree more efficient than linked list Do not need to check every value / tree removes half values each time Linked List O(n), Binary Tree O(log n) (2 marks - 1 per bullet)Mark yourself: how many marks did you get?/ 2 - Question 16H446/01 · June 20212 marks
Compare the efficiency of a binary search tree to a hash table when searching for data.
Show mark scheme
Binary tree less efficient than hash table Hash table can find data immediately / without checking other values Binary tree O(log n), Hash table O(1) (2 marks - 1 per bullet)Mark yourself: how many marks did you get?/ 2 - Question 17H446/02 · June 20212 marks
Define the term heuristic in relation to the A* algorithm.
Show mark scheme
A rule of thumb / estimate / guess That estimates the distance/cost from each node to the destination node To speed up the process of finding a solution (2 marks - 1 per bullet, max 2)Mark yourself: how many marks did you get?/ 2 - Question 18H446/02 · June 20204 marks
Give two similarities and two differences between a tree and a graph data structure.
Show mark scheme
Similarities: Both consist of nodes, Both are connected by edges/links, Both are non-linear data structures, Both are dynamic data structures Differences: Tree is 1-directional vs graph 2-directional, Tree has root node vs graph no clear root, Tree has no cycles vs graph can have cycles, Tree not weighted vs graph edges can be weighted (4 marks - 1 per valid point, max 4)Mark yourself: how many marks did you get?/ 4 - Question 19H446/01 · June 20194 marks
Explain how a hash table can be used to handle collisions.
Show mark scheme
Linear probing: Move through structure one space at a time to find next free space Chaining: Each location points to start of linked list, new item added to end of list Overflow area: Points to overflow area where new item stored with other values (4 marks - 1 per bullet, max 4)Mark yourself: how many marks did you get?/ 4 - Question 20H446/01 · June 201912 marks
Discuss whether a hash table or linked list is better to store acceptable websites, comparing how each structure can be searched and has data added.
Show mark scheme
Levels of response question (12 marks) AO1: Linked list - start at first node, follow pointers until value found or end reached. Time grows linearly O(n). Hash table - hash the key, access correct location. Time largely constant O(1) if no collisions. AO2: Linked list search time increases with size. Hash table search time stays same regardless of size (without collisions). Adding to linked list - constant time if last node location stored. Adding to hash table - constant time unless collisions. AO3: Hash table is likely best option assuming enough space and good hashing algorithm. Gives consistent performance even as whitelist grows.Mark yourself: how many marks did you get?/ 12 - Question 21H446/011 mark
State which of a stack or queue would be considered as a 'First In First Out' data structure.
Show mark scheme
A queue (1 mark)Mark yourself: how many marks did you get?/ 1
- 1Stack: LIFO - Push (add), Pop (remove), track top pointer; Check empty before pop
- 2Queue: FIFO - Enqueue (add rear), Dequeue (remove front), head/tail pointers
- 3Linked list: Nodes with data + pointer; O(1) insert at front, O(n) search
- 4Binary Search Tree: Left < Node < Right; In-order traversal gives sorted output
- •Practice answering questions under timed conditions
- •Check your answers against the mark scheme carefully
- •Focus on understanding the marking points, not just memorising answers
- •Review past paper questions from multiple years to spot patterns