Data structures worksheet with answers

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

1. ANode, then left subtree, then right subtree
2. BLeft subtree, then right subtree, then node
3. CRight subtree, then node, then left subtree
4. DLeft subtree, then node, then right subtree

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

1. APeek
2. BPush
3. CEnqueue
4. DPop

Which structure is typically used to implement a priority queue?

1. AA singly linked list without order
2. BA heap
3. CA stack
4. DA string

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

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

AVL trees and red-black trees guarantee:

1. AThat keys are stored in insertion order
2. BO(log n) height through rebalancing
3. CConstant-time search in every case
4. DThat no node has two children

The keys 50, 30, 70, 20, 40 are inserted in this order into an empty binary search tree. What is the left child of 30?

1. A70
2. B50
3. C20
4. D40

What is the running time of breadth-first search on a graph with V vertices stored as an adjacency matrix?

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

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

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