Universidad de Costa Rica
Escuela de Ciencias de la
Computación e Informática
Profesor Adolfo Di Mare
CI-1101
II Semestre 2014
[<=] [home] [<>] [\/] [=>]
CI-1101 Programación I

Examen Final [solución]

      Duración: Ciento veinte minutos. Lea bien el examen antes de hacerlo. El examen es a libro abierto. Cuenta la documentación. Cuenta la redacción y la ortografía. Puede hacer el examen con lápiz. Resuelva solo tres de las preguntas. ¡No haga más de lo que se le pide!

 

1) [33 pts] Existen mucho algoritmos que funcionan mejor si se aplican a matrices cuadradas que se tienen sus valores por bandas. Estas son algunas de esas matrices:
                1 2 3 0 0 0                 1 2 3 0 0
 1  2  0  0     0 2 3 0 0 0      1 0 0      2 1 2 3 0
-2  1  2  0     0 4 1 0 0 0      0 1 0      0 2 1 2 3
 0 -2  1  2     0 0 5 1 0 0      0 0 1      0 0 2 1 2
 0  0 -2  1     0 0 0 0 1 0                 0 0 0 2 1
                0 0 0 0 3 9

      La primera es una matriz 4x4 que tiene una banda de 2 sub-diagonales de ancho. La primera sub-diagonal es la diagonal de la matriz (que tiene valores "1"), y la segunda es la que está inmediatamente arriba de la diagonal (formada de los valores "2"). Como segunda sub-diagonal también se cuenta a la que está debajo de la diagonal principal (formada de los valores "-2").

      La cuarta matriz es una matriz de dimensión 5x5, y su caso es un poco diferente, pues es una matriz que tiene bandas de ancho 3. Aunque su última sub- diagonal hacia abajo es la formada por los doces ("2"), tiene una tercera sub-diagonal hacia arriba formada por los valores "3". Por eso su ancho de banda es "3" (y NO es "2").

      El ancho de banda de la matriz identidad es "1", porque sólo tiene valores diferentes de cero en la diagonal. Una matriz llena de ceros tendrá ancho de banda "0".

1.a) [4 pts] Escriba la declaración de la clase Matriz_Cuadrada, e incluya al método anchoBanda(). Haga las cosas de forma que la dimensión de su matriz puede variar en el rango [1..MaxDim].

1.b) [5 pts] Especifique el método Matriz_Cuadrada.anchoBanda() que retorna el tamaño de la banda más ancha de la matriz. Note que en el caso peor anchoBanda() retornará "n", la dimensión de la matriz, que ocurre cuando la matriz no contiene un triángulo inferior y otro superior lleno de ceros ("0"). [Sugerencia: Calcule el tamaño del triángulo de ceros inferior y superior de la matriz].

1.c) [24 pts] Implemente Matriz_Cuadrada.anchoBanda().

 

2) [33 pts] Una dirección internet [URL] contiene letras, dígitos y los caracteres { '.' '-' '_' '/' ':' '(' ')' '&' '+' } que están después de la hilera "http://". Escriba un programa completo que lea un archivo de texto y grabe con System.out.print(), en renglones aparte, únicamente aquellas parejas de direcciones internet que aparecen juntas en el mismo renglón pero separadas por algún caracter. Suponga que cuenta con el método estático saqueHttp(str,n) que retorna un número que indica adonde comienza la n-ésima dirección internet que parece en una hilera (o str.length() si no hay otra). Después de ejecutar su programa se obtendría un resultado similar al siguiente:
http://www.ucr.ac.cr <--> http://ecci.ucr.ac.cr
http://mail.google.com <--> http://mail.yahoo.com

 

3) [33 pts] Considere la rutina mezcladora(a,b) cuya implementación se muestra aquí.

public static String mezcladora( int a, int b ) {
    if ( a>0 ) {
        return mezcladora(-a,b);
    }
    else if ( b>0 ) {
        return mezcladora(a,-b);
    }

    System.out.print( "(" + a + "," + b + ")\n" );
    if ( a<0 ) {
        String demeA = mezcladora( a+1,b );
        demeA = '+' + demeA;
        return demeA;
    }
    else if ( b<0 ) {
        String demeB = mezcladora( a,b+1 );
        demeB = demeB + '-';
        return demeB;
    }
    else {
        return ":";
    }
}

3.a) [24 pts] Muestre los registros de activación como cajitas Jeliot para los llamados si la invocación inicial de la rutina es mezcladora(1,-2). También muestre el valor retornado al terminar cada invocación.

3.b) [6 pts] Muestre los valores que graba mezcladora(3,2).

3.c) [3 pts] Diga qué hace esta rutina y sugiera una forma más directa de hacer lo mismo.

3.d) [0 pts] Muestre los valores que graba mezcladora(-3,-4).

 

Soluciones

[mailto:] Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 2014
Derechos de autor reservados © 2014
[home] <> [/\]