Data structures worksheet with answers

A hash table stores data as:

1. AA sorted list only
2. BKey–value pairs located by a hash function
3. CA tree with ordered keys
4. DA fixed-length string

What is the name of the stack operation that adds an element to the top?

1. APush
2. BPop
3. CEnqueue
4. DPeek

What is the defining feature of a set as an abstract data type?

1. AIt stores key-value pairs
2. BIt stores elements in sorted order
3. CIt stores elements without duplicates
4. DIt allows access only at one end

A circular buffer (ring buffer) is commonly used to implement:

1. AA binary search tree
2. BA hash function
3. CA graph traversal
4. DA fixed-size queue

What balance condition does an AVL tree maintain at every node?

1. ABoth subtrees of every node contain exactly the same number of nodes
2. BEvery node is coloured red or black
3. CAll leaves are at exactly the same depth
4. DThe heights of the left and right subtrees differ by at most 1

What is true of the adjacency matrix of an undirected graph?

1. AIt is always upper triangular
2. BIts main diagonal always contains ones
3. CEach row has exactly one 1
4. DIt is symmetric about the main diagonal

What is the main advantage of a skip list over a sorted linked list?

1. AIt uses no extra memory
2. BGuaranteed O(1) search because every node stores a pointer to every other node
3. CIt stores keys without order
4. DExpected O(log n) search by using several levels of forward pointers

A Fenwick tree (binary indexed tree) over an array of n numbers supports which operations in O(log n)?

1. APrefix-sum queries and single-element updates
2. BSorting the array and binary search
3. CFinding the median in O(1)
4. DInserting elements at any position