Examen de Prácticas de programación UOC 2020 · Juny
Examen de Prácticas de programación de la UOC (Grado en Ingeniería Informática) 2020, Juny: 5 problemas con solución. Hazlo online con corrección al momento.
Temas del examen: Especificación: precondiciones y postcondiciones · Diseño descendente sobre vectores de registros en lenguaje algorítmico · Comprensión y traza de algoritmos recursivos · Transformación entre versión recursiva e iterativa en C · Análisis de complejidad y eficiencia
Pregunta 1.a - Especificación de precondiciones · Especificación: precondiciones y postcondiciones
A partir del modelado de datos de un torneo de ajedrez, considérense las siguientes definiciones de tipos y constantes en lenguaje algorítmico:
const
MAX_PAIRINGS: integer:= 5;
MAX_ROUNDS: integer:= 9;
end const
type
tLevel = {master, advanced, medium, novice};
tResult = {whiteWins, blackWins, draw};
tDate = record
day: integer;
month: integer;
year: integer;
end record
tPlayer = record
id: integer;
name: string;
age: integer;
nacionality: string;
elo: integer;
level: tLevel;
end record
tPairing = record
idPairing: integer;
idWhitePlayer: integer;
idBlackPlayer: integer;
result: tResult;
end record
tRound = record
number: integer;
pairings: vector [MAX_PAIRINGS] of tPairing;
numPairings: integer;
numWhiteWins: integer;
numBlackWins: integer;
numDraws: integer;
end record
tChessTournament = record
name: string;
location: string;
date: tDate;
players: pointer to tPlayer;
numPlayers: integer;
rounds: vector [MAX_ROUNDS] of tRound;
numRounds: integer;
end record
end type
Se dispone de la cabecera de la función:
function level_loosers (c: tChessTournament): integer
Su propósito es computar y devolver el número total de partidas en las que el participante derrotado poseía un nivel estrictamente superior al vencedor.
a. [10%] Especifica las precondiciones formales asociadas a la función, asumiendo que el campeonato cuenta como mínimo con una ronda disputada y que cada contrincante figura debidamente registrado en el torneo.
Pregunta 1.b - Diseño descendente · Diseño descendente sobre vectores de registros en lenguaje algorítmico
A partir del modelado de datos de un torneo de ajedrez, considérense las siguientes definiciones de tipos y constantes en lenguaje algorítmico:
const
MAX_PAIRINGS: integer:= 5;
MAX_ROUNDS: integer:= 9;
end const
type
tLevel = {master, advanced, medium, novice};
tResult = {whiteWins, blackWins, draw};
tDate = record
day: integer;
month: integer;
year: integer;
end record
tPlayer = record
id: integer;
name: string;
age: integer;
nacionality: string;
elo: integer;
level: tLevel;
end record
tPairing = record
idPairing: integer;
idWhitePlayer: integer;
idBlackPlayer: integer;
result: tResult;
end record
tRound = record
number: integer;
pairings: vector [MAX_PAIRINGS] of tPairing;
numPairings: integer;
numWhiteWins: integer;
numBlackWins: integer;
numDraws: integer;
end record
tChessTournament = record
name: string;
location: string;
date: tDate;
players: pointer to tPlayer;
numPlayers: integer;
rounds: vector [MAX_ROUNDS] of tRound;
numRounds: integer;
end record
end type
Se dispone de la cabecera de la función:
function level_loosers (c: tChessTournament): integer
Su propósito es computar y devolver el número total de partidas en las que el participante derrotado poseía un nivel estrictamente superior al vencedor.
b. [30%] Realiza la implementación de la función utilizando pseudocódigo algorítmico conforme a la metodología de diseño descendente. Deberán desarrollarse además todas aquellas subrutinas auxiliares que resulten necesarias en los distintos niveles de abstracción.
Pregunta 2.a - Comprensión y traza recursiva · Comprensión y traza de algoritmos recursivos
Pregunta 2 [60%]. Análisis y transformación de algoritmo recursivo
A partir del siguiente algoritmo recursivo implementado en C:
#define MAX 64
int guess (int v[MAX], int x)
{
int res;
assert (0 <= x && x <= MAX);
if (x == 0) // (1)
res = 0; // (2)
else // (3)
{
res = guess(v, x-1); // (5)
if (v[x-1] == (x-1)) // (6)
res = res + 1; // (7)
}
return res;
}
a. [10%] Explica la funcionalidad de este método e ilustra de manera detallada la traza de ejecución de llamadas y retornos para la siguiente invocación:
int test;
test = guess({0, 1, 9, 3}, 4);
Pregunta 2.b - Transformación a iterativo · Transformación entre versión recursiva e iterativa en C
Pregunta 2 [60%]. Análisis y transformación de algoritmo recursivo
A partir del siguiente algoritmo recursivo implementado en C:
#define MAX 64
int guess (int v[MAX], int x)
{
int res;
assert (0 <= x && x <= MAX);
if (x == 0) // (1)
res = 0; // (2)
else // (3)
{
res = guess(v, x-1); // (5)
if (v[x-1] == (x-1)) // (6)
res = res + 1; // (7)
}
return res;
}
b. [20%] Reescribe la función para convertirla en un método puramente iterativo en C.
Pregunta 2.c - Análisis de complejidad · Análisis de complejidad y eficiencia
Pregunta 2 [60%]. Análisis y transformación de algoritmo recursivo
A partir del siguiente algoritmo recursivo implementado en C:
#define MAX 64
int guess (int v[MAX], int x)
{
int res;
assert (0 <= x && x <= MAX);
if (x == 0) // (1)
res = 0; // (2)
else // (3)
{
res = guess(v, x-1); // (5)
if (v[x-1] == (x-1)) // (6)
res = res + 1; // (7)
}
return res;
}
c. [30%] Determina la complejidad temporal teórica de la versión recursiva original mediante la formulación y resolución de la relación de recurrencia correspondiente.
También puedes estudiar por temas
Practica un tema con ejercicios de los exámenes de todos los años, mezclados.
- Comprensión y traza de algoritmos recursivos · 9 problemas · 95 % de que salga
- Especificación: precondiciones y postcondiciones · 8 problemas · 95 % de que salga
- Diseño descendente sobre vectores de registros en lenguaje algorítmico · 8 problemas · 95 % de que salga
- Transformación entre versión recursiva e iterativa en C · 8 problemas · 95 % de que salga
- Análisis de complejidad y eficiencia · 8 problemas · 95 % de que salga