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. CA node and its parent
4. DNodes at the same depth in different subtrees

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

1. ARight subtree, then node, then left subtree
2. BLeft subtree, then node, then right subtree
3. CLeft subtree, then right subtree, then node
4. DNode, then left subtree, then right subtree

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

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

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

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

In a binary min-heap stored in an array (index starting at 0), the children of the node at index i are at:

1. A2i and 2i + 1
2. Bi/2 and i/2 + 1
3. C2i + 1 and 2i + 2
4. Di + 1 and i + 2

What is the cost of inserting an element in the middle of an array of n elements?

1. AO(log n), because of binary search
2. BO(n²), because each element moves n times
3. CO(n), because later elements must shift
4. DO(1), because the index is known

Which property must a red-black tree satisfy?

1. AEvery path from a node to its descendant leaves has the same number of black nodes
2. BThe root must be red
3. CEvery red node must have red children, so red nodes always form unbroken chains to the leaves
4. DEvery node must be red

In the BST with root 50, left subtree 30 (children 20, 40) and right subtree 70 (children 60, 80), the root is deleted using the in-order successor. Which key becomes the new root?

1. A80
2. B40
3. C60
4. D70