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 an undirected graph, what is the degree of a vertex?

  1. AIts position in the adjacency list
  2. BThe length of the longest path from it
  3. CThe number of vertices in the graph
  4. DThe number of edges connected to it
2.Easy

What does a hash function do in a hash table?

  1. AMaps a key to an index in the table
  2. BSorts the keys in the table
  3. CCounts how many keys are stored
  4. DEncrypts the values in the table
3.Easy

Which data structure is most suitable for the "undo" feature in a text editor?

  1. AHash set
  2. BQueue
  3. CGraph
  4. DStack
4.Medium

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

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

How long does a search for a word of length L take in a trie with a fixed alphabet?

  1. AO(L × n)
  2. BO(log n), where n is the number of words
  3. CO(n), where n is the number of words
  4. DO(L), independent of how many words are stored
6.Medium

In a circular queue stored in an array of capacity n, how is the next position after index i computed?

  1. Ai + 1
  2. B(i − 1) mod n
  3. C2i + 1
  4. D(i + 1) mod n
7.Hard

Which structure lets you compute the maximum of every window of size k in an array in O(n) total?

  1. AA sorted array updated by shifting
  2. BA min-heap rebuilt for every window
  3. CA singly linked list of the window's elements
  4. DA deque holding indices in decreasing order of value
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(n) time and O(1) extra space
  3. CO(1) time and O(1) extra space
  4. DO(n log n) time and O(1) extra space

Answer key

  1. 1. D · The number of edges connected to it
  2. 2. A · Maps a key to an index in the table
  3. 3. D · Stack
  4. 4. C · O(log n)
  5. 5. D · O(L), independent of how many words are stored
  6. 6. D · (i + 1) mod n
  7. 7. D · A deque holding indices in decreasing order of value
  8. 8. B · O(n) time and O(1) extra space

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