Data structures worksheet with answers

A graph consists of:

1. ARows and columns
2. BOnly a root and leaves
3. CVertices (nodes) connected by edges
4. DKeys and hashes only

What is a directed graph?

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

What is the main difference between a static array and a dynamic array?

1. AA dynamic array stores its elements in linked nodes so it can grow one at a time
2. BA static array allows slower index access
3. CA dynamic array can grow by moving to a larger block of memory
4. DA static array can only store numbers

A queue is implemented with two stacks: push onto an "in" stack, and pop from an "out" stack, refilling it from "in" when empty. What is the amortised cost per operation?

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

Which data structure is used to check whether the brackets in "{[()]}" are balanced?

1. AA stack
2. BA queue
3. CA binary search tree
4. DA hash table

How do you find the minimum key in a binary search tree?

1. ALook at the root only
2. BFollow right children from the root until there is no right child
3. CFollow left children from the root until there is no left child
4. DVisit every leaf and compare them

The union-find (disjoint set) structure with union by rank and path compression has an amortised cost per operation of:

1. AO(n²)
2. BO(log n) exactly
3. CO(n)
4. DO(α(n)), the inverse Ackermann function, which is practically constant

Which problem of linear probing does double hashing mainly reduce?

1. AThe need for a hash function
2. BThe O(n) cost of reading a key's value
3. CPrimary clustering, where long runs of occupied slots form
4. DThe need to store keys in the table