Start learning →

Data Structures: final assessment

This covers the whole course. Take it after the last module.

Final quiz

1. Which Big-O describes binary search on a sorted array?
2. Which structure does a running program use to remember where each function call returns to?
3. How can a loop over a circular linked list know when to stop?
4. A binary tree has 7 nodes, and every level is full. How many leaves does it have?
5. What is the load factor of a hash table?
6. A singly linked list has head and tail pointers. Which operation is still O(n)?
7. What does the postfix expression 8 2 3 * - evaluate to?
8. A circular queue of capacity 6 has front = 4 and count = 3. Where does the next item go?
9. Keys 5, 3, 8 and 4 are inserted into an empty binary search tree. Where is 4?
10. A max-heap is stored as [9, 7, 8, 2, 5]. Which value is the parent of 5?
11. A hash table has 8 buckets and uses hash(key) = key % 8. Which pair of keys collides?
12. A graph has 6 vertices, numbered 0 to 5, and the edges 0–1, 1–2 and 4–5. How many connected components does it have?
13. Which structure can answer how many stored words start with a given prefix, in time that depends only on the length of the prefix?
14. Ten items, numbered 1 to 10, start in separate groups. After the unions (1,2), (3,4), (2,4), (1,3) and (5,6), how many groups are there?
15. An array changes often, and range sums are asked for just as often. Which structure does both in O(log n)?
16. Keys 1, 2, 3, 4 and 5 are inserted in that order into an empty AVL tree. What is its height, counting levels?
17. A program holds a million records and must repeatedly take the one with the earliest deadline, while new records keep arriving. Which structure fits?

Practical assessment: Build a task scheduler

Without using hints, write a program that keeps a set of tasks, each with a name and a priority, and always runs the most urgent one next.

Final project

A city route planner: Build a program that reads a map of cities and roads, and finds the route with the fewest roads between any two cities.

How it is evaluated

To complete this course