Data structures worksheet with answers

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

1. ABinary tree
2. BQueue
3. CStack
4. DHeap

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

1. AHash table
2. BStack
3. CLinked list
4. DQueue

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. CTwo copies of the data and one pointer
4. DData and two pointers, one to the next node and one to the node after that

A hash table of size 7 uses h(k) = k mod 7 and linear probing. After inserting 10, where is 17 stored?

1. AIndex 3
2. BIndex 0
3. CIndex 6
4. DIndex 4

Why can a binary heap be stored in an array without any pointers?

1. AAll keys in a heap are equal
2. BIt is a complete binary tree, so positions follow simple index formulas
3. CArrays automatically keep the keys in sorted order, so no pointers are needed
4. DHeaps never contain more than 100 elements

A binary tree has root 1 with left child 2 and right child 3; node 2 has children 4 (left) and 5 (right). What is the postorder traversal?

1. A4 2 5 1 3
2. B4 5 2 3 1
3. C5 4 3 2 1
4. D1 2 4 5 3

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

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

Why are B-trees used in databases and file systems?

1. AThey use less memory than any array, so the entire index always fits in main memory
2. BThey store data unsorted
3. CTheir high branching factor keeps the tree shallow, reducing slow disk reads
4. DThey need no rebalancing