Examen Final Enero 2010 (2010)

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 2010
Páginas 12
Fecha de subida 16/09/2014
Descargas 0
Subido por

Vista previa del texto

Fundamentos de Ordenadores 14 de Enero de 2011 Departamento de Arquitectura de Computadores Notas provisionales: Límite alegaciones: Notas definitivas: 21/01/2011, 20:00 26/01/2011, 09:00 28/01/2011, 20:00 Profesores: C. Barrado, P. Bofill, M. Jiménez, J. Jo, X. León, S. Llorente, F. Mochon, M. Moretó, B. Otero, A. San Martino, G. Utrera, M. Valero, M. A. Villanueva.
• • • Duración del examen: 3h Conteste los problemas 1, 2, 3, 4 y 5 en hojas de examen separadas Se puede consultar únicamente el folio resumen Problema 1 (1.5 puntos, 30 minutos) a) (0.5 ptos) Defina el tipo de datos tcarta que permite almacenar la siguiente información de una carta de la baraja inglesa.
• Palo de la carta /* T-Tréboles, P-Picas, C-Corazones, D-Diamantes */ • Número de la carta /* valor entre 1 y 13, donde los números 1, 11, 12 y 13 corresponden al As, la J, la Q y la K, respectivamente */ b) (1 pto) Escriba un programa en C que permita introducir desde teclado los datos de un conjunto de cartas y muestre por pantalla el valor total del conjunto de cartas.
El programa pedirá primero al usuario cuantas cartas va a introducir y a continuación solicitará la información de las cartas (ver los ejemplos de ejecución) El valor de un conjunto de cartas es la suma del valor individual de cada carta y el valor de una carta es directamente el número que representa, excepto el As que vale 15 y las figuras J (11), Q (12) y K (13) que valen siempre 10. Además, las cartas rojas (Corazones y Diamantes) duplican su valor individual.
A la hora de leer los datos de las cartas se debe comprobar que el palo y el número sean válidos. Si no es así, se debe mostrar un mensaje indicando que hay un error en los datos de entrada.
Ejemplos de ejecución: Ejemplo 1: Cuantas cartas va a introducir? 4 Introduzca las cartas separadas por blancos: 10C 11T 3P 4D Valor total: 41 Ejemplo 2: Cuantas cartas va a introducir? 4 Introduzca las cartas separadas por blancos: 10H 15T 3P 4D Hay errores en la entrada de datos.
1 Recordatorio de instrucciones básicas de IA32 (para los problemas 4 y 5): /* Copiar movl op1, movw op1, movb op1, contenidos: op2 /* op2 /* op2 /* op2 = op1 */ op2, op1 de 4 bytes */ op2, op1 de 2 bytes */ op2, op1 de 1 byte */ /* Suma: op2 = op2 + op1 */ addl op1, op2 /* op2, op1 de 4 bytes */ addw op1, op2 /* op2, op1 de 2 bytes */ addb op1, op2 /* op2, op1 de 1 byte */ /* Resta: subl op1, subw op1, subb op1, op2 = op2 op2 /* op2 /* op2 /* op1 */ op2, op1 de 4 bytes */ op2, op1 de 2 bytes */ op2, op1 de 1 byte */ /* Incremento/Decremento: incl/decl op1 /* op1 incw/decw op1 /* op1 incb/decb op1 /* op1 op1++/op1-- */ de 4 bytes */ de 2 bytes */ de 1 byte */ /* Producto: op2 = op2 * op1 op3 = op2 * op1 */ imull op1, op2 /* op2, op1 de imull op1, op2, op3 /* op3, op2, inmediato, op3 o registro */ imulw op1, op2 /* op2, op1 de imulw op1, op2, op3 /* op3, op2, inmediato, op3 o registro */ 4 bytes, op2 es registro */ op1 de 4 bytes, op1 es es registro y op2 es memoria 2 bytes, op2 es registro */ op1 de 2 bytes, op1 es es registro y op2 es memoria /* Salto incondicional */ jmp etiqueta /* salto a etiqueta */ /* Comparación: op2 - op1, sólo modifica registro de flags */ cmpl op1, op2 /* op2, op1 de 4 bytes */ cmpw op1, op2 /* op2, op1 de 2 bytes */ cmpb op1, op2 /* op2, op1 de 1 byte */ /* Salto condicional según valores del registro je etiqueta /* salto a etiqueta si jne etiqueta /* salto a etiqueta si jg etiqueta /* salto a etiqueta si jge etiqueta /* salto a etiqueta si jl etiqueta /* salto a etiqueta si jle etiqueta /* salto a etiqueta si de flags */ op1 == op2 */ op1 != op2 */ op2 > op1 */ op2 >= op1 */ op2 < op1 */ op2 <= op1 */ /* conversión de tipo: op2=ExtSigno(op1) */ movsbl op1, op2 /* op2 de 4 bytes, op1 de 1 byte */ movsbw op1, op2 /* op2 de 2 bytes, op1 de 1 byte */ movswl op1, op2 /* op2 de 4 bytes, op1 de 2 byte */ /* gestión de subrutinas */ call etiqueta /* salto a etiqueta y guarda en pila la dirección de retorno */ ret /* saca de la pila la dirección de retorno y pasa a ejecutar la instrucción que se encuentra en esa dirección de retorno */ pushl op1 /* guarda op1 en la cima de la pila */ popl op1 /* extrae el valor almacenado en la cima de la pila y lo guarda en op1 */ 2 Problema 2 (1.5 puntos, 30 minutos) Queremos hacer la unión de dos vectores de enteros.
El vector A es de dimensión N (constante definida) y NO contiene elementos repetidos. El vector B es de dimensión N y NO contiene elementos repetidos, aunque alguno de sus elementos puede coincidir con algún elemento del vector A.
Se pide rellenar el código que falta para crear un vector unión que contenga todos los elementos de los vectores A y B pero ninguno repetido (tenga en cuenta que los valores de inicialización de vectores y constante se muestran como ejemplo). También queremos conocer el número de elementos guardados en ese vector unión (como máximo 2*N).
Por ejemplo, para los siguientes valores de N, A y B: #define N 5 int A[N] ={1, 3, 8, 2, 10}; int B[N] ={1, 6, 9, 11, 2}; El resultado sería: Vector union: 1, 3, 8, 2, 10, 6, 9, 11, Total de elementos: 8 Código: #include <stdio.h> #define N 5 main() { int totalElementos; int A[N]={1,3,8,2,10}; int B[N]={1,6,9,11,3}; int res[2*N]; /* Añadir las variables que os hagan falta */ /* Aqui va vuestro código */ printf("Vector union: "); for(i=0;i<totalElementos;i++) printf(" %d,",res[i]); printf("\n"); printf("Total de elementos: %d\n",totalElementos); } 3 Problema 3 ( 3 puntos, 60 minutos) La línea aérea vuela_siempre_seguro tiene una aplicación informática que gestiona la información de todos sus pasajeros para un vuelo. Esta aplicación utiliza los siguientes tipos de datos: #define MNOM 50 #define MAXP 150 #define CIERTO 1 #define FALSO 0 typedef struct{ int num; /* Numero de fila */ char letra; /* Posicion en la fila */ }Tasiento; typedef struct{ char nom[MNOM]; char categoria[MNOM]; Tasiento asiento; char obs[MNOM]; /* Nombre y apellidos del pasajero */ /* Primera clase, Segunda clase */ /* Numero de asiento */ /* Observaciones (Vegetariano, Alergico, Atencion personal, Silla ruedas). Solo puede incluirse una observación por pasajero. */ }Tpasajero; typedef struct{ int numpasajeros; /* Numero de pasajeros del vuelo */ Tpasajero pasajeros[MAXP]; /* Información de los pasajeros ordenada por orden alfabético (A-Z) del campo nom */ }Tvuelo; Actualmente la aplicación ya tiene implementadas las siguientes funciones: void leer_cadena(char cad[MNOM]) : Esta función lee del teclado una cadena de caracteres finalizada en '\n' y la guarda en cad.
int compara_cadenas(char cad1[MNOM], char cad2[MNOM]) : Esta función devuelve CIERTO si las cadenas cad1 y cad2 son exactamente iguales y FALSO en caso contrario.
void leer_pasajero(Tpasajero *p) : Esta función lee del teclado la información asociada a un pasajero y la guarda en *p. La información introducida desde el teclado tiene el siguiente formato: nombre: categoría: asiento: observación int buscar_pasajero(Tvuelo v, char nom[MNOM], int *pos) : Esta función devuelve CIERTO si el pasajero cuyo nombre está en nom se encuentra en la lista de pasajeros asociada al campo pasajeros del parámetro v. En el caso contrario, la función devuelve FALSO. Además, la función indica en *pos la posición que tiene (o que debería ocupar) el pasajero de nombre nom en el campo pasajeros del parámetro v.
NOTA: La información de los pasajeros en el campo pasajeros del parámetro v se encuentra ordenada alfabéticamente (de la A a la Z) por el campo nom.
Sin embargo, la aplicación informática que gestiona el personal de tierra cuando realiza el check-in de sus pasajeros tiene algunas limitaciones, y los responsables quieren mejorar dicha aplicación incluyendo nuevas funcionalidades. Para poder realizar esto, se pide que implemente las siguientes funciones usando las anteriores cuando sea necesario: a) (1.0 pto) int insertar_pasajero(Tvuelo *v, Tpasajero p) Esta función inserta el pasajero p en la lista de pasajeros (campo pasajeros del parámetro v) si el pasajero no se encuentra en dicha lista y la cantidad máxima de pasajeros de la lista no excede el valor MAXP. En cualquier otro caso, el pasajero no se inserta en la lista. Si es posible insertar el pasajero deberá conservarse el orden alfabético A-Z del campo nom en la lista de pasajeros.
La función devuelve CIERTO si el pasajero p ha sido insertado y FALSO en caso contrario.
4 b) (1.0 pto) int pasaje_categ_obs(Tvuelo v,char cat[MNOM],char obs[MNOM]) Esta función muestra por pantalla la ubicacion en el avión (número de asiento) de todos los pasajeros del vuelo v que tienen la categoria indicada en cat y la observación indicada en obs.
Además, la función devuelve la cantidad de pasajeros que cumplen con ambas condiciones (categoria+observación). Por ejemplo, si tenemos en cat “Segunda clase”, en obs “Atencion personal” y en v la siguiente información: Cruzado Laura: Primera clase: 3B: Vegetariano Dominguez Eli: Segunda clase: 24F: Alergico Gomez Virginia: Segunda clase: 17A: Atencion personal Martinez Diego: Primera clase: 2D: Silla ruedas Prieto Alex: Segunda clase: 22C: Atencion personal La función mostrará por pantalla los asientos 17A y 22C y retornará el valor de 2 (Gomez Virginia y Prieto Alex cumplen con estos criterios).
En caso de que no hubiese ningún pasajero que cumpla las dos condiciones, la función mostrará por pantalla el mensaje “No hay pasajeros que cumplan ambos criterios” y, consecuentemente, retornará un 0.
c) (1.0 pto) void main() Usando las funciones de la aplicación, escriba el programa principal que pida por teclado la información de 5 pasajeros y la incluya en una variable del tipo Tvuelo. El programa debe indicar si cada pasajero leído ha sido insertado en la lista de pasajeros.
Luego, el programa debe pedir desde teclado una categoría y una observación concretas y mostrar por pantalla los asientos que ocupan todos los pasajeros que cumplen con estos criterios. Además, el programa deberá mostrar por pantalla la cantidad total de pasajeros que tienen estas características (categoría y observación).
Ejemplos de ejecución: Ejemplo 1 Ejemplo 2 Introduzca la informacion de los 5 pasajeros: Introduzca la informacion de los 5 pasajeros: Cruzado Laura: Primera clase: 3B: Vegetariano Pasajero insertado Cruzado Laura: Primera clase: 3B: Vegetariano Pasajero insertado Dominguez Eli: Segunda clase: 24F: Alergico Pasajero insertado Dominguez Eli: Segunda clase: 24F: Alergico Pasajero insertado Gomez Virginia: Segunda clase: 17A: Atencion personal Pasajero insertado Martinez Diego: Primera clase: 2D: Silla ruedas Pasajero insertado Gomez Virginia: Segunda clase: 17A: Atencion personal Pasajero insertado Cruzado Laura: Primera clase: 3B: Vegetariano Pasajero no insertado Prieto Alex: Segunda clase: 22C: Atencion personal Pasajero insertado Prieto Alex: Segunda clase: 22C: Atencion personal Pasajero insertado Introduzca la categoria: Segunda clase Introduzca la categoria: Primera clase Introduzca la observacion: Silla de ruedas Los asientos de los pasajeros que cumplen con estos criterios son: No hay pasajeros que cumplan ambos criterios Cantidad de pasajeros con estos criterios: 0 Introduzca la observacion: Vegetariano Los asientos de los pasajeros que cumplen con estos criterios son: 3B Cantidad de pasajeros con estos criterios: 1 5 Problema 4 (1.5 puntos, 20 minutos) a) (0.3 ptos) Traduzca a ensamblador de IA32 la definición de las siguientes constantes y variables declaradas en lenguaje C.
#define DIM_MAX 20 short fuente[DIM_MAX], destino[DIM_MAX]; int i; b) (1.2 ptos) Traduzca a ensamblador de IA32 el siguiente código en lenguaje C. Utilice el registro %esi para almacenar el valor de la variable i.
for (i=0; i < DIM_MAX; i++) { if (fuente [i] >=0 || i*2 <= 10) destino[i] = fuente[i]; else destino[i] = -1 * fuente[i]; } Problema 5 (2.5 puntos, 40 minutos) Segons el següent codi: int f1(int *par1,int par2) { int i, res=0, fact=1; /* Estat pila */ for(i=0;i<par2;i++) { res=res+par2; fact=fact*par2; } *par1=fact; return (res); } Es demana: a) (0.5 ptos) Dibuixar l’estat de la pila (bloc d’activació) al punt del codi assenyalat com /* Estat pila */. Indicar clarament, els desplaçaments respecte al %ebp de totes les variables locals i paràmetres, suposant que la variable fact s’ha de guardar a la pila, mentre que les variables i i res es guarden a registres.
b) (1.5 ptos) Traduir a ensamblador IA32 la funció f1 completament.
c) (0.5 ptos) Per altra banda, a un altre punt del programa es crida a la funció f1: ...
int var, v[4]; v[0]=f1(&var,2); ...
Traduir a ensamblador IA32 la línia de codi assenyalada amb una fletxa i que correspon a la invocació de la funció f1. Suposem que les variables v i var han estat declarades, com a tals, a la secció bss.
6 Solución Problema 1 (1.5 puntos, 30 minutos) Solución: a) (0.5 ptos) typedef struct { char palo; int numero; }tcarta; b) (1 pto) void main() { tcarta c; int ncartas, total, valc, i, error; printf("Cuantas cartas va a introducir? "); scanf("%d%*c", &ncartas); error=0; total=0; printf("Introduzca las cartas separadas por blancos: "); for (i=0; i<ncartas && error==0; i++) { scanf("%d%c%*c", &c.numero, &c.palo); valc=0; if (c.numero>=1 && c.numero<=13 && (c.palo=='T' || c.palo=='P' || c.palo=='C' || c.palo == 'D')) { if (c.numero>=2 && c.numero<=10) valc=c.numero; else if (c.numero==1) valc=15; else valc=10; if (c.palo=='C' || c.palo == 'D') valc = valc*2; total = total+valc; } else error=1; } if (error==1) printf("Hay errores en la entrada de datos.\n"); else printf("Valor total: %d\n", total); } 7 Problema 2 (1.5 puntos, 30 minutos) #include <stdio.h> #define N 5 #define FALSO 0 #define CIERTO 1 main() { int totalElementos; int A[N]={1,3,8,2,10}; int B[N]={1,6,9,11,3}; int res[2*N]; /* Añadir las variables que os hagan falta */ int i,j, esta; /* Aqui va vuestro código */ for(i=0;i<N;i++) /*Copiar el vector A en res*/ res[i]=A[i]; totalElementos=N; for(i=0;i<N;i++)/*añadir los elementos de B no repetidos*/ { esta=FALSO; for(j=0;j<N && esta==FALSO;j++) { if(A[j]==B[i]) esta=CIERTO; } if(esta==FALSO) /*Añadimos al final el elemento pues no esta repetido*/ { res[totalElementos]=B[i]; totalElementos++; } } printf("Vector union: "); for(i=0;i<totalElementos;i++) printf(" %d,",res[i]); printf("\n"); printf("Total de elementos: %d\n",totalElementos); } 8 Problema 3 (3 puntos, 60 minutos) a) (1.0 pto) int insertar_pasajero(Tvuelo *v, Tpasajero p) { int i, pos, ins=FALSO; if (!buscar_pasajero(*v,p.nom,&pos) && (v->numpasajeros<MAXP)) { for(i=v->numpasajeros; i>pos; i--){ v->pasajeros[i]=v->pasajeros[i-1]; } v->pasajeros[pos]=p; ins = CIERTO; (v->numpasajeros)++; } return(ins); } b) (1.0 pto) int pasaje_categ_obs(Tvuelo v,char cat[MNOM],char obs[MNOM]) int i, cont=0; { for (i=0;i<v.numpasajeros;i++){ if (compara_cadenas(v.pasajeros[i].categoria, cat) && compara_cadenas(v.pasajeros[i].obs, obs)) { /* Categoria y Observacion coinciden */ printf("%d%c\n", v.pasajeros[i].asiento.num, v.pasajeros[i].asiento.letra); cont ++; } } if (cont == 0) printf(“No hay pasajeros que cumplan ambos criterios\n”); return(cont); } c) (1.0 pto) void main(){ char categoria[MNOM], obs[MNOM]; Tpasajero p; int cont, i; Tvuelo v; v.numpasajeros=0; for (i=0;i<5;i++){ leer_pasajero(&p); if(insertar_pasajero(&v,p)) printf(“Pasajero insertado\n”); else printf(“Pasajero no insertado\n”); } printf("\n Introduce la categoria: \n "); leer_cadena(categoria); printf("\n Introduce la observacion: \n "); leer_cadena(obs); printf("Los asientos de los pasajeros que cumplen con estos criterios son:\n"); cont = pasaje_categ_obs(v,categoria,obs); printf("Cantidad de pasajeros con estos criterios:%d\n",cont); } 9 Problema 4 (1.5 puntos, 20 minutos) a) (0.3 ptos) DIM_MAX = 20 .comm fuente, DIM_MAX * 2, 2 .comm destino, DIM_MAX * 2, 2 .comm i, 4, 4 b) (1.2 ptos) Versión normal movl $0, %esi for: cmpl $DIM_MAX, %esi # i < DIM_MAX ? jge endfor movw fuente (, %esi, 2), %ax cmpw $0, %ax # fuente[i] >= 0 jge if imull $2, %esi, %ebx cmpl $10, %ebx # i*2 <= 10 jg else if: movw %ax, destino (, %esi, 2) # destino[i] = fuente[i] incl %esi # i++ jmp for # Volver al bucle else: imulw $-1, %ax # fuente[i] * -1 movw %ax, destino (, %esi, 2) # destino[i] = fuente[i] * -1 incl %esi # i++ jmp for # Volver al bucle endfor: 10 Versión optimizada movl $0, %esi for: cmpl $DIM_MAX, %esi # i < DIM_MAX ? jge endfor movw fuente (, %esi, 2), %ax cmpw $0, %ax # fuente[i] >= 0 jge comun imull $2, %esi, %ebx cmpl $10, %ebx # i*2 <= 10 jle comun # No se cumple ninguna de las 2 condiciones.
imulw $-1, %ax # fuente[i] * -1 comun: movw %ax, destino (, %esi, 2) # destino[i] = fuente[i] o # destino[i] = fuente[i] * -1 incl %esi # i++ jmp for # Vover al bucle endfor: Problema 5 ( 2.5 puntos, 40 minutos) a) (0.5 ptos) registres fact %ebp %ebp-4 %ebp %ebp+4 %eip/@ret par1 (int *) par2 %ebp+8 %ebp+12 11 b) (1.5 ptos) f1: PUSHL %EBP MOVL %ESP,%EBP SUBL $4,%ESP PUSHL %EDI # per la variable res PUSHL %EBX # registre auxiliar PUSHL %ESI # per la variable i MOVL $0,%EDI # res=0 MOVL $1, -4(%EBP) # fact=1 MOVL $0,%ESI # i=0 e_for: CMPL 12(%EBP),%ESI JGE e_fifor MOVL 12(%EBP),%EBX ADDL %EBX,%EDI # res=res+par2 MOVL -4(%EBP),%EBX IMULL 12(%EBP),%EBX MOVL %EBX,-4(%EBP) # fact=fact*par2 INCL %ESI JMP e_for e_fifor: MOVL -4(%EBP),%EBX MOVL 8(%EBP),%ESI MOVL %EBX, (%ESI) # *par1=fact MOVL %EDI,%EAX # return res POPL %ESI POPL %EBX POPL %EDI MOVL %EBP,%ESP POPL %EBP RET c) (0.5 ptos) MOVL $2,%EBX PUSHL %EBX MOVL $var,%EBX PUSHL %EBX CALL f1 ADDL $8,%ESP MOVL %EAX,v 12 ...