Data structures worksheet with answers

Which operation is O(1) for an array but O(n) for a singly linked list?

1. AAccessing the element at index i
2. BReading the first element
3. CInserting at the head
4. DRemoving the head element

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

Which data structure is used to perform a level-order traversal of a tree?

1. AHash table
2. BQueue
3. CPriority queue
4. DStack

How long does it take to check whether the edge (u, v) exists using an adjacency matrix?

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

A circular buffer (ring buffer) is commonly used to implement:

1. AA binary search tree
2. BA graph traversal
3. CA hash function
4. DA fixed-size queue

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

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

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

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

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