Data structures worksheet with answers

Which structure is typically used to implement a priority queue?

1. AA heap
2. BA singly linked list without order
3. CA string
4. DA stack

What is the root of a tree?

1. AThe top node with no parent
2. BThe node with the largest value
3. CA node with no children
4. DAny node in the middle

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

1. ALinked list
2. BHash table
3. CQueue
4. DStack

How is a new element inserted into a binary heap?

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

What is the time complexity of searching for a key in a balanced binary search tree?

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

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

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

Which property keeps every B-tree perfectly balanced?

1. AThe keys are stored only in the root
2. BEach node stores one key
3. CAll leaves are at the same depth
4. DEvery node has exactly two children

Deleting a node with two children from a binary search tree is usually done by:

1. ARemoving the whole subtree
2. BReplacing it with its in-order successor (or predecessor) and deleting that node
3. CRebuilding the subtree below it from scratch and reinserting every key it contained
4. DSwapping it with the root