AQA A-Level Computer Science: Data Structures

The following data structure and operations were written for this exercise.

A circular queue is implemented in a fixed array of size 6 (valid indices 0 to 5). It maintains three variables: front (index of the item to dequeue next), rear (index of the most recently enqueued item) and count (the number of items held). The queue starts empty with front = 0, rear = -1 and count = 0. The enqueue and dequeue operations use modular arithmetic to wrap pointers around the end of the array:

CONSTANT MAX_SIZE = 6
PROCEDURE enqueue(item)
    IF count = MAX_SIZE THEN
        OUTPUT "Queue is full"
    ELSE
        rear = (rear + 1) MOD MAX_SIZE
        queue[rear] = item
        count = count + 1
    ENDIF
ENDPROCEDURE

(a) Starting from the empty queue, trace the following sequence of operations: enqueue(21), enqueue(34), enqueue(47), enqueue(58), dequeue(), dequeue(), enqueue(63), enqueue(72), enqueue(89). Give the value of front, rear and count, and the array contents, after each operation, as a table. [6 marks]

(b) Explain why this queue is implemented as a circular queue rather than a simple linear queue, referring to the behaviour of the enqueue(89) step in your trace. [2 marks]

(c) Write the pseudocode for a dequeue() operation. It must include the underflow check, return the removed item, and advance the front pointer correctly. [4 marks]

The following data was written for this exercise.

The integer keys below are inserted, in the order shown, into an initially empty binary search tree (BST):

50, 30, 70, 20, 40, 60, 80, 35, 65

Recall the BST ordering rule: at every node, all keys in the left subtree are smaller than the node's key and all keys in the right subtree are larger.

(a) Construct the BST. Describe its structure by stating, for each key, its parent and whether it is a left or right child (the root has no parent), as a table. [4 marks]

(b) Give the pre-order and the post-order traversal of the completed tree. [3 marks]

(c) State the in-order traversal, and explain what is special about the order it produces. [2 marks]

The following data was written for this exercise.

A hash table uses an array of size $m = 10$m=10 (indices 0 to 9) and the hash function $h(k) = k \bmod 10$h(k)=kmod10. Collisions are resolved by open addressing with linear probing: if the home slot is occupied, the algorithm tries $(h(k) + 1) \bmod 10$(h(k)+1)mod10, then $(h(k) + 2) \bmod 10$(h(k)+2)mod10, and so on until a free slot is found.

The following integer keys are inserted, in order, into the initially empty table:

35, 12, 25, 45, 18, 22

(a) Insert the keys, showing for each one its home slot $h(k)$h(k), the slots probed, and the slot it finally occupies, as a table. [4 marks]

(b) Draw the final state of the array, slots 0 to 9. [1 mark]

(c) State the load factor of the table after all six insertions. [1 mark]

The following data was written for this exercise.

An undirected, unweighted graph has five vertices A, B, C, D, E and the following edges:

A-B, A-C, B-C, B-D, C-E, D-E

(a) Represent the graph as an adjacency matrix, using 1 for an edge and 0 for no edge, with rows and columns ordered A, B, C, D, E. [3 marks]

(b) Represent the same graph as an adjacency list. [2 marks]

A programmer must store a collection of records whose number is not known until the program is running and may change frequently as the program executes.

Explain the difference between a static and a dynamic data structure, and use that difference to recommend which the programmer should choose here. Refer to memory allocation in your answer. [4 marks]

A queue and a stack are both abstract data types built from an ordered collection of items.

(a) State the rule that governs the order in which items leave a queue, and the rule for a stack, naming each rule with its standard abbreviation. [2 marks]

(b) Give one realistic use case for a queue and briefly say why a queue (rather than a stack) suits it. [1 mark]