Data structures worksheet with answers

How are the elements of an array stored in memory?

1. AScattered, linked by pointers
2. BIn a tree of memory pages
3. CIn random locations chosen by a hash
4. DIn one contiguous block, one after another

Which structure is typically used to implement a priority queue?

1. AA heap
2. BA stack
3. CA string
4. DA singly linked list without order

Which data structure is used to perform a level-order traversal of a tree?

1. AQueue
2. BStack
3. CPriority queue
4. DHash table

An adjacency matrix for a graph with V vertices uses how much memory?

1. AO(V + E)
2. BO(V²)
3. CO(E)
4. DO(log V)

What is the worst-case height of a binary search tree with n nodes if keys are inserted in sorted order?

1. An (it becomes a linked list)
2. B√n
3. C1
4. Dlog₂ n

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

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

Why might a server choose its hash function at random from a universal family?

1. ATo guarantee that no two keys can ever collide, whatever keys an attacker sends
2. BTo remove the need to resize the table
3. CTo make it very unlikely that an attacker can pick many keys that all collide
4. DTo make the hash table sorted

Which statement about heapsort is correct?

1. AIt sorts in place in O(n log n) worst-case time but is not stable
2. BIt is stable and needs O(n) extra memory
3. CIt needs a binary search tree as extra storage, so it uses O(n) extra memory
4. DIt runs in O(n) time on any input