Data structures worksheet with answers

Which data structure works on the principle "first in, first out"?

1. AQueue
2. BHeap
3. CStack
4. DBinary tree

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

1. APop
2. BPush
3. CEnqueue
4. DPeek

In an undirected graph, what is the degree of a vertex?

1. AThe number of vertices in the graph
2. BThe length of the longest path from it
3. CThe number of edges connected to it
4. DIts position in the adjacency list

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

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

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

1. A0.5
2. B1
3. C2
4. DThere is no maximum

Which collision resolution method stores colliding keys in a list at the same bucket?

1. ADouble hashing
2. BQuadratic probing
3. CSeparate chaining
4. DLinear probing

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

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