Data structures worksheet with answers

The height of a tree is commonly defined as:

1. AThe total number of nodes in the tree, counting the root and every leaf
2. BThe number of leaves in the tree
3. CThe number of children of the root
4. DThe number of edges on the longest path from the root to a leaf

What is the load factor of a hash table?

1. AThe number of collisions so far
2. BThe time needed to load the table from disk
3. CThe number of stored elements divided by the number of buckets
4. DThe number of buckets divided by the average length of the keys stored

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

1. APush
2. BPeek
3. CEnqueue
4. DPop

How much memory does an adjacency list use for a graph with V vertices and E edges?

1. AO(V × E)
2. BO(V + E)
3. CO(E²)
4. DO(V²)

In a binary heap stored in an array starting at index 0, where is the parent of the node at index i?

1. AAt index ⌊i / 2⌋ + 1
2. BAt index i − 1
3. CAt index ⌊(i − 1) / 2⌋
4. DAt index 2i + 1

In a hash table using open addressing, what is the maximum possible load factor?

1. AThere is no maximum
2. B2
3. C0.5
4. D1

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. BEvery node must be red
3. CThe root must be red
4. DEvery red node must have red children, so red nodes always form unbroken chains to the leaves

Which property keeps every B-tree perfectly balanced?

1. AEach node stores one key
2. BThe keys are stored only in the root
3. CEvery node has exactly two children
4. DAll leaves are at the same depth