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: precondiciones y postcondiciones
Considerando la definición de datos de un torneo de ajedrez empleada a lo largo del curso:
const
MAX_PAIRINGS: integer:= 5;
MAX_ROUNDS: integer:= 9;
end const
type
tResult = {whiteWins, blackWins, draw};
tDate = record
day: integer;
month: integer;
year: integer;
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;
rounds: vector [MAX_ROUNDS] of tRound;
numRounds: integer;
end record
end type
Dada la cabecera de la función:
function winners_round (c: tChessTournament; num: integer): list(integer)
que debe retornar una lista con los identificadores de todos los participantes vencedores en la ronda num:
a.
[10%] Especifica las precondiciones que requiere la función, asumiendo que la ronda indicada por num existe.
Pregunta 1.b · Diseño descendente sobre vectores de registros en lenguaje algorítmico
Considerando la definición de datos de un torneo de ajedrez empleada a lo largo del curso:
const
MAX_PAIRINGS: integer:= 5;
MAX_ROUNDS: integer:= 9;
end const
type
tResult = {whiteWins, blackWins, draw};
tDate = record
day: integer;
month: integer;
year: integer;
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;
rounds: vector [MAX_ROUNDS] of tRound;
numRounds: integer;
end record
end type
Dada la cabecera de la función:
function winners_round (c: tChessTournament; num: integer): list(integer)
que debe retornar una lista con los identificadores de todos los participantes vencedores en la ronda num:
b) [30%] Codifica la función en lenguaje algorítmico empleando diseño descendente. Se deben programar todos los subprogramas auxiliares necesarios a excepción de las primitivas del TAD lista.
Pregunta 2.a · Comprensión y traza de algoritmos recursivos
A partir del código C de la función recursiva guess:
#define MAX 64
void guess (int v[MAX], int x, int value)
{
assert (0 <= x && x <= MAX);
if (x > 0) // (1)
{ // (2)
if (v[x-1] > value) v[x-1] = value; // (3)
guess(v, x-1, value); // (4)
}
}
a)
[10%] Explica el propósito del método y muestra paso a paso la traza de ejecución para la llamada:
int v[4] = {4, 6, 2, 9};
guess (v, 4, 5);
Pregunta 2.b · Transformación entre versión recursiva e iterativa en C
A partir del código C de la función recursiva guess:
#define MAX 64
void guess (int v[MAX], int x, int value)
{
assert (0 <= x && x <= MAX);
if (x > 0) // (1)
{ // (2)
if (v[x-1] > value) v[x-1] = value; // (3)
guess(v, x-1, value); // (4)
}
}
b)
[20%] Escribe una implementación iterativa equivalente en lenguaje C.
Pregunta 2.c · Análisis de complejidad y eficiencia
A partir del código C de la función recursiva guess:
#define MAX 64
void guess (int v[MAX], int x, int value)
{
assert (0 <= x && x <= MAX);
if (x > 0) // (1)
{ // (2)
if (v[x-1] > value) v[x-1] = value; // (3)
guess(v, x-1, value); // (4)
}
}
c)
[30%] Deduce formalmente la complejidad computacional del algoritmo en su versión recursiva.
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