AED2 Segundo parcial

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). O(n). O(n log n). O(n^2). O(log n).

Al insertar un nodo en un árbol rojinegro. Seleccione la respuesta correcta. 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 siempre se debe realizar una rotación. El nodo se inserta como una hoja roja y si su padre es rojo, el árbol se vuelve inválido. El nodo se inserta como una hoja roja y siempre se debe realizar una doble rotación. El nodo se inserta como una hoja negra y se realiza una reestructuración en la raíz.

Al insertar un nodo en un árbol rojinegro: Seleccione la respuesta correcta. Sí insertamos una hoja roja y su padre es rojo, estaríamos incumpliendo la 3er regla. Sí insertamos una hoja negra y su padre es negro, estaríamos incumpliendo la 3er regla. Sí insertamos una hoja roja y su abuelo es negro, estaríamos incumpliendo la 4ta regla. Sí insertamos una hoja negra y su padre es rojo, estaríamos incumpliendo la 3er regla. Sí insertamos una hoja roja y su padre es negro, estaríamos incumpliendo la 1ra regla.

Al insertar un nodo en un árbol rojinegro, lo que se conoce como "caso 5" es: Cuando su padre es ROJO y su tío es NEGRO, se aplican las rotaciones y ahí finaliza el reequilibrio. Cuando su padre es ROJO y su tío es ROJO, se cambia el color del padre y del tío. Cuando su abuelo es NEGRO y su padre es ROJO, se realiza una rotación doble. Cuando su padre es NEGRO y su tío es ROJO, se aplica una rotación y un cambio de color. Cuando su padre es ROJO y su abuelo es NEGRO, no se realiza ninguna rotación y se cambia el color del nodo.

Altura de un árbol AVL es: Seleccione 2 (dos) respuestas correctas. '0 Si el árbol T contiene sólo la raíz. 1+max(H(Ti),H(Td)) si contiene más nodos. (siendo Ti el subárbol izquierdo y Td el subárbol derecho). '1 Si el árbol T tiene un solo nodo. '2 Si el árbol T tiene dos niveles completos. 'h Si el árbol T tiene h nodos.

Casos de inserción en ARN son: Seleccione las 3 (tres) respuestas correctas. Inserción de un nodo X con Padre ROJO y Tío ROJO. 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 NEGRO y Tío NEGRO. Inserción de un nodo X con Padre ROJO y Tío NEGRO.

¿Cuál de estás es una afirmación correcta 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 e insertarlo en la lista ordenada ascendentemente. Los nodos se crean al final del proceso y se les asigna un peso de acuerdo a su orden en el alfabeto. Se comienza creando un nodo para cada símbolo y se los organiza en una lista ordenada descendentemente según su frecuencia. Los símbolos con menor frecuencia se agrupan y se asigna un único nodo con un peso igual a la suma de sus frecuencias. Los nodos hoja se insertan en la lista ordenada de forma aleatoria.

¿Cuál de las siguientes afirmaciones explica la principal diferencia entre árboles AA con los árboles rojinegros?. En los árboles AA los hijos izquierdos no pueden ser rojos. En los árboles AA los hijos derechos no pueden ser rojos. En los árboles rojinegros, todos los nodos tienen la misma altura. En los árboles rojinegros, los nodos rojos no pueden tener hijos rojos. En los árboles AA los nodos negros no pueden tener hijos rojos.

¿Cuál de las siguientes reglas de los árboles rojinegros es falsa? Seleccione la respuesta correcta. Si un nodo es negro, sus hijos deben ser rojos. La raíz siempre debe ser negra. Los nodos rojos no pueden tener hijos rojos. Las hojas (nodos nulos) se consideran negras. Un nodo rojo debe tener un padre negro.

¿Cuáles de estas afirmaciones son correctas? Seleccione 3(tres) respuestas correctas. El método Shannon-Fano está basado en la codificación de la entropía. El método RLE es basado en diccionario. La reducción de datos en la compresión puede afectar o no a la calidad de la información. El método Shannon-Fano genera códigos basados en probabilidades de los símbolos. El método Shannon-Fano requiere una etapa de compresión de datos previa.

Cuando comprimimos con Huffman. Seleccione la respuesta correcta. Suele no terminarse de escribir un byte completo y por convención se rellena con bits ceros. La compresión Huffman siempre utiliza bloques de 8 bits, por lo que nunca es necesario rellenar bits. Al comprimir con Huffman, los códigos son siempre de longitud fija y no se necesita ningún relleno adicional. La compresión Huffman usa un esquema de longitud fija para los códigos, por lo que nunca se deja un byte incompleto. Durante la compresión Huffman, los datos se dividen en bloques de 16 bits, eliminando la necesidad de relleno de bits.

Cuando descomprimimos con Huffman. Seleccione la respuesta correcta. Es importante tener la cantidad de datos originales ya que podríamos confundir los datos de relleno con información a decodificar. (Si no sabemos cuántos datos hay que descomprimir, es posible que tengamos bits en cero que se pueden llegar a confundir con datos reales). El proceso de descompresión con Huffman siempre requiere la reconstrucción completa del árbol de Huffman desde el inicio. Durante la descompresión con Huffman, los datos de relleno no son un problema ya que se eliminan durante la compresión. El esquema de Huffman no utiliza ningún método de relleno, por lo que la descompresión no se ve afectada. La descompresión con Huffman no necesita saber la cantidad de datos originales ya que los códigos se interpretan en bloques fijos.

Cuando leemos todo un archivo, para evitar errores nos detendremos cuando encontremos la condición: Seleccione la respuesta correcta. EOF ya que indica "End Of File". Un carácter nulo (\0) ya que indica el final de un archivo de texto. Un byte de valor 0xFF ya que marca el final del archivo en formato binario. Un salto de línea (\n) ya que indica el final de una línea en el archivo. Un error de lectura ya que el archivo puede estar corrupto o dañado.

Cuando un subárbol izquierdo de cualquier nodo (si no está vacío) contiene valores menores que el contiene dicho nodo, y el subárbol derecho (si no está vacío) contiene valores mayores estamos hablando de un: Árbol Binario de Búsqueda. Árbol AVL. Árbol Rojinegro. Árbol B-Tree. Árbol Splay.

Decimos que un árbol M-ario es completo si cumple que... Cada nodo interno tiene exactamente M hijos. Cada nodo interno tiene al menos M hijos, pero no necesariamente exactamente M. Todos los nodos tienen exactamente M hijos, incluidos los nodos hoja. Cada nivel del árbol está completamente lleno antes de pasar al siguiente nivel. Todos los nodos internos tienen al menos M hijos y los nodos hoja están en el último nivel.

Dentro de la teoría de información y la compresión de datos, ¿Cuáles de estas definiciones son correctas?: Seleccione las 4 (cuatro) respuestas correctas. La redundancia son los datos que son repetitivos o previsibles. Factor de compresión = (bytes arch original / bytes archivo comprimido). Razón de compresión = (bytes arch comprimido / bytes arch original). La información irrelevante es la que no podemos apreciar y cuya eliminación por lo tanto no afecta al contenido del mensaje. La redundancia es la cantidad de información nueva que se agrega durante la compresión.

El acceso a un archivo según el orden de almacenamiento de sus datos registros, uno tras otro: Seleccione la respuesta correcta. Se llama acceso secuencial. Se llama acceso directo. Se llama acceso simultáneo. Se llama acceso por índice. Se llama acceso por clave.

El acceso a un registro determinado, sin que ello implique la consulta de los registros precedentes. Se llama acceso Directo (aleatorio). Se llama acceso secuencial. Se llama acceso por índice. Se llama acceso secuencial y por clave. Se llama acceso por clave.

El algoritmo de eliminación en los árboles AA, se implementa en forma más directa, porque su definición nos asegura que... Los hijos izquierdo los rojos están prohibidos. Los nodos rojos no pueden tener hijos. Los nodos siempre están equilibrados antes de la eliminación. Todos los nodos deben tener exactamente dos hijos. Los nodos se eliminan en orden ascendente.

El algoritmo de Huffman: Se caracteriza por armar una lista de árboles. Se caracteriza por crear códigos de longitud fija para cada símbolo. Se caracteriza por construir una tabla de frecuencias antes de codificar. Se caracteriza por ordenar los símbolos en una lista y asignar códigos basados en el orden. Se caracteriza por utilizar un enfoque de compresión basado en diccionario.

El algoritmo de Huffman consiste en: Seleccione la respuesta correcta. Crear una lista de árboles y a partir de allí una Tabla. Ordenar los símbolos en función de su frecuencia y asignar códigos basados en el orden. Crear una tabla de frecuencias y asignar códigos fijos a cada símbolo. Crear una tabla de frecuencias y luego codificar los símbolos mediante una tabla de mapeo. Usar un diccionario para almacenar las frecuencias de los símbolos y codificar en función del índice.

El algoritmo de mapeo de Bits: Es un algoritmo de ordenamiento y funciona al pensar en una porción de memoria como un conjunto de bits numerados. Es un algoritmo de codificación que convierte caracteres en códigos binarios de longitud variable. Es un algoritmo de búsqueda que organiza los bits en una estructura de árbol binario para optimizar el acceso. Es un algoritmo de encriptación que cifra datos convirtiéndolos en secuencias de bits aleatorios. Es un algoritmo de análisis de datos que convierte una secuencia de bits en números decimales.

El algoritmo de Shanon-Fano: En el que se construye un código sin prefijo basado en un conjunto de símbolos y sus probabilidades. En el que se construye un árbol binario para codificar símbolos de manera eficiente. En el que se utiliza una tabla de frecuencias para asignar códigos fijos a los símbolos. En el que los símbolos se codifican en bloques de tamaño fijo y luego se comprimen. En el que se construye una tabla de códigos de longitud fija para representar los símbolos.

El algoritmo de Shanon-Fano: Se caracteriza por dividir en 2 conjuntos cuya suma de probabilidades sean tan iguales como sea posible. Se caracteriza por asignar códigos de longitud fija a cada símbolo según su frecuencia. Divide los símbolos en función de su orden alfabético en lugar de sus probabilidades. Utiliza una tabla de frecuencias para codificar cada símbolo con una secuencia binaria predefinida. Se basa en la codificación de longitud fija para todos los símbolos, sin considerar sus frecuencias.

El algoritmo para encontrar todos los anagramas posibles realiza todo el trabajo en una pasada sobre el archivo de entrada, computando la firma de cada palabra, ordenándolo e imprimiendo todos los conjuntos de anagramas correspondientes a la palabra que se busca. Falso. Verdadero.

El Algoritmo para mantener un árbol AVL equilibrado se basa en... Reequilibrados locales. Redistribución de nodos en toda la estructura. Aplicación de rotaciones simples y dobles para asegurar el equilibrio. Cambios en la estructura del árbol para equilibrar los subárboles. Actualización de la profundidad de todos los nodos en el árbol.

El algoritmo que tiende a reducir el número de pasadas que hagamos en los algoritmos de ordenamiento externo es: Mezcla Equilibrada Múltiple. Ordenamiento por selección. Ordenamiento por inserción. Ordenamiento rápido (quicksort). Ordenamiento por fusión simple.

El algoritmo RLE (compresión RLE): Se caracteriza por comprimir bytes repetidos adyacentes. Se basa en la codificación de longitud variable para representar símbolos. Utiliza una tabla de frecuencias para asignar códigos a secuencias de bytes. Comprime datos utilizando una codificación de longitud fija para todos los símbolos. Reemplaza secuencias de datos con códigos basados en el orden alfabético de los símbolos.

El árbol Adelson-Velskii-Landis se caracteriza por ser: Seleccione la respuesta correcta. Un árbol autobalanceado que garantiza que la altura del subárbol izquierdo diferirá de la altura del árbol derecho, como máximo en 1. Un árbol binario que garantiza que todos los nodos tienen exactamente dos hijos. Un árbol de búsqueda con una altura fija que no depende de la cantidad de nodos. Un árbol binario de búsqueda con balanceo dinámico basado en rotaciones. Un árbol de búsqueda donde la altura de cada subárbol puede diferir en más de 1 nivel.

El borrado en un árbol BST de un nodo con 2 hijos: Tiene 2 posibles soluciones. Se resuelve moviendo el nodo al final del árbol y luego eliminándolo. Se resuelve cambiando el nodo por uno de sus hijos directos. Se resuelve eliminando el nodo y ajustando solo los nodos hoja. Se resuelve eliminando el nodo y manteniendo el árbol sin balancear.

El borrado en un árbol BST de un nodo con un hijo: Implica apuntar el nodo referencial del padre al hijo del nodo a borrar y luego borrar el nodo. Requiere mover el nodo a borrar al final del árbol y ajustar los punteros correspondientes. Consiste en eliminar el nodo y redistribuir el árbol para mantener el balance. Implica copiar el valor del hijo al nodo a borrar y luego eliminar el hijo. Exige reestructurar el árbol como un árbol AVL para mantener el equilibrio.

El borrado en un árbol BST de un nodo sin hijos: Es tan simple como eliminar el nodo, y poner en nulo el dato referencial que lo apunta del padre. Requiere reemplazar el nodo con un nodo especial que indique su eliminación. Implica ajustar todos los nodos en el árbol para mantener el equilibrio. Exige copiar el valor del nodo a eliminar al nodo padre antes de eliminarlo. Consiste en mover el nodo a eliminar a un nodo hoja y luego eliminarlo.

El concepto de árbol equilibrado es: La altura del subárbol izquierdo difiere como máximo en 1 con la altura del subárbol derecho. Todos los nodos deben tener exactamente dos hijos para mantener el equilibrio. La altura de cada subárbol debe ser la misma para considerar el árbol equilibrado. El árbol se balancea ajustando el número de nodos en cada nivel. Cada nivel del árbol debe estar completamente lleno para mantener el equilibrio.

El concepto de árbol perfectamente equilibrado es: 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. La altura de todos los subárboles en cada nodo debe ser la misma. El número de nodos en el subárbol izquierdo y derecho debe ser exactamente igual. La diferencia en la altura de los subárboles izquierdo y derecho debe ser exactamente 0. Cada nodo debe tener el mismo número de hijos para que el árbol sea considerado perfectamente equilibrado.

El concepto principal de un BST es: Para cualquier nodo del árbol, todos los nodos con clave menor que la suya están en su subárbol izquierdo. Todos los nodos deben tener exactamente un hijo izquierdo y un hijo derecho. La altura del árbol debe ser la misma en todos los nodos para considerarlo un BST. Los nodos se ordenan de manera que cada nivel del árbol tiene el mismo número de nodos. Los nodos con claves menores que la raíz deben estar a la derecha de la raíz.

El coste de una operación en un árbol BST: Es proporcional a la profundidad del último nodo. Es constante y no depende de la estructura del árbol. Es proporcional al número total de nodos en el árbol. Es proporcional al número de operaciones realizadas en el árbol. Es inversamente proporcional al número de nodos en el árbol.

El equilibrio de un árbol AVL se logra: Seleccione la respuesta correcta. Haciendo operaciones de re-equilibrado después de una operación de inserción o de borrado. Cambiando la estructura del árbol después de cada consulta. Aplicando rotaciones solamente después de cada búsqueda. Asegurando que todos los nodos tengan el mismo número de hijos para mantener el equilibrio. Rebalanceando el árbol en el momento de la creación inicial, sin necesidad de ajustes posteriores.

El Factor de equilibrio de un árbol AVL me dice que: Si su valor es 1 el nodo está equilibrado y su subárbol izquierdo es un nivel más alto. Si su valor es -1, el nodo está equilibrado y su subárbol derecho es un nivel más alto. Si su valor es mayor que 1, el nodo está desequilibrado y necesita una rotación. Si su valor es -2, el nodo está equilibrado y su subárbol izquierdo es dos niveles más alto. Si su valor es 2, el nodo está equilibrado y su subárbol derecho es dos niveles más alto.

El hecho de incrementar el número de archivos auxiliares, es una característica del método: Seleccione la respuesta correcta. Mezcla equilibrada múltiple. Ordenamiento por inserción. Ordenamiento por selección. Ordenamiento rápido (quicksort). Ordenamiento por burbuja.

El marcador EOF de un archivo. Seleccione 4 (cuatro) respuestas correctas. Conceptualmente en caso de un archivo indica que se llegó al final del mismo. Es un indicador o marca de que no hay más información que recuperar de una fuente de datos. Existe en la tabla ASCII aunque es un carácter no imprimible. En UNIX y linux se puede generar un EOF desde el shell (consola) tecleando Ctrl+D para indicar el EOF de datos ingresados por teclado, así como en Microsoft DOS y Windows se genera mediante la combinación Ctrl+Z. En sistemas operativos y bibliotecas de programación, se utiliza para manejar la terminación de la lectura de archivos.

El método de compresión de datos que, basado en tablas, donde las entradas de la tabla son reemplazadas por cadenas de datos repetidos. Se conoce como... Compresión Lempel-Ziv. Compresión RLE (Run-Length Encoding). Compresión por codificación Huffman. Compresión por sustitución de caracteres fijos. Compresión por fragmentación de datos.

El método de fusión natural se diferencia del de mezcla directa: seleccione la respuesta correcta. Respecto a la longitud de las secuencias de registros. En la complejidad de los algoritmos de ordenamiento utilizados. En la cantidad de archivos de entrada requeridos para el proceso. En el tipo de estructuras de datos utilizadas para almacenar los registros durante el proceso. En el método de acceso a los archivos durante la fusión.

El método de mezcla directa, cada pasada escribe el total de n registros: Seleccione la respuesta correcta. Por lo que el número total de movimientos es O(n Log n). Por lo que el número total de movimientos es O(n²). Por lo que el número total de movimientos es O(n). Por lo que el número total de movimientos es O(n Log² n). Por lo que el número total de movimientos es O(n Log³ n).

El método de Mezcla directa repite el algoritmo hasta que: Seleccione la respuesta correcta. Hasta que la longitud de la subsecuencia sea la del archivo original. Hasta que todas las subsecuencias estén ordenadas en memoria. Hasta que se haya leído el archivo completo en una sola pasada. Hasta que el número de archivos de salida sea uno. Hasta que se hayan combinado todos los registros en el archivo de entrada.

El método de ordenación externa mezcla directa: Seleccione la respuesta correcta. En el paso i obtiene secuencias ordenadas de longitud 2^i. En el paso i obtiene secuencias ordenadas de longitud 2^i-1. En el paso i obtiene secuencias ordenadas de longitud 2^i+1. En el paso i obtiene secuencias ordenadas de longitud i+1. En el paso i obtiene secuencias ordenadas de longitud 2^(i+1).

El método de ordenación fusión natural: Seleccione la respuesta correcta. Distribuye en todo momento secuencias ordenadas (tramos) lo mas largas posibles. Utiliza únicamente una pasada para ordenar todo el archivo completo. Ordena los registros en memoria antes de escribirlos en el archivo. Requiere que el archivo completo esté en memoria antes de iniciar el proceso. Divide el archivo en partes iguales antes de aplicar la fusión.

El método de ordenamiento externo que consiste en distribuir secuencias ordenadas lo más largas posibles, determinando secuencias ordenadas máximas o tramos, recibe el nombre de... Mezcla Natural. Ordenamiento por inserción externa. Mezcla Equilibrada Múltiple. Ordenamiento por selección externa. Ordenamiento por burbuja externa.

El método de ordenamiento externo que utiliza m archivos (m-1 archivos de entrada y 1 de salida) es: Método Polifásico. Método de Mezcla Directa. Método de Ordenamiento por Inserción. Método de Mezcla Equilibrada. Método de Ordenamiento por Selección.

El método de ordenamiento por Mezcla Natural. Seleccione 2 (dos) respuestas correctas. Mejora el tiempo de ejecución de la mezcla directa. Se distribuye secuencias ordenadas lo más largas posibles. Mejora el tiempo de ejecución de la mezcla directa. (Correcta). Utiliza un número fijo de archivos para la mezcla. Requiere que todo el archivo esté en memoria antes de comenzar la ordenación.

El método original propuesto por Huffman, requiere dos pasadas sobre los datos para realizar la compresión, en la primera, se obtienen las estadísticas de los símbolos, en la segunda se realiza la compresión. Una mejora es que el compresor y el descompresor inician con un árbol vacio y conforme se lean y procesan (comprimir / descomprimir) los símbolos, ambos modifican el árbol de la misma forma. Y se llama: Huffman Adaptable. Codificación de Huffman Estática. Codificación de Huffman Fija. Codificación de Huffman Binaria. Codificación de Huffman en Bloques.

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 total de nodos en el árbol dividido por el número de enlaces hasta el nodo. El nivel es la diferencia en altura entre el subárbol izquierdo y el subárbol derecho del nodo. El nivel es el número de enlaces a la derecha desde el nodo hasta el centinela. El nivel es el número de enlaces en el camino desde el nodo hasta la raíz del árbol.

El número mínimo de nodos de un árbol AVL es: Exponencial respecto a su altura. Lineal respecto a su altura. Constante respecto a su altura. Cuadrático respecto a su altura. Logarítmico respecto a su altura.

El ordenamiento externo: seleccione 4 (cuatro) respuestas correctas. Es ordenamiento basado en archivos. Tiene como técnica reducir el número de acceso a archivos. Usa un esquema de separación y mezcla. En un dispositivo secuencial, tal como una cinta, es mucho más lento que uno que permita acceso directo, tal como un disco. Se realiza completamente en memoria principal sin necesidad de acceso a medios secundarios.

El peor caso de un árbol BST es de complejidad: O(N). O(N log N). O(log N). O(N^2). O(1).

El principal objetivo del ordenamiento externo, puede definirse como... Reducir el número de accesos a los archivos. Optimizar el rendimiento del algoritmo de ordenamiento interno. Eliminar la necesidad de fusión de archivos durante el ordenamiento. Minimizar el uso de la memoria principal durante el proceso de ordenamiento. Incrementar el número de archivos de entrada durante el proceso de ordenamiento.

El reemplazar el valor del nodo por el de su predecesor o por el de su sucesor en inorden: Y luego el borrado del nodo, se hace cuando se intenta borrar un nodo con 2 hijos en un árbol BST. Y luego realizar una rotación para mantener el equilibrio del árbol. Y luego ajustar los factores de equilibrio del árbol para mantener la propiedad AVL. Y luego mover el nodo a una posición temporal antes de borrarlo. Y luego reordenar los nodos del árbol para mantener el orden de los elementos.

En árboles AVL, definimos el Factor de Equilibrio como... La diferencia entre las alturas del árbol. La diferencia entre el número de nodos en el subárbol izquierdo y derecho. La altura del subárbol izquierdo menos la altura del subárbol derecho. La suma de las alturas de los subárboles izquierdo y derecho del nodo. El número total de nodos en el árbol menos la diferencia en alturas de los subárboles.

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

En el algoritmo de Huffman, para descomprimir necesitamos el árbol o la tabla y, además: El tamaño original del archivo. La frecuencia de aparición de cada símbolo en el archivo comprimido. La clave de cifrado utilizada durante la compresión. La versión del algoritmo de Huffman utilizado para la compresión. El número de pasadas realizadas durante la compresión.

En el algoritmo de Huffman. Seleccione la respuesta correcta. Se codifica en el árbol generado información solo en los nodos hojas. Se codifica información en todos los nodos del árbol, incluidos los nodos internos. Se codifica información en los nodos internos, mientras que las hojas contienen los códigos. Se codifica información en los nodos internos y las hojas contienen solo símbolos. Se codifica información en las ramas del árbol y no en los nodos.

En el algoritmo de Huffman. Seleccione la respuesta correcta. Se leen los códigos desde la raíz hacia las hojas. Se leen los códigos desde los nodos internos hacia las hojas. Se leen los códigos en orden inverso a cómo se generan. Se leen los códigos de manera aleatoria en el árbol. Se leen los códigos en el orden en que se insertan los nodos en el árbol.

En el ámbito de la teoría de la información la entropía, o entropía de Shannon (en honor a Claude E. Shannon): Mide la incertidumbre de una fuente de información. Mide la cantidad de datos que se pueden comprimir en un archivo. Mide la velocidad a la que se transmiten los datos en una red. Mide la cantidad de redundancia en una fuente de información. Mide el tamaño total del archivo después de la compresión.

En el método polifásico, en el momento en que un archivo de entrada alcanza su final pasa a ser de salida, y el que era de salida pasa a ser de entrada. Verdadero. Falso.

En el tratamiento de archivos, si los registros son de tamaño variable: Seleccione la respuesta correcta. Deberé procesarlo en forma secuencial. Deberé procesarlo en forma aleatoria. Deberé procesarlo en forma indexada. Deberé procesarlo en forma binaria. Deberé procesarlo en forma directa.

En el tratamiento de archivos, si quiero recuperar un registro especifico y los registros son de tamaño fijo: Seleccione la respuesta correcta. Deberé procesarlo en forma directa (aleatoria). Deberé procesarlo en forma secuencial. Deberé procesarlo en forma indexada. Deberé procesarlo en forma binaria. Deberé procesarlo en forma por lotes.

En estructuras de datos, a una colección de datos guardados en un dispositivo de almacenamiento permanente se la conoce como... Archivo. Tabla. Registro. Buffer. Estructura de datos.

En la eliminación de un nodo del árbol AA: La eliminación se simplifica ya que el caso de un único hijo solo se puede dar en el nivel 1. La eliminación se complica debido a la necesidad de rotaciones múltiples. La eliminación siempre requiere una reestructuración completa del árbol. La eliminación se simplifica ya que no se requiere ajustar los niveles del árbol. La eliminación se simplifica ya que no se permite tener nodos con dos hijos.

En los 5 casos de borrado en un árbol rojo-negro. Seleccione 4 (cuatro) respuestas correctas. Se analiza si X es la raíz. Si el nodo X es doble negro, su hermano es negro y su padre es negro. Si el nodo X es doble negro, su hermano es negro (con hijos negros) y su padre rojo. Si el nodo X es negro y su hermano es rojo y su padre negro. Se verifica si el nodo a borrar es rojo o negro.

En los árboles AA, al realizar una inserción, ¿Qué sucede si aparecen dos enlaces horizontales derechos?. Se realiza una operación de reparto, posiblemente incrementando el nivel del nuevo nodo raíz del subárbol correspondiente. Se realiza una rotación simple para equilibrar el árbol sin cambiar el nivel del nodo raíz. Se cambian los colores de los nodos involucrados sin ajustar el nivel del árbol. Se realizan rotaciones dobles para mantener la estructura del árbol sin cambiar el nivel. Se ajusta el nivel de los nodos hijos sin afectar al nodo raíz del subárbol.

En los árboles AA, AVL y los árboles rojinegros, luego de insertar un nodo pueden necesitarse algunas rotaciones. Una de ellas se conoce como la operación Giro, que consiste en... Eliminar enlaces horizontales izquierdos. Reorganizar los enlaces entre nodos para balancear el árbol sin cambios en el nivel. Actualizar los factores de equilibrio de los nodos sin modificar su estructura. Recolorear los nodos afectados para mantener las propiedades del árbol. Ajustar el nivel de los nodos superiores sin realizar cambios en los enlaces.

En los árboles AA, en un enlace horizontal se debe cumplir que... La conexión se da entre un nodo y un hijo suyo del mismo nivel. La conexión se da entre un nodo y un hijo suyo de nivel superior. La conexión se da entre un nodo y un hijo suyo que tenga un color diferente. La conexión se da entre un nodo y un hijo de otro subárbol sin importar el nivel. La conexión se da entre un nodo y un nodo en el mismo nivel que no sea hijo suyo.

En los árboles autobalanceados son válidas estas definiciones de equilibrio. Seleccione las 2 (dos) respuestas correctas. Árbol Equilibrado: La altura del subárbol izquierdo difiere como máximo en 1 con la altura del subárbol derecho. Árbol Perfectamente Equilibrado: El peso del subárbol izquierdo difiere como máximo en 1 con el peso del subárbol derecho. Árbol Rojo-Negro: En el árbol, todos los caminos desde la raíz hasta las hojas tienen el mismo número de nodos negros. Árbol Rojo-Negro: Cada nodo rojo tiene hijos negros. Árbol AA: Los enlaces horizontales no están permitidos entre nodos del mismo nivel.

En los árboles rojinegros cuando eliminamos un nodo negro con un hijo negro: Seleccione la respuesta correcta. Se reemplaza por una hoja fantasma doble negra. Se reemplaza por un nodo blanco con un hijo rojo. Se reemplaza por una hoja fantasma roja. Se reemplaza por un nodo negro con un hijo doble negro. Se reemplaza por un nodo negro con un hijo negro.

En los árboles rojinegros cuando eliminamos un nodo negro sin hijos. Seleccione la respuesta correcta. Se debe hacer la eliminación y luego analizar los 6 casos posibles de reestructuración. Se debe hacer la eliminación y luego simplemente recolorear el nodo padre a negro. Se debe hacer la eliminación y luego ajustar el color de los nodos hijos sin reestructuración. Se debe hacer la eliminación y luego realizar rotaciones para mantener el equilibrio. Se debe hacer la eliminación y luego fusionar el nodo con el nodo hermano.

En los árboles rojinegros cuando eliminamos un nodo rojo con un sólo hijo: Seleccione la respuesta correcta. Simplemente se reemplaza el nodo borrado por su hijo, conservando el color del original, sin necesidad de análisis de reequilibrio. Se realiza una rotación para mantener el equilibrio y luego se reemplaza el nodo borrado por su hijo. Se reemplaza el nodo borrado por su hijo y se realiza un análisis completo del árbol para reequilibrar. Se reemplaza el nodo borrado por su hijo y se convierte el árbol en un árbol binario de búsqueda temporalmente. Se elimina el nodo y se ajustan los colores y niveles de todos los nodos padres.

En los árboles rojinegros podemos afirmar que el camino más largo desde la raíz hasta una hoja es... No es más largo que 2 veces el camino más corto desde la raíz del árbol a una hoja en dicho árbol. Es exactamente 3 veces más largo que el camino más corto desde la raíz hasta una hoja. No es más largo que el doble del número de nodos en el camino más corto desde la raíz hasta una hoja. Es más largo que 3 veces el camino más corto desde la raíz hasta una hoja. Es independiente de la longitud del camino más corto desde la raíz hasta una hoja.

En los árboles rojinegros se puede borrar... Un nodo hoja o con un hijo. Solo un nodo hoja. Solo un nodo con dos hijos. Un nodo interno con más de dos hijos. Solo un nodo negro con dos hijos rojos.

En los árboles rojinegros. Seleccione 3 (tres) respuestas correctas. Cada camino desde un nodo dado a sus hojas descendientes contiene el mismo número de nodos negros. Todas las hojas fantasmas (NULL) son negras. Todo nodo es o bien rojo o bien negro. La raíz del árbol puede ser roja o negra. Un árbol rojinegro puede tener hojas de color rojo.

En los árboles rojinegros: Seleccione la respuesta correcta. Las hojas no son relevantes y no contienen datos. Las hojas contienen los datos más importantes del árbol. Las hojas pueden ser de cualquier color. Las hojas son siempre nodos negros que contienen datos. Las hojas pueden contener uno o más hijos.

En los archivos secuenciales: Seleccione las 4 (cuatro) respuestas correctas. Pueden ser implementados en dispositivos directos como disco. Se hereda su funcionamiento del manejo de cintas magnéticas. Se permite longitud variable de registro. Un claro ejemplo es un archivo .txt. Solo pueden ser implementados en dispositivos de cinta.

En los archivos aleatorios: Seleccione las 4 (cuatro) respuestas correctas: Los registros son de tamaño fijo. Permite la simulación secuencial. Un programa puede comenzar a leer o escribir un archivo de acceso aleatorio en cualquier posición. Una tabla de base de datos es un claro ejemplo de ello. Pueden ser implementados en dispositivos secuenciales, como cintas.

¿En qué consiste el proceso compresión de datos?. El proceso de codificar información usando menos bits que una representación sin codificar. El proceso de duplicar datos en un archivo para mejorar su precisión. El proceso de dividir un archivo en partes más pequeñas sin cambiar su tamaño total. El proceso de eliminar datos importantes para reducir el tamaño del archivo. El proceso de transformar datos en su forma original sin pérdida de información.

En un árbol AVL, después de un borrado se aplica una RDD si: Seleccione la respuesta correcta. El FE del nodo actual es 2 y el FE del nodo izquierdo es <0. El FE del nodo actual es -2 y el FE del nodo derecho es >0. El FE del nodo actual es 2 y el FE del nodo derecho es >0. El FE del nodo actual es -1 y el FE del nodo izquierdo es >0. El FE del nodo actual es 0 y el FE del nodo izquierdo es 1.

En un árbol AVL, después de una inserción se aplica una RDI si: Seleccione la respuesta correcta. El FE del nodo actual es -2 y el FE del nodo derecho es > 0. El FE del nodo actual es 1 y el FE del nodo derecho es 0. El FE del nodo actual es -1 y el FE del nodo izquierdo es > 0. El FE del nodo actual es 0 y el FE del nodo izquierdo es -1. El FE del nodo actual es 2 y el FE del nodo izquierdo es < 0.

En un árbol AVL por convención el Factor de Equilibrio es: Nivel del subárbol izquierdo - nivel del subárbol derecho, del nodo que se está analizando. Nivel del subárbol derecho - Nivel del subárbol izquierdo, del nodo que se está analizando. Altura del subárbol derecho - Altura del subárbol izquierdo, del nodo que se está analizando. Número de nodos en el subárbol izquierdo - Número de nodos en el subárbol derecho. Suma de los niveles de ambos subárboles, dividido por 2.

En un árbol B. seleccione 4 (cuatro) respuestas correctas. Cada elemento de un nodo interno actúa como un valor separador, que lo divide en subárboles. En el mejor de los casos, la altura de un árbol-B es (logaritmo en base M de n). En el peor de los casos, la altura de un árbol-B es N. Se mantiene balanceado porque requiere que todos los nodos hoja se encuentren a la misma altura. Cada nodo hoja puede contener solo un elemento.

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

En un árbol B M-ario: Los nodos internos contienen m-1 claves para guiar la búsqueda. Los nodos internos contienen exactamente M claves para guiar la búsqueda. Los nodos internos pueden contener entre 1 y M claves. Los nodos internos no contienen claves, solo punteros. Cada nodo interno contiene como máximo M+1 claves.

En un árbol de búsqueda M-ario, ¿cuántas claves son necesarias para decidir cuál de las ramas se debe utilizar para definir el árbol?. M-1 claves. M claves. M+1 claves. M/2 claves. 2M claves.

En un árbol rojinegro cuando eliminamos un nodo negro con un hijo negro: Seleccione la respuesta correcta. Se reemplaza por una hoja fantasma doble negra. Se reemplaza el nodo por su hijo negro y se ajusta el color del hijo a rojo. Se reemplaza el nodo por su hijo y se colorea el hijo de rojo si es negro. Se elimina el nodo y se realiza una rotación simple a la izquierda o derecha. Se reemplaza el nodo por una hoja fantasma simple negra.

En una árbol AVL, después de una inserción se aplica una RDI si: Seleccione la respuesta correcta. El FE del nodo actual es -2 y el FE del nodo derecho es > 0. El FE del nodo actual es 2 y el FE del nodo izquierdo es < 0. El FE del nodo actual es 1 y el FE del nodo derecho es 0. El FE del nodo actual es -1 y el FE del nodo derecho es > 0. El FE del nodo actual es 0 y el FE del nodo derecho es -1.

En una rotación doble a derecha, si tenemos un nodo P(fe=-2) y su hijo izquierdo Q(fe=1) y el hijo derecho de Q llamado R(fe=0). Se realiza en orden, el subarbol izquierdo de R queda como hijo derecho de Q, R pasa como hijo izquierdo de P y como hijo izquierdo de R. Luego el subarbol derecho de R pasa como hijo izquierdo de P y P como hijo derecho de R. Falso. Verdadero.

En una Rotación simple a la derecha, de un arból de raiz (r) y de hijos izquierdo (i) y derecho (d), lo que haremos será formar un nuevo árbol cuya raíz sea la raíz del hijo izquierdo, como hijo izquierdo colocamos el hijo izquierdo de i (nuestro i¿) y como hijo derecho construimos un nuevo árbol que tendrá como raíz, la raíz del árbol (r), el hijo derecho de i (d¿) será el hijo izquierdo y el hijo derecho será el hijo derecho del árbol (d). Verdadero. Falso.

En una rotación simple a la izquierda, de un arból de raiz (r) y de hijos izquierdo (i) y derecho (d), lo que haremos será formar un nuevo árbol cuya raíz sea la raíz del hijo izquierdo, como hijo izquierdo colocamos el hijo izquierdo de i (nuestro i¿) y como hijo derecho construimos un nuevo árbol que tendrá como raíz, la raíz del árbol (r), el hijo derecho de i (d¿) será el hijo izquierdo y el hijo derecho será el hijo derecho del árbol (d). Falso. Verdadero.

En una rotación simple de un árbol AVL. Seleccione la respuesta correcta. Se intercambian los datos referenciales entre el padre y uno de sus hijos. El hijo depende de si es RSI o RSD. Se intercambia el color de los nodos entre el padre y el hijo. Se realiza una rotación alrededor del nodo raíz del subárbol para mantener el equilibrio. El padre se convierte en hijo del nodo que estaba originalmente en el lugar del hijo. Se mueve el nodo actual a una nueva posición en el árbol y el hijo se convierte en la nueva raíz del subárbol.

Es el método más simple de ordenamiento externo: Mezcla Directa. Manejo de Fusión Natural. Mezcla Equilibrada Múltiple. Ordenamiento Polifásico. Ordenamiento por Intercalación.

¿Es posible buscar el elemento K-esimo de un árbol BST?. Sí. Si actualizamos el tamaño de los nodos en cada operación de modificación del árbol. No, porque los árboles BST no mantienen un orden secuencial de los elementos. Sí, pero solo si el árbol está equilibrado. No, ya que un BST no almacena información sobre el número de nodos en cada subárbol. Sí, mediante una búsqueda exhaustiva en el árbol.

Este método de ordenamiento mejora el tiempo de ejecución de la mezcla directa: Mezcla Natural. Mezcla Equilibrada Múltiple. Ordenamiento por Intercalación. Método Polifásico. Ordenamiento por Inserción.

Estos algoritmos. "funcionan entre el conjunto de soluciones de un problema llamado fenotipo, y el conjunto de individuos de una población natural, codificando la información de cada solución en una cadena, generalmente binaria". Estamos hablando de: Algoritmos Genéticos. Algoritmos de Optimización por Enjambre. Algoritmos Evolutivos. Algoritmos de Búsqueda Aleatoria. Algoritmos de Programación Dinámica.

Indique que afirmación es correcta sobre compresión: Huffman, construye los códigos de abajo hacia arriba combinando repetidamente las dos entradas menos comunes en la lista de poblaciones hasta que quedan solo dos. Huffman, construye los códigos de arriba hacia abajo, dividiendo repetidamente el conjunto de símbolos en dos grupos hasta que todos los símbolos están codificados. Huffman, construye los códigos asignando frecuencias a los símbolos y codificando cada símbolo individualmente sin combinar nodos. Huffman, utiliza una lista de símbolos ordenada por frecuencia para crear códigos sin construir un árbol de Huffman. Huffman, combina los símbolos más frecuentes primero para construir el árbol de códigos desde la raíz hasta las hojas.