Exam 32026-09-10

Python Structures and Graph Search Exam

60 minutes · 60 points · functions, lists, class, dict, graph, DFS, and BFS

Exam Instructions

Order: The paper starts with direct code reading, moves through short explanations, and ends with four coding tasks. Later questions reuse the same graph, so read it carefully once.

Section A

10 min · 12 pts

Section B

15 min · 18 pts

Section C

35 min · 30 pts

Allowed: Normal Python syntax, list, dict, set, tuple, range, len, and collections.deque. Do not use Dijkstra, heapq, file I/O, or external packages.

Section A — Choices

6 questions · 12 points · about 10 minutes. Q1-Q5 are single choice; Q6 is multiple choice.

Q1Foundation1 min2 pts

A return value that nobody receives

What does the program print?

python

def triple(number):    number = number * 3    return numberscore = 4triple(score)print(score)

A. 4B. 12C. NoneD. The program crashes

Q2Foundation1 min2 pts

A function changes a list

What does the program print?

python

def add_exit(exits):    exits.append("east")route = ["north"]add_exit(route)print(route)

A. ['north']B. ['north', 'east']C. ['east']D. None

Q3Foundation1 min2 pts

What comes out of a dict loop?

Which two lines are printed?

python

scores = {"Ada": 8, "Bo": 5}for value in scores:    print(value)

A. "Ada", then "Bo"B. 8, then 5C. ("Ada", 8), then ("Bo", 5)D. 0, then 1

Q4Foundation2 min2 pts

Two independent objects

What does the final print show?

python

class Counter:    def __init__(self, start):        self.value = start    def add(self, amount):        self.value += amountfirst = Counter(2)second = Counter(5)first.add(3)print(first.value, second.value)

A. 2 5B. 5 2C. 5 5D. 8 8

Q5Intermediate2 min2 pts

BFS visit order from A

Use each neighbour list from left to right. Which is the BFS order? Node X is disconnected.

python

graph = {    "A": ["B", "C"],    "B": ["D"],    "C": ["E"],    "D": ["F"],    "E": ["D", "F"],    "F": [],    "X": [],}

A. A, B, D, F, C, EB. A, B, C, D, E, FC. A, C, E, F, D, BD. A, B, C, D, E, F, X

Q6Intermediate3 min2 pts

Multiple choice: choose every true statement

Select every correct option. You must choose the complete set for the 2 points.

A. A tuple such as (2, 3) can be a dict key.B. A list such as [2, 3] can be a dict key.C. BFS finds a shortest edge-count path in an unweighted graph.D. DFS always finds the shortest path first.E. A visited structure prevents cycles from causing endless work.

Section B — Short Answer

3 questions · 18 points · about 15 minutes. Precise reasoning matters more than length.

Q7Intermediate5 min6 pts

Trace mutation and rebinding

Write both output lines exactly.
Explain why route receives C but not D.

python

def prepare(path):    path.append("C")    path = path.copy()    path.append("D")    return pathroute = ["A", "B"]new_route = prepare(route)print(route)print(new_route)

Your answer

Q8Intermediate5 min6 pts

Design a visit counter with a hash table

Input visits: ["lab", "hall", "lab", "vault", "lab"]. Required result: {"lab": 3, "hall": 1, "vault": 1}.

Use 4-6 sentences to describe a dict-based algorithm.
State what each key and value means.
Explain how to handle a room seen for the first time.
Explain why a dict is useful here.

Your answer

Q9Intermediate5 min6 pts

Choose BFS or DFS for a route

Goal: find a route from A to F using the fewest edges. Answer in 4-6 sentences.

python

graph = {    "A": ["B", "C"],    "B": ["D"],    "C": ["E"],    "D": ["F"],    "E": ["D", "F"],    "F": [],    "X": [],}

Choose BFS or DFS and explain why.
Name the frontier structure it uses.
Say when a node should be added to visited.
State the shortest distance from A to F.

Your answer

Section C — Coding

4 questions · 30 points · about 35 minutes. Complete each function in its answer editor.

Q10Foundation6 min6 pts

Function + list: collect matching indexes

Input: values: list of numbers; limit: number
Output: A new list of every index i where values[i] >= limit, in increasing index order. values must stay unchanged.

python

def positions_at_least(values, limit):    # Return a NEW list containing the indexes whose values are >= limit.    # Do not change values.    passprint(positions_at_least([4, 9, 2, 9], 8))# expected: [1, 3]print(positions_at_least([5, 5], 6))# expected: []

Your code

Q11Intermediate7 min7 pts

Hash table: build a frequency table

Input: words: list of strings
Output: A dict mapping each distinct word to its count. Return {} for an empty list. Matching is case-sensitive.

python

def frequency_table(words):    # Return a dict that maps each word to the number of times it appears.    # An empty input list must return {}.    passprint(frequency_table(["red", "blue", "red", "red"]))# expected: {'red': 3, 'blue': 1}print(frequency_table([]))# expected: {}

Your code

Q12Advanced10 min8 pts

DFS: return the visit order

Input: graph: adjacency dict with every node present as a key; start: existing node name
Output: A list containing each node reachable from start exactly once, in depth-first order. Follow neighbours left to right and handle cycles.

python

graph = {    "A": ["B", "C"],    "B": ["D"],    "C": ["E"],    "D": ["F"],    "E": ["D", "F"],    "F": [],    "X": [],}def dfs_order(graph, start):    # Follow each neighbour list from left to right.    # Return every reachable node once, in DFS visit order.    passprint(dfs_order(graph, "A"))# expected: ['A', 'B', 'D', 'F', 'C', 'E']print(dfs_order(graph, "X"))# expected: ['X']

Your code

Q13Advanced12 min9 pts

BFS: shortest distance

Input: graph: adjacency dict; start and goal: existing node names
Output: The minimum number of edges from start to goal; 0 for the same node; -1 when unreachable. The graph may contain cycles.

python

from collections import dequegraph = {    "A": ["B", "C"],    "B": ["D"],    "C": ["E"],    "D": ["F"],    "E": ["D", "F"],    "F": [],    "X": [],}def shortest_distance(graph, start, goal):    # Return the fewest number of edges from start to goal.    # Return 0 when start == goal.    # Return -1 when goal cannot be reached.    passprint(shortest_distance(graph, "A", "F"))  # 3print(shortest_distance(graph, "A", "A"))  # 0print(shortest_distance(graph, "F", "A"))  # -1

Your code