Data structures worksheet with answers

Free printable Data structures worksheet: 8 problems from easy to exam level, with an answer key. Print it or save it as a PDF.

New worksheetPractise online with hints

For teachers: free to print, copy and use in class. Every new worksheet has new values and its own answer key. A link to ExamProblems on your course page is appreciated.

Name: ____________________   Date: ____________

1.Easy

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

  1. AInserting at the beginning
  2. BAccessing the 5th element
  3. CReading the last element by index
  4. DFinding the length of a fixed array
2.Easy

What does a map (dictionary) store?

  1. APairs of equal keys
  2. BKey-value pairs with unique keys
  3. CValues sorted by size
  4. DOnly values in insertion order
3.Easy

What is the max-heap property?

  1. AThe keys are sorted from left to right
  2. BAll leaves contain the maximum key
  3. CEvery left child's key is greater than or equal to its right sibling's key
  4. DEvery parent's key is greater than or equal to its children's keys
4.Medium

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(1)
  2. BO(n)
  3. CO(log n)
  4. DO(n²)
5.Medium

In a binary heap stored in an array starting at index 0, where is the parent of the node at index i?

  1. AAt index ⌊i / 2⌋ + 1
  2. BAt index 2i + 1
  3. CAt index i − 1
  4. DAt index ⌊(i − 1) / 2⌋
6.Medium

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. B40
  3. C50
  4. D20
7.Hard

A segment tree is typically used to:

  1. AAnswer range queries (such as range sums) and updates in O(log n)
  2. BStore a graph's edges
  3. CSort strings alphabetically by storing each prefix in a separate tree node
  4. DImplement a stack
8.Hard

The time complexity of decrease-key in a binary heap (given the element's position) is:

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

Answer key

  1. 1. A · Inserting at the beginning
  2. 2. B · Key-value pairs with unique keys
  3. 3. D · Every parent's key is greater than or equal to its children's keys
  4. 4. A · O(1)
  5. 5. D · At index ⌊(i − 1) / 2⌋
  6. 6. D · 20
  7. 7. A · Answer range queries (such as range sums) and updates in O(log n)
  8. 8. A · O(log n)

Full step-by-step solutions: practise this topic on examproblems.com.