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

In a singly linked list, what does the next pointer of the last node contain?

  1. AThe address of the previous node
  2. BThe number of nodes in the list
  3. CNull (no node)
  4. DThe address of the first node
2.Easy

The depth of a node in a tree is:

  1. AThe number of nodes in its subtree
  2. BThe number of edges from the root to that node
  3. CThe number of edges from that node to the deepest leaf
  4. DThe number of children of that node
3.Easy

What is the main difference between a static array and a dynamic array?

  1. AA dynamic array stores its elements in linked nodes so it can grow one at a time
  2. BA dynamic array can grow by moving to a larger block of memory
  3. CA static array allows slower index access
  4. DA static array can only store numbers
4.Medium

A trie (prefix tree) is especially efficient for:

  1. AFinding shortest paths
  2. BStoring matrices
  3. CPrefix searches such as autocomplete
  4. DSorting numbers
5.Medium

What is the time complexity of searching for a key in a balanced binary search tree?

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

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

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

The union-find (disjoint set) structure with union by rank and path compression has an amortised cost per operation of:

  1. AO(α(n)), the inverse Ackermann function, which is practically constant
  2. BO(log n) exactly
  3. CO(n²)
  4. DO(n)
8.Hard

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

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

Answer key

  1. 1. C · Null (no node)
  2. 2. B · The number of edges from the root to that node
  3. 3. B · A dynamic array can grow by moving to a larger block of memory
  4. 4. C · Prefix searches such as autocomplete
  5. 5. A · O(log n)
  6. 6. C · O(V²)
  7. 7. A · O(α(n)), the inverse Ackermann function, which is practically constant
  8. 8. C · Possible false positives but no false negatives

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