Data structures worksheet with answers

What does the peek (or top) operation on a stack do?

1. AReturns the bottom element of the stack
2. BRemoves the top element and returns it
3. CReturns the top element without removing it
4. DRemoves all elements from the stack

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

1. ALeft subtree, then right subtree, then node
2. BNode, then left subtree, then right subtree
3. CLeft subtree, then node, then right subtree
4. DLevel by level from the top

What is a directed graph?

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

How many nodes does a perfect binary tree of height h have, with height counted in edges?

1. A2^h
2. B2^h+1 − 1
3. Ch²
4. D2h + 1

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

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

In a hash table using open addressing, what is the maximum possible load factor?

1. A1
2. B0.5
3. C2
4. DThere is no maximum

Which data structure supports an LRU (least recently used) cache with O(1) get and put?

1. AA hash map combined with a doubly linked list
2. BA stack only
3. CA single sorted array
4. DA binary search tree only

An object is stored as a key in a hash map, and then a field used by its hash function is changed. What is the likely result?

1. AThe map throws an error at the moment the field changes
2. BLooking up the object may fail because it sits in the bucket for its old hash
3. CNothing changes, because a key's hash is computed only once when the program starts
4. DThe map automatically moves the key to its new bucket