Data structures worksheet with answers

Which operation is slow in an array but fast at the head of a linked list?

1. AFinding the length of a fixed array
2. BInserting at the beginning
3. CAccessing the 5th element
4. DReading the last element by index

What is the load factor of a hash table?

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

Which data structure works on the principle "first in, first out"?

1. AHeap
2. BStack
3. CBinary tree
4. DQueue

Why is traversing an array often much faster in practice than traversing a linked list of the same length?

1. ALinked lists always store elements on disk
2. BArrays use fewer instructions to compare values
3. CArray traversal is O(1) in total, while linked list traversal is O(n)
4. DArray elements are contiguous, so they make good use of the CPU cache

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

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

What is the value of the postfix expression 3 4 + 2 * ?

1. A24
2. B11
3. C10
4. D14

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

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

Which problem of linear probing does double hashing mainly reduce?

1. AThe need to store keys in the table
2. BPrimary clustering, where long runs of occupied slots form
3. CThe need for a hash function
4. DThe O(n) cost of reading a key's value