Data Structures

1 Explain the difference between a stack and a queue, giving one use for each. 4

One mark for each of the following, to a maximum of 4.

• A stack is last in first out
• A queue is first in first out
• Gives a valid stack use such as the call stack or undo
• Gives a valid queue use such as a print spooler or scheduling

Model answer. A stack operates on a last in first out basis, so the most recently pushed item is the first one removed by a pop, and only the top of the stack is directly accessible. A queue operates on a first in first out basis, so items are dequeued in the order they were added and access is at both ends, adding at the rear and removing from the front. A stack is used for the call stack in a running program, where each function call pushes a return address and local variables that must be restored in exactly the reverse order as calls return, and it is equally the natural structure for undo functionality. A queue is used for a print spooler, where jobs must be printed in the order they were submitted so that no user is unfairly delayed by someone who submitted later.

2 Compare an array and a linked list. 6

One mark for each of the following, to a maximum of 6.

• An array occupies contiguous memory, a linked list does not
• An array has a fixed size, a linked list can grow and shrink dynamically
• Array elements are accessed directly by index in constant time
• A linked list must be traversed from the start, so access is slower
• Inserting into the middle of an array requires shifting subsequent elements
• Inserting into a linked list only requires changing pointers

Model answer. An array stores its elements in a contiguous block of memory, all of the same type and size, which allows the address of any element to be calculated directly from the base address and the index, giving constant time access to any position. Its size is fixed when it is created, so it cannot grow, and inserting an element into the middle requires every subsequent element to be shifted one position along, which on a large array is extremely expensive. A linked list stores each element in a node that may be located anywhere in memory, together with a pointer to the next node, so the list can grow and shrink at run time as nodes are created and destroyed. The cost of that flexibility is access time: there is no way to calculate the address of the nth item, so the list must be traversed from the head following pointers, which takes time proportional to the position. In exchange, inserting or deleting in the middle requires only that two pointers be reassigned, with no data movement at all. Each node also carries the memory overhead of its pointer, which an array does not. The choice therefore depends on the workload: arrays suit data that is read by index and rarely restructured, while linked lists suit data that is frequently inserted into and removed from.

3 Explain how a hash table achieves constant time lookup and describe one method of resolving collisions. 5

One mark for each of the following, to a maximum of 5.

• A hash function converts the key into an array index
• The item is stored at and retrieved from that index directly
• No search of the structure is required, so lookup time does not depend on the number of items
• A collision occurs when two keys hash to the same index
• Describes chaining or linear probing as a resolution method

Model answer. A hash table achieves fast lookup by applying a hash function to the key, which deterministically converts it into an index within the underlying array. The item is stored at that index when inserted, and on retrieval the same hash function is applied to the search key to produce the same index, so the item is found by a single direct array access without searching any part of the structure. Because the position is calculated rather than searched for, the time taken does not grow as the number of stored items increases, giving average constant time performance. A collision occurs when two different keys produce the same index. One resolution method is separate chaining, in which each slot in the array holds a linked list rather than a single item, and any keys hashing to that slot are appended to its list. Lookup then hashes to the slot and searches only that short list, and performance degrades gracefully as the table fills. The alternative, linear probing, stores the colliding item in the next free slot instead, which avoids extra structures but tends to produce clusters of occupied slots that lengthen future searches.

4 A program must repeatedly find a customer record by their unique customer ID from several million records. Recommend a data structure and justify your choice. 5

One mark for each of the following, to a maximum of 5.

• Recommends a hash table
• The customer ID is a unique key suited to hashing
• The hash function calculates the position so no search is needed
• Lookup is average constant time regardless of the number of records
• Compares favourably with alternatives such as a linear search or a tree

Model answer. A hash table is the right structure here. Each customer has a unique ID, which is precisely the kind of key a hash table is designed around, and the required operation is repeated lookup by that key rather than ordered traversal or range queries. The hash function converts the customer ID directly into an array index, so the record is retrieved by a single array access with no searching whatsoever, and crucially the time taken does not grow as the number of records increases, so retrieval from ten million records is essentially as fast as from ten. The alternatives are markedly worse for this workload. A linear search through an unsorted array would examine on average half of the several million records for every lookup, which is completely impractical at any volume of queries. A binary search tree would give logarithmic performance, requiring around twenty three comparisons for eight million records, which is far better than linear but still substantially slower than a single calculated access, and it would degrade badly if the IDs happened to be inserted in sorted order. The hash table's costs are that it does not maintain any useful ordering and that performance depends on a good hash function and on rehashing when the load factor rises, but since the requirement is purely lookup by unique key, neither of those is a meaningful drawback.

5 Explain the difference between an adjacency matrix and an adjacency list, and state when each is preferable. 4

One mark for each of the following, to a maximum of 4.

• An adjacency matrix is a two dimensional array recording whether each pair of vertices is connected
• An adjacency list stores for each vertex a list of the vertices it connects to
• A matrix uses space proportional to the square of the number of vertices regardless of edges
• A list is preferable for sparse graphs and a matrix for dense graphs or frequent edge checks

Model answer. An adjacency matrix represents a graph as a two dimensional array in which the entry at row i and column j records whether an edge exists from vertex i to vertex j, and in a weighted graph holds the weight of that edge. An adjacency list instead stores, for each vertex, a list of the vertices it is directly connected to. The essential difference is space. A matrix requires storage proportional to the square of the number of vertices whether or not the edges exist, so a graph of ten thousand vertices needs a hundred million entries even if only a few thousand edges are present. An adjacency list uses space proportional to the number of edges actually present. A matrix is therefore preferable for dense graphs, where most possible edges exist so little space is wasted, and where the ability to check whether a specific edge exists in constant time matters. An adjacency list is preferable for sparse graphs, which is the far more common case in practice, since real road networks, social networks and dependency graphs all have far fewer edges than the theoretical maximum.