Data structures worksheet with answers

The depth of a node in a tree is:

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

In a binary search tree, values in the left subtree of a node are:

1. ASmaller than the node's value
2. BLarger than the node's value
3. CEqual to the node's value
4. DIn random order

A graph consists of:

1. AVertices (nodes) connected by edges
2. BKeys and hashes only
3. CRows and columns
4. DOnly a root and leaves

A queue is implemented with two stacks: push onto an "in" stack, and pop from an "out" stack, refilling it from "in" when empty. What is the amortised cost per operation?

1. AO(log n)
2. BO(n²)
3. CO(1)
4. DO(n)

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

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

An adjacency matrix for a graph with V vertices uses how much memory?

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

Why do databases often use B+ trees rather than plain B-trees for indexes?

1. AB+ trees use binary internal nodes, which reduces the number of disk reads
2. BAll records are in linked leaves, which makes range scans efficient
3. CB+ trees store data only in the root
4. DB+ trees do not need to be balanced

The keys 5, 3, 8, 1 are inserted in this order into an empty array-based binary min-heap. What is the final array?

1. A[1, 3, 8, 5]
2. B[3, 1, 8, 5]
3. C[1, 5, 8, 3]
4. D[1, 3, 5, 8]