OCR A-Level Computer Science: Data Structures

The following data were written for this exercise.

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

42, 25, 63, 17, 33, 55, 70, 28

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 and present it as a table with the columns shown below, giving for every node its left child and its right child (write - where a child is absent). Do not draw a diagram. [4 marks]

Node	Left child	Right child
...	...	...

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

(c) State why an in-order traversal of a BST yields the keys in sorted order; give the average-case time complexity of searching a balanced BST in Big-O notation; and explain what that complexity becomes if the keys are instead inserted in already-sorted order, justifying the change. [4 marks]

The following expression was written for this exercise.

A stack is used to convert an arithmetic expression from infix notation to postfix (Reverse Polish) notation, and then to evaluate the postfix form. The infix expression to process is:

(3 + 4) * 2 - 5

The conversion uses the standard shunting algorithm with a single operator stack and an output list, with * and / of higher precedence than + and -, and processing left to right.

(a) Convert the expression to postfix. Show, as a table, the operator stack and the output after each token is processed. State the final postfix expression. [5 marks]

(b) Evaluate the postfix expression you produced, using a second stack. Show the evaluation stack after each token is processed, and state the final result. [4 marks]

The following data were written for this exercise.

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

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

23, 14, 9, 45, 36, 25

(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. Then give the final state of the array (slots 0 to 10). [4 marks]

(b) State the load factor of the table after all six insertions, and state one consequence for performance of allowing the load factor to become high. [2 marks]

The following data were written for this exercise.

An undirected, unweighted graph has five vertices P, Q, R, S, T and the following edges (given as an edge list):

P-Q, P-R, Q-S, R-S, R-T, S-T

(a) Represent the graph as an adjacency matrix, using 1 for an edge and 0 for no edge, with rows and columns ordered P, Q, R, S, T. Then represent the same graph as an adjacency list. [4 marks]

(b) State one situation in which an adjacency matrix is the preferable representation and one in which an adjacency list is preferable, justifying each with reference to memory use or lookup speed and to whether the graph is dense or sparse. [1 mark]

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

A circular queue is held in a fixed array of size 5 (valid indices 0 to 4). It maintains front (index of the next item to dequeue), rear (index of the most recently enqueued item) and count (the number of items held). The queue starts empty with front = 0, rear = -1, count = 0. enqueue advances rear as (rear + 1) MOD 5 and dequeue advances front as (front + 1) MOD 5.

(a) Starting from the empty queue, trace the sequence enqueue(10), enqueue(20), enqueue(30), dequeue(), dequeue(), enqueue(40), enqueue(50), enqueue(60), enqueue(70). Give front, rear, count and the array contents after each operation, as a table. [3 marks]

(b) State one advantage of a circular queue over a simple linear queue, referring to the enqueue(60) step of your trace. [1 mark]

An array and a linked list are both ways to store an ordered sequence of items, but they behave very differently for different operations.

Compare an array with a (singly) linked list for each of the following, in each case giving the Big-O time complexity of both:

(i) inserting a new item at the front of the sequence; and

(ii) random access to the item at a given index. [3 marks]