Data structures worksheet with answers

The depth of a node in a tree is:

1. AThe number of edges from that node to the deepest leaf
2. BThe number of edges from the root to that node
3. CThe number of nodes in its subtree
4. DThe number of children of that node

What is the defining feature of a set as an abstract data type?

1. AIt stores elements in sorted order
2. BIt stores elements without duplicates
3. CIt stores key-value pairs
4. DIt allows access only at one end

In a singly linked list, what does the next pointer of the last node contain?

1. AThe address of the previous node
2. BThe number of nodes in the list
3. CThe address of the first node
4. DNull (no node)

A binary tree has root 1 with left child 2 and right child 3; node 2 has children 4 (left) and 5 (right). What is the preorder traversal?

1. A4 2 5 1 3
2. B1 2 4 5 3
3. C1 2 3 4 5
4. D4 5 2 3 1

An application needs fast lookups and also needs to list keys in sorted order and answer range queries. Which structure fits best?

1. AA hash table
2. BA balanced binary search tree
3. CA stack
4. DAn unsorted linked list

How many nodes does a perfect binary tree of height h have, with height counted in edges?

1. A2^h
2. B2h + 1
3. C2^h+1 − 1
4. Dh²

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. A60
2. B80
3. C70
4. D40

You must keep the k smallest values from a stream of n numbers using O(k) memory. Which approach works in O(n log k) time?

1. AA FIFO queue of the last k values
2. BA min-heap holding all n values, from which the k smallest are popped at the end
3. CA max-heap of size k, replacing its root when a smaller value arrives
4. DA sorted array of all n values