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, each node contains:

  1. AData and references to all other nodes
  2. BOnly data
  3. CData and a reference to the next node
  4. DData and an index
2.Easy

What does the peek (or top) operation on a stack do?

  1. AReturns the bottom element of the stack
  2. BRemoves all elements from the stack
  3. CRemoves the top element and returns it
  4. DReturns the top element without removing it
3.Easy

A graph consists of:

  1. AKeys and hashes only
  2. BRows and columns
  3. CVertices (nodes) connected by edges
  4. DOnly a root and leaves
4.Medium

A node in a binary search tree has a right subtree. Where is its in-order successor?

  1. AThe leftmost node of its right subtree
  2. BIts right child, always
  3. CIts parent, always
  4. DThe rightmost node of its left subtree
5.Medium

What is the purpose of a sentinel (dummy) node in a linked list?

  1. ATo prevent the list from growing beyond a fixed maximum number of nodes
  2. BTo make the list sorted
  3. CTo simplify code by removing special cases at the head or tail
  4. DTo store the number of elements
6.Medium

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

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

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

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

How does a radix tree (compressed trie) improve on a plain trie?

  1. AIt sorts the children of each node by frequency
  2. BIt stores each word in a hash table at the root instead of in separate nodes
  3. CIt keeps only the first letter of each word
  4. DIt merges chains of single-child nodes into one edge labelled with a string

Answer key

  1. 1. C · Data and a reference to the next node
  2. 2. D · Returns the top element without removing it
  3. 3. C · Vertices (nodes) connected by edges
  4. 4. A · The leftmost node of its right subtree
  5. 5. C · To simplify code by removing special cases at the head or tail
  6. 6. B · Array elements are contiguous, so they make good use of the CPU cache
  7. 7. D · To make it very unlikely that an attacker can pick many keys that all collide
  8. 8. D · It merges chains of single-child nodes into one edge labelled with a string

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