Data structures worksheet with answers

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

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

In which order does a preorder traversal of a binary tree visit nodes?

1. ALevel by level from the top
2. BLeft subtree, then right subtree, then node
3. CNode, then left subtree, then right subtree
4. DLeft subtree, then node, then right subtree

What is the load factor of a hash table?

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

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

An in-order traversal of a binary search tree visits the keys in:

1. ALevel order
2. BDescending order always
3. CAscending sorted order
4. DInsertion order

In a circular queue stored in an array of capacity n, how is the next position after index i computed?

1. A(i − 1) mod n
2. Bi + 1
3. C(i + 1) mod n
4. D2i + 1

Why can elements not simply be deleted from a standard Bloom filter by clearing their bits?

1. ABits in a Bloom filter cannot be changed after creation
2. BDeleting would increase the false positive rate to 100%
3. CThose bits may also belong to other elements, which would cause false negatives
4. DBloom filters store the full elements, and these cannot be located again once hashed

An AVL node is unbalanced because its left child's right subtree became too tall (left-right case). Which fix is applied?

1. AA right rotation at the left child, then a left rotation at the node
2. BA left rotation at the left child, then a right rotation at the node
3. CA single left rotation at the node
4. DA single right rotation at the node