Data Structures and Their Operations - Worksheets, Questions and Revision

12 original exam-style questions - 5 pages of questions with a full mark scheme - free printable PDF.

Download PDF Jump to mark scheme (page 6)Read the revision guide

Next in this strand

Revision Library

revisionlibrary.co.uk

A-Level · Component 02: Algorithms and Programming

A2.5 Data Structures and Their Operations

OCR H446 · Calculators not allowed · about 135 minutes

Total Marks

Name: _______________________________ Date: ____ / ____ / ______

Answer ALL questions. Show all your working.

A ticket-checking app used at a small theatre in Leeds implements a stack, a data structure that operates on a Last In First Out (LIFO) basis, to keep track of tickets as they are scanned.

(a)State what is meant by the term 'Last In First Out (LIFO)'.(1)

(b)Give one real-world example of the use of a stack, other than the scenario described above.(1)

(c)An empty stack is implemented using an array of maximum size 3 (indices 0 to 2), with a pointer called top that stores the index of the top item. When the stack is empty, top = -1. The following operations are performed, in order:
push(5), push(9), push(2), pop(), push(7)

Complete a trace table showing the contents of the array and the value of top after each of the five operations.(4)

(d)Explain what would happen if a further operation, push(3), were attempted immediately after the operations in part (c).(2)

(Total for Question 1 is 8 marks)

A print-queue manager used in a school office in Norwich implements a linear queue, a data structure that operates on a First In First Out (FIFO) basis, using an array of size 5 (indices 0 to 4). Two pointers are used: front (the index of the item at the front of the queue) and rear (the index of the item most recently added). Initially front = 0 and rear = -1 (the queue is empty).

(a)State what is meant by the term 'First In First Out (FIFO)'.(1)

(b)The following operations are performed, in order, on the initially empty queue:
enqueue(A), enqueue(B), enqueue(C), dequeue(), enqueue(D)

Complete a trace table showing the array contents, front and rear after each operation.(5)

(c)Explain one disadvantage of a linear queue, compared with a circular queue, in the context of the array above once index 0 has been vacated by the dequeue in part (b).(2)

(d)Describe how a circular queue would allow index 0 to be reused once rear reaches the last index of the array.(2)

(Total for Question 2 is 10 marks)

A student-run society at a university in Bristol keeps its members' ID numbers in a singly linked list, in the order they joined. Each node stores a data field and a pointer field holding the address of the next node; a pointer called head stores the address of the first node, and the last node's pointer field holds a null value.

(a)State the purpose of the pointer field in a node of a singly linked list.(1)

(b)The pseudocode below is intended to traverse a linked list from head and output every data value. Complete the two missing lines, (i) and (ii).

current <- head
WHILE ...........(i)........... DO
  OUTPUT current.data
  current <- ...........(ii)...........
ENDWHILE

(2)

(c)The list currently holds the ID numbers 10 -> 25 -> 40 (head points to the node holding 10; each arrow represents a pointer to the next node; the node holding 40 has a null pointer). A new node called newNode has already been created holding the value 18. Write pseudocode to insert newNode between the nodes holding 10 and 25, given that a pointer variable current already references the node holding 10.(3)

(d)State the value of head.next.next.data after the insertion in part (c).(1)

(Total for Question 3 is 7 marks)

The society's linked list from Question 3 now holds 10 -> 18 -> 25 -> 40, with head pointing to the node holding 10 and the node holding 40 having a null pointer.

(a)A pointer variable previous already references the node holding 18. Write pseudocode to delete the node holding 25 from the list.(3)

(b)A member of the society claims: 'Deleting a node from a linked list is always more efficient than deleting an item from the middle of an array.' Explain whether this claim is correct, referring to the number of elements that must be updated or moved in each structure.(3)

(c)State the Big O time complexity of searching for a given value in an unsorted singly linked list of n nodes, and justify your answer.(2)

(Total for Question 4 is 8 marks)

A calculator app developed by a startup in Manchester evaluates arithmetic expressions that have already been converted into postfix (Reverse Polish) notation, using a stack. Tokens are scanned left to right: when a number is read, it is pushed onto the stack; when an operator is read, the top two values are popped (the second-popped value, a, is the left operand and the first-popped value, b, is the right operand), the operation a operator b is applied, and the result is pushed back onto the stack.

Consider the postfix expression: 6 2 3 + * 4 -

(a)Complete a trace table showing the contents of the stack after each token in the expression has been processed.(6)

(b)State the final value of the expression.(1)

(c)Explain why a stack, rather than a queue, is the appropriate data structure for evaluating postfix expressions in this way.(2)

(Total for Question 5 is 9 marks)

A customer-service call centre in Cardiff models its call-holding system as a circular queue, implemented using an array of size 5 (indices 0 to 4), pointers front and rear, and a count of the number of calls currently held. Initially front = 0, rear = 0, count = 0. To enqueue: if count = 5 the queue is full; otherwise array[rear] <- item, rear <- (rear + 1) MOD 5, count <- count + 1. To dequeue: if count = 0 the queue is empty; otherwise item <- array[front], front <- (front + 1) MOD 5, count <- count - 1.

The following calls are held, in order: enqueue(P), enqueue(Q), enqueue(R), dequeue(), dequeue(), enqueue(S), enqueue(T), enqueue(U)

(a)Complete a trace table recording front, rear and count after each of the eight operations.(8)

(b)State the front-to-rear order of the calls remaining in the queue after all eight operations.(1)

(c)Explain why the array slot at index 0 can safely be reused for enqueue(U), even though it previously held the value P.(2)

(Total for Question 6 is 11 marks)

A library index system used in a school in Preston stores book reference numbers in a binary search tree (BST), so that they can be searched efficiently. Starting from an empty tree, the following values are inserted, one at a time, always starting comparisons at the root: 50, 30, 70, 20, 40, 60, 80, 35. The standard BST insertion rule is used: at each node, if the new value is less than the node's value, move left; otherwise, move right; the value is inserted at the first empty position reached.

(a)Determine the position of 35 in the completed tree, by comparing it against the root and each node subsequently reached, stating at each step whether the comparison sends it left or right. Hence state the parent of 35 and whether it becomes the left or right child of that parent.(3)

(b)State the value stored at the root of the completed tree.(1)

(c)Write out the pre-order traversal of the completed tree.(3)

(d)Write out the in-order traversal of the completed tree, and state what property of a binary search tree this result demonstrates.(3)

(Total for Question 7 is 10 marks)

A file-directory viewer developed by a software company in Oxford represents a small folder structure as a binary tree, where each node stores a single-letter identifier. The root node is M. M's left child is H and right child is T. H's left child is D and right child is L. T's left child is S and right child is W. Nodes D, L, S and W each have no children.

(a)Write out the result of a pre-order traversal of the tree.(2)

(b)Write out the result of an in-order traversal of the tree.(2)

(c)Write out the result of a post-order traversal of the tree.(2)

(d)Write out the result of a breadth-first (level-order) traversal of the tree, and state the abstract data type that is used to implement this traversal, giving a reason for its use.(3)

(Total for Question 8 is 9 marks)

A social-network analysis tool built by a data-science team in Sheffield models the friendship connections between five users, Aisha, Ben, Chidi, Priya and Tom, as an undirected graph, where an edge represents a mutual friendship. The friendships are: Aisha-Ben, Aisha-Chidi, Ben-Chidi, Ben-Priya, Chidi-Priya, Priya-Tom.

(a)Complete the adjacency matrix for this graph, using 1 to indicate a friendship and 0 to indicate no friendship, with rows and columns ordered alphabetically: Aisha, Ben, Chidi, Priya, Tom.(4)

(b)Write the adjacency list representation of the same graph.(3)

(c)State one advantage of using an adjacency list, rather than an adjacency matrix, to represent a sparse graph such as this one (a graph with relatively few edges compared with the number of possible edges).(2)

(Total for Question 9 is 9 marks)

A route-planning tool used by a delivery company in Leicester models six delivery hubs, Amir, Beth, Carlos, Dana, Elif and Farah, and the direct roads connecting them, as an undirected graph. The roads are: Amir-Beth, Amir-Carlos, Beth-Dana, Carlos-Dana, Carlos-Elif, Dana-Farah, Elif-Farah. When visiting the neighbours of a hub, they are always considered in alphabetical order.

(a)Perform a breadth-first search (BFS) of the graph starting at Amir, using a queue. Show the changing contents of the queue and state the order in which the hubs are visited.(4)

(b)Perform a depth-first search (DFS) of the graph starting at Amir, using a stack (or recursion), always exploring the first unvisited neighbour in alphabetical order before backtracking. State the order in which the hubs are visited.(4)

(c)Explain, with reference to the traversals performed in (a) and (b), one situation in which BFS would be preferred over DFS.(2)

(Total for Question 10 is 10 marks)

An online ticket-booking system used by a leisure centre in Swansea stores booking reference numbers in a hash table with 7 slots (indices 0 to 6), using the hash function h(k) = k MOD 7. Collisions are resolved using linear probing: if the calculated slot is already occupied, the next slot is tried (wrapping from slot 6 back to slot 0), and so on, until an empty slot is found.

The following keys are inserted, in this order, into an initially empty hash table: 23, 12, 15, 8, 19, 30

(a)Calculate h(k) for each of the six keys.(3)

(b)Complete a trace table showing the slot at which each key is finally stored, including any probing required due to collisions.(6)

(c)State the final contents of the hash table (slot index: key) for all 7 slots.(1)

(d)Calculate the load factor of the hash table after all six keys have been inserted, giving your answer as a fraction in its simplest form.(2)

(e)Explain one disadvantage of linear probing as a collision-resolution technique, compared with separate chaining.(2)

(Total for Question 11 is 14 marks)

A software engineer at a customer-records company based in Glasgow is designing a system that must store a large, frequently changing collection of customer records and needs to support fast insertion, deletion and look-up of a record by its unique customer ID.

(a)Discuss the suitability of a hash table, a binary search tree and a linked list for this purpose, comparing their typical time complexities for insertion, deletion and look-up, and recommend which structure the engineer should choose, justifying your recommendation.(9)

(Total for Question 12 is 9 marks)

Mark scheme · A2.5 Data Structures and Their Operations

Question 1

(a) B1 the most recently added item is the first one to be removed (oe)
(a) Answer: The item most recently added to the structure is the first one to be removed.
(b) B1 any valid example, e.g. the undo function in a word processor, the back button in a web browser, or storing return addresses/local variables for function calls (call stack) (oe)
(b) Answer: The undo feature in a word processor, which reverses the most recent action first.
(c) B1 push(5): array = [5, _, _], top = 0
(c) B1 push(9): array = [5, 9, _], top = 1
(c) B1 push(2): array = [5, 9, 2], top = 2
(c) B1 pop(): array = [5, 9, _], top = 1; then push(7): array = [5, 9, 7], top = 2
(c) Answer: push(5): [5,_,_] top=0. push(9): [5,9,_] top=1. push(2): [5,9,2] top=2. pop(): [5,9,_] top=1 (2 removed). push(7): [5,9,7] top=2.
(d) B1 a stack overflow error would occur ft from (c)
(d) B1 because top (2) already equals the maximum valid index (size - 1 = 2), so the array is completely full and there is no free slot to store 3 (oe)
(d) Answer: A stack overflow occurs, because top is already at index 2, the maximum index of the array (size 3, indices 0 to 2), so there is no room to push another item.

Question 2

(a) B1 the item that has been in the structure the longest (added first) is the first one to be removed (oe)
(a) Answer: The item that was added earliest is the first one to be removed.
(b) B1 enqueue(A): array = [A,_,_,_,_], front = 0, rear = 0
(b) B1 enqueue(B): array = [A,B,_,_,_], front = 0, rear = 1
(b) B1 enqueue(C): array = [A,B,C,_,_], front = 0, rear = 2
(b) B1 dequeue(): removes A, front = 1, rear = 2
(b) B1 enqueue(D): array = [_,B,C,D,_], front = 1, rear = 3
(b) Answer: After all five operations: front = 1, rear = 3, and the queue (front to rear) holds B, C, D.
(c) B1 once an item is dequeued from the front, that array slot (e.g. index 0) becomes unusable in a linear queue, since only rear moves forward on enqueue (oe)
(c) B1 as more items are enqueued and dequeued, rear keeps advancing towards the last index, so the queue can eventually report as full (no more room after rear) even though earlier slots are actually free, wasting space (oe)
(c) Answer: Index 0 becomes wasted space once A is dequeued, because a linear queue only ever moves rear forward; eventually rear reaches the final index and the queue is reported full, even though slots such as index 0 are actually empty.
(d) B1 the rear pointer wraps around back to index 0 using modulo arithmetic, e.g. rear = (rear + 1) MOD size, once it passes the last index (oe)
(d) B1 this reuses slots that have already been dequeued (are now outside the front-to-rear range), as long as the queue is not already full, so space is not wasted (oe)
(d) Answer: In a circular queue, rear is calculated using rear = (rear + 1) MOD size, so once rear passes the last index it wraps back to index 0; provided that slot has already been freed by an earlier dequeue, it can safely be reused instead of being left wasted.

Question 3

(a) B1 it stores the address of (a reference to) the next node in the list, or a null value if it is the last node (oe)
(a) Answer: It stores the address of the next node in the list, or a null value if there is no next node.
(b) B1 (i) current <> NULL (or current ≠ NULL / current is not null) (oe)
(b) B1 (ii) current.next
(b) Answer: (i) current <> NULL (ii) current.next
(c) M1 newNode.next <- current.next (newNode's pointer is set to reference the node holding 25, i.e. what current currently points to)
(c) A1 current.next <- newNode (the node holding 10 is redirected to point to newNode)
(c) B1 correctly performs these two assignments in this order, so that the reference to the node holding 25 is not lost before newNode is linked to it (oe)

newNode.next <- current.next
current.next <- newNode

(d) B1 25 ft from (c)
(d) Answer: 25

Question 4

(a) M1 target <- previous.next (references the node to be removed, the node holding 25)
(a) M1 previous.next <- target.next (bypasses the removed node, linking the node holding 18 directly to the node holding 40)
(a) A1 resulting list correctly reads 10 -> 18 -> 40 (the node holding 25 is no longer reachable and may be discarded/freed)

(a) Answer:

target <- previous.next
previous.next <- target.next

(b) B1 the claim is correct in terms of the work needed once the position is known (oe)
(b) B1 deleting from a linked list only requires updating one pointer (previous.next), regardless of how many nodes are in the list, once the node to delete has been located (oe)
(b) B1 deleting from the middle of an array requires shifting every subsequent element one position to the left to close the gap, so the number of elements moved depends on the size of the array/list (oe)
(b) Answer: The claim is correct: once the node before the target has been found, deleting it from a linked list only involves changing one pointer, whereas deleting from the middle of an array requires shifting every element after it one place to the left to close the gap.
(c) B1 O(n) cao
(c) B1 in the worst case every node must be visited in turn, following the next pointers from head until the value is found or a null pointer is reached, since there is no direct/random access to a given position (oe)
(c) Answer: O(n), because in the worst case every one of the n nodes must be visited in turn, following pointers from head, since a linked list has no direct access to a given position.

Question 5

(a) B1 after 6, 2, 3 are read: stack = [6, 2, 3] (three pushes)
(a) B1 '+' : pops 3 (b) and 2 (a), computes 2 + 3 = 5, pushes 5: stack = [6, 5]
(a) B1 '*' : pops 5 (b) and 6 (a), computes 6 * 5 = 30, pushes 30: stack = [30]
(a) B1 after 4 is read: stack = [30, 4]
(a) B1 '-' : pops 4 (b) and 30 (a), computes 30 - 4 = 26, pushes 26: stack = [26]
(a) B1 final stack correctly shown as [26] with all intermediate values consistent
(a) Answer: Stack after each token: [6] -> [6,2] -> [6,2,3] -> [6,5] -> [30] -> [30,4] -> [26]
(b) B1 26 ft from (a)
(b) Answer: 26
(c) B1 an operator always needs to combine with the operands nearest to it (most recently pushed), which matches a stack's LIFO behaviour (oe)
(c) B1 a queue would return items in the order they were first inserted (FIFO), which would not give the operator the correct, most recent operands needed for evaluation (oe)
(c) Answer: An operator always needs to act on the two most recently seen operands, which is exactly what a stack's LIFO behaviour provides; a queue's FIFO behaviour would instead return the oldest values first, giving the wrong operands.

Question 6

(a) B1 enqueue(P): array[0] = P, rear = 1, count = 1
(a) B1 enqueue(Q): array[1] = Q, rear = 2, count = 2
(a) B1 enqueue(R): array[2] = R, rear = 3, count = 3
(a) B1 dequeue(): removes P, front = 1, count = 2
(a) B1 dequeue(): removes Q, front = 2, count = 1
(a) B1 enqueue(S): array[3] = S, rear = 4, count = 2
(a) B1 enqueue(T): array[4] = T, rear = (4+1) MOD 5 = 0, count = 3
(a) B1 enqueue(U): array[0] = U (overwriting the freed slot that held P), rear = 1, count = 4
(a) Answer: After all eight operations: front = 2, rear = 1, count = 4, with the queue (front to rear) holding R, S, T, U.
(b) B1 R, S, T, U ft from (a)
(b) Answer: R, S, T, U
(c) B1 P was removed by an earlier dequeue operation, so it is no longer part of the logical queue and is no longer referenced by front or count (oe)
(c) B1 a circular queue reuses slots via modulo arithmetic on the rear pointer once they fall outside the current front-to-rear range represented by count, avoiding the wasted-space problem of a linear queue (oe)
(c) Answer: P was already removed by the earlier dequeue() call, so index 0 is no longer part of the logical queue; because the queue is circular, rear can wrap back to index 0 using modulo arithmetic and safely overwrite it with U.

Question 7

(a) M1 compares 35 with the root, 50: since 35 < 50, moves left (to the subtree rooted at 30)
(a) M1 compares 35 with 30: since 35 ≥ 30, moves right (to the subtree rooted at 40)
(a) A1 compares 35 with 40: since 35 < 40, and 40 has no left child, 35 becomes the left child of 40 cao
(a) Answer: 35 becomes the left child of 40.
(b) B1 50
(b) Answer: 50
(c) M1 correctly traverses the left subtree of 50 (rooted at 30) in pre-order: 30, 20, 40, 35
(c) M1 correctly traverses the right subtree of 50 (rooted at 70) in pre-order: 70, 60, 80
(c) A1 50, 30, 20, 40, 35, 70, 60, 80 cao
(c) Answer: 50, 30, 20, 40, 35, 70, 60, 80
(d) M1 correctly traverses the left subtree of 50 in-order: 20, 30, 35, 40
(d) M1 correctly traverses the right subtree of 50 in-order: 60, 70, 80, giving the full sequence 20, 30, 35, 40, 50, 60, 70, 80 cao
(d) B1 states that an in-order traversal of a BST always produces the stored values in ascending (sorted) order (oe)
(d) Answer: 20, 30, 35, 40, 50, 60, 70, 80. This demonstrates that an in-order traversal of a binary search tree always visits the values in ascending (sorted) order.

Question 8

(a) M1 correct method applied: node, then left subtree, then right subtree, at every level
(a) A1 M, H, D, L, T, S, W cao
(a) Answer: M, H, D, L, T, S, W
(b) M1 correct method applied: left subtree, then node, then right subtree, at every level
(b) A1 D, H, L, M, S, T, W cao
(b) Answer: D, H, L, M, S, T, W
(c) M1 correct method applied: left subtree, then right subtree, then node, at every level
(c) A1 D, L, H, S, W, T, M cao
(c) Answer: D, L, H, S, W, T, M
(d) B1 M, H, T, D, L, S, W cao
(d) B1 a queue
(d) B1 nodes are added (enqueued) to the queue in the order they are discovered, level by level, and removed (dequeued) in the same order, so the FIFO behaviour of a queue ensures each level is fully visited before moving to the next (oe)
(d) Answer: M, H, T, D, L, S, W. A queue is used, because its FIFO behaviour ensures nodes are visited level by level, in the same order they were discovered.

Question 9

(a) B1 Aisha's row/column correct: connected to Ben and Chidi only
(a) B1 Ben's row/column correct: connected to Aisha, Chidi and Priya
(a) B1 Chidi's and Priya's rows/columns correct: Chidi connected to Aisha, Ben, Priya; Priya connected to Ben, Chidi, Tom
(a) B1 Tom's row/column correct (connected to Priya only), matrix symmetric about the diagonal, and all diagonal entries 0 (no self-friendships)
(a) Answer: Aisha Ben Chidi Priya Tom
Aisha 0 1 1 0 0
Ben 1 0 1 1 0
Chidi 1 1 0 1 0
Priya 0 1 1 0 1
Tom 0 0 0 1 0
(b) B1 Aisha: [Ben, Chidi]
(b) B1 Ben: [Aisha, Chidi, Priya]; Chidi: [Aisha, Ben, Priya]
(b) B1 Priya: [Ben, Chidi, Tom]; Tom: [Priya]
(b) Answer: Aisha: [Ben, Chidi]; Ben: [Aisha, Chidi, Priya]; Chidi: [Aisha, Ben, Priya]; Priya: [Ben, Chidi, Tom]; Tom: [Priya]
(c) B1 an adjacency list uses less memory for a sparse graph, since it only stores the edges that actually exist (oe)
(c) B1 an adjacency matrix always requires space proportional to the square of the number of vertices (n²), regardless of how few edges are actually present, which wastes space for a sparse graph (oe)
(c) Answer: An adjacency list uses less memory, because it only stores the edges that actually exist, whereas an adjacency matrix always needs n² storage regardless of how sparse the graph is.

Question 10

(a) M1 visits Amir, then enqueues its unvisited neighbours in alphabetical order, Beth then Carlos: queue = [Beth, Carlos]
(a) M1 dequeues and visits Beth before Carlos (FIFO order), correctly enqueuing each hub's new unvisited neighbours as they are found (Dana when processing Beth; Elif when processing Carlos; Farah when processing Dana)
(a) A1 final visit order: Amir, Beth, Carlos, Dana, Elif, Farah cao
(a) B1 correctly states that the algorithm terminates once the queue becomes empty, with every hub visited exactly once
(a) Answer: Amir, Beth, Carlos, Dana, Elif, Farah
(b) M1 visits Amir, then immediately visits Beth (its first unvisited neighbour), rather than visiting all of Amir's neighbours first
(b) M1 correctly continues deep from Beth to Dana, then from Dana to Carlos (Beth already visited), then from Carlos to Elif, then from Elif to Farah, backtracking only once no unvisited neighbours remain
(b) A1 final visit order: Amir, Beth, Dana, Carlos, Elif, Farah cao
(b) B1 correctly identifies that DFS uses a stack (explicitly, or implicitly via the recursive call stack), in contrast to the queue used by BFS
(b) Answer: Amir, Beth, Dana, Carlos, Elif, Farah
(c) B1 identifies a suitable use case, e.g. finding the shortest route (fewest roads) between two hubs in this unweighted graph (oe)
(c) B1 justifies this: BFS explores all hubs at the current distance from the start before moving further away, so the first time the target hub is reached is guaranteed to be via a shortest path, whereas DFS explores one branch fully before backtracking and does not guarantee this (oe)
(c) Answer: BFS would be preferred for finding the shortest route (fewest roads) between two hubs, because it visits all hubs at each distance from the start before moving further out, so the first time it reaches the target hub is guaranteed to be via a shortest path, which DFS does not guarantee.

Question 11

(a) B1 h(23) = 2 and h(12) = 5
(a) B1 h(15) = 1 and h(8) = 1
(a) B1 h(19) = 5 and h(30) = 2
(a) Answer: h(23)=2, h(12)=5, h(15)=1, h(8)=1, h(19)=5, h(30)=2
(b) B1 23: h=2, slot 2 empty, stored at slot 2
(b) B1 12: h=5, slot 5 empty, stored at slot 5
(b) B1 15: h=1, slot 1 empty, stored at slot 1
(b) B1 8: h=1, slot 1 occupied (15); probes slot 2, occupied (23); probes slot 3, empty; stored at slot 3
(b) B1 19: h=5, slot 5 occupied (12); probes slot 6, empty; stored at slot 6
(b) B1 30: h=2, slot 2 occupied (23); probes slot 3, occupied (8); probes slot 4, empty; stored at slot 4
(b) Answer: 23->slot2, 12->slot5, 15->slot1, 8->slot3 (after probing 1,2), 19->slot6 (after probing 5), 30->slot4 (after probing 2,3)
(c) B1 0: empty, 1: 15, 2: 23, 3: 8, 4: 30, 5: 12, 6: 19 ft from (b)
(c) Answer: 0: empty, 1: 15, 2: 23, 3: 8, 4: 30, 5: 12, 6: 19
(d) M1 load factor = number of occupied slots / total number of slots = 6 / 7
(d) A1 6/7 cao (accept awrt 0.86)
(d) Answer: 6/7
(e) B1 linear probing can lead to clustering, where consecutive occupied slots build up, making future collisions (and therefore searches and insertions) increasingly likely and increasingly slow (oe)
(e) B1 separate chaining instead allows each slot to hold multiple items (e.g. in a linked list), so performance degrades less severely, and a slot never has to overflow into a neighbouring one (oe)
(e) Answer: Linear probing can cause clustering, where a build-up of consecutive occupied slots makes further collisions, and therefore searches, progressively slower, as seen with the probing needed for 8 and 30 above; separate chaining avoids this, since each slot can hold multiple items in its own chain rather than spilling into neighbouring slots.