Data structures worksheet with answers

What is the load factor of a hash table?

1. AThe number of buckets divided by the average length of the keys stored
2. BThe number of collisions so far
3. CThe number of stored elements divided by the number of buckets
4. DThe time needed to load the table from disk

In a tree, what is a leaf?

1. AA node with exactly one child
2. BA node with no children
3. CA node with no parent
4. DThe node with the largest value

In a singly linked list, what does the next pointer of the last node contain?

1. AThe address of the first node
2. BNull (no node)
3. CThe number of nodes in the list
4. DThe address of the previous node

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

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

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

How is a new element inserted into a binary heap?

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

How long does it take to search for an arbitrary key in a binary min-heap of n elements?

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

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. A80
2. B60
3. C40
4. D70