CI-1303 Examen Final


  Universidad de Costa Rica 

  Escuela de Ciencias de la 

  Computación e Informática

Profesor Adolfo Di Mare
CI-1303
II Semestre 1996

$[\/]$

CI-1303 Estructuras de Datos y Análisis de Algoritmos

Examen Final

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! ¡Conteste TODAS las 4 preguntas!

1) [25 pts] Un método de ordenamiento es Estable si preserva el orden original de los valores iguales en el vector a ordenar.

1.a) [8 pts] Muestre con un contra-ejemplo que el QuickSort() no es estable.

1.a) [8 pts] Muestre con un contra-ejemplo que el HeapSort() no es estable.

1.a) [9 pts] Pruebe que MergeSort() es estable.

2) [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.

2.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.

2.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.

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

3) [25 pts] Considere el algoritmo de Dijkstra para obtener el camino de de costo mínimo desde un vértice.

3.a) [10 pts] Muestre mediante un contra-ejemplo que el algoritmo no funciona cuando el grafo tiene arcos negativos. Indique cuál es el número mínimo de nodos que debe tener dicho grafo.

3.b) [15 pts] Corra el algoritmo de Dijstra en un grafo de 5 nodos completamente conectado en que el valor del arco (i,j) es 2^i+3^j, y el del arco (i,i) es siempre cero. El nodo de origen es el [3].

2^i <==> (2 4 8 16 32)
    
3^j <==> (3 9 27 81 243)

1) [25 pts] En esta pregunta usted calculará la complejidad del algoritmo de Boyer-Moore para reconocimiento de patrones. (Note que el valor de cada una de las secciones de esta pregunta es diferente).

4.a) [2 pts] Suponga que el alfabeto base tiene 256 símbolos diferentes [ASCII]. Explique cuál es la forma de implementar la tabla de corrimientos para las letras que están en el patrón, y calcule el costo en espacio de esa solución.

4.b) [8 pts] Suponga que el alfabeto base tiene 16K símbolos diferentes [UNICODE]. Calcule el costo en espacio y tiempo de usar una tabla de dispersión [HASH] para alamacenar la tabla de corrimientos.

4.c) [8 pts] Suponga que el alfabeto base tiene 16K símbolos diferentes [UNICODE]. Calcule el costo en espacio y tiempo de usar un arreglo ordenado de símboles para alamacenar la tabla de corrimientos.

4.d) [5 pts] Compare las ventajas y desventajas de las dos formas de alamacenar la tabla de corrimientos y explique cuál es la mejor.

4.e) [2 pts] ¿Cuáles son las desventajas del algoritmo de Boyer Moore que justifican que la mayoría de las implementaciones de strstr() no lo usen? (Este es el caso de la biblioteca de Borland).

$[/\]$