Data structures worksheet with answers

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

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

What is a deque (double-ended queue)?

1. AA structure that allows insertion and removal at both ends
2. BTwo separate queues sharing one array
3. CA queue sorted by priority
4. DA queue that only allows removal at the back

What is the name of the queue operation that removes the element at the front?

1. APush
2. BEnqueue
3. CInsert
4. DDequeue

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

1. A√n
2. Bn (it becomes a linked list)
3. Clog₂ n
4. D1

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

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

How much memory does an adjacency list use for a graph with V vertices and E edges?

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

In a hash table using open addressing, why is deletion often done with a "tombstone" marker?

1. ATombstones speed up hashing
2. BEmptying the slot could break the probe sequence for other keys
3. CIt makes the table sorted
4. DDeleted keys must be kept forever for security, so slots can never be reused

In Kruskal's minimum spanning tree algorithm, what is the union-find structure used for?

1. AChecking whether an edge's two endpoints are already connected
2. BChoosing the starting vertex
3. CStoring each vertex's current distance from the source during the search
4. DSorting the edges by weight