Data structures worksheet with answers

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

In which order does a preorder traversal of a binary tree visit nodes?

1. ALevel by level from the top
2. BLeft subtree, then right subtree, then node
3. CLeft subtree, then node, then right subtree
4. DNode, then left subtree, then right subtree

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

1. AInserting at the beginning
2. BReading the last element by index
3. CAccessing the 5th element
4. DFinding the length of a fixed array

Why can a binary heap be stored in an array without any pointers?

1. AHeaps never contain more than 100 elements
2. BIt is a complete binary tree, so positions follow simple index formulas
3. CAll keys in a heap are equal
4. DArrays automatically keep the keys in sorted order, so no pointers are needed

Which data structure does a running program use to keep track of active function calls and their local variables?

1. AThe heap memory queue
2. BA hash table of functions
3. CThe call stack
4. DA binary search tree of frames

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. C1
4. Dlog₂ n

Deleting a node with two children from a binary search tree is usually done by:

1. ARemoving the whole subtree
2. BReplacing it with its in-order successor (or predecessor) and deleting that node
3. CRebuilding the subtree below it from scratch and reinserting every key it contained
4. DSwapping it with the root

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

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