Data structures worksheet with answers

A graph consists of:

1. ARows and columns
2. BVertices (nodes) connected by edges
3. COnly a root and leaves
4. DKeys and hashes only

In which order does a postorder traversal of a binary tree visit nodes?

1. ARight subtree, then node, then left subtree
2. BNode, then left subtree, then right subtree
3. CLeft subtree, then node, then right subtree
4. DLeft subtree, then right subtree, then node

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

1. APush
2. BEnqueue
3. CPop
4. DPeek

In a circular queue stored in an array of capacity n, how is the next position after index i computed?

1. Ai + 1
2. B2i + 1
3. C(i − 1) mod n
4. D(i + 1) mod n

What balance condition does an AVL tree maintain at every node?

1. AEvery node is coloured red or black
2. BThe heights of the left and right subtrees differ by at most 1
3. CAll leaves are at exactly the same depth
4. DBoth subtrees of every node contain exactly the same number of nodes

A binary tree has root 1 with left child 2 and right child 3; node 2 has children 4 (left) and 5 (right). What is the preorder traversal?

1. A1 2 3 4 5
2. B1 2 4 5 3
3. C4 2 5 1 3
4. D4 5 2 3 1

An AVL node is unbalanced because its left child's right subtree became too tall (left-right case). Which fix is applied?

1. AA single right rotation at the node
2. BA right rotation at the left child, then a left rotation at the node
3. CA single left rotation at the node
4. DA left rotation at the left child, then a right rotation at the node

What does a splay tree do after each access?

1. ARebuilds the whole tree in balanced form
2. BRecolours the nodes on the search path
3. CMoves the accessed node to a leaf
4. DRotates the accessed node up to the root