Introducción a la programación Parcial 2 - 27-11-2018
Nombre:
Nota media: Ha de obtenerse una nota mínima de 4 sobre 10 en el test y de 4 sobre 10 en el problema para hacer media.
Test (5 puntos)
Las respuestas deben marcarse en el cuadro siguiente. En cada pregunta, sólo una de las respuestas es correcta.
Nota test (sobre 10): 1.25 * ( PreguntasBien - (PreguntasMal / 3) )
R E S P U E S T A S
1 2 3 4 5 6 7 8
a
b
c
d
Pregunta 1
En el vector con ocupación variable V hay cinco valores almacenados: A B C D E.
Se ejecuta el siguiente módulo sobre V:
void desplazar (vov &V) {
int i;
for(i=[Link]-1;i>0;i--)
[Link][i-1] = [Link][i];
}
¿Qué información queda en V?
a) A A A A A b) E E E E E c) A A B C D d) B C D E E
Pregunta 2
Los mejores algoritmos de búsqueda de un elemento en un vector tienen complejidad:
a) O(log n) si buscamos en un vector ordenado y O(n) si buscamos en un vector sin ordenar
b) O(n) si buscamos en un vector ordenado y O(log n) si buscamos en un vector sin ordenar
c) O(log n), independientemente de que busquemos en un vector ordenado o sin ordenar
d) O(n), independientemente de que busquemos en un vector ordenado o sin ordenar
Pregunta 3
Se implementa el TAD Cola con la siguiente representación en un vector con ocupación variable. En el ejemplo, Z es el
primer elemento de la cola y E, el último.
Z A H R E
Vector Z A H R E
Contador 5
¿Cuál de las siguientes afirmaciones es correcta?
a) encolar (insertar), desencolar (borrar) y primero se pueden implementar con coste O(1)
b) encolar (insertar) y primero se pueden implementar con coste O(1) y desencolar (borrar) con coste O(n)
c) encolar (insertar) se puede implementar con coste O(1) y desencolar (borrar) y primero con coste O(n)
d) desencolar (borrar) y primero se pueden implementar con coste O(1) y encolar (insertar) con coste O(n)
Pregunta 4
¿Es correcta la siguiente función para determinar si la matriz cuadrada A es simétrica o no?
bool simetrica (tipoMatriz A) {
int i, j;
bool sim;
sim = true;
for (i=0; i<N; i++) {
for (j=0; j < N/2; j++) {
if (A[i][j] != A[j][i])
sim = false;
}
}
return sim;
}
a) Sí, y no compara el mismo par nunca b) Sí, pero se compara el mismo par dos veces c) No d) Se cuelga
Introducción a la programación Parcial 2 - 27-11-2018
Pregunta 5
Dada esta definición de tipos y las siguientes funciones:
typedef int vector[100];
int mayor1 (vector v) { int mayor2 (vector v) {
int i, max; int i, max;
max = v[0]; max = 0;
for (i = 1; i <100; i++) { for (i = 0; i<100; i++) {
if (v[i] > max) if (v[i] > max)
max = v[i]; max = v[i];
} }
return (max); return (max);
} }
¿Cuál de los módulos anteriores es correcto para calcular el mayor de los elementos del vector?
a) mayor1 b) mayor2 c) mayor1 y mayor 2 d) Ninguno de los dos
Pregunta 6
¿En cuál de los siguientes supuestos se produce el caso mejor en el algoritmo de inserción al principio en un vector con
ocupación variable?
a) Cuando el tamaño del vector es el mínimo posible.
b) Hay un caso único, independiente de los valores que haya en el vector o del valor que se inserte.
c) Cuando el elemento que se quiere insertar es menor que todos los que hay en el vector.
d) Cuando el elemento que se quiere insertar es mayor que todos los que hay en el vector.
Pregunta 7
Dada la siguiente definición de constantes, tipos y variables:
const int N = 100;
struct TipoRegistro {
float X;
int Y;
}
typedef TipoRegistro TipoVector[N];
struct TipoEstructura {
TipoVector Vector;
int Cont;
}
// variables
TipoEstructura E;
TipoRegistro R;
¿Cuál de las siguientes asignaciones es correcta?
a) [Link][100].Y = R.Y; b) TipoVector[3].X = 3.1; c) [Link][0] = R; d) E[5].Vector = R;
Pregunta 8
Dada la siguiente definición: typedef int TVector[10].
¿Cuál de los siguiente módulos determina correctamente si un valor X está almacenado en el vector?
bool buscar1(TVector V, int X){ bool buscar2(TVector V, int X){
bool enc; int pos = 0;
int i; if (pos<10)
enc = false; if(V[pos]==X)
while (!enc) return true;
if (V[i]==X) else return (buscar2(V,X));
enc = true; else
return enc; return false;
} }
a) buscar1 b) buscar2 c) los dos d) ninguno
Introducción a la programación Parcial 2 - 27-11-2018
Problema: Objetivos de Desarrollo Sostenible (ODS) (5 puntos)
El 25 de septiembre de 2015, los líderes mundiales adoptaron un conjunto de objetivos globales para erradicar la pobreza,
proteger el planeta y asegurar la prosperidad para todos como parte de una nueva agenda de desarrollo sostenible. Cada
objetivo tiene metas específicas que deben alcanzarse antes de 2030.
Una ONG te ha pedido ayuda para desarrollar una aplicación que permita consultar el nivel de cumplimiento de esas metas
por parte de los países.
Hay 17 objetivos identificados por un número de 1 a 17 (Fin de la pobreza, Educación de calidad, Igualdad de género, etc.).
Esta ONG hace una estimación del grado de cumplimiento (un porcentaje, de 0 a 100%) de un objetivo por un país.
Ya se ha definido un TAD Objetivo que gestiona la información de un objetivo en un país: código del objetivo (un entero),
nombre del país (una cadena) y grado de cumplimiento (un real). Las cabeceras de las operaciones del TAD Objetivo son:
// Inicia la información del objetivo con los datos indicados
void nuevo (int codigo, string pais, float grado, Objetivo &ob);
// Actualiza el grado de cumplimiento del objetivo ob
void actualizaObjetivo( Objetivo &ob, float grado);
int obtenerCodigo (Objetivo ob); //Devuelve el código del objetivo ob
string obtenerPais (Objetivo ob); //Devuelve el país del objetivo ob
float obtenerGrado (Objetivo ob);//Devuelve el grado de cumplimiento de ob
A partir del número de países y del número de objetivos se ha estimado que habrá menos de 3500 datos que almacenar.
La especificación de las operaciones del TAD Gestor que se deben implementar son las siguientes:
TAD
Gestor: iniciar, insertar, media, mayor, borrar
Operaciones
iniciar salida Gestor
efecto Inicia la estructura sin información
insertar (g: Gestor, código: entero, país: string, grado: real)
modifica g
efecto Actualiza el gestor con la información de un nuevo dato. Si ya existía
información de ese mismo código de objetivo y país, se sustituye por el nuevo
dato. Si no, se inserta la nueva información. Podemos suponer que la estructura
no está llena.
media (g: Gestor, código: entero) salida real
efecto Devuelve el grado medio de cumplimiento del código de indicador
dato. El grado medio se calcula como la media del cumplimiento de todos los
países sobre los que hay información en el gestor. Si no hubiera ningún dato de
ese indicador, devolverá 0.
mayor (g: Gestor) salida entero, string
efecto Devuelve el código y el país del indicador que tiene el mayor grado de
cumplimiento. Podemos suponer que habrá como mínimo un objetivo
almacenado en el gestor. Si hay varios objetivos con el mismo grado de
cumplimiento, devolverá uno cualquiera.
borrar (g: Gestor, país: string) modifica Gestor
efecto Elimina de la estructura la información de todos los objetivos del país
indicado.
Otro voluntario de esta ONG ya ha implementado el TAD Objetivo, ha definido la estructura de datos para el Gestor y ha
implementado la operación iniciar.
const int MAX = 3500;
typedef Objetivo TVector[MAX];
struct Gestor {
TVector vector;
int ocupadas;
};
void iniciar (Gestor &g) {
[Link] = 0;
}
1. Implementar de forma eficiente las operaciones insertar, media, mayor y borrar del TAD Gestor. (2.5 puntos
cada una)