Examen Final [solución]

      Duración: tres horas. 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. ¡No haga más de lo que se le pide! De las todas las preguntas:

1) [25 pts] El algoritmo de Dijkstra.

1.a) [10 pts] Dibuje un grafo de al menos cinco vértices en el que el algoritmo de Dijkstra no funciona. Como valor de las aristas use números diferentes tomados del conjunto {1, -1, 2, -2, 4, -4, 8, -8, 16, -16, 32, -32}.

1.b) [10 pts] Corra el algoritmo de Dijkstra para mostrar que efectivamente no encuentra el resultado deseado.

1.a) [5 pts] Explique por qué el algoritmo de Dijkstra no funciona con su grafo.

2) [25 pts] Simulación.

      Se necesita un programa que permita visualizar el estado de un elevador para un edificio de cinco pisos. Además, también se requiere usar algunos de los módulos del programa para hacer una simulación, de manera que sea posible definir la mejor política de funcionamiento del elevador, para minimizar tanto el uso de electricidad como el tiempo de llegada del elevador cuando una persona lo solicita desde cualquier piso.

2.a) [10 pts] El elevador tiene dos estados: el piso en que está en cada momento, y la dirección de ascenso o descenso que lleva. También es necesario saber en qué pisos tiene que parar. Haga un diagrama de la estructura de datos que se puede usar para resolver este problema.

2.b) [5 pts] Especifique el método Traslado() que sirve para que el elevador pase de un piso a otro.

2.c) [10 pts] Implemente el método Traslado().

3) [25 pts] Matrices.

      En una aplicación matemática se requiere obtener eficientemente los valores almacenados en una matriz secuencialmente (una tras otro), tanto por filas como por columnas. La aplicación correrá en un sistema operativo que tiene memoria virtual paginada en bloques de 4 K bytes.

3.a) [5 pts] Importa minimizar el tiempo de ejecución, aún a costo del espacio. Haga un diagrama de la estructura de datos que usted utilizaría para resolver este problema.

3.b) [5 pts] Declare la clase C++ Matrix.

3.c) [5 pts] Especifique el método Matrix::Next_by_Row() que sirve para obtener, secuencialente, los valores almacenados en la matriz por filas.

3.d) [10 pts] Implemente los métodos Matrix::Next_by_Row() y Matrix::Next_by_Column().

4) [25 pts] Métodos de ordenamiento

      Considere un algoritmo para ordenar un vector que genera, aleatoriamente, una permutación y que luego prueba para ver si al reordenar el vector de acuerdo a la permutación resulta que el vector queda ordenado.

4.a) [5 pts] Haga un ejemplo descriptivo de cómo funciona el algoritmo PermuteSort() en un vector que tenga al menos 10 valores diferentes.

4.b) [10 pts] Suponga que cuenta con el procedimiento Permuta(long double seed, vector[]&) que retorna una permutación de acuerdo a la semilla aleatoria "seed". Implemente el algoritmo PermuteSort().

4.c) [10 pts] Calcule la complejidad de tiempo de PermuteSort().

5) [25 pts] Suponga que usted tiene que hacer el árbol genealógico de cada costarricense, que contiene los nombres de los padres para cada uno de los ciudadanos vivos y, por recursión, de los muertos.

5.a) [5 pts] Discuta si este "árbol" es un árbol en el sentido estricto de la palabra. Tome como referencia la teoría de estructuras de datos que usted ha estudiado.

5.b) [5 pts] Haga un diagrama de una estructura de datos que sirva para resolver este problema. No omita incluir los casos más importantes.

5.c) [15 pts] Implemente la operación Descendiente(), que imprime a todos los descendientes de una persona.

Soluciones

Adolfo Di Mare <adolfo@di-mare.com>.
Copyright © 1999
Derechos de autor reservados © 1999