Data structures worksheet with answers

How are the elements of an array stored in memory?

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

What is the load factor of a hash table?

1. AThe number of stored elements divided by the number of buckets
2. BThe number of buckets divided by the average length of the keys stored
3. CThe time needed to load the table from disk
4. DThe number of collisions so far

What is a directed graph?

1. AA graph whose edges all have weights
2. BA graph in which every pair of distinct vertices is joined by an edge
3. CA graph whose edges have a direction from one vertex to another
4. DA graph that has no cycles

Which abstract data type does Dijkstra's algorithm use to choose the next vertex to process?

1. AA set with no ordering
2. BA stack
3. CA min-priority queue
4. DA FIFO queue

An in-order traversal of a binary search tree visits the keys in:

1. AInsertion order
2. BAscending sorted order
3. CDescending order always
4. DLevel order

You have a reference to a node in the middle of a list. In which list can you remove it in O(1)?

1. AA dynamic array
2. BA sorted array
3. CA doubly linked list
4. DA singly linked list

What guarantee do the red-black tree rules give about the height of a tree with n keys?

1. AThe height is at most 2 log₂(n + 1)
2. BThe height is exactly log₂ n
3. CThe height is at most log₂ n + 1
4. DThe height is at most n / 2

Kahn's algorithm for topological sorting repeatedly removes vertices with in-degree 0. Which structure holds those vertices?

1. AA max-heap ordered by out-degree
2. BA queue (or any collection) of vertices whose in-degree is 0
3. CAn adjacency matrix recording which vertices have already been removed
4. DA stack of all visited edges