CI-1201 Examen #1


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1201
II Semestre 2008

$[\/]$

CI-1201 Programación II

Examen #1 [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 todas las preguntas. ¡No haga más de lo que se le pide!

1) [33 pts] Una norma es una función real que satisface estas condiciones:

f(x) == 0 <==> x==0;
f(x) >= 0;
f(x+y) < f(x)+f(y);
f(αx) = |α| f(x);.

1.a) [16 pts] Especifique la función emplantillada "norm()" que sirve para calcular la norma. Suponga que el argumento es una matriz de valores numéricos, "int", "complex", etc. Incluya ejemplos de prueba BUnit en su especificación.

1.b) [17 pts] Implemente de 2 maneras su función "norm()". Una consiste en sumar las normas de los cuadrados de cada uno de los elementos de la matriz, y la otra se calcula tomando la raíz cuadrada de la primera. ¡No se le meta al Rep!

2) [33 pts] Es una verdad bien conocida que los autores del Código Da Vinci descubrieron frases secretas codificadas en la Biblia. Usted creará una biblioteca que permita encontrar esas frases.

2.a) [5 pts] Especifique la función "SoloDigitos()" que toma una hilera C++ y le elimina todos los caracteres que no son numéricos. Recuerde usar la función booleana "isdigit()" que retorna "true" si su argumento es un dígito. Incluya ejemplos de prueba BUnit en su especificación.

2.b) [12 pts] Implemente "SoloDigitos()".

2.c) [16 pts] Especifique e implemente la función "Bomba(s,b)" que busca la hilera "s" como una subsecuencia dentro de la hilera "b". Para eso, ponga las letras de la hilera "b" dentro de una matriz cuadrada suficientemente grande, una tras otra por filas y por columnas, y luego verifique si "s aparece en alguna de las diagonales de esa matriz.

2.d) [0 pts] Explique cómo usar estas 2 funciones para encontrar los mensajes secretos ocultos en la Biblia.

3) [33 pts] La lista de la biblioteca STL está implementada usando un Rep similar al que se muestra en este diagrama, en donde el nodo cabecera de la lista está al final. Esta implementación tiene varias ventajas, pero también puede hacerle creer al programador que la lista tiene comportamientos equivocados pues al incrementar un iterador que denota el final de la lista L.end() se alcanza el valor inicial de la lista.

<=====================================================> <=============> | prev next | | prev next | | +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ | | +-+-+ | <===>|*|*|<===>|*|*|<===>|*|*|<===>|*|*|<===>|*|*|<===> <===>|*|*|<===> +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ +-+-+ | 1 | | 2 | | 3 | | 4 | | ? | | ? | +---+ +---+ +---+ +---+ +---+ +---+ ^ m_val ^ ^ ^ | | | | L.front() L.back() L.end() Lista vacía

3.a) [0 pts] Explique por qué esta implementación es incorrecta.

/// Graba circularmente hasta el infinito el contenido de \c L en \c cout.
/// \pre ! L.empty()
template <class E>
void circulador( const std::list<E>& L ) {
    typedef typename std::list<E>::const_iterator ITR;
    ITR it = L.begin();
    for (;;) {
        if ( it == L.end() ) {
            ++it;
        }
    }
    cout << *it;
}

3.b) [16 pts] Especifique la clase emplantillada circular<> que sirve para implementar la función circulador() así:

/// Graba circularmente hasta el infinito el contenido de \c L en \c cout.
/// \pre ! L.empty()
template <class E>
void circulador( const std::list<E>& L ) {
    circular<E> it(L);
    for (;;) {
        cout << *it;
        it++;
    }
}

3.c) [17 pts] Implemente circular<>.

Soluciones

$[/\]$