Algoritmos y estructura de datos 2 - 2do parcial 09/2024

1 – Completa el fragmento con la opción correcta. En un árbol AVL, después de una inserción, se aplica un RDI si_______. -El factor de equilibrio (FE) del nodo actual es -2 y el FE del nodo derecho es >0. -.

2 - Completa el fragmento con la opción correcta. En una rotación simple de un árbol AVL_______. -Se intercambian los datos referenciales entre el padre y uno de sus hijos. El hijo depende de si es RSI o RSD. -.

3 - Completa el fragmento con la opción correcta. Una característica del ARN es que__________. - El camino desde un nodo a sus hojas contiene el mismo número de nodos negros. -.

4 - Completa el fragmento con la opción correcta. El borrado de un árbol BST de un nodo con dos hijos_________. - Se puede ejecutar, pero antes se debe reducir modificando a un caso de un hijo. - Tiene dos posibles soluciones.

5 - Completa el fragmento con la opción correcta. El número mínimo de nodos de un árbol AVL es _______. - Exponencial respecto a su altura. - Proporcional respecto a su altura.

7 – Completa el fragmento con la opción correcta. La inserción en un árbol BST_________. - Consiste en una búsqueda no exitosa y la inserción en ese lugar. - Precisa de un dato referencial en donde poner el dato insertado, si no será imposible hacerlo.

8 – En el algoritmo de Huffman, ¿Qué se necesita para descomprimir, además de un árbol o la tabla?. - El ratio de compresión. - El tamaño del archivo.

9 - Completa el fragmento con la opción correcta. Si hablamos de rotaciones simples en un árbol AVL________. - Estamos hablando de una RDI o RDD dependiendo del valor del factor de equilibrio. - Estamos hablando de una RSI o una RSD dependiendo del valor del factor de equilibrio.

10 - Completa el fragmento con la opción correcta. El borrado de un árbol BST_______. - Implica que se debe analizar los tres casos posibles de borrado. - Implica que se deben analizar los cuatro casos posibles de borrado.

11 - ¿Qué es la compresión?. - Es un caso particular de recodificación. - Es un caso particular de manipulación de la información el cual aumenta la entropía.

12 - Completa el fragmento con la opción correcta. Los árboles AA se diferencian de los arboles rojinegros en que________. - Sus hijos izquierdos no pueden ser rojos. - Sus hijos derechos no pueden ser negros.

13 – Un árbol BST, al estar ordenado, nos facilita la búsqueda de un elemento, ¿Cómo se procede?. - Se realiza partiendo de la raíz y preguntando si el dato buscado es mayor o menor que el dato del nodo. Si es menor, se prosigue recursivamente por la raíz izquierda y si es mayor se prosigue recursivamente……. -.

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

15 - Completa el fragmento con la opción correcta. La característica única llamada división de “dos a tres”________. - Es una ventaja de usar árboles B* sobre arboles B. - Es una desventaja de los árboles AVL frente a los RN.

16 - Completa el fragmento con la opción correcta. En los árboles rojinegros cuando eliminamos un nodo negro sin hijos, _________. - Se debe hacer eliminación y luego analizar los 6 casos posibles de reestructuración. - Se debe hacer la eliminación y el hijo negro toma su posición.

17 - ¿En que codificación los símbolos se ordenan por probabilidad, del más probable al menos probable, dividiéndose en 2 conjuntos, cuya suma de probabilidades sean tan iguales como sea posible?. - Codificación de Shannon Fano. - Codificación Lempel-Ziv-Welch.

18 - ¿En qué consiste el algoritmo de búsqueda de anagrama? Selecciona 4(cuatro) respuestas correctas. - Se utiliza la permutación de letras. - Consiste en registrar firmas (signatures). - Los anagramas serán todas las palabras que tengan la misma firma. - Consiste en un método de 2 pasadas. - Se genera un archivo indexado por la palabra original, para poder acceder a la firma.

19 - ¿Qué es la entropía?. - Una medida de incertidumbre. -.

20 - ¿Qué es el algoritmo de mapeo de bits?. - Es una algoritmo de ordenamiento y funciona al pensar en una porción de memoria como un conjunto de bits numerados. -.

21 - ¿Cuál es el objetivo por el que se desarrolló el proyecto PNG?. - Desarrollar un formato de archivos sofisticado y flexible que soportara diferentes tipos de imágenes y se pudieran transferir fácilmente por internet. -.

22 – Señala la opción correcta. La codificación binaria: - Es un caso particular de la codificación de Huffman. -.

23 - ¿Cuál es la definición que corresponde a una imagen del tipo “cartoon-like”?. - Es una imagen en color que se compone de áreas uniformes. -.

24 – Si decimos que, al comprimir los archivos de la campaña publicitaria, aplicaremos compresión PNG, ¿a qué nos referimos?. - Es un algoritmo sin pérdida para bitmaps no sujeto a patentes. - Genera archivos con movimiento.

25 - ¿Cuál de las siguientes afirmaciones respecto al árbol obtenido en la fase de codificación (Huffman) es correcta?. - Se puede conocer el código asociado a un símbolo y obtener el símbolo asociado al código. -.

26 – En el proceso de inserción en un árbol binario de búsqueda, ¿Cuál es la condición de parada y donde se inserta el nuevo hijo?. - La condición de parada es llegar a un nodo que no tenga un hijo en la rama por la que la búsqueda debería seguir. El nuevo nodo se inserta en este hueco, como su nuevo hijo. -.

27 – En algoritmos de poda dinámica, ¿Qué significan TAAT y DAAT?. - TAAT: Term-at-a-time y DAAT: Document-at-a-time. -.

28 - ¿Cuál es el caso trivial que se produce al realizar eliminaciones o borrados de árboles rojinegros descendentes?. - Hermano negro nulo. -.

29 – Señala la opción correcta. El término resolución se utiliza para: - Indicar el número de pixeles por unidad de longitud de imagen. -.

30 - ¿Cuál de las siguientes opciones es incorrecta respecto al proceso de inserción en un árbol AA?. - Los nodos rojos solo pueden añadirse como hijos izquierdos. -.

31 – Cuál de las siguientes afirmaciones es incorrecta respecto de la creación de códigos Huffman?. - No pueden tener variaciones. -.

6 – Seleccione las 3 (tres) respuestas correctas. Los casos de inserción en ARN son: - Inserción de un nodo X con padre ROJO Tío NEGRO (X hijo derecho de P). - Inserción de un nodo X con padre ROJO Tío NEGRO (X hijo izquierdo de P). - Inserción de un nodo X con Padre ROJO y Tío NEGRO. - Inserción de un nodo X en un árbol no vacío y su padre es negro, quedando como rojo. - Inserción de un nodo X en un árbol vacío, quedando como rojo.