Download ISC-423: Estructuras de Datos y Algoritmos 17 de Marzo

ISC-423: Estructuras de Datos y Algoritmos
17 de Marzo de 2010
SEGUNDO PARCIAL TEORICO
1 – (20 puntos) Suponga que en un árbol binario de búsqueda tenemos números entre el 1 y el
1000 y que queremos buscar el número 363. ¿Cuál de las siguientes secuencias no puede ser la
secuencia de nodos examinada? ¿Por qué?
1.
2.
3.
4.
5.
2, 252, 401, 398, 330, 344, 397, 363
924, 220, 911, 244, 898, 258, 362, 363
925, 202, 911, 240, 912, 245, 363
2, 399, 387, 219, 266, 382, 381, 278, 363
935, 278, 347, 621, 299, 392, 358, 363
2- (10 puntos) El profesor López piensa que ha descubierto una propiedad interesante de los
árboles binarios de búsqueda. Suponga que la búsqueda de k en un árbol binario de búsqueda
resulte en una hoja. Considere tres conjuntos: A, las llaves a la izquierda del camino de
búsqueda; B, las llaves del camino de búsqueda; y C, las llaves a la derecha del camino de
búsqueda. El profesor López dice que cualquier a ∈ A, b ∈ B, y c ∈ C tiene que satisfacer lo
siguiente: a ≤ b ≤ c. Dé el contraejemplo más pequeño posible de este caso.
3 – (10 puntos) Escriba una función O(n) no-recursiva que dado un árbol binario de n-nodos,
imprima en orden la data de cada nodo. Utilice no más que espacio constante fuera del árbol y
no modifique nunca al árbol.
4 – (10 puntos) Muestre el resultado de insertar 2, 1, 4, 5, 9, 3, 6, 7 a un árbol Red-Black (muestre
el árbol al final de cada inserción).
5 – (10 puntos) En clase se dijo que los árboles B-Trees (siendo los 2-3-4 un tipo de ellos) son
diseñados para trabajar bien en discos y cualquier otro dispositivo de almacenamiento
secundario de acceso directo. Argumente porqué.
6 – (10 puntos) Escriba un algoritmo parar encontrar la llave mínima y su predecesor en un
árbol 2-3-4.
7 – (20 puntos) Llaves iguales en un árbol binario de búsqueda puede llevar a problemas de
implementación.
a. ¿Cuál es el rendimiento asintótico del procedimiento de inserción cuando se insertan n
elementos con llaves idénticas en un árbol binario de búsqueda inicialmente vacío?
El examen tiene una duración de 120 minutos. Mida su tiempo apropiadamente. Escriba su nombre y
matrícula en cada hoja de solución. El examen tiene un valor de 100 puntos de los cuales 10 son de bono.
BUENA SUERTE
Se propone mejorar el procedimiento de inserción haciendo pruebas antes de la línea 5 para
determinar si z.key == x.key y probando antes de la línea 11 para determinar si z.key == y.key.
Si la igualdad se cumple, implementaremos una de las siguientes estrategias. Para cada
estrategia, encuentre el rendimiento asintótico para la inserción de n elementos con llaves
idénticas en un árbol binario de búsqueda inicialmente vacio. (Las estrategias están descritas
para la línea 5, donde comparamos las llaves de z y x. Sustituya y por x para llegar a las
estrategias para la línea 11).
b. Mantener una bandera booleana x.b en el nodo x, y asignar x a x.left o x.right
dependiendo del valor de x.b, el cual alterna entre FALSE y TRUE cada vez que
visitamos a x mientras insertamos un nodo con la misma llave de x.
c. Mantener una lista de nodos con llaves iguales en x, e insertar z a la lista.
d. Aleatoriamente asignar x.left o x.right a x (Dé el rendimiento para el peor caso y derivar
informalmente el tiempo de ejecución esperado)
TREE-INSERT(T, z)
1 y = NIL
2 x = T.root
3 while x ≠ NIL
4
y=x
5
if z.key < x.key
6
x = x.left
7
else x = x.right
8 z.p = y
9 if y == NIL
10
T.root = z // árbol T estaba vacío
11 elseif z.key < y.key
12
y.left = z
13 else y.right = z
El examen tiene una duración de 120 minutos. Mida su tiempo apropiadamente. Escriba su nombre y
matrícula en cada hoja de solución. El examen tiene un valor de 100 puntos de los cuales 10 son de bono.
BUENA SUERTE