Data structures worksheet with answers

In a binary search tree, values in the left subtree of a node are:

1. AEqual to the node's value
2. BSmaller than the node's value
3. CLarger than the node's value
4. DIn random order

In a singly linked list, each node contains:

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

A graph consists of:

1. AOnly a root and leaves
2. BVertices (nodes) connected by edges
3. CKeys and hashes only
4. DRows and columns

A trie (prefix tree) is especially efficient for:

1. AFinding shortest paths
2. BStoring matrices
3. CPrefix searches such as autocomplete
4. DSorting numbers

An application needs fast lookups and also needs to list keys in sorted order and answer range queries. Which structure fits best?

1. AA stack
2. BA hash table
3. CA balanced binary search tree
4. DAn unsorted linked list

You have a reference to a node in the middle of a list. In which list can you remove it in O(1)?

1. AA dynamic array
2. BA doubly linked list
3. CA singly linked list
4. DA sorted array

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(n)
3. CO(log n)
4. DO(1)

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

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