Data structures worksheet with answers

What is the load factor of a hash table?

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

What is the main difference between a static array and a dynamic array?

1. AA static array can only store numbers
2. BA dynamic array can grow by moving to a larger block of memory
3. CA static array allows slower index access
4. DA dynamic array stores its elements in linked nodes so it can grow one at a time

What is a weighted graph?

1. AA graph that is stored on disk
2. BA graph with more edges than vertices
3. CA graph in which some vertices are heavier than others because they have more edges
4. DA graph in which each edge has a numeric value such as a cost or distance

A trie (prefix tree) is especially efficient for:

1. APrefix searches such as autocomplete
2. BFinding shortest paths
3. CStoring matrices
4. DSorting numbers

In a circular queue stored in an array of capacity n, how is the next position after index i computed?

1. A(i + 1) mod n
2. B2i + 1
3. C(i − 1) mod n
4. Di + 1

How long does a search for a word of length L take in a trie with a fixed alphabet?

1. AO(n), where n is the number of words
2. BO(L), independent of how many words are stored
3. CO(L × n)
4. DO(log n), where n is the number of words

Under simple uniform hashing, what is the expected time of a search in a hash table with chaining, n keys and m buckets?

1. AO(m)
2. BO(log n)
3. CO(n)
4. DO(1 + α), where α = n / m

In a circular buffer, front == rear can mean either empty or full. What is a common way to tell them apart?

1. AAlways clear the buffer whenever front equals rear, so the state is empty
2. BKeep a separate element count, or always leave one slot unused
3. CStore the front and rear in the same variable
4. DMake the buffer size a power of two