Data structures worksheet with answers

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

1. AEnqueue
2. BPush
3. CPeek
4. DPop

What is a deque (double-ended queue)?

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

In an adjacency list representation of a graph, what is stored for each vertex?

1. AThe shortest path to every other vertex
2. BThe total number of edges in the graph
3. CA list of its neighbouring vertices
4. DA row of V Boolean values

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

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

What is the worst-case height of a binary search tree with n nodes if keys are inserted in sorted order?

1. A√n
2. Bn (it becomes a linked list)
3. C1
4. Dlog₂ n

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

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

How can you detect whether a singly linked list contains a cycle using O(1) extra memory?

1. ACount the nodes until the count exceeds the list length field
2. BMove one pointer by one step and another by two steps and check whether they meet
3. CSort the list and look for duplicates
4. DStore every visited node in a hash set

What does a splay tree do after each access?

1. ARebuilds the whole tree in balanced form
2. BRotates the accessed node up to the root
3. CRecolours the nodes on the search path
4. DMoves the accessed node to a leaf