Examen Final Julio 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 11
Fecha de subida 16/09/2014
Descargas 0
Subido por

Vista previa del texto

Fonaments d’Ordinadors 19 de junio de 2012 Departament d’Arquitectura de Computadors Notas provisionales: 26/06/2012 a partir de las 12:00 Límite alegaciones: 27/06/2012 a partir de las 13:00 Notas definitivas: 29/06/2012 a partir de las 16:00 Profesores: C. Alonso, M. Jiménez, J. Jo, E. Lara, S. Llorente, T. Monreal, J.L. Pérez, B. Otero.
• • • • 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 No se puede utilizar ningún dispositivo electrónico durante la realización del examen Problema 1 (2.0 puntos, 50 minutos) A partir del siguiente código: #define MAX 9 typedef struct { int R; /* Componente rojo */ int A; /* Componente azul */ int V; /* Componente verde */ } tpixel; main() { tpixel p; char cad[MAX]; /* Código apartado a) */ /* Código apartado b) */ } Se pide: a) (1.0 pto) Leer de teclado una cadena de 9 caracteres y almacenarla en la variable cad. A continuación, rotar la cadena 3 posiciones a la derecha y mostrarla por pantalla. La cadena rotada debe quedar almacenada en la variable cad.
Ejemplo de ejecución: Introducir cadena: 123456789 Cadena con rotación: 789123456 NOTAS: • Suponer que el usuario nunca introduce una cadena con menos de 9 caracteres.
• Si el usuario introduce más de 9 caracteres, sólo se guardarán los 9 primeros.
• Para realizar la rotación de la cadena no se puede utilizar una cadena auxiliar.
• Añadir la declaración de todas las variables necesarias para resolver el ejercicio.
b) (1.0 pto) La variable cad almacena una cadena de caracteres numéricos que representa la intensidad de los colores básicos de un píxel de la pantalla: rojo (los tres primeros caracteres), azul (los 3 caracteres centrales) y verde (los 3 últimos caracteres). Escriba el código necesario para almacenar en la variable p el valor numérico de la intensidad correspondiente a cada color básico y muestre por pantalla un mensaje que indique cuál es el color dominante del píxel, es decir, el color con mayor intensidad.
Ejemplo: Si la variable cad almacena la cadena 789123456, la variable p deberá almacenar los valores 789, 123 y 456 en los campos R, A y V, respectivamente y por pantalla se mostrará el mensaje: El color dominante es el ROJO.
789 ROJO 123 456 AZUL VERDE NOTAS: • Añadir todas las variables necesarias para resolver el ejercicio.
• Suponga que sólo puede haber un único color dominante.
1 Problema 2 (4.5 puntos, 70 minutos) Como ya habréis leído en la prensa, el ayuntamiento de Barcelona acaba de proponer una nueva red de transporte público, que añade nuevas líneas a la red actual y modifica algunas de las existentes. El ayuntamiento nos ha pedido que desarrollemos un programa informático que les ayude con la actualización de la nueva red de autobuses.
Para ello el programa dispone de los siguientes tipos de datos y las siguientes variables inicializadas: #define MAX_CHAR 50 #define MAX_LINEAS 200 typedef struct { int num; /* número de línea */ char origen[MAX_CHAR]; /* origen de la línea */ char destino[MAX_CHAR]; /* destino de la línea */ } tlinea_autobus; typedef struct { int num_lineas; /* número total de líneas */ tlinea_autobus llineas[MAX_LINEAS]; /* lista de líneas de autobuses, ordenada de menor a mayor por número de línea */ } tlista_lineas_autobus; main() { tlista_lineas_autobus actuales={9, {{6,"Pg. Manuel Girona", "Poblenou"}, {7, "Diagonal Mar", "Zona Universitaria"}, {9, "Pl. Catalunya", "Pg. Zona Franca"}, {10, "Pg. Maritim", "Montbau"}, {11, "Trinitat Vella", "Roquetes"}, {13, "Mercat St. Antoni", "Can Clos"}, {192, "Poblenou", "Poblenou"}, {193, "C. Montjuic", "C. Montjuic"}, {196, "Pl. Kennedy", "Bellesguard"}}}; tlista_lineas_autobus news={4, {{6,"Campus Nord", "Poblenou"}, {8, "Campus Nord", "Pl. Espanya"}, {13, "Pl. Catalunya", "Can Clos"}, {195, "Pl. Adria", "Pl. Adria"}}}; } El tipo de dato tlinea_autobus permite almacenar la información de una línea de autobús (número de línea, origen y destino). Por ejemplo: {6, “Pg. Manuel Girona”, “Poblenou”}.
El tipo de dato tlista_lineas_autobus permite almacenar una lista de líneas de autobuses.
El campo num_lineas indica cuántas líneas hay almacenadas en el campo llineas. Observar que la lista está ordenada de menor a mayor por el número de línea.
El ayuntamiento quiere que implementemos un programa que dada la lista de líneas de autobuses actuales (variable actuales del main) y la lista que contiene las líneas nuevas y las modificadas (variable news del main), actualice la lista actuales para que contenga la nueva red de autobuses. Recordar que la lista debe seguir ordenada de menor a mayor por número de línea.
El programa también debe mostrar por pantalla el listado de la nueva red de autobuses.
Ejemplo: Después de la ejecución del programa y suponiendo la inicialización anterior, la variable actuales, debe almacenar: actuales={11, {{6,"Campus Nord", "Poblenou"}, {7, "Diagonal Mar", "Zona Universitaria"}, {8, "Campus Nord", "Pl. Espanya"}, {9, "Pl. Catalunya", "Pg. Zona Franca"}, {10, "Pg. Maritim", "Montbau"},{11, "Trinitat Vella", "Roquetes"}, {13, "Pl. Catalunya", "Can Clos"}, {192, "Poblenou", "Poblenou"}, {193, "C. Montjuic", "C. Montjuic"}, {195, "Pl. Adria", "Pl. Adria"}, {196, "Pl. Kennedy", "Bellesguard"}}}; 2 Observamos que las líneas 8 y 195 son nuevas y las hemos insertado (manteniendo el orden) en actuales, y que las líneas 6 y 13 ya existían previamente, por lo que simplemente se ha actualizado la información de la línea (nuevo origen y/o destino).
El programa mostrará la información por pantalla de la siguiente manera: LINEAS DE AUTOBUSES: Linea 6: Campus Nord - Poblenou Linea 7: Diagonal Mar - Zona Universitaria Linea 8: Campus Nord - Pl. Espanya Linea 9: Pl. Catalunya - Pg. Zona Franca Linea 10: Pg. Maritim - Montbau Linea 11: Trinitat Vella - Roquetes Linea 13: Pl. Catalunya - Can Clos Linea 192: Poblenou - Poblenou Linea 193: C. Montjuic - C. Montjuic Linea 195: Pl. Adria - Pl. Adria Linea 196: Pl. Kennedy – Bellesguard Se pide implementar las siguientes funciones y el programa principal: a) (1.0 pto) int existe_linea(tlista_lineas_autobus la, int num, int *pos) Esta función comprueba si la línea de número num ya existe en la lista de líneas la. Si existe, la función devuelve un 1, a través del return, y la posición donde se encuentra en la lista, a través del parámetro pos.
Si no existe, la función devuelve un 0, a través del return, y la posición donde debería insertarse para mantener el orden, a través del parámetro pos.
NOTA: Se valorarán las implementaciones que aprovechen la ordenación de la lista.
b) (0.5 ptos) void sustituir_linea(tlista_lineas_autobus *la, tlinea_autobus new, int pos) Esta función sustituye la línea de autobús almacenada en la posición pos de la lista de líneas apuntada por el parámetro la, por la línea almacenada en new.
c) (0.75 ptos) void anyadir_linea(tlista_lineas_autobus *la, tlinea_autobus new, int pos) Esta función añade la nueva línea de autobús new a la lista de líneas apuntada por el parámetro la. La nueva línea se debe insertar en la posición pos de la lista de líneas.
NOTA: Podéis suponer que siempre hay espacio para almacenar la nueva línea en la lista.
d) (0.75 ptos) void mostrar_lineas (tlista_lineas_autobus la) Muestra por pantalla todas las líneas de autobuses almacenadas en el parámetro la tal y como indica el ejemplo anterior.
Para la implementación de esta función debéis usar la siguiente función: void mostrar_cadena (char cad[MAX_CHAR]) que muestra por pantalla la cadena cad que se le pasa como parámetro.
NOTA: Suponer que la función mostrar_cadena ya está hecha. No hay que implementarla.
e) (1.5 pto) Escriba el programa principal para que dada la lista de líneas de autobuses actuales y la lista que contiene las líneas nuevas y las modificadas, actualice la lista actuales para que contenga la nueva red de autobuses. Recordar que la lista debe seguir ordenada de menor a mayor por número de línea. El programa también debe mostrar por pantalla el listado de la nueva red de autobuses.
NOTAS: • • Utilice todas las funciones anteriores.
Podéis suponer que en la lista actuales hay espacio para almacenar todas las líneas nuevas.
3 Problema 3 (3.5 puntos, 60 minutos) a) (1.0 pto) Traduce el siguiente código a ensamblador IA32 cumpliendo las indicaciones: #define N 10 main() { short int v[N] = {0,-2,-1,0,1,2,3,4,5,6},t[N]={0,1,2,3,4,5,6,7,8,9}; int i, num, j; num = 0; for(i=0; i<N; i++) if(v[i] >= 0) { j = 0; /* Código interno */ if(j != -1) num++; } } Indicaciones: • La variable i está almacenada todo el tiempo en %edx almacenada en memoria.
• num está almacenada en %ecx y justo antes del final del programa se escribe a memoria.
• Considera que ya están hechas las siguientes secciones del código: y la variable j está La declaración e inicialización de las variables v y t: .data v: .word 0,-2,-1,0,1,2,3,4,5,6 t: .word 0,1,2,3,4,5,6,7,8,9 La finalización del programa: MOV $0,%ebx MOV $1,%eax INT $0x80 b) (2.5 ptos) Supón que existe una función posicion que usaremos para completar el código anterior. La función devuelve la posición donde se encuentra un valor en un vector ó -1 si no se encuentra. La declaración de la función es la siguiente: void posicion(short int t[],short int valor,int *j) { int enc; enc = 0; while(*j < N && enc == 0) if(t[*j] == valor) enc = 1; else (*j)++; if(enc == 0) *j = -1; } Se quiere sustituir en el código inicial (apartado a)) el comentario /* Código interno */ por la llamada a la función: posicion(&t[0],v[i],&j); Realizando esta sustitución habremos escrito un programa en C que cuenta cuántos elementos positivos tienen en común dos vectores v y t de igual tamaño (valor de num al final del código).
Se pide contestar en los folios del examen (páginas 5 y 6) las siguientes cuestiones: 4 Nombre y Apellidos:_________________________________________________DNI:____________________ (0.5 ptos) Rellenar el siguiente cuadro con las instrucciones en ensamblador IA32 que falten para traducir la siguiente llamada: posicion(&t[0],v[i],&j); # Salvar registros PUSHL %eax PUSHL %ecx PUSHL %edx # Escribe a continuación las instrucciones para hacer el paso de parámetros # de derecha a izquierda # Llamada a subrutina CALL posicion # Recoger resultado (La subrutina no devuelve resultado) # Escribe a continuación las instrucciones para eliminar los parámetros # Restaurar registros POPL %edx POPL %ecx POPL %eax (0.5 ptos) Dibuja en el siguiente recuadro el bloque de activación (contenido de la pila) y adónde apuntan los registros %esp y %ebp después de la declaración de la variable local de posicion (justo antes de salvar los registros en el código de la subrutina).
5 (1.5 ptos) Rellenar el siguiente cuadro con las instrucciones en ensamblador IA32 que falten para implementar la subrutina: posicion: # Establecer enlace dinámico PUSHL %ebp MOVL %esp, %ebp # Escribe a continuación las instrucciones para reservar espacio para la variable local # Salvar registros PUSHL %ebx PUSHL %esi PUSHL %edi # Escribe a continuación las instrucciones asociadas al código de la función # Devolver resultado (La subrutina no devuelve resultado) # Restaurar registros POPL %edi POPL %esi POPL %ebx # Escribe a continuación las instrucciones para liberar el espacio de la variable local # Deshacer enlace dinámico POPL %ebp # Retorno RET 6 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 */ 7 Solución Problema 1 (2.0 puntos, 50 minutos) #include <stdio.h> #define MAX 9 typedef struct { int R; /* Componente rojo */ int A; /* Componente azul */ int V; /* Componente verde */ } tpixel; main() { tpixel p; long num; int j=0, i=0, dif, aux; char c, cad[MAX]; /* a) (1.0 pto) */ printf("Introducir cadena:"); for(i=0; i<MAX; i++) scanf("%c",&cad[i]); for(i=0;i<3;i++) { c = cad[MAX-1]; for(j = MAX-1; j>0; j--) cad[j] = cad[j-1]; cad[0] = c; } printf("Cadena con rotacion:"); for(i=0; i<MAX; i++) printf("%c",cad[i]); printf("\n"); /* b) (1.0 pto) */ p.R = (cad[0]-‘0’)*100 + (cad[1]-‘0’)*10 + cad[2]-‘0’; p.A = (cad[3]-‘0’)*100 + (cad[4]-‘0’)*10 + cad[5]-‘0’; p.V = (cad[6]-‘0’)*100 + (cad[7]-‘0’)*10 + cad[8]-‘0’; if (p.R > p.A && p.R > p.V) printf("El color dominante es el ROJO\n"); else if (p.A > p.R && p.A > p.V) printf("El color dominante es el AZUL\n"); else printf("El color dominante es el VERDE\n"); } Problema 2 (4.5 puntos, 70 minutos) a) (1.0 pto) int existe_linea(tlista_lineas_autobus la, int num, int *pos) { int i; for (i=0; i<la.num_lineas && la.llineas[i].num<num; i++); *pos=i; if (i<la.num_lineas && la.llineas[i].num==num) return (1); else 1 return (0); } b) (0.5 ptos) void sustituir_linea (tlista_lineas_autobus *la, tlinea_autobus new, int pos) { la->llineas[pos]=new; } c) (0.75 ptos) void anyadir_linea(tlista_lineas_autobus *la, tlinea_autobus new, int pos) { int i; for (i=la->num_lineas-1; i>=pos; i--) la->llineas[i+1]=la->llineas[i]; la->llineas[pos]=new; la->num_lineas++; } d) (0.75 ptos) void mostrar_lineas (tlista_lineas_autobus la) { int i; printf ("\nLINEAS DE AUTOBUSES:\n"); for (i=0; i<la.num_lineas; i++) { printf("Linea %d: ", la.llineas[i].num); mostrar_cadena(la.llineas[i].origen); printf(" - "); mostrar_cadena(la.llineas[i].destino); printf("\n"); } } e) (1.5 pto) main() { tlista_lineas_autobus actuales={9, {{6,"Pg. Manuel Girona", "Poblenou"},{7, "Diagonal Mar", "Zona Universitaria"},{9, "Pl. Catalunya", "Pg. Zona Franca"},{10, "Pg. Maritim", "Montbau"},{11, "Trinitat Vella", "Roquetes"},{13, "Mercat St. Antoni", "Can Clos"},{192, "Poblenou", "Poblenou"},{193, "C. Montjuic","C. Montjuic"},{196, "Pl. Kennedy", "Bellesguard"}}}; tlista_lineas_autobus news={4, {{6,"Campus Nord", "Poblenou"},{8, "Campus Nord", "Pl. Espanya"},{13, "Pl. Catalunya", "Can Clos"},{195, "Pl.
Adria", "Pl. Adria"}}}; int i, pos; for (i=0; i<news.num_lineas; i++) { if (existe_linea(actuales, news.llineas[i].num, &pos)==1) sustituir_linea(&actuales, news.llineas[i], pos); else anyadir_linea(&actuales, news.llineas[i], pos); } mostrar_lineas (actuales); } 2 Problema 3 (3.5 puntos, 60 minutos) a) (1.0 pto) N = 10 .bss .comm num,4,4 .comm j,4,4 .text .global main main: MOVL $0,%ecx MOVL $0,%edx for: CMPL $N,%edx JGE ffor CMPW $0,v(,%edx,2) JL fif MOVL $0,j # Código interno CMPL $-1,j JE fif INCL %ecx fif: INCL %edx JMP for ffor: MOVL %ecx,num # i en %edx # num primero en %ecx y al final a memoria # num = 0 # i = 0 # i - N # v[i] - 0 # j = 0 # j - (-1) # num++ # i++ # num = %ecx b) (2.5 ptos) (0.5 ptos) Rellenar el siguiente cuadro con las instrucciones en ensamblador IA32 que falten para traducir la siguiente llamada: posicion(&t[0],v[i],&j); # Salvar registros PUSHL %eax PUSHL %ecx PUSHL %edx # Escribe a continuación las instrucciones para hacer el paso de parámetros # de derecha a izquierda PUSHL $j PUSHL v(,%edx,2) PUSHL $t # &j: paso por referencia # v[i]: paso por valor # &t[0]: paso de vector por referencia # Llamada a subrutina CALL posicion # Recoger resultado (La subrutina no devuelve resultado) # Escribe a continuación las instrucciones para eliminar los parámetros ADDL $12,%esp # Restaurar registros POPL %edx POPL %ecx POPL %eax (0.5 ptos) Dibuja el bloque de activación (contenido de la pila) y adónde apuntan los registros %esp y %ebp después de la declaración de la variable local de posición (justo antes de salvar los registros en el código de la subrutina).
%esp enc %esp enc %ebp %ebp %ebp @ret @ret &t[0] t v[i] Parámetros reales ó valor &j j %edx %edx %ecx %ecx %eax 3 %eax %ebp Parámetros formales (1.5 ptos) Rellenar el siguiente cuadro con las instrucciones en ensamblador IA32 que falten para implementar la subrutina: posicion: # Establecer enlace dinámico PUSHL %ebp MOVL %esp, %ebp # Escribe a continuación las instrucciones para reservar espacio para la variable local SUBL $4,%esp # Salvar PUSHL PUSHL PUSHL # int enc registros %ebx %esi %edi # Escribe a continuación las instrucciones asociadas al código de la función MOVL $0,-4(%ebp) # MOVL 16(%ebp),%eax # CMPL $N,(%eax) # JGE fwh CMPL $0,-4(%ebp) # JNE fwh MOVL (%eax),%ebx # MOVL 8(%ebp),%esi # MOVW 12(%ebp),%di # CMPW %di,(%esi,%ebx,2) # JNE else MOVL $1,-4(%ebp) # JMP wh else: INCL (%eax) # JMP wh fwh: CMPL $0,-4(%ebp) # JNE fincalculo MOVL $-1,(%eax) # fincalculo: wh: enc = 0 %eax = &j *j - N enc - 0 %ebx = *j %esi = &t[0] %di = v[i] t[*j] - v[i] enc = 1 (*j)++ enc - 0 *j = -1 # Devolver resultado # Restaurar registros POPL %edi POPL %esi POPL %ebx # Escribe a continuación las instrucciones para liberar el espacio de la variable local ADDL $4,%esp # ó MOVL %ebp,%esp # Deshacer enlace dinámico POPL %ebp # Retorno RET 4 ...