if-3001 Examen #1


  Universidad de Costa Rica 

  Recinto de Golfito 

  Informática Empresarial

Profesores Di Mare y Noguera
IF-3001
I Semestre 2013

$[\/]$

IF-3001 Algoritmos y Estructuras de Datos

Examen #1 [solución]

1) [33 pts] Búsqueda binaria

public int busque( char dato , cha VEC[] ) {
    int inicio = 0;
    int fin = VEC.length - 1;
    int pos;
    while (inicio <= fin) {
        pos = (inicio+fin) / 2;
        if ( VEC[pos] == dato ) { return pos; }
        else if ( VEC[pos] < dato ) {
            inicio = pos+1;
        }
        else {
            fin = pos-1;
        }
    }
    return VEC.length;
}

1.a) [0 pts] Expliqué qué condiciones debe cumplir V[] para que busque() funcione correctamente.

1.b) [11 pts] Esta implementación de busque() use como pivote el elemento medio del vector para continuar la búsqueda. Explique cómo lograr que esta rutina use como pivote al elemento que se encuentra de primero en la última tercer parte del vector. Recuerde incluir el código Java.

1.c) [11 pts] Calcule la cantidad máxima de veces que el ciclo while() se ejecuta si el vector tiene 1024==2^10 valores. Repita el cálculo para la versión b) de la rutina busque().

1.d) [11 pts] Desarrolle una fórmula matemática que permite determinar el número de veces que el ciclos while() se ejecuta si la cantidad de valores de VEC[] es "n".

1.e) [0 pts] Haga un gráfico que muestre la complejidad del algoritmo busque().

2) [33 pts] Listas doblemente enlazadas

<=====================================================>
│  prev next                                          │
│    ┌─┬─┐     ┌─┬─┐     ┌─┬─┐     ┌─┬─┐     ┌─┬─┐    │
<===>│*│*│<===>│*│*│<===>│*│*│<===>│*│*│<===>│*│*│<===>
     ├─┴─┤     ├─┴─┤     ├─┴─┤     ├─┴─┤     ├─┴─┤
     │ 1 │     │ 2 │     │ 3 │     │ 4 │     │?.*│
     └───┘     └───┘     └───┘     └───┘     └───┘
       ^       m_val                 ^         ^
       │                             │         │
    L.front()                     L.back()   L.end()

2.a) [5 pts] Haga un diagrama de la lista circular con referencia al último valor de la lista. Suponga que los valores almacenados en su lista L son (10, 20, 30).

2.b) [11 pts] Muestre con dibujos cómo se hace la inserción del valor 40 al final de la lista L. Explique qué ocurre en cada paso.

2.c) [5 pts] Haga la declaración Java de la clase "list" y de su clase anidada "node".

2.d) [6 pts] Implemente el método list.add(int) que agrega un valor numérico al final de la lista.

2.e) [6 pts] Implemente el método list.push_front() que agrega un valor al principio de la lista.

3) [33 pts] Algoritmos exhaustivos

Suponga que usted tiene una matriz cuadrada y numérica, en donde está almacenada una cadena de números que representa un navío enemigo. Construya una rutina que reciba, además de la matriz, un número, que sirve para identificar la cadena de números que usted busca.

Su programa debe grabar las coordenadas de la cadena de números buscada. Eso sí, no se limite a grabar solo las coordenadas en cualquier orden, sino que hágalo comenzando por aquel extremo de la cadena que se encuentre más cerca del punto (0,0) (use cualquier métrica o norma para calcular esta distancia, después de que ya calculado ambos extremos).

Soluciones

$[/\]$