Universidad de Costa Rica
Escuela de Ciencias de la
Computación e Informática
Profesores Di Mare y Noguera
IF-3001
I Semestre 2013
[<=] [home] [<>] [\/] [=>]
IF-3001 Algoritmos y Estructuras de Datos

Examen #2 [solución]

 

1) [33 pts] Método de ordenamiento List.bubbleSort() 

public static void bubbleSort( int VEC[] ) {
    int i,j;
    for ( i=VEC.length; i>0; --i ) {
        for ( j=1; j<i; ++j ) {
            if ( VEC[j]<VEC[j-1] ) ) {
                intercambie( VEC, j,j-1 );
            }
        }
    }
}

/** Determina si los primeros N valores de la
   * lista están ordenados ascendentemente.
   */
public boolean estaOrdenado( int N ) {
    if ( N<=1 ) { return true; }

    List.Node jN,jNplus;
    Integer jVal, jPlusVal;
    jN = this.m_head;
    jNplus = jN.m_next;
    for ( int i=1; i<N; ++i ) { // N-1 veces
        jVal     = (Integer) jN.m_data;
        jPlusVal = (Integer) jNplus.m_data;
        if ( jVal.intValue() <= jPlusVal.intValue() ) { /* ok */ }
        else { return false; }
        jN = jNplus;
        jNplus = jNplus.m_next;
    }
    return true;
}

      Verifique que esta implementación Java de este método de ordenamiento funciona correctamente y, en caso contrario, corríjala. Luego utilice la clase lista doblemente enlazada vista en clase para incluirle su método bubbleSort() que utilizar este ordenamiento. Para verificar que su implementación funciona correctamente, utilice las rutinas de permutaciones que desarrolló una tarea previa para constatar que su método funciona con tadas las permutaciones de números consecutives en el rango [0..10]. Explique por que su método List.bubbleSort() no necesita ningun parámetro. Recuerde: ¡es necesario que manipule los enlaces de la lista!

 

2) [33 pts]

2.a) [5 pts] Expliqué cómo se puede usar una lista Java para implementar el contenedor Cola. Llame saque() a la operación que elimina el siguiente valor que hay que eliminar de la lista cuando funciona como si fuera una cola [la otra operación debería ser mete()].

2.b) [6 pts] Suponga que usted cuenta con una clase Grafo que le permite almacenar nodos y enlaces. Especifique las operaciones conecte(n1,n2,val) y conectados() que sirven para agregar enlaces al grafo y para obtener la lista de nodos que están enlazados a un nodo específico (no se complique la vida, y asuma que los enlaces siempre son bidireccionales).

2.c) [0 pts] Suponga que su grafo contiene las siguientes conexiones [ a-e=5, e-f=4, a-d=1, d-f=3, a-b=2, b-c=2, c-f=8, d-f=8 ]. Dibuje el grafo y constate que, al recorrerlo por niveles empezando con el nodo "a", una posible secuencia de recorrido es (a b d e c f) y otras es (a e b d e f).

2.d) [22 pts] Implemente un iterador Java completo, similar al que usó en unas de sus tareas programadas, junto con sus operaciones hasNext() y next(), que permita recorrer un grafo por niveles. Use la lista como una cola o use su contenedor cola implementado con base en la lista.

Soluciones

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