Computer Science

1. 1.

   An empty stack receives PUSH(A), PUSH(B), POP(), PUSH(C), POP(). State the returned values in order and the remaining stack.

   [3 marks] · no calculator

   Answer explanation

   Draft walkthroughs are based on marking guidance, not independently verified derivations.

   1. A stack removes the most recently added unremoved item. Removing B reveals A, then adding and removing C leaves that original A unchanged.

   Marking points

   • The first POP returns B.
   • The second POP returns C.
   • Only A remains.

   Examiner tip: Do not apply FIFO behaviour to a stack.

2. 2.

   Explain why a queue is appropriate for serving print jobs in arrival order and identify the insertion and removal ends.

   [3 marks] · no calculator

   Answer explanation

   Draft walkthroughs are based on marking guidance, not independently verified derivations.

   1. Maintaining separate ends prevents a new job from overtaking earlier waiting jobs. Priority printing would require a different ordering policy, but the stated arrival-order requirement fits a queue.

   Marking points

   • It provides first-in-first-out order.
   • New jobs are enqueued at the rear.
   • The oldest waiting job is dequeued from the front.

   Examiner tip: FIFO does not by itself promise a maximum waiting time.

3. 3.

   Insert keys 10, 17 and 24 into an empty size-7 hash table using h(k)=k mod 7 and linear probing, zero-based slots. State their final slots.

   [3 marks] · no calculator

   Answer explanation

   Draft walkthroughs are based on marking guidance, not independently verified derivations.

   1. All keys have remainder three. Linear probing advances to the next slot until an empty one is found, so successive collisions form a cluster without overwriting prior keys.

   Marking points

   • 10 occupies slot 3.
   • 17 collides at 3 and occupies slot 4.
   • 24 probes 3 and 4 then occupies slot 5.

   Examiner tip: A collision does not authorise replacing the stored key.

4. 4.

   For an undirected graph with edges A-B, A-C, B-D and C-D, perform BFS from A, enqueueing unvisited neighbours alphabetically and marking on enqueue. Give visit order and shortest A-to-D edge count.

   [3 marks] · no calculator

   Answer explanation

   Draft walkthroughs are based on marking guidance, not independently verified derivations.

   1. BFS's queue processes all vertices at one distance before the next distance. Starting at A places B and C at distance one, then discovers D at distance two.

   Marking points

   • Visit order is A, B, C, D.
   • D is enqueued from B and not enqueued again from C.
   • Shortest edge count is 2.

   Examiner tip: Marking on enqueue prevents duplicate queue entries through different parents.

5. 5.

   A hash table uses linear probing and search stops at an empty slot. Explain why deleting a key by simply clearing its slot can break search, and how tombstones address this.

   [4 marks] · no calculator

   Answer explanation

   Draft walkthroughs are based on marking guidance, not independently verified derivations.

   1. An empty-never-used slot is evidence that no key on that probe chain lies further along; a deleted slot is not. A distinct deleted state preserves that logical distinction.

   Marking points

   • A later colliding key may lie beyond the deleted slot.
   • Clearing creates an apparent end to the probe chain, so search can stop too early.
   • A tombstone records deletion while telling search to continue probing.
   • Insertion can reuse tombstones, with duplicate detection handled across the probe chain.

   Examiner tip: Search must distinguish never-used from deleted slots.

6. 6.

   Use Dijkstra's algorithm from A on an undirected graph: A-B=4, A-C=1, C-B=2, B-D=1, C-D=5. Determine the shortest A-to-D path and explain why the algorithm requires nonnegative edge weights.

   [4 marks] · no calculator

   Answer explanation

   Draft walkthroughs are based on marking guidance, not independently verified derivations.

   1. Initial alternatives for D include the route through C of weight six. Relaxing from improved B gives four, with predecessors D<-B<-C<-A. Nonnegative continuation ensures an unsettled longer prefix cannot later undercut a settled minimum.

   Marking points

   • C is settled at distance 1.
   • B is improved to distance 3 through C.
   • Shortest path is A-C-B-D with total weight 4.
   • Negative edges can allow a later path to improve an already settled distance, invalidating the greedy finalisation rule.

   Examiner tip: For weighted graphs, BFS edge count is not a substitute for minimum total weight.

Original, unofficial practice questions from SubjectScout — not official past-paper questions.