Quiz: Stacks, Queues, and Beyond

Test your understanding before moving on. Target: 70% or higher to proceed confidently.

Section 1: Multiple Choice (1 point each)

1. Which principle describes a stack's access pattern?

• A) FIFO — First In, First Out
• B) LIFO — Last In, First Out
• C) Random access
• D) Priority-based access

2. What is the output of this code?

s = Stack()
s.push(1)
s.push(2)
s.push(3)
s.pop()
s.push(4)
print(s.peek())

• A) 1
• B) 2
• C) 3
• D) 4

3. Which operation is NOT part of the standard stack ADT?

• A) push(item)
• B) pop()
• C) insert(index, item)
• D) peek()

4. Why does our Queue implementation use collections.deque instead of a plain list?

• A) deque uses less memory than a list
• B) deque.popleft() is O(1), while list.pop(0) is O(n)
• C) Lists cannot store mixed types
• D) deque automatically sorts elements

5. In the bracket-matching algorithm, what data structure is used and why?

• A) Queue — brackets must be checked in order of appearance
• B) Stack — the most recently opened bracket must be the first one closed
• C) Dictionary — to map opening brackets to closing brackets
• D) Set — to check if a character is a bracket in O(1)

6. What is the output of this code?

q = Queue()
q.enqueue("X")
q.enqueue("Y")
q.enqueue("Z")
print(q.dequeue())
print(q.dequeue())

• A) Z, Y
• B) X, Y
• C) Y, X
• D) Z, X

7. What does ADT stand for, and what does it describe?

• A) Advanced Data Technology — the fastest implementation of a data structure
• B) Abstract Data Type — the operations and behavior of a data structure, independent of implementation
• C) Automated Data Testing — a framework for testing data structures
• D) Applied Data Transformation — converting between data formats

8. In a linked list, each node contains:

• A) Only data
• B) Data and an index number
• C) Data and a reference to the next node
• D) Data and a reference to all other nodes

9. What is the time complexity of accessing the 100th element in a linked list?

• A) O(1)
• B) O(log n)
• C) O(n)
• D) O(n^2)

10. Which data structure would be BEST for modeling a social network (who follows whom)?

• A) Stack
• B) Queue
• C) Tree
• D) Graph

Section 2: Short Answer (2 points each)

11. Explain the difference between push and enqueue. Under what circumstances would you use each?

12. A student writes this code:

my_queue = []
my_queue.append("task1")
my_queue.append("task2")
my_queue.append("task3")
first = my_queue.pop(0)

Identify the problem and suggest a fix.

from collections import deque
my_queue = deque()
my_queue.append("task1")
my_queue.append("task2")
my_queue.append("task3")
first = my_queue.popleft()  # O(1) instead of O(n)

13. What happens when you try to pop() from an empty stack in our implementation? Why is this behavior (raising an exception) preferable to returning None?

14. Explain the threshold concept from this chapter in your own words: "A stack is a CONCEPT (LIFO behavior) that can be IMPLEMENTED in many ways." Give an example.

Section 3: Code Analysis (3 points each)

15. What does this function do? Trace through it with the input "hello".

def mystery(text: str) -> bool:
    s = Stack()
    for ch in text:
        s.push(ch)
    reversed_text = ""
    while not s.is_empty():
        reversed_text += s.pop()
    return text == reversed_text

16. This code has a bug. Find it and explain how to fix it.

def process_tasks(task_list: list[str]) -> None:
    q = Queue()
    for task in task_list:
        q.enqueue(task)

    for i in range(len(task_list) + 1):  # Bug is here
        task = q.dequeue()
        print(f"Processing: {task}")

while not q.is_empty():
    task = q.dequeue()
    print(f"Processing: {task}")

17. Analyze this undo/redo sequence. What is the final value of editor.text?

editor = TextEditor()
editor.type_text("AB")       # text = "AB"
editor.type_text("CD")       # text = "ABCD"
editor.type_text("EF")       # text = "ABCDEF"
editor.undo()                # text = ?
editor.undo()                # text = ?
editor.redo()                # text = ?
editor.type_text("GH")       # text = ?
editor.redo()                # text = ? (does anything happen?)

18. Compare these two implementations of the same operation. Which is better and why?

# Version A
def drain_queue_a(q: Queue) -> list:
    result = []
    while q.size() > 0:
        result.append(q.dequeue())
    return result

# Version B
def drain_queue_b(q: Queue) -> list:
    result = []
    try:
        while True:
            result.append(q.dequeue())
    except IndexError:
        pass
    return result

Section 4: Conceptual Questions (2 points each)

19. A student says: "Linked lists are better than Python lists because insertion is O(1)." What important caveat are they missing?

20. For each scenario, name the best data structure and justify your choice in one sentence:

a) Managing browser tabs that you open and close in order b) Processing customer service tickets in the order they were submitted c) Representing a family tree d) Checking if a word exists in a dictionary of 100,000 words e) Implementing Ctrl+Z in a word processor