Data structures worksheet with answers

What is a directed graph?

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

What is the name of the stack operation that adds an element to the top?

1. APop
2. BPush
3. CPeek
4. DEnqueue

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

1. AQueue
2. BBinary tree
3. CStack
4. DHeap

How is a new element inserted into a binary heap?

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

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

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

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/2 and i/2 + 1
2. Bi + 1 and i + 2
3. C2i and 2i + 1
4. D2i + 1 and 2i + 2

The time complexity of decrease-key in a binary heap (given the element's position) is:

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

Why do databases often use B+ trees rather than plain B-trees for indexes?

1. AAll records are in linked leaves, which makes range scans efficient
2. BB+ trees do not need to be balanced
3. CB+ trees use binary internal nodes, which reduces the number of disk reads
4. DB+ trees store data only in the root