Data structures worksheet with answers

Which structure is typically used to implement a priority queue?

1. AA heap
2. BA stack
3. CA string
4. DA singly linked list without order

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

1. ARemoving the head element
2. BReading the first element
3. CAccessing the element at index i
4. DInserting at the head

What is a deque (double-ended queue)?

1. AA queue sorted by priority
2. BA structure that allows insertion and removal at both ends
3. CTwo separate queues sharing one array
4. DA queue that only allows removal at the back

A road network has 100,000 junctions, each connected to about 4 others. Which representation is most suitable?

1. AAdjacency matrix
2. BAdjacency list
3. CA single sorted array of vertices
4. DA binary heap of edges

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

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

A trie (prefix tree) is especially efficient for:

1. AFinding shortest paths
2. BPrefix searches such as autocomplete
3. CSorting numbers
4. DStoring matrices

Which property keeps every B-tree perfectly balanced?

1. AThe keys are stored only in the root
2. BEvery node has exactly two children
3. CAll leaves are at the same depth
4. DEach node stores one key

Why do databases often use B+ trees rather than plain B-trees for indexes?

1. AAll records are in linked leaves, which makes range scans efficient
2. BB+ trees use binary internal nodes, which reduces the number of disk reads
3. CB+ trees store data only in the root
4. DB+ trees do not need to be balanced