Algoritmos y Estructuras de Datos
2022-2
Tercer Parcial
23 de noviembre de 2022
Indicaciones generales
1. Este es un examen individual con una duración de 120 minutos: de 9:00am a 11:00am.
2. En e-aulas puede acceder a las diapositivas y a la sección correspondiente a este parcial.
3. Solamente será posible tener acceso a [Link] y a los sitios web corres-
pondientes a la documentación de C++ dispuestos por el profesor.
4. Maletas, morrales, bolsos, etc. deben estar ubicados al frente del salón.
5. Celulares y otros dispositivos electrónicos deben estar apagados y ser guardados dentro de
las maletas antes de ser ubicadas en su respectiva posición.
6. El estudiante no debe intentar ocultar ningún código que no sea propio en la solución a la
actividad.
7. El estudiante solo podrá disponer de hojas en blanco como borrador de apuntes (opcional).
8. El estudiante puede tener una hoja manuscrita de resumen (opcional). Esta hoja debe estar
marcada con nombre completo.
9. e-aulas se cerrará a la hora en punto acordada. La solución de la actividad debe ser subida
antes de esta hora. El material entregado a través de e-aulas será calificado tal como está.
Si ningún tipo de material es entregado por este medio, la nota de la evaluación será 0.0.
Se aconseja subir a e-aulas versiones parciales de la solución a la actividad.
10. Todas las evaluaciones serán realizadas en el sistema operativo GNU/Linux.
11. Todas las entregas están sujetas a herramientas automatizadas de detección de plagio en
códigos.
12. Cualquier incumplimiento de lo anterior conlleva la anulación del examen.
13. Las respuestas deben estar totalmente justificadas.
14. Entrega: archivos con extensión .cpp o .hpp según el caso, conteniendo el código. Nombre
los archivos como pY.Z, con Y = 1,2,3 y Z = cpp, hpp.
1. [50 ptos.] Sea T un árbol binario de búsqueda con N nodos, incluyendo nodos internos y
hojas. Un nodo lleno (full node) se define como aquel nodo que tiene dos y solamente dos
hijos. Implemente los métodos
1 void print_full_nodes ( Node <T > *n , std :: ostream & out ) const ;
2 void print_full_nodes ( std :: ostream & out = std :: cout ) const ;
con encapsulamiento privado y público, respectivamente. Invocando print_full_nodes(T,
outstr), el primer método imprime, al flujo outstr, únicamente los nodos en n que son nodos
llenos. El segundo método es simplemente un wrapper público que invoca al primer método,
y que por defecto imprime al flujo std::cout.
2. [50 ptos.] Un heap binario es, en esencia, un árbol binario en donde cada nodo cumple con la
propiedad de que la llave de sus hijos, si los tiene, es menor a su propia llave.
Usando la plantilla proporcionada implemente el método
Página 1 de 2
Algoritmos y Estructuras de Datos
2022-2
1 bool test_bhprop ( std :: vector < int > & v )
que recibe un vector vacı́o y retorna true si todos los nodos de la estructura cumplen con la
propiedad de heap binario o false en caso contrario. En el vector que se pasa por referencia
quedan plasmadas las posiciones en la estructura de todos los nodos que no cumplen con la
propiedad o cuyos descendientes (hijos, hijos de los hijos, etc...) no cumplen con la propiedad.
Por ejemplo, si la estructura en forma de arreglo es
12 11 9 7 10 8 4 1 2 0 5 3 6 13
El método debe retornar false y el vector contendrá los ı́ndices 6 2 0, dado que el nodo en
la posición 6 (un 4) tiene cómo hijo un 13, de manera que no cumple con la propiedad. En
cuanto a la posición 2 (un 9) aunque cumple con la propiedad, uno de sus hijos es la posición
6, que como vimos no la cumple. Finalmente, la posición 0 (un 12) también está en la lista por
que es padre de 2 que a su vez es padre de 6, que como vimos no cumple con la propiedad.
Página 2 de 2
