Data structures worksheet with answers

What does each node in a doubly linked list contain?

1. AData and a pointer to the next node only
2. BData, a pointer to the next node and a pointer to the previous node
3. CData and two pointers, one to the next node and one to the node after that
4. DTwo copies of the data and one pointer

What is the defining feature of a set as an abstract data type?

1. AIt stores key-value pairs
2. BIt stores elements without duplicates
3. CIt stores elements in sorted order
4. DIt allows access only at one end

In a tree, what are sibling nodes?

1. ANodes that share the same parent
2. BNodes at the same depth in different subtrees
3. CNodes that have no children
4. DA node and its parent

What is true of the adjacency matrix of an undirected graph?

1. AIts main diagonal always contains ones
2. BIt is always upper triangular
3. CEach row has exactly one 1
4. DIt is symmetric about the main diagonal

In a binary min-heap stored in an array (index starting at 0), the children of the node at index i are at:

1. Ai + 1 and i + 2
2. B2i and 2i + 1
3. Ci/2 and i/2 + 1
4. D2i + 1 and 2i + 2

An in-order traversal of a binary search tree visits the keys in:

1. AInsertion order
2. BDescending order always
3. CLevel order
4. DAscending sorted order

A Fenwick tree (binary indexed tree) over an array of n numbers supports which operations in O(log n)?

1. ASorting the array and binary search
2. BPrefix-sum queries and single-element updates
3. CFinding the median in O(1)
4. DInserting elements at any position

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

1. AIt stores each word in a hash table at the root instead of in separate nodes
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 keeps only the first letter of each word