Data structures worksheet with answers

In a tree, what are sibling nodes?

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

In an undirected graph, what is the degree of a vertex?

1. AThe number of edges connected to it
2. BThe length of the longest path from it
3. CIts position in the adjacency list
4. DThe number of vertices in the graph

How are the elements of an array stored in memory?

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

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

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

How does extract-min work in a binary min-heap?

1. ARemove the root and shift all elements one place left
2. BSearch all leaves for the new minimum
3. CRemove the last element of the array
4. DMove the last element to the root and sift it down

A queue is implemented with two stacks: push onto an "in" stack, and pop from an "out" stack, refilling it from "in" when empty. What is the amortised cost per operation?

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

A segment tree is typically used to:

1. AAnswer range queries (such as range sums) and updates in O(log n)
2. BImplement a stack
3. CSort strings alphabetically by storing each prefix in a separate tree node
4. DStore a graph's edges

Why are B-trees used in databases and file systems?

1. ATheir high branching factor keeps the tree shallow, reducing slow disk reads
2. BThey use less memory than any array, so the entire index always fits in main memory
3. CThey store data unsorted
4. DThey need no rebalancing