Examen de Matemática Discreta UAB 2026 · seminaris Parcial 1 (20/04/2026)

Pregunta 1 (5 punts). Algorisme BFS i detecció de cicles

Considereu la implementació en Python d'un recorregut en amplada (BFS):

1. def bfs(graph, start):

2. to_visit = []

3. visited = []

4. to_visit.append(start)

5. while to_visit:

6. # CUA (FIFO): traiem el primer

7. actual = to_visit.pop(0)

8. veins = graph.neighbors(actual)

9. for v in veins:

10. if v not in to_visit:

11. to_visit.append(v)

12. visited.append(actual)

13. return visited

I el graf dirigit $G = (V, E)$ definit per les següents arestes dirigides:

$A \rightarrow B$

$B \rightarrow C$

$B \rightarrow D$

$C \rightarrow A$

a.

(2 punts) Efectueu el seguiment de l'execució de la crida bfs(G, 'A') completant la taula amb l'estat de les variables al final de cadascuna de les primeres 5 iteracions del bucle while. La fila INICIAL reflecteix l'estat just abans d'entrar al bucle.

Iteració

actual

visited

to_visit

INICIAL

—

[]

['A']

1

2

3

4

5

b.

(1 punt) Raoneu quin inconvenient o error presenta l'algorisme i per quina raó es manifesta.

c.

(2 punts) Assenyaleu el número de línia que cal esmenar i escriviu la correcció necessària.

Pregunta 2 (5 punts). Graf de crides de funcions i ordre d'execució

Analitzeu el codi següent en Python (tingueu present que la sentència pass no executa cap acció):

def f():

g()

k()

def g():

h()

z()

def h():

pass

def z():

pass

def k():

pass

a)

[2 punts] Representeu aquest conjunt de crides com un graf (utilitzant fletxes si és dirigit o arestes sense orientació si és no dirigit) en què:

Cada funció es correspongui amb un vèrtex.

Existeixi una aresta de $u$ a $v$ ($u \rightarrow v$) si la funció $u$ crida la funció $v$.

Dibuixeu o descriviu detalladament el graf resultant.

b)

[1 punt] Si es vol simular l'execució real de les crides a funcions tal com fa un intèrpret o un sistema operatiu, quina estructura de dades lineal ( pila o cua) s'hauria de fer servir per administrar les funcions pendents de finalitzar? Justifiqueu la decisió breument.

c)

[2 punts] El flux d'execució d'un programa en encadenar crides de funcions correspon a una cerca en amplada ( BFS) o a una cerca en profunditat ( DFS)? Justifiqueu la tria en funció del patró d'execució.