Download Certamen 1

UNIVERSIDAD TECNICA FEDERICO SANTA
MARIA
DEPARTAMENTO DE ELECTRONICA
ELO320 Estructuras de Datos y Algoritmos
1. Se tiene el siguiente árbol de búsqueda.
a) ¿Cuáles son todos los órdenes posibles en los que llegaron las claves para formar el
árbol?.
b) En un listado post-orden quienes figuran antes y después del valor 6.
c) En un listado post-orden quienes figuran antes y después del valor 2.
d) Dibujar el árbol, luego de: insertar el nodo con valor 5, y descartar los nodos con valores
4 y luego el 7. Indicar alternativas de solución, si las hubiera.
15 puntos
7
3
8
4
1
2
6
2. Para el siguiente árbol AVL
7
3
8
4
1
a) Indique los factores de balance de cada nodo.
b) Dibujar el árbol AVL, después de la inserción de un nodo con valor 2. ¿Qué operaciones
se efectúan?.
c) Habiendo ya insertado el nodo con valor 2, dibujar el árbol AVL, después de la inserción
de un nodo con valor 6. ¿Qué operaciones se efectúan?.
15 puntos.
3. Determinar la solución de la siguiente relación de recurrencia:
T(n) = T(n/2) + n, con T(1)= 2.
Puede emplear que la suma de la siguiente progresión geométrica es:
n
 2 i 2
( n 1 )
 2
i1
Cual es el orden de complejidad.
15 puntos.
4. Diseñar una función, con el siguiente prototipo:
int trayectoria(pnodo t, int valor);
Retorna 1 si lo encontró, 0 si árbol vacío o no lo encontró.
a) Que imprima la trayectoria desde el nodo con clave igual al argumento valor hasta la
raíz, si éste se encuentra en el árbol, y “no encontrado” en caso contrario.
15 puntos.
Tomás Arredondo Vidal. Leopoldo Silva Bijit.
08-08-2017
1
UNIVERSIDAD TECNICA FEDERICO SANTA
MARIA
DEPARTAMENTO DE ELECTRONICA
ELO320 Estructuras de Datos y Algoritmos
b) Discuta la forma de diseño, si se desea imprimir los valores de los nodos desde la raíz,
hasta el nodo que tiene igual valor de clave que el argumento dado.
15 puntos.
5. Para una tabla de hash cerrado de tamaño 9, se tiene la siguiente función de hash:
h(x) = (7x + 1) % 9;
Considere la siguiente secuencia de operaciones:
Insertar 13
Insertar 20
Insertar 4
Insertar 8
Descartar 4
Buscar 8
Insertar 16
Indice
0
1
2
3
4
5
6
7
8
Valor Estado
a) Muestre el contenido de la tabla después de realizadas las operaciones anteriores,
asumiendo linear probing para resolver colisiones. Indicando cuándo se producen
colisiones y la razón por la que se almacena en una posición determinada.
b) Luego de lo anterior, indicar fundamentadamente qué casos de inserciones o búsquedas
tienen mayor costo, indicando el número de comparaciones que son necesarias. 25 puntos.
Tomás Arredondo Vidal. Leopoldo Silva Bijit.
08-08-2017
2