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 children of that node
3. CThe number of edges from the root to that node
4. DThe number of edges from that node to the deepest leaf

Which data structure works on the principle "last in, first out"?

1. AQueue
2. BLinked list
3. CHash table
4. DStack

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

1. ALeft subtree, then node, then right subtree
2. BLeft subtree, then right subtree, then node
3. CRight subtree, then node, then left subtree
4. DNode, then left subtree, then right subtree

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. A1 2 4 5 3
2. B1 2 3 4 5
3. C4 2 5 1 3
4. D4 5 2 3 1

Why can a binary heap be stored in an array without any pointers?

1. AHeaps never contain more than 100 elements
2. BArrays automatically keep the keys in sorted order, so no pointers are needed
3. CIt is a complete binary tree, so positions follow simple index formulas
4. DAll keys in a heap are equal

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

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

A Bloom filter can answer "is this element in the set?" with:

1. APossible false positives but no false negatives
2. BAnswers only for numbers
3. CPossible false negatives but no false positives
4. DExact answers always

Why are B-trees used in databases and file systems?

1. ATheir high branching factor keeps the tree shallow, reducing slow disk reads
2. BThey use less memory than any array, so the entire index always fits in main memory
3. CThey need no rebalancing
4. DThey store data unsorted