Data structures worksheet with answers

What does each node in a doubly linked list contain?

1. AData, a pointer to the next node and a pointer to the previous node
2. BData and two pointers, one to the next node and one to the node after that
3. CTwo copies of the data and one pointer
4. DData and a pointer to the next node only

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 time needed to load the table from disk
3. CThe number of stored elements divided by the number of buckets
4. DThe number of collisions so far

What is a directed graph?

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

In a binary heap stored in an array starting at index 0, where is the parent of the node at index i?

1. AAt index ⌊i / 2⌋ + 1
2. BAt index ⌊(i − 1) / 2⌋
3. CAt index 2i + 1
4. DAt index i − 1

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

1. ALevel order
2. BInsertion order
3. CDescending order always
4. DAscending sorted order

Which abstract data type does Dijkstra's algorithm use to choose the next vertex to process?

1. AA stack
2. BA FIFO queue
3. CA min-priority queue
4. DA set with no ordering

Which problem of linear probing does double hashing mainly reduce?

1. AThe need for a hash function
2. BThe O(n) cost of reading a key's value
3. CPrimary clustering, where long runs of occupied slots form
4. DThe need to store keys in the table

What are the time and extra space costs of reversing a singly linked list in place?

1. AO(n log n) time and O(1) extra space
2. BO(1) time and O(1) extra space
3. CO(n) time and O(1) extra space
4. DO(n) time and O(n) extra space