Data structures worksheet with answers

In a tree, what is a leaf?

1. AA node with no children
2. BThe node with the largest value
3. CA node with exactly one child
4. DA node with no parent

What is the name of the stack operation that adds an element to the top?

1. APop
2. BPush
3. CPeek
4. DEnqueue

What is a directed graph?

1. AA graph in which every pair of distinct vertices is joined by an edge
2. BA graph that has no cycles
3. CA graph whose edges all have weights
4. DA graph whose edges have a direction from one vertex to another

AVL trees and red-black trees guarantee:

1. AThat no node has two children
2. BThat keys are stored in insertion order
3. CConstant-time search in every case
4. DO(log n) height through rebalancing

A node in a binary search tree has a right subtree. Where is its in-order successor?

1. AIts parent, always
2. BThe leftmost node of its right subtree
3. CIts right child, always
4. DThe rightmost node of its left subtree

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

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

Inserting a key into an AVL tree makes a node's left subtree too tall, and the new key went into the left subtree of its left child (left-left case). Which fix is applied?

1. AA single left rotation at the unbalanced node
2. BA left rotation at the child, then a right rotation at the node
3. CRecolouring the node and its child
4. DA single right rotation at the unbalanced node

Which problem of linear probing does double hashing mainly reduce?

1. AThe O(n) cost of reading a key's value
2. BThe need for a hash function
3. CThe need to store keys in the table
4. DPrimary clustering, where long runs of occupied slots form