data_structures/practice_set.py

Data Structures Lab

Three problem types, mixed difficulty: arrange the code, trace the state, check the concept. Work through them in any order.

PART A

Arrange the Code

Drag the scrambled lines back into the order that makes each function correct. Lines marked fixed give you the scaffolding.

A1 — Balanced Parentheses

stack

Implement is_balanced, which returns True if every opening bracket has a matching, correctly nested closing bracket.

def is_balanced(expr):
    stack = []
    for ch in expr:
        if ch in "([{":
            stack.append(ch)
        elif ch in ")]}":
            if len(stack) == 0:
                return False
            top = stack.pop()
            pairs = {')': '(', ']': '[', '}': '{'}
            if top != pairs[ch]:
                return False
    return len(stack) == 0

Show test cases

is_balanced("({[]})") → True
is_balanced("([)]") → False
is_balanced("(()") → False

A2 — Insert at Head

linked list

Add value as the new first node of the linked list and return the new head.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def insert_at_head(head, value):
    new_node = Node(value)
    new_node.next = head
    head = new_node
    return head

Show test cases

Inserting 3, then 2, then 1 → list reads [1, 2, 3]

A3 — BST Insertion

tree

Insert val into the binary search tree rooted at root, preserving BST order.

def insert(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

Show test cases

Inserting 5, 2, 8, 1, 3 → in-order traversal reads [1, 2, 3, 5, 8]

PART B

Trace the Code

Step through each line and predict the resulting state before checking the answer.

B1 — Queue Operations

queue

For each step, what does the line return (if anything), and what does q contain afterward?

from collections import deque
q = deque()
q.append(10)        # step 1
q.append(20)        # step 2
q.popleft()          # step 3
q.append(30)         # step 4
front = q[0]          # step 5

Show trace table

Step	Returned	q after
1	—	`[10]`
2	—	`[10, 20]`
3	`10`	`[20]`
4	—	`[20, 30]`
5	`20`	`[20, 30]`

B2 — Word Frequency Count

hash table

Trace the loop iteration by iteration. After each one, what does counts contain?

counts = {}
words = ["cat", "dog", "cat", "bird", "dog", "cat"]

for w in words:
    counts[w] = counts.get(w, 0) + 1

Show trace table

Iter	w	counts after
1	`cat`	`{cat:1}`
2	`dog`	`{cat:1, dog:1}`
3	`cat`	`{cat:2, dog:1}`
4	`bird`	`{cat:2, dog:1, bird:1}`
5	`dog`	`{cat:2, dog:2, bird:1}`
6	`cat`	`{cat:3, dog:2, bird:1}`

B3 — Recursive Tree Height

tree

Trace the recursive calls. What does each call return, and what's the final printed value?

def height(node):
    if node is None:
        return 0
    return 1 + max(height(node.left), height(node.right))

tree = TreeNode(1, TreeNode(2, TreeNode(4)), TreeNode(3))
print(height(tree))

Show answer

height(4)=1 → height(2)=2 → height(3)=1 → height(1)=3
Printed output: 3

PART C

Concept Checks

One best answer each. Distractors target common misconceptions.

C1 — List Insertion Cost

list

What is the time complexity of inserting an element at the beginning of a Python list of length n?

O(1)
O(n)
O(log n)
O(n²)

O(1) is the common slip — append is O(1) at the end, but inserting at index 0 shifts every element.

C2 — Stack Discipline

stack

A stack follows which discipline?

First-In-First-Out (FIFO)
Last-In-First-Out (LIFO)
Random access
Priority-based

C3 — Linked List Advantage

linked list

Compared to an array, what's the main advantage of a singly linked list?

Faster random access (indexing)
Efficient insert/delete at the head, no shifting
Uses less memory per element
Better cache locality

C4 — In-order Traversal

tree

In a binary search tree, an in-order traversal visits nodes:

In the order they were inserted
From largest to smallest
In ascending sorted order
In a random order determined by tree shape

C5 — Hash Table Degradation

hash table

What's the primary cause of degraded, O(n) performance in a hash table?

Using too few keys
Many keys colliding into the same bucket
Using string keys instead of integers
Inserting keys in sorted order

C6 — BFS Helper Structure

graph

Breadth-first search on a graph typically uses which structure to track nodes to visit next?

Stack
Queue
Hash table
Min-heap only