Examen Final Enero 2012 (2012)

Examen Español
Universidad Universidad Politécnica de Cataluña (UPC)
Grado Ingeniería de Sistemas de Telecomunicación - 1º curso
Asignatura Fonamentos de Ordenadores
Año del apunte 2012
Páginas 9
Fecha de subida 16/09/2014
Descargas 0
Subido por

Vista previa del texto

Fonaments d’Ordinadors 17 de enero de 2012 Departament d’Arquitectura de Computadors Notas provisionales: 23/01/2012, a las 14h Límite alegaciones: Notas definitivas: 25/01/2012, hasta 15h 26/01/2012, a las 13h Profesores: P. Bofill, J. Delgado, M. Farreras, M. Jiménez, J. Jo, E. Lara, S. Llorente, T. Monreal, M. Moretó, B.
Otero, E. Rodriguez, M.A. Villanueva.
• • • • Duración del examen: 3h Contestar los problemas 1, 2 y 3 en hojas de examen separadas Se puede consultar únicamente la documentación entregada en el examen Colocar las etiquetas entregadas en ambas caras de todas las hojas de respuestas Problema 1 (3.0 puntos, 60 minutos) a) (0.5 punts) Escriu un programa en C que llegeixi de teclat una frase acabada en ‘\n’ de com a màxim MAX_CHARS caràcters. Es pot assumir que l’usuari no introduirà mai una frase que superi aquesta longitud. Desa la longitud de la frase a la variable lon_frase (sense contar el ‘\n’). Després de llegir la frase, mostra la mateixa frase per pantalla. No es poden usar funcions de la llibreria string.h ni %s per llegir o mostrar cadenes de caràcters.
Exemple d’execució (En negreta les dades introduïdes per l’usuari): Introduir frase acabada en '\n': Bon dia a tothom! Avui toca examen de FO Frase llegida: Bon dia a tothom! Avui toca examen de FO b) (1.5 punts) A continuació, s’ha de trobar la lletra de l’abecedari que apareix més vegades repetida a la frase llegida a l’anterior exercici. No s’ha de diferenciar entre majúscules i minúscules. En cas d’empat, mostra la lletra que primer es troba a l’abecedari. També s’ha de mostrar el número d’aparicions d’aquesta lletra. Recorda que hi ha un total de 26 lletres diferents. Declara les noves variables que es necessiten i, després, escriu el tros de codi que aniria al final del codi anterior.
Exemple d’execució (En negreta les dades introduïdes per l’usuari): Introduir frase acabada en '\n': Bon dia a tothom! Avui toca examen de FO Frase llegida: Bon dia a tothom! Avui toca examen de FO La lletra que surt mes vegades a la frase es: a (5 vegades) c) (1.0 punt) Assumeix que disposem d’un codi que llegeix una seqüència de caràcters acaba en un ‘.’ i la guarda a la variable seqüencia, així com guarda la seva longitud a la variable lon_sequencia. Escriu un codi que determini quantes vegades apareix la seqüència a la frase introduïda al primer apartat. En aquest cas, s’ha de diferenciar entre majúscules i minúscules. Declara les noves variables que es necessiten i, després, afegeix el tros de codi que aniria al final del codi anterior. No fa falta implementar el codi que demana la seqüència a l’usuari.
Exemple d’execució (En negreta les dades introduïdes per l’usuari): Introduir frase acabada en '\n': Bon dia a tothom! Avui toca examen de FO Frase llegida: Bon dia a tothom! Avui toca examen de FO La lletra que surt mes vegades a la frase es: a (5 vegades) Introduir sequencia a cercar acabada en '.': to.
La sequencia apareix 2 vegades a la frase.
1 Problema 2 (3.0 puntos, 50 minutos) La cadena de gimnasios siempre_en_forma tiene una aplicación informática que gestiona la información de sus socios. Actualmente la aplicación ya tiene implementadas las funcionalidades de buscar socios y mostrar cadena de caracteres, y se quiere añadir las funcionalidades de eliminar socios y realizar descuento a socios menores de 25 años, así como el menú principal, que permitirá a los usuarios interactuar con la aplicación.
Para ello la aplicación dispone de los siguientes tipos de datos: #define MAXN 50 #define MAXS 100 typedef struct{ int dia; int mes; int anyo; }tfecha; typedef struct{ int num_socio; char nom[MAXN]; tfecha fn; /* Fecha de nacimiento */ float cuota; }tsocio; typedef struct{ int num_socios; tsocio socio[MAXS]; }tlista_socios; Suponga que la aplicación tiene implementadas las siguientes funciones: int buscar_socio (tlista_socios ls, int nsocio) Esta función devuelve la posición que ocupa el socio con número de socio nsocio en la lista. Si no hay ningún socio con dicho número devuelve -1.
void mostrar_cadena(char cad[MAXN]) Muestra por pantalla la cadena cad que se le pasa como parámetro.
Se pide: a) (1.0 pto) Implementar la siguiente función: int eliminar_socio(tlista_socios *ls, int nsocio) Esta función elimina de la lista de socios (parámetro ls) el socio que se ha dado de baja (parámetro nsocio), si este se encuentra en la lista. En caso contrario, no se elimina ningún socio de la lista. Para obtener la posición que ocupa un socio en la lista utiliza la función buscar_socio.
La función devuelve 0 si el socio ha sido eliminado de la lista, -1 si no existe ningún socio con el número de socio nsocio, que se le pasa como parámetro, y -2 si la lista está vacía.
b) (1.0 pto) Implementar la siguiente función: int descuento_menores_25(tlista_socios *ls, tfecha fa) Esta función realiza un 25% de descuento sobre la cuota (modificando dicho campo), a los socios menores de 25 años (inclusive), y muestra el nombre del socio al que se le ha aplicado el descuento y el monto de la nueva cuota. Esta función recibe como parámetros la lista de socios (parámetro ls) y la fecha actual (parámetro fa). La aplicación devuelve el número de socios menores de 25 años (0 en caso de que no haya ninguno).
Por ejemplo, si tenemos la socia Sara Pons que nació el 01/11/1987 y paga una cuota de 80€, la función mostrará por pantalla: Los socios menores de 25 años son: Sara Pons Nueva cuota: 60.00€ c) (1.0 pto) Usando las funciones implementadas en los apartados anteriores, escribir el programa principal, que pida al usuario desde teclado el número del socio que se quiere dar de baja del gimnasio, lo elimine de la lista y muestre por pantalla si se ha eliminado correctamente. En caso contrario, mostrará el error correspondiente, es decir, si no hay 2 ningún socio con el número introducido por el usuario, o si la lista está vacía. A continuación, el programa mostrará por pantalla todos los socios que han podido disfrutar de la promoción descuento menores de 25, para ello mostrará el nombre y la nueva cuota de cada uno de los socios a los que se les ha aplicado la promoción. El programa también mostrará el número de socios a los que se ha aplicado la promoción.
Ejemplos de ejecución: Suponga que tenemos la lista de socios inicializada como se muestra a continuación: tlista_socios ls={5,{{1, "Juan Perez", {01,02,1970}, 60}, {2, "Sara Pons", {01,11,1987}, 80},{5, "Jose Tor", {01,01,1978}, 65}, {6, "Alicia Puente", {02,05,1979}, 90},{8, "Tom Peña", {07,12,1960}, 90}}}; Ejemplo 1 Introduzca el número del socio a dar de baja: 2 El socio se ha eliminado correctamente El descuento menores de 25 se ha aplicado a 0 socio(s).
Ejemplo 2 Introduzca el número del socio a dar de baja: 15 El socio no se ha eliminado. No hay ningún socio con dicho número en la lista Los socios menores de 25 años son: Sara Pons Nueva cuota: 60.00 El descuento menores de 25 se ha aplicado a 1 socio(s).
Problema 3 (4.0 puntos, 70 minutos) Queremos convertir en una subrutina el siguiente código ensamblador IA32 que ordena un vector de 10 números enteros que empieza en la dirección vector: ordenar: a: b: c: movl $1, %esi cmpl $10, %esi jge d movl vector(, %esi, 4), %eax movl %esi, %edi decl %edi cmpl $0, %edi jl c cmpl vector(, %edi, 4), %eax jge c movl vector(, %edi, 4), %edx movl %edx, 4+vector(, %edi, 4) # En la instrucción anterior, 4+vector es el desplazamiento decl %edi jmp b incl %edi movl %eax, vector (, %edi, 4) incl %esi jmp a d: Responder razonada y brevemente las siguientes preguntas: a) (1.25 ptos) Observar cómo realiza la ordenación del vector de enteros el código anterior.
Escribir el código en lenguaje C.
b) (0.5 ptos) Como primera fase en la conversión del código a una subrutina, añadir (indicando dónde) el código ensamblador para las fases 4 a 11 (las necesarias) de la programación de una subrutina. Suponga que todas las variables locales se almacenan en registros.
NOTA: La cabecera de la función en C de la subrutina es: void ordenar (int vector[10]); 3 c) (0.5 ptos) Dibujar el estado de la pila (bloque de activación) justo antes de ejecutar la primera instrucción del código del enunciado. Indicar los desplazamientos respecto a %ebp de todos los elementos de la pila.
d) (0.5 ptos) Como segunda fase en la conversión del código a una subrutina, deberíamos modificar todos los accesos a los elementos del vector que se pasa como parámetro.
Cambiar (por la instrucción o instrucciones necesarias) sólo la instrucción: movl vector(, %esi, 4), %eax e) (1.25 ptos) Codificar en ensamblador el siguiente trozo de un main de un programa escrito en lenguaje C donde se llama a la subrutina ordenar que hemos ido construyendo (suponga que el vector ya está declarado e inicializado): while (vector [9] > 100){ vector[9] = 100; ordenar(vector); if (vector[0] == 100) vector[0] = 0; } 4 Documentación para el problema 3 Operaciones involucradas en el uso de subrutinas: SUBR1 (Subrutina que llama) SUBR2 (Subrutina llamada) 1 4 5 6 2 3 12 13 14 Salvar registros (%eax, %ecx, %edx) Paso de parámetros Llamada a SUBR2 Recoger resultado Eliminar parámetros Restaurar registros (%edx, %ecx, %eax) Establecer enlace dinámico Reservar espacio para variables locales Salvar registros (%ebx, %esi, %edi) # Código de SUB2 7 8 Devolver resultado Restaurar registros (%edi, %esi, %ebx) Liberar espacio de variables locales Deshacer enlace dinámico Retorno 9 10 11 NOTA: La numeración indica el orden cronológico en el que se ejecutan las operaciones.
Instrucciones básicas de IA32: /* Copiar contenidos: op2 = op1 */ movl op1, op2 movw op1, op2 movb op1, op2 /* op2, op1 de 4 bytes */ /* op2, op1 de 2 bytes */ /* op2, op1 de 1 byte */ /* Suma: op2 = op2 + op1 */ addl op1, op2 addw op1, op2 addb op1, op2 /* op2, op1 de 4 bytes */ /* op2, op1 de 2 bytes */ /* op2, op1 de 1 byte */ /* Resta: op2 = op2 - op1 */ subl op1, op2 subw op1, op2 subb op1, op2 /* op2, op1 de 4 bytes */ /* op2, op1 de 2 bytes */ /* op2, op1 de 1 byte */ /* Producto: op2 = op2 * op1 */ imull op1, op2 imull op1, op2, op3 imulw op1, op2 imulw op1, op2, op3 /* /* /* /* /* /* op2, op1 de 4 bytes.op2 es registro */ op3, op2, op1 de 4 bytes, op1 es inmediato, op2 es memoria o registro y op3 es registro op2, op1 de 2 bytes, op2 es registro op3, op2, op1 de 4 bytes, op1 es inmediato, op2 es memoria o registro y op3 es registro */ */ */ */ /* Salto incondicional */ jmp etiqueta /* salto a etiqueta */ /* Comparación: op2 - op1, sólo modifica registro de flags */ cmpl op1, op2 cmpw op1, op2 cmpb op1, op2 /* op2, op1 de 4 bytes */ /* op2, op1 de 2 bytes */ /* op2, op1 de 1 byte */ /* Salto condicional según valores del registro de flags */ je jne jg jge jl jle etiqueta etiqueta etiqueta etiqueta etiqueta etiqueta /* /* /* /* /* /* salto salto salto salto salto salto a a a a a a etiqueta etiqueta etiqueta etiqueta etiqueta etiqueta si si si si si si op1 op1 op2 op2 op2 op2 == op2 != op2 > op1 >= op1 < op1 <= op1 */ */ */ */ */ */ /* Conversión de tipo: op2 = ExtSigno(op1) */ movsbl movsbw movswl op1, op2 op1, op2 op1, op2 /* op2 de 4 bytes, op1 de 1 byte. op2 es registro */ /* op2 de 2 bytes, op1 de 1 byte. op2 es registro */ /* op2 de 4 bytes, op1 de 2 byte. op2 es registro */ /* Gestión de subrutinas */ call etiqueta ret /* salto a etiqueta y guarda en pila la dirección de retorno */ /* saca de la pila la dirección de retorno y ejecuta la instrucción que se encuentra en la dirección de retorno */ /* Instrucciones para el manejo de la pila */ push[w|l] op1 pop[w|l] op1 /* Copia el operando op1 en la cima de la pila */ /* Copia en el operando op1 lo que se encuentra en la cima de la pila */ 5 Fonaments d’Ordinadors 17 de enero de 2012 Departament d’Arquitectura de Computadors Notas provisionales: 23/01/2012, a las 14h Límite alegaciones: Notas definitivas: 25/01/2012, hasta 15h 26/01/2012, a las 13h Profesores: P. Bofill, J. Delgado, M. Farreras, M. Jiménez, J. Jo, E. Lara, S. Llorente, T. Monreal, M. Moretó, B.
Otero, E. Rodriguez, M.A. Villanueva.
• • • • Duración del examen: 3h Contestar los problemas 1, 2 y 3 en hojas de examen separadas Se puede consultar únicamente la documentación entregada en el examen Colocar las etiquetas entregadas en ambas caras de todas las hojas de respuestas Solución Problema 1 (3.0 puntos, 60 minutos) #include <stdio.h> #define MAX_CHARS 256 #define NUM_LLETRES 26 main(){ char frase[MAX_CHARS], sequencia[MAX_CHARS]; int i, j, lon_frase, lon_sequencia, num_repeticions, posi_max; int num_aparicions[NUM_LLETRES]; // (0.5 ptos) Apartado a printf("Introducir la frase acabada en '\n': "); i = 0; scanf("%c", &frase[i]); while (frase[i]!='\n'){ i++; scanf("%c", &frase[i]); } lon_frase = i; printf("Frase llegida: "); for (i=0; i<lon_frase; i++){ printf("%c", frase[i]); } printf("\n"); // (1.5 ptos) Apartado 1.b for (i=0; i<NUM_LLETRES; i++) num_aparicions[i] = 0; for (i=0; i<lon_frase; i++){ if (frase[i]>='a' && frase[i]<='z') num_aparicions[frase[i]-'a']++; else if (frase[i]>='A' && frase[i]<='Z') num_aparicions[frase[i]-'A']++; } posi_max = 0; for (i=0; i<NUM_LLETRES; i++) if (num_aparicions[i]>num_aparicions[posi_max]) posi_max = i; printf("La letra que aparece mas veces en la frase es: %c (%d vegades)\n",'a'+posi_max,num_aparicions[posi_max]); // (0 ptos) Apartado 1.c (se supone implementado) printf("Introducir la secuencia a buscar acabada en '.':\n"); i = 0; scanf("%c", &sequencia[i]); while (sequencia[i]!='.'){ i++; scanf("%c", &sequencia[i]); } 1 lon_sequencia = i; // (1.0 pto) Apartado 1.c num_repeticions = 0; for (i=0; i<lon_frase-lon_sequencia+1; i++){ j = 0; while (frase[i+j]==sequencia[j] && j<lon_sequencia) j++; if (j==lon_sequencia) num_repeticions++; } printf("La secuencia aparece %d veces en la frase.\n", num_repeticions); } Problema 2 (3.0 puntos, 50 minutos) a) (1 pto) int eliminar_socio(tlista_socios *ls, int nsocio){ int pos, i, er; er=-1; if(ls->num_socios==0) er = -2; else{ pos = buscar_socio(*ls, nsocio); if(pos!=-1){ for(i=pos; i<ls->num_socios-1; i++) ls->socio[i] = ls->socio[i+1]; ls->num_socios--; er = 0; } } return er; } b) (1 pto) int descuento_menores_25(tlista_socios *ls, tfecha fa){ int i, desc=0, edad; for(i=0; i<ls->num_socios; i++){ if((fa.mes > ls->socio[i].fn.mes) || (fa.mes == ls->socio[i].fn.mes && fa.dia >= ls->socio[i].fn.dia)) edad = fa.anyo - ls->socio[i].fn.anyo; else edad = fa.anyo - ls->socio[i].fn.anyo - 1; if(edad<=25){ if(desc==0) printf("Los socios menores de 25 años son:\n"); ls->socio[i].cuota = ls->socio[i].cuota*0.75; mostrar_cadena(ls->socio[i].nom); printf("\nNueva cuota: %f€\n", ls->socio[i].cuota); desc++; } } return desc; } c) (1 pto) main(){ //La lista socios se la proporcionamos tlista_socios ls = {5,{{1, "Juan Perez", {01,02,1970}, 60}, {2, "Sara Pons", {01,11,1987}, 80},{5, "Jose Tor", {01,01,1978}, 65}, {6, "Alicia Puente", {02,05,1979}, 90},{8, "Tom Peña", {07,12,1960}, 90}}}; int pos, ns, total25; tfecha fecha_act = {17,01,2012}; printf("Introduzca el número de socio que se quiere dar de baja: "); scanf("%d", &ns); pos = eliminar_socio(&ls, ns); if(pos == -2) printf("No hay socios en la lista\n"); 2 else if (pos == -1) printf("El socio no se ha eliminado. No hay ningún socio con dicho número en la lista\n"); else printf("El socio se ha eliminado correctamente\n"); total25 = descuento_menores_25(&ls,fecha_act); printf("El descuento menores de 25 se ha aplicado a %d socio(s).\n", total25); } Problema 3 (4.0 puntos, 70 minutos) a) (1.25 ptos) for (i = 1; i < 10; i++){ tmp = vector[i]; j = i – 1; while ((j >= 0) && (tmp < vector[j])){ vector[j + 1] = vector[j]; j--; } j++; vector[j] = tmp; } Otra alternativa puede ser: for (i = 1; i < 10; i++){ tmp = vector[i]; for j = i - 1; (j >= 0) && (tmp < vector[j]); j--){ aux = vector[j]; vector[j+1] = aux; } j++; vector[j] = tmp; } O cualquier combinación de lo anterior (for vs. while, uso de variable auxiliar).
b) (0.5 ptos) pushl %ebp movl %esp, %ebp pushl %esi pushl %edi # Asumimos que la subrutina de llamada salva %eax y %edx si es necesario # Código inicial aquí popl %edi popl %esi movl %ebp, %esp # No es estrictamente necesario # al no tener variables locales en la pila popl %ebp ret c) (0.5 ptos) %edi %ebp – 8 %esi %ebp – 4 %ebp %ebp @retorno %ebp + 4 @vector %ebp + 8 NOTA: Aceptar que es posible salvar en la pila %eax, %edx, %ecx 3 a) (0.5 ptos) Como la dirección del vector está en la dirección de la pila %ebp+8, hemos de acceder allí para obtener la dirección y después, indirectamente, al elemento del vector que nos interese. Por tanto, movl vector(, %esi, 4), %eax cambia a: movl 8(%ebp), %ecx movl (%ecx, %esi, 4), %eax NOTA: Si en vez de %ecx usamos %ebx, será necesario salvar el estado del registro en la pila.
b) (1.25 ptos) while: if: end_if: end_while: movl $9, %edi cmpl $100, vector (,%edi,4) # O directamente sin %edi: jle end_while movl $100, vector(,%edi,4) # Alternativamente: pushl $vector call ordenar addl $4, %esp cmpl $100, vector jne end_if movl $0, vector jmp while 4 cmpl $100, vector+36 movl $100, vector+36 ...