Data structures worksheet with answers

What is a deque (double-ended queue)?

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

In a tree, what are sibling nodes?

1. AA node and its parent
2. BNodes at the same depth in different subtrees
3. CNodes that have no children
4. DNodes that share the same parent

The height of a tree is commonly defined as:

1. AThe total number of nodes in the tree, counting the root and every leaf
2. BThe number of children of the root
3. CThe number of leaves in the tree
4. DThe number of edges on the longest path from the root to a leaf

Which data structure is used to check whether the brackets in "{[()]}" are balanced?

1. AA queue
2. BA binary search tree
3. CA hash table
4. DA stack

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

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

Which data structure is used by depth-first search (iterative version)?

1. AA stack
2. BA heap
3. CA hash table only
4. DA queue

A dynamic array doubles when full. Why do many implementations shrink it only when it is one quarter full, not half full?

1. ATo avoid repeated resizing when pushes and pops alternate near the boundary
2. BBecause halving at one half would lose elements
3. CTo keep the array sorted
4. DBecause the memory allocator can only release memory in quarters of a block

Without union by rank or path compression, what is the worst-case cost of a single find in a union-find structure with n elements?

1. AO(1)
2. BO(α(n))
3. CO(n)
4. DO(log n)