Fundamentals of ADTs practice questions.

A queue is implemented in an array of 8 places. After many enqueue and dequeue operations the rear has reached place 7 while places 0 to 6 are free. Which technique stores the next item without moving any data?

• Copying the whole array into a new array that has 16 places.
• Treating the array as circular, so that place 0 follows place 7.
• Sorting the array so that the places in use lie at the front.
• Exchanging the front pointer and the rear pointer with each other.

Answer: Treating the array as circular, so that place 0 follows place 7.

Wrapping the rear round to index 0 reuses the places that dequeue has freed, which is why a queue held in an array is normally built as a circular buffer. Copying or sorting would also work but costs time in proportion to the number of items stored.

Which statement is true of a doubly linked list but not of a singly linked list?

• Each node stores one data item together with a link field.
• The final node of the list stores a null value in its link.
• Any node can be reached from either of its two neighbours.
• The structure grows and shrinks while the program is running.

Answer: Any node can be reached from either of its two neighbours.

A second link in every node points back to the previous node, so a traversal can run in both directions and a deletion needs no separate search for the predecessor. The other three statements are equally true of a singly linked list.

A singly linked list holds 12 nodes. State how many nodes are visited in total when the list is traversed once from the head to the last node. (give a whole number)

Answer: 12

A linked list has no index, so the only way to reach node 12 is to follow the links through all 11 nodes in front of it, and the traversal therefore touches every node exactly once. This is the price paid for the cheap insertions that the links make possible.

The values 60, 25, 80, 15 and 40 are inserted into an empty binary search tree in that order. State the value that ends up in the leftmost node of the finished tree. (give a whole number)

Answer: 15

Going left at every node always leads to the smallest value stored, and 15 is smaller than both 60 and 25, so it hangs to the left of 25. The leftmost node of any binary search tree therefore holds the minimum, which is why finding the minimum needs no full traversal.

A stack is used to reverse the six letters of a word, one letter per element. State the number of pop operations needed to produce the reversed word. (give a whole number)

Answer: 6

Every letter has to come back out of the stack, and a stack releases exactly one item per pop, so six pushes are matched by six pops. Because the last letter pushed is the first popped, the letters emerge in the opposite order without any further work.

A balanced binary search tree holds 15 values. State the greatest number of nodes that have to be compared with the target before a search can report success or failure. (give a whole number)

Answer: 4

A balanced tree of 15 nodes has the root, then 2, then 4, then 8 nodes, so the longest path from the root visits four nodes. Each comparison discards one whole subtree, which is why the cost grows with the height and not with the number of values.