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 graph, what is a cycle?

  1. AA vertex with no edges
  2. BA path that starts and ends at the same vertex
  3. CAn edge with a weight of zero
  4. DA path that visits every vertex
2.Easy

The depth of a node in a tree is:

  1. AThe number of children of that node
  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 nodes in its subtree
3.Easy

What is the load factor of a hash table?

  1. AThe number of stored elements divided by the number of buckets
  2. BThe time needed to load the table from disk
  3. CThe number of collisions so far
  4. DThe number of buckets divided by the average length of the keys stored
4.Medium

A road network has 100,000 junctions, each connected to about 4 others. Which representation is most suitable?

  1. AA binary heap of edges
  2. BAdjacency matrix
  3. CA single sorted array of vertices
  4. DAdjacency list
5.Medium

What happens when a hash table rehashes after its load factor exceeds a threshold?

  1. AOnly the colliding keys are moved to a new overflow list at the end of the table
  2. BThe existing keys are sorted in place
  3. CA larger table is allocated and every key is inserted again
  4. DThe oldest keys are deleted to make room
6.Medium

How is a new element inserted into a binary heap?

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

Without union by rank or path compression, what is the worst-case cost of a single find in a union-find structure with n elements?

  1. AO(n)
  2. BO(1)
  3. CO(α(n))
  4. DO(log n)
8.Hard

A dynamic array doubles when full. Why do many implementations shrink it only when it is one quarter full, not half full?

  1. ABecause halving at one half would lose elements
  2. BTo keep the array sorted
  3. CTo avoid repeated resizing when pushes and pops alternate near the boundary
  4. DBecause the memory allocator can only release memory in quarters of a block

Answer key

  1. 1. B · A path that starts and ends at the same vertex
  2. 2. B · The number of edges from the root to that node
  3. 3. A · The number of stored elements divided by the number of buckets
  4. 4. D · Adjacency list
  5. 5. C · A larger table is allocated and every key is inserted again
  6. 6. B · Place it at the end of the array and sift it up while it violates the heap property
  7. 7. A · O(n)
  8. 8. C · To avoid repeated resizing when pushes and pops alternate near the boundary

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