Data structures worksheet with answers

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

1. ALeft subtree, then right subtree, then node
2. BRight subtree, then node, then left subtree
3. CNode, then left subtree, then right subtree
4. DLeft subtree, then node, then right subtree

In a graph, what is a cycle?

1. AAn edge with a weight of zero
2. BA vertex with no edges
3. CA path that visits every vertex
4. DA path that starts and ends at the same vertex

Which operation is slow in an array but fast at the head of a linked list?

1. AReading the last element by index
2. BFinding the length of a fixed array
3. CAccessing the 5th element
4. DInserting at the beginning

Which abstract data type does Dijkstra's algorithm use to choose the next vertex to process?

1. AA stack
2. BA FIFO queue
3. CA min-priority queue
4. DA set with no ordering

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

1. Ah²
2. B2h + 1
3. C2^h+1 − 1
4. D2^h

How long does it take to check whether the edge (u, v) exists using an adjacency matrix?

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

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 need no rebalancing
3. CThey use less memory than any array, so the entire index always fits in main memory
4. DThey store data unsorted

What is the main advantage of a skip list over a sorted linked list?

1. AIt stores keys without order
2. BIt uses no extra memory
3. CGuaranteed O(1) search because every node stores a pointer to every other node
4. DExpected O(log n) search by using several levels of forward pointers