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

What is a weighted graph?

  1. AA graph in which each edge has a numeric value such as a cost or distance
  2. BA graph with more edges than vertices
  3. CA graph in which some vertices are heavier than others because they have more edges
  4. DA graph that is stored on disk
2.Easy

Which structure is typically used to implement a priority queue?

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

What is a directed graph?

  1. AA graph whose edges all have weights
  2. BA graph whose edges have a direction from one vertex to another
  3. CA graph that has no cycles
  4. DA graph in which every pair of distinct vertices is joined by an edge
4.Medium

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

  1. A14
  2. B24
  3. C10
  4. D11
5.Medium

Why is traversing an array often much faster in practice than traversing a linked list of the same length?

  1. ALinked lists always store elements on disk
  2. BArray traversal is O(1) in total, while linked list traversal is O(n)
  3. CArrays use fewer instructions to compare values
  4. DArray elements are contiguous, so they make good use of the CPU cache
6.Medium

How is a new element inserted into a binary heap?

  1. ARebuild the whole heap from scratch
  2. BPlace it at the root and sift it down
  3. CPlace it at the end of the array and sift it up while it violates the heap property
  4. DInsert it at its sorted position by shifting all of the larger elements one place right
7.Hard

Why might a server choose its hash function at random from a universal family?

  1. ATo guarantee that no two keys can ever collide, whatever keys an attacker sends
  2. BTo make the hash table sorted
  3. CTo remove the need to resize the table
  4. DTo make it very unlikely that an attacker can pick many keys that all collide
8.Hard

Kahn's algorithm for topological sorting repeatedly removes vertices with in-degree 0. Which structure holds those vertices?

  1. AA max-heap ordered by out-degree
  2. BA stack of all visited edges
  3. CAn adjacency matrix recording which vertices have already been removed
  4. DA queue (or any collection) of vertices whose in-degree is 0

Answer key

  1. 1. A · A graph in which each edge has a numeric value such as a cost or distance
  2. 2. A · A heap
  3. 3. B · A graph whose edges have a direction from one vertex to another
  4. 4. A · 14
  5. 5. D · Array elements are contiguous, so they make good use of the CPU cache
  6. 6. C · Place it at the end of the array and sift it up while it violates the heap property
  7. 7. D · To make it very unlikely that an attacker can pick many keys that all collide
  8. 8. D · A queue (or any collection) of vertices whose in-degree is 0

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