Algoritmo y estructura de datos 2 segundo parcial 08/2024

1) Completa el fragmento con la opción correcta. El número mínimo de nodos de un árbol AVL es: - Lineal respecto a su altura. - Logarítmica proporcional a su altura. - Inversamente proporcional a su altura. - Exponencial respecto a su altura. - Proporcional respecto a su altura.

2) ¿Cuál es el algoritmo de Shannon-Fano?. - En el que el método de compresión está basado en tablas, donde las entradas de la tabla son reemplazadas por cadenas de datos repetidos. - En el que secuencias de datos consecutivas con el mismo valor son almacenadas como un único valor, más su recuento. - En el que se asignan códigos binarios lo más cortos posibles a aquellos simbolos que ocurren con mayor frecuencia en los datos. - En el que se construye un código sin prefijo, basado en un conjunto de simbolos y sus probabilidades. - En el que secuencias de datos consecutivas con el mismo valor son almacenadas con etiquetas de posición y repetición.

3) Completa el fragmento con la opción correcta. Al insertar un nodo en unn árbol rojinegro: - El nodo se inserta como una hoja y se cambia el color de su padre a negro sin importar el color que tuviera antes. - El nodo se inserta como una hoja roja y si su padre es negro ahí se termina la operatoria. - El nodo se inserta como una hoja negra y si su padre es negro ahí se termina la operatoria. - El nodo se inserta como una hoja roja y si su padre es rojo ahí se termina la operatoria. - El nodo se inserta como una hoja sin color y dependiendo el color del padre cambia el color de la hoja para no tener que reequilibrar.

4) Completa el fragmento con la opción correcta. Al insertar un nodo en un árbol rojinegro, lo que se conoce como “caso 3 “ocurre: - Cuando su padre es rojo y su tío es rojo, se aplican rotaciones y se debe volver a analizar el abuelo para ver qué caso es. - Cuando su padre es negro y su tío es rojo, se aplican las rotaciones y ahí finaliza el reequilibrio. - Cuando su padre es negro y su tío es rojo, se aplican las rotaciones y se debe volver a analizar el abuelo para ver qué caso es. - Cuando su padre es negro y su tío es negro, se aplican rotaciones y ahí finaliza el reequilibrio. - Cuando su padre es rojo y su tío es rojo, se aplican las rotaciones y ahí finaliza el reequilibrio.

5) Completa el fragmento con la opción correcta. Al insertar un nodo en un árbol rojinegro: - Si insertamos una hoja roja y su padre es negro, estaríamos incumpliendo la tercera regla. - Puede ser insertado en la raíz en forma directa ( sin rotaciones previas o posteriores), siempre y cuando su color sea negro. - Solo la primera y segunda regla deben respetarse, las otras no importan, son sugerencias. - Si insertamos una hoja roja y su padre es rojo, estaríamos incumpliendo la tercera regla. - Puede ser insertado de cualquier color en el medio del árbol sin rotaciones previas ni posteriores, siempre y cuando no rompa la alternancia de colores.

6) Completa el fragmento con la opción correcta. La estructura mejor preparada para almacenar los datos en disco es: - Árbol AVL. - Árbol AA. - Árbol rojinegro. - Árbol ABAB. - Árbol B.

7) Completa el fragmento con la opción correcta. Se trata de un árbol equilibrado cuando_: - La altura del subarbol izquierdo difiere, como máximo en 1, con la altura del subarbol derecho. - El número de nodos del subarbol izquierdo es igual al número de nodos del subarbol derecho. - El número de nodos del subarbol izquierdo difiere, como máximo en 1, con el número de nodos del subarbol derecho. - Los nodos hojas estarán todos al mismo nivel. - La altura del subarbol izquierdo será la misma que la altura del subarbol derecho.

8) Completa el fragmento con la opción correcta. El equilibrio de un árbol AVL se logra: - Haciendo operaciones de reequilibrado durante un borrado. - Haciendo operaciones de reequilibrado despues de una operación de inserción o de borrado. - Haciendo operaciones de reequilibrado durante una inserción o borrado. - Luego de hacer todas las operaciones de inserción y borrado, se hace una sola operación de reequilibrio. - Haciendo operaciones de reequilibrado despues de una operación de inserción.

9) Selecciona 4 (cuatro) respuestas correctas. En un árbol B: - La raíz tiene siempre M hijos si no es un nodo hoja. - Un nodo no hoja con k hijos contiene k-1 elementos almacenados. - Cada nodo tiene como máximo M hijos. - Cada nodo (excepto raíz) tiene como mínimo (M)/2 claves. - Todos los nodos hoja aparecen al mismo nivel.

10) Selecciona las 4 (cuatro) respuestas correctas. Un árbol B: - Que posee un nodo con K claves tiene C + 1 hijos. - De grado M puede tener M-1 claves. - Tiene todos los nodos hoja al mismo nivel. - Tiene que tener todos sus nodos al menos M/2 hijos. - De grado M puede tener M hijos.

11) Completa el fragmento con la opción correcta. Una de las propiedades de los arboles rojinegros dice que: - Todos los caminos de la raíz a una referencia NULL deben contener el mismo número de nodos rojos. - Si un nodo es negro, sus hijos deben ser rojos. -Todos los caminos de un nodo a una referencia NULL deben contener el mismo número de nodos negros. - Todos los caminos de un nodo a una referencia NULL deben contener el mismo número de nodos rojos. - Si un nodo es rojo, sus hijos pueden ser de cualquier color.

13) Completa el fragmento con la opción correcta. En los arboles rojinegros: - Las hojas son relevantes y son las que contienen datos. - Son definidos así porque son los dos colores más importantes, pero usa otros colores. - Las hojas no son relevantes y no contienen datos. - Tomados por su definición, no garantizan equilibrio alguno en su estructura. - Las hojas son relevantes y contienen datos.

14) ¿Para qué sirve la técnica de bitmapping?. - Para representar, por medio de imágenes, pequeños volúmenes de informacion. - Para representar, por medio de un arreglo multidimensional de bits, grandes volúmenes de informacion. - Para representar, por medio de un vector de bits, grandes volúmenes de informacion. - Para representar, por medio de un vector de bits, pequeños volúmenes de informacion. - Para representar, por medio de un arreglo multidimensional de bits, pequeños volúmenes de informacion.

15) Completa el fragmento con la opción correcta. El nivel de un nodo de un árbol AA es: - El nivel es el número de enlaces izquierdos que hay en el camino hasta el centinela. - El nivel es el número de enlaces que hay en el camino hasta el abuelo. - El nivel es el número de enlaces izquierdos con nodos rojos que hay en el camino hasta el centinela. - El nivel es el número de enlaces que hay en el camino hasta la raíz. - El nivel es el número de enlaces derechos que hay en el camino hasta el centinela.

16) Si poseemos un archivo de 50000 registros y queremos representarlo (para ordenarlo) con una cadena de 50000 bits, usamos la técnica bitmapping ¿Cómo se llama en realidad esta técnica?. - Bitmap bit vector sort. - Bitmap bit image representación (BMP). - Bitmap bit chain sort. - Bit chain sort. - Bitmap bit vector representación.

17) ¿Es posible buscar el elemento k-esimo de un árbol BST?. - Si. Mientras solo se hagan operaciones de borrado. - Si. Mientras solo se hagan operaciones de inserción. - No. No es posible codificar ese método, por la estructura de un árbol BST. - Si. Es el mismo método de buscar valor. - Si. Si actualizamos el tamaño de los nodos en cada operación de modificación del árbol.

18) ¿En qué consiste la compresión de Huffman? Seleccione la respuesta correcta. - Consiste en leer el archivo original Byte a Byte y codificar el archivo nuevo bit a bit, obteniendo los códigos desde las hojas hasta la raíz. - Consiste en leer el archivo original Byte a Byte y codificar el archivo nuevo bit a bit. - Consiste en crear la tabla a partir del árbol generado. - Consiste en leer el archivo original Bit a Bit y codificar el archivo nuevo Byte a Byte. - Consiste en leer el archivo original Bit a Bit y codificar el archivo nuevo Byte a Byte, obteniendo los códigos desde las hojas hacia la raíz.

19) Completa el fragmento con la opción correcta. En un árbol AVL, por convención, el Factor de Equilibrio es el: - Nivel del subarbol izquierdo – nivel del subarbol derecho del nodo que se esta analizando. - Nivel del subarbol izquierdo – nivel del subarbol derecho, del nodo padre. - Nivel del subarbol derecho – nivel del subarbol izquierdo, del nodo raíz. - Nivel del subarbol izquierdo – nivel del subarbol derecho, del nodo raíz. - Nivel del subarbol derecho – nivel del subarbol izquierdo, del nodo padre.

20) Completa el fragmento con la opción correcta. En los arboles rojinegros cuando eliminamos un nodo rojo con un solo hijo: - Simplemente, se reemplaza el nodo borrado por su hijo, conservando el color del original y se analiza a partir de ahí si el árbol necesita reequilibrio. - Se reemplaza el nodo borrado por su hijo solo si este es negro y se debe hacer el analisis de reequilibrio. - Hay que recolorear el árbol antes de poder borrarlo. - Simplemente, se reemplaza el nodo borrado por su hijo, conservando el color original, sin necesidad de analisis de reequilibrio. - Se reemplaza el nodo borrado por su hijo solo si este también es rojo y no hay necesidad de analisis de reequilibrio.

12) ¿Qué es el algoritmo de mapeo de bits?. - Es el método más rápido y eficiente para ordenar un conjunto determinado de números reales. - Es la técnica para ordenar archivos de imagen. - Es el método que emplea archivos para ordenar registros. - Es un algoritmo de ordenamiento y funciona al pensar en una porción de memoria como un conjunto de bits numerados. - Es el método más simple de ordenamiento externo.