Abstract data types practice questions.

A program uses a stack only through the operations push, pop, peek and isEmpty. The stack is later rebuilt from a fixed-size array into a linked list. What is the effect on the rest of the program?

• It must be rewritten, because pop now removes the item from the opposite end.
• It must be rewritten wherever the stack is created, because a linked list is given no capacity.
• Nothing changes, because the program depends only on the operations the stack offers.
• Nothing changes, but push and pop now deal with the items in the reverse order.

Answer: Nothing changes, because the program depends only on the operations the stack offers.

An abstract data type is defined by the operations it provides and the behaviour it promises, not by the arrangement of the data in memory, so any implementation that keeps those promises can be swapped in. Only code that reached inside the structure, for example indexing the array directly, would break.

The values 50, 30, 70 and 40 are inserted into an initially empty binary search tree in that order. Where does 40 end up?

• As the right child of 30.
• As the left child of 70.
• As the left child of 30.
• As the right child of 50, taking the place that 70 held.

Answer: As the right child of 30.

40 is compared with 50 and goes left to 30, then compared with 30 and goes right, where the position is still free. A binary search tree never moves a node that is already placed, so the insertion order alone decides the shape.

A singly linked list holds the nodes A, B and C in that order. Which pair of steps, carried out in the order given, inserts a new node X between A and B?

• Set the link of A to X, then set the link of X to B.
• Set the link of X to A, then set the link of B to X.
• Set the link of B to X, then set the link of X to C.
• Set the link of X to B, then set the link of A to X.

Answer: Set the link of X to B, then set the link of A to X.

X has to be joined to the rest of the list before the only pointer that still reaches B is overwritten; doing it the other way round leaves B and C unreachable. Here the order of the two assignments is the whole answer.

An application keeps 5000 records in name order and inserts a new record about once a second, almost always somewhere in the middle. Which implementation makes those insertions cheapest?

• A fixed-size array, because any element is reached directly from its index number.
• A linked list, because only two links have to be changed.
• A stack, because the record added most recently is the one that is needed next.
• A two-dimensional array, because the records can be grouped by their first letter.

Answer: A linked list, because only two links have to be changed.

Inserting into the middle of an array pushes every later element up one place, while a linked list only rewrites the link of the previous node and the link of the new node. Direct access by index buys nothing when the position has to be found by traversal in either case.

A binary tree stores 8 at the root, 3 and 10 as the children of the root, and 1 and 6 as the children of 3. A pre-order traversal is carried out. Which output does it produce?

• 8, 3, 1, 6, 10
• 1, 3, 6, 8, 10
• 1, 6, 3, 10, 8
• 8, 3, 10, 1, 6

Answer: 8, 3, 1, 6, 10

Pre-order visits the node itself, then the whole of its left subtree, then its right subtree, giving 8, then 3 with its children 1 and 6, then 10. The three distractors are the in-order, the post-order and the level-by-level results, which is why the rule has to be applied rather than remembered.

Why does a search of a binary search tree that was built from values already in ascending order cost as much as a search of an unsorted list?

• The comparison made at each node is carried out in the wrong direction.
• The whole tree has to be traversed in order before any comparison can be made.
• Every value is stored twice, once in each of the two subtrees.
• Every node has only a right child, so the tree becomes one long chain.

Answer: Every node has only a right child, so the tree becomes one long chain.

The shape of a binary search tree is decided by the order of insertion, and sorted input places every new value to the right of everything before it. The tree degenerates into a linked list, so the search walks past every node instead of discarding half the data at each step.