Data structures worksheet with answers

Which data structure works on the principle "first in, first out"?

1. ABinary tree
2. BStack
3. CHeap
4. DQueue

In a tree, what are sibling nodes?

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

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 allows access only at one end
4. DIt stores elements in sorted order

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

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

What is the worst-case height of a binary search tree with n nodes if keys are inserted in sorted order?

1. Alog₂ n
2. B1
3. Cn (it becomes a linked list)
4. D√n

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 singly linked list
2. BA sorted array
3. CA doubly linked list
4. DA dynamic array

In the BST with root 50, left subtree 30 (children 20, 40) and right subtree 70 (children 60, 80), the root is deleted using the in-order successor. Which key becomes the new root?

1. A60
2. B40
3. C80
4. D70

An object is stored as a key in a hash map, and then a field used by its hash function is changed. What is the likely result?

1. ANothing changes, because a key's hash is computed only once when the program starts
2. BThe map automatically moves the key to its new bucket
3. CLooking up the object may fail because it sits in the bucket for its old hash
4. DThe map throws an error at the moment the field changes