UNIVERSIDAD DE COSTA RICA
FACULTAD DE INGENIERÍA
ESCUELA DE CIENCIAS DE LA COMPUTACIÓN E INFORMÁTICA
CI-1221 Estructuras de Datos y Análisis de Algoritmos
II Ciclo de 2009
II EXAMEN PARCIAL
1. [15 pts.] Pilas. En ciertas aplicaciones es necesario tener dos pilas que compartan un espacio
contiguo en memoria (i.e., un arreglo) tal que ninguna pila se desborde al menos que el total de
espacio reservado para ambas se agote.
(a) Explique cómo implementar tales pilas en un arreglo A[1. . n] . [4 pts.]
(b) Escriba el código correspondiente a las operaciones Push(i, j) [3 pts.] y Pop( j) [3 pts.] en
donde el argumento i indica el elemento a ser insertado y el argumento j j=1,2 indica
la pila en que debe ser insertado o de la cuál debe ser sacado el elemento.
(c) Ilustre su implementación realizando la siguiente secuencia de inserciones y borrados en un
arreglo de tamaño 8: Push(1,1), Push(2,2), Push(3,1), Pop(2), Pop(1). [5 pts.]
NOTA: Las operaciones Push y Pop deben correr en tiempo 1 .
2. [10 pts.] Listas enlazadas. Indique el costo computacional de cada una de las siguientes
operaciones realizadas sobre una lista doblemente enlazada con nodo centinela. [2 pts. c/u]
(a) Inserción al principio de la lista.
(b) Inserción al final de la lista.
(c) Inserción a la mitad de la lista.
(d) Acceso al elemento ubicado en la mitad de la lista.
(e) Acceso al penúltimo elemento de la lista.
3. [10 pts.] Tablas hash. Sea una tabla hash con resolución de colisiones mediante
encadenamiento. Utilice la tabla siguiente para indicar la complejidad computacional de
búsquedas fallidas y exitosas, en el peor y mejor casos, y en el caso promedio. Asuma que la
función hash cumple con la propiedad de distribución uniforme de los elementos y que el factor
de carga de la tabla es 1 . [2 pts. c/celda vacía]
Caso → Peor Promedio Mejor
Búsqueda ↓
Fallida
Exitosa 1
4. [10 pts.] Tablas hash. Sea una tabla hash de tamaño 10 con resolución de colisiones mediante
direccionamiento abierto (open addressing) con función hash doble
h k , i=h1 k i h 2 k mod 10 , donde h 1 k =k mod 10 y h 2 k =1k mod 9. Inserte
los elementos 0, 10, 2, 5 y 1 en la tabla y muestre la configuración de la tabla después de cada
una de las inserciones utilizando la tabla siguiente (si lo prefiere puede mostrar en cada fila solo
el elemento recién insertado). [2 pts. c/ inserción]
Posición → 0 1 2 3 4 5 6 7 8 9
Elemento
insertado ↓
0
10
2
5
1
5. [10 pts.] Árboles de búsqueda binarios.
(a) Construya un árbol de búsqueda binario que contenga los elementos 35, 18, 25, 48, 40 y 72,
insertados en ese order. Muestre el árbol parcial después de cada inserción [1 pto. c/inserción].
(b) Utilice el árbol creado en (a) para buscar los elementos 34 y 36 y muestre los nodos
visitados durante cada una de estas búsquedas [2 pts. c/búsqueda].
6. [10 pts.] Árboles de búsqueda binarios. El siguiente es el código para encontrar el sucesor de un
nodo en un árbol de búsqueda binario.
TREE-SUCCESSOR(x)
if right[x] = NIL
then return TREE-MINIMUM(right[x])
y ← p[x]
while y = NIL and x = right[y]
do
x←y
y ← p[y]
return y
Escriba el código correspondiente a la búsqueda del predecesor de un nodo en un árbol de búsqueda
binario.
7. [5 pts.] Árboles de búsqueda binarios. Efectúe una rotación a la derecha sobre la raíz del
siguiente árbol (i.e., intercambie el rol de paternidad entre los nodos con llaves 8 y 3).
8. [15 pts.] Árboles rojinegros. Un arbol rojinegro relajado es un arbol rojinegro en el que se
permite que la raíz del árbol sea roja (pero todas las otras propiedades de un árbol rojinegro se
conservan). Considere un arbol rojinegro relajado con raíz roja al cual se le cambia el color de
su raíz de rojo a negro.
(a) ¿Seguiría el árbol siendo un árbol rojinegro relajado? Explique.
(b) ¿Cumpliría el árbol con las propiedades requeridas para ser rojinegro (simple)? Explique.
(c) ¿Se vería modificada la altura negra del árbol? Explique.
9. [15 pts.] Árboles rojinegros. Inserte la llave 5 en el siguiente árbol rojinegro y haga las
transformaciones necesarias para conservar su propiedad de árbol rojinegro. Muestre la
configuración del árbol después de cada una de las rotaciones y cambio de colores de los nodos.
