Pregunta 2 · Matemática Discreta UAB 2026
Tema: Recorreguts BFS i DFS · Del examen Examen de seminaris Parcial 1 (20/04/2026) (2026)
Enunciado
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 a () si la funció crida la funció .
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ó.
Solución
Según los criterios oficiales de corrección
a) Representeu aquest conjunt de crides com un graf... Dibuixeu o descriviu detalladament el graf resultant.
Solución: Graf dirigit (dígraf) : - Vèrtexs: - Arestes dirigides:
b) quina estructura de dades lineal (pila o cua) s'hauria de fer servir per administrar les funcions pendents de finalitzar?
Solución: pila
b) Justifiqueu la decisió breument.
Solución: Quan una funció crida una altra funció, la funció invocant queda pausada i la nova funció invocada s'ha d'executar completament abans que la primera pugui reprendre la seva execució. Per tant, la darrera funció que ha estat cridada és la primera que ha d'acabar i ser desapilada.
c) 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)?
Solución: DFS / cerca en profunditat
c) Justifiqueu la tria en funció del patró d'execució.
Solución: Quan s'invoca f(), aquesta crida g(), i abans de procedir amb la crida a k() (que se situa al mateix nivell dins de f), el fil d'execució descendeix en la branca de g(), executant h() i després z(). Només quan tota la branca subjacent s'ha completat es produeix el retorn (backtracking) cap a f() per poder passar a la següent instrucció, k(). Aquest comportament d'explorar completament una branca abans de passar al següent germà és la definició exacta de DFS.
Dibuixeu o descriviu detalladament el graf resultant.
Solución: Graf dirigit amb vèrtexs {f, g, h, z, k} i arestes dirigides f -> g, f -> k, g -> h, g -> z.
La explicación paso a paso, hecha con IA, es Premium. Premium
Resuélvelo aquí mismo: corrección automática, pistas y solución paso a paso.
‹ Pregunta 1 · 2026 · Exercici 5 - Recorreguts BFS i DFS · Juny 2026 ›