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. ANull (no node)
  2. BThe address of the previous node
  3. CThe address of the first node
  4. DThe number of nodes in the list
2.Easy

How many edges does a tree with n nodes have?

  1. A2n
  2. Bn
  3. Cn + 1
  4. Dn − 1
3.Easy

In an adjacency list representation of a graph, what is stored for each vertex?

  1. AA list of its neighbouring vertices
  2. BThe shortest path to every other vertex
  3. CThe total number of edges in the graph
  4. DA row of V Boolean values
4.Medium

What is the value of the postfix expression 3 4 + 2 * ?

  1. A14
  2. B10
  3. C24
  4. D11
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 i − 1
  3. CAt index 2i + 1
  4. DAt index ⌊(i − 1) / 2⌋
6.Medium

Why can a binary heap be stored in an array without any pointers?

  1. AArrays automatically keep the keys in sorted order, so no pointers are needed
  2. BAll keys in a heap are equal
  3. CIt is a complete binary tree, so positions follow simple index formulas
  4. DHeaps never contain more than 100 elements
7.Hard

For each element of an array you want the next greater element to its right, in O(n) total time. Which structure helps?

  1. AA binary search tree rebuilt for each element
  2. BA hash table of all elements
  3. CA stack that keeps elements waiting for their answer
  4. DA queue that holds every pair of elements
8.Hard

What are the time and extra space costs of reversing a singly linked list in place?

  1. AO(n) time and O(n) extra space
  2. BO(1) time and O(1) extra space
  3. CO(n) time and O(1) extra space
  4. DO(n log n) time and O(1) extra space

Answer key

  1. 1. A · Null (no node)
  2. 2. D · n − 1
  3. 3. A · A list of its neighbouring vertices
  4. 4. A · 14
  5. 5. D · At index ⌊(i − 1) / 2⌋
  6. 6. C · It is a complete binary tree, so positions follow simple index formulas
  7. 7. C · A stack that keeps elements waiting for their answer
  8. 8. C · O(n) time and O(1) extra space

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