Algoritmos y Estructura de Datos II (2do Parcial)

Las dos operaciones básicas de los árboles AA son: ....... Torsión y división. ........ .........

¿Qué es la compresión?. Es un caso particular de recodificación. ............. Es un caso particular de recursividad. .........

¿Qué es importante cuando descomprimimos Huffman?. .............. ............... Es importante tener la cantidad de datos originales, ya que podríamos confundir los datos de relleno con información a decodificar. ................

La inserción en un ábol BST: .... Consiste en la inserción en el nodo raíz, para que solo se reordene. .......... Consiste en una búsqueda no exitosa y la inserción en ese lugar.

Se trata de un árbol equilibrado cuando: La altura del subárbol izquierdo difiere, como máximo en 1, con la altura del subárbol derecho. ... ....... La altura del subárbol izquierdo será la misma que la altura del subárbol derecho.

En un árbol AVL, por convención, el Factor de equilibrio es el: ........ Nivel del subárbol izquierdo - nivel del subárbol derecho, del nodo raíz. Nivel del subárbol izquierdo - nivel del subárbol derecho del nodo que se está analizando. .......

El árbol perfectamente equilibrado ocurre cuando: ......... La altura del subárbol izquierdo será la misma que la altura del subárbol derecho. .......... El número de nodos del subárbol izquierdo difiere, como máximo en 1, con el número de nodos del subárbol derecho.

Los árboles AA se diferencian de los árboles rojinegros en que: Para estos no existen colores. ....... Sus hijos izquierdos no pueden ser rojos. ................

El borrado en un árbol BST de un nodo con un hijo: Implica apuntar el nodo referencial del hijo al padre del nodo a borrar y luego, borrar el nodo. ......... ........... Implica apuntar el nodo referencial del padre al hijo del nodo a borrar y luego, borrar el nodo.

¿Qué codificación es una forma muy simple de compresión de datos, en la que secuencias de datos consecutivas con el mismo valor, son almacenadas como un único valor, más su recuento?. ...... Codificación RLE. ..... Codificación Huffman.

¿En que cosiste la codificación de Huffman, como método?. ....... Se asignan códigos binarios lo más cortos posibles a aquellos símbolos que ocurren con mayor frecuencia en los datos. ........ ........

La inserción en un árbol AA se realiza: ........... En el nivel más alto. ...... En el nivel más bajo.

¿En qué se basa la diferencia de Shannon-Fano con la codificación de Huffman?. En que Huffman comprime y Shannon-Fano solo permuta valores para que otro método comprima. ...... En como construye cada uno el árbol. ...

En un árbol AVL, después de un borrado se aplica una RDD si: ........ El factor de equilibrio (FE) del nodo actual es 2 y el FE del nodo izquierdo es <0. .... El factor de equilibrio (FE) del nodo actual es -2 y el FE del nodo derecho es >0.

A través de los árboles AVL llegaremos a un procedimiento de búsqueda análogo al de los ABB garantizando que, el peor caso sea: .......... ..... O(log2 n). ............

¿Qué se puede afirmar sobre la codificación de Huffman?. Al comienzo se crea un nodo hoja para cada símbolo, asociando un peso según su frecuencia de aparición; luego se lo inserta en la lista ordenada. .......... ......... En la lectura del archivo primero se construye el árbol y luego la tabla.

En los árboles rojinegros, cuando eliminamos un nodo negro con un hijo negro: ............ Se reemplaza por una hoja fantasma doble negra. ...... Se reemplaza por una hoja fantasma sin color.

En árbol AVL, después de una inserción, se aplica una RDI si: El factor de equilibrio (FE) del nodo actual es 2 y el FE del nodo izquierdo es <0. ....... El factor de equilibrio (FE) del nodo actual es -2 y el FE del nodo derecho es >0. ............

Las reglas de los árboles rojinegros garantizan que: ....... Que nunca habrá una alternancia exacta entre nodos por nivel, rojos y negros (siempre habrá una repetición padre negro hijo negro o padre rojo hijo rojo). ............. El camino más largo desde la raíz hasta una hoja no es más largo que dos veces el camino más corto desde la raíz a una hoja.

Respecto a los árboles AA: (4 Opciones correctas). Son una variación del árbol rojo-negro. Reciben el nombre de su inventor, Arne Andersson. Tiene la particularidad que cada nodo de nivel mayor que uno debe tener dos hijos. Tiene la particularidad que ningún nodo rojo puede ser un hijo izquierdo. Tiene la particularidad de que el nivel de un hijo derecho es menor que el de su padre.