Data Structures: Stacks, Queues, and Trees Worksheet

Question 1

A stack starts empty. The operations are push(4), push(9), push(2), pop(), push(7), pop(). What values are removed by the two pop operations, in order, and what remains in the stack from bottom to top?

Accepted Answer

The first pop removes 2, and the second pop removes 7. The remaining stack from bottom to top is 4, 9.

Question 2

A queue starts empty. The operations are enqueue(A), enqueue(B), enqueue(C), dequeue(), enqueue(D), dequeue(). What values are removed by the two dequeue operations, in order, and what remains in the queue from front to back?

Accepted Answer

The first dequeue removes A, and the second dequeue removes B. The remaining queue from front to back is C, D.

Question 3

Explain the difference between LIFO and FIFO. Name one data structure that uses each rule.

Accepted Answer

LIFO means last in, first out, and a stack uses this rule. FIFO means first in, first out, and a queue uses this rule.

Question 4

A program checks whether parentheses are balanced in the expression (a + b) * (c + d). Which data structure is best for tracking the opening parentheses, and why?

Accepted Answer

A stack is best because each closing parenthesis should match the most recent unmatched opening parenthesis.

Question 5

A printer receives jobs in the order Job1, Job2, Job3, and Job4. If the printer processes jobs in the order they arrive, which data structure should manage the jobs? What job is processed first?

Accepted Answer

A queue should manage the jobs because it processes items first in, first out. Job1 is processed first.

Question 6

Draw or describe the binary tree with root 10, left child 5, right child 15, left child of 5 equal to 2, and right child of 5 equal to 7. Then list the leaf nodes.

Accepted Answer

The root is 10, with children 5 and 15. Node 5 has children 2 and 7. The leaf nodes are 2, 7, and 15 because they have no children.

Question 7

For the binary tree with root A, left child B, right child C, left child of B equal to D, and right child of B equal to E, write the preorder traversal.

Accepted Answer

The preorder traversal is A, B, D, E, C because preorder visits the root first, then the left subtree, then the right subtree.

Question 8

For the binary tree with root A, left child B, right child C, left child of B equal to D, and right child of B equal to E, write the inorder traversal.

Accepted Answer

The inorder traversal is D, B, E, A, C because inorder visits the left subtree, then the root, then the right subtree.

Question 9

For the binary search tree containing the values 8, 3, 10, 1, 6, 14, 4, 7, and 13, list the values in sorted order using an inorder traversal.

Accepted Answer

The values in sorted order are 1, 3, 4, 6, 7, 8, 10, 13, 14. An inorder traversal of a binary search tree visits values from smallest to largest.

Question 10

A binary search tree is empty. Insert the values 12, 5, 18, 2, 9, and 15 in that order. What are the left and right children of 12?

Accepted Answer

The left child of 12 is 5, and the right child of 12 is 18. Values less than 12 go to the left side, and values greater than 12 go to the right side.

Question 11

Choose the best data structure for an undo feature in a text editor: stack, queue, or tree. Explain your choice.

Accepted Answer

A stack is the best choice because the most recent action should be undone first. This matches last in, first out behavior.

Question 12

A customer service system must help customers in the same order they joined the waiting list. Choose the best data structure and explain what operation adds a customer and what operation serves a customer.

Accepted Answer

A queue is the best data structure because customers should be helped first in, first out. Enqueue adds a customer, and dequeue serves a customer.

Data Structures: Stacks, Queues, and Trees

Related Cheat Sheets

More CS Worksheets

More Grade 9-12 Worksheets