Assignments

14.4. Assignments#

These assignments reinforce the main Chapter 14 ideas: matching structures to operations, implementing stacks and queues, and representing relationships with trees and graphs.

14.4.1. Preview Questions#

  1. What is the difference between an abstract data type and a concrete implementation?

  2. Give one real-world example that behaves like a stack.

  3. Give one real-world example that behaves like a queue.

  4. Why is a dictionary a natural way to represent an adjacency list?

  5. When would a tree be a better model than a graph?

14.4.2. Lab Assignment#

Build a small task-management simulation.

Requirements:

  • Use a queue for incoming tasks.

  • Use a stack for undo history.

  • Use a dictionary to store task metadata by task ID.

  • Demonstrate adding three tasks, completing two tasks, undoing one action, and looking up one task by ID.

  • Include short comments explaining why each structure was chosen.

14.4.3. Homework Questions#

  1. Implement a function is_balanced(text) that checks whether parentheses in a string are balanced.

  2. Create a queue-based simulation of a customer-service line with at least five customers.

  3. Represent a small company hierarchy as a tree and print it with indentation.

  4. Represent course prerequisites as a graph using a dictionary.

  5. Write a short paragraph comparing BFS and DFS. Include one situation where each would be useful.

14.4.4. Review Questions#

  1. What operation makes a stack different from a queue?

  2. Why is collections.deque better than a list for queue behavior?

  3. What does a node store in a linked structure?

  4. What is the root of a tree?

  5. What are nodes and edges in a graph?

  6. Which traversal uses a queue: BFS or DFS?

  7. Which traversal can naturally use a stack: BFS or DFS?

Contents