Download Parcial III 2008-2009B

Universidad de ISTMO – Tehuantepec.
Ingeniería en Computación.
Tercer Examen Parcial de Estructuras de Datos.
Profesor: M.I.A Daniel Alejandro García López
Alumno: _______________________________________
___________________________
Calificación:________
1.- Mostrar el proceso de creación de un árbol AVL all insertar cada uno de los elementos de la
siguiente secuencia de números 50, 30, 20, 60, 70, 55, 57, 58(10%).
2.- Construya el árbol binario de búsqueda de la siguiente secuencia de números 30, 20, 5, 48,
40, 10, 35,25, 45,50,38,35,25 y después elimine
limine de ese árbol binario de búsqueda los
siguientes elementos. Muestre
uestre el árbol resultante después de cada elemento eliminado
30,10,38,45,15,28,50,38,25.. (10%).
3.- Inserte
nserte en el siguiente árbol la secuencia de números dada, de tal forma que resulte un
árbol AVL correcto. 25, 16, 19,27,12,8,18,23,6,36.
19,27,12,8,18,23,6,36. Muestre el árbol resultante después de cada
elemento insertado, así como el factor de equilibrio de cada nodo(15%).
nodo
4.- Realice
ealice el recorrido en preorden,
preor
enorden y postorden de cada uno de los siguientes
árboles(10%).
5.- Verifique que el siguiente pseudocódigo
pseudo
para la eliminación del primer elemento
eleme
de una
lista doblemente enlazada sea correcta sino corrija el error (5%).
Sea P y F el apuntador al primer y último nodo de la lista respectivamente.
Q es un apuntador. INFO, LIGADER,LIGAIZQ son los campos de cada nodo de la lista.
Hacer Q=F
Si(Q^.LIGADER<>NULO) entonces
Hacer P=Q^.LIGAIZQy P^.LIGADER=NULO
Sino
P=NULO y F=NULO;
Finsi
Quitar Q
6.- Proponga un tipo de dato definido por el usuario para representar un árbol que tenga la
capacidad de almacenar uno, dos , tres o más hijos en cada uno de sus nodo. Y escriba el
procedimiento para mostrar los valores que contiene una estructura de ese tipo(15%).
tipo
7.- Dibuje el árbol binario que mostraría como resultado de los recorridos en (10%)
Preorden: a,g,d,k,e,t,u,p,y,z,r,m
En orden: k,d,g,e,a,u,y,p,z,t,r,m
Postorden: k,d,e,g,y,z,p,u,m,r,t,a
8.- Escriba un procedimiento para ordenar eficientemente una lista doblemente ligada
basándose en el algoritmo merge sort(20%).
sort
9.-Convierta
Convierta el siguiente bosque en representación de un árbol binario(5%).
binario