Algoritmos y Estructuras de Datos Parcial 2 Siglo 21
Material de estudio importado para Algoritmos y Estructuras de Datos II
Temario y Contenido
Este parcial contiene 180 preguntas de opción múltiple y verdadero/falso. A continuación tienes un vistazo de los temas evaluados:
A través de los árboles AVL se logra un procedimiento de búsqueda análogo al de los ABB, garantizando que el peor caso sea:
Al insertar un nodo en un árbol rojinegro, este se inserta como una hoja roja. Si su padre es negro, entonces...
Si al insertar una hoja roja en un árbol rojinegro, su padre también es rojo, ¿qué regla fundamental se estaría incumpliendo?
En la inserción de un árbol rojinegro, el 'caso 5' se produce cuando el nuevo nodo tiene un padre ROJO y un tío NEGRO. La solución implica:
¿Cómo se define la Altura de un árbol AVL? (Seleccione 2 respuestas correctas)
¿Cuáles son los casos principales a considerar al insertar en un Árbol Rojinegro (ARN) cuando se viola la regla 'padre-hijo rojos'? (Seleccione 3 respuestas correctas)
¿Cuál de estas es una afirmación correcta sobre la codificación de Huffman?
¿Cuál es la principal diferencia estructural entre los árboles AA y los árboles rojinegros?
¿Cuál de las siguientes supuestas 'reglas' de los árboles rojinegros es en realidad FALSA?
¿Cuáles de estas afirmaciones sobre compresión de datos son correctas? (Seleccione 3 respuestas correctas)
Al comprimir con Huffman, el flujo de bits resultante no siempre ocupa un número exacto de bytes. ¿Qué se hace convencionalmente con el último byte si queda incompleto?
Al descomprimir con Huffman, ¿por qué es crucial conocer la cantidad de datos originales o el número de bits válidos en el último byte?
Al leer un archivo en la mayoría de los lenguajes de programación, la condición estándar para detectar que se ha llegado al final es:
Un árbol binario donde, para cualquier nodo, todos los valores en su subárbol izquierdo son menores y todos los del subárbol derecho son mayores, es un:
Se dice que un árbol M-ario es completo si cumple que:
En teoría de la información y compresión, ¿cuáles de estas definiciones son correctas? (Seleccione 4 respuestas correctas)
El acceso a un archivo leyendo sus registros en el orden físico en que están almacenados se denomina:
El acceso a cualquier registro de un archivo directamente, sin necesidad de leer los anteriores, se denomina:
El algoritmo de eliminación en los árboles AA es relativamente directo porque su estructura asegura que:
El algoritmo de Huffman, en su fase de construcción, se caracteriza por:
El algoritmo de Huffman consiste en crear una lista de árboles de un solo nodo (uno por símbolo) para luego:
El algoritmo de ordenamiento por mapa de bits (Bitmapping) funciona al pensar en una porción de memoria como:
El algoritmo de Shannon-Fano se caracteriza por ser un método de codificación en el que:
La estrategia principal del algoritmo de Shannon-Fano es:
Respecto al algoritmo para encontrar anagramas computando una 'firma' para cada palabra, ¿cuál afirmación es VERDADERA?
El algoritmo para mantener un árbol AVL equilibrado se basa fundamentalmente en:
En ordenamiento externo, el algoritmo que busca reducir el número de pasadas sobre los datos utilizando más de dos archivos auxiliares es:
El algoritmo de compresión RLE (Run-Length Encoding) se caracteriza por:
El árbol Adelson-Velskii-Landis (AVL) se caracteriza por ser:
El borrado en un árbol BST de un nodo con 2 hijos:
Al borrar un nodo con un solo hijo en un árbol BST, el procedimiento correcto es:
El borrado de un nodo sin hijos (una hoja) en un árbol BST consiste en:
El concepto de 'árbol equilibrado' (según la definición de AVL) es:
El concepto de 'árbol perfectamente equilibrado' es:
El concepto principal de un BST (Árbol Binario de Búsqueda) es:
El coste (complejidad temporal) de una operación en un árbol BST es proporcional a:
El equilibrio de un árbol AVL se mantiene:
El Factor de Equilibrio (FE) de un nodo en un árbol AVL se calcula como Altura(subárbol izq) - Altura(subárbol der). Si su valor es 1, significa que:
El método de ordenamiento externo que se caracteriza por incrementar el número de archivos auxiliares para mejorar la eficiencia es:
El marcador EOF de un archivo... (Seleccione 4 respuestas correctas)
El método de compresión de datos basado en un diccionario que reemplaza cadenas de datos recurrentes por una referencia se conoce como:
El método de ordenamiento externo 'fusión natural' se diferencia del de 'mezcla directa' principalmente en:
El método de ordenamiento externo 'mezcla directa', para un archivo de N registros, tiene una complejidad total de movimientos de:
El algoritmo de 'Mezcla directa' se repite hasta que:
En el método de ordenación externa 'mezcla directa', en el paso (o pasada) 'i', se obtienen secuencias ordenadas de longitud:
El método de ordenación 'fusión natural' se caracteriza porque en cada pasada:
El método de ordenamiento externo que aprovecha las 'carreras' o secuencias ya ordenadas de máxima longitud en los datos se llama:
El método de ordenamiento externo que utiliza 'm' archivos, donde 'm-1' son de entrada y 1 de salida en cada paso, es:
El método de ordenamiento por Mezcla Natural... (Seleccione 2 respuestas correctas)
Una mejora al algoritmo de Huffman, que evita la primera pasada para contar frecuencias construyendo el árbol dinámicamente, se llama:
El 'nivel' de un nodo en un árbol AA se define como:
El número mínimo de nodos de un árbol AVL de altura 'h' es:
El ordenamiento externo... (Seleccione 4 respuestas correctas)
El peor caso de complejidad de búsqueda, inserción o borrado en un árbol BST no balanceado es:
El principal objetivo de los algoritmos de ordenamiento externo es:
En un árbol BST, el borrado de un nodo con 2 hijos se soluciona reemplazando su valor por el de su predecesor o sucesor in-orden, y luego:
En árboles AVL, el Factor de Equilibrio (FE) se define como:
En el algoritmo de búsqueda de anagramas basado en 'firmas'... (Seleccione 4 respuestas correctas)
En el algoritmo de Huffman, para descomprimir un archivo, además del flujo de bits comprimido, ¿qué otra información es indispensable?
En el árbol generado por el algoritmo de Huffman, la información (los símbolos originales) se encuentra:
En el algoritmo de Huffman, los códigos binarios para cada símbolo se leen:
En el ámbito de la teoría de la información, la entropía de Shannon mide:
En el método polifásico, en el momento en que un archivo de entrada se agota, este pasa a ser el nuevo archivo de salida. ¿Verdadero o Falso?
En el tratamiento de archivos, si los registros son de tamaño variable, la forma más práctica de procesarlos es:
En el tratamiento de archivos, si quiero recuperar un registro específico y los registros son de tamaño fijo, el método más eficiente es:
En estructuras de datos, a una colección de datos relacionados y guardados en un dispositivo de almacenamiento permanente se la conoce como:
En la eliminación de un nodo en un árbol AA, la operación se simplifica porque el caso de un nodo con un único hijo solo puede darse en:
En los casos de borrado en un árbol rojo-negro, ¿cuáles de las siguientes situaciones se analizan para el reequilibrio? (Seleccione 4 respuestas correctas)
En los árboles AA, si una inserción provoca la aparición de dos enlaces horizontales derechos consecutivos (un 'abuelo' y un 'padre' rojos), ¿qué operación se realiza?
En los árboles AA, la operación 'Giro' (skew) consiste en:
En los árboles AA, un enlace horizontal representa:
En los árboles autobalanceados, son válidas estas definiciones de equilibrio: (Seleccione 2 respuestas correctas)
En los árboles rojinegros, cuando eliminamos un nodo negro que es reemplazado por un hijo también negro, el problema se maneja tratando al hijo como:
En los árboles rojinegros, al eliminar un nodo negro sin hijos:
En los árboles rojinegros, si eliminamos un nodo rojo (que por definición debe ser una hoja):
Las reglas de los árboles rojinegros garantizan que el camino más largo desde la raíz hasta una hoja es, como máximo:
En los árboles rojinegros, el algoritmo de borrado está diseñado para borrar directamente:
Seleccione 3 propiedades fundamentales de los árboles rojinegros:
En la teoría de los árboles rojinegros, las hojas (NIL):
Sobre los archivos secuenciales, ¿qué afirmaciones son correctas? (Seleccione 4)
Sobre los archivos de acceso aleatorio (directo), ¿qué afirmaciones son correctas? (Seleccione 3)
¿En qué consiste el proceso de compresión de datos?
En un árbol AVL, después de un borrado, se aplica una Rotación Doble a Derecha (RDD) si el nodo desequilibrado tiene un FE de +2 y...
En un árbol AVL, después de una inserción, se aplica una Rotación Doble a Izquierda (RDI) si el nodo desequilibrado tiene un FE de -2 y...
En un árbol AVL, por convención, el Factor de Equilibrio (FE) de un nodo se calcula como:
En un árbol B... (Seleccione 4 respuestas correctas)
En un árbol B de orden M... (Seleccione 4 respuestas correctas)
En un árbol B M-ario, los nodos internos contienen:
En un árbol de búsqueda M-ario, ¿cuántas claves se necesitan en un nodo para decidir entre M posibles ramas (hijos)?
En un árbol rojinegro, cuando se elimina un nodo negro con un solo hijo (que debe ser rojo y tener dos hojas NIL negras), el procedimiento implica:
En una rotación doble a derecha (RDD) sobre un nodo P desequilibrado (fe=+2), su hijo izquierdo Q (fe=-1) y el hijo derecho de Q llamado R...
En una rotación simple a la derecha, la raíz del subárbol original se convierte en:
En una rotación simple a la izquierda, la raíz del subárbol original se convierte en:
En una rotación simple de un árbol AVL, ¿qué se intercambia?
El método más simple de ordenamiento externo es:
¿Es posible buscar eficientemente el k-ésimo menor elemento en un árbol BST?
Este método de ordenamiento externo mejora el tiempo de ejecución de la mezcla directa al aprovechar las secuencias ya ordenadas en los datos:
Los algoritmos que funcionan manteniendo un conjunto de posibles soluciones que compiten y se combinan entre sí, de forma que las más aptas prevalecen, son los:
Indique qué afirmación sobre la construcción del árbol de Huffman es correcta:
La característica única llamada división 'dos a tres' (2-3 split), que mejora la utilización de espacio, es una ventaja de:
La codificación de Huffman es un método en el que se asignan códigos binarios:
Una de las afirmaciones correctas sobre la compresión de datos es que:
La compresión de Huffman consiste en:
La compresión es un caso particular de:
La compresión RLE (Run-length encoding) es un método en el que:
La condición de equilibrio de un árbol AVL implica que tendrá una profundidad:
La definición 'uso de una tabla de códigos de longitud variable para codificar un símbolo, basada en la probabilidad de aparición de cada símbolo' pertenece a:
La definición 'forma simple de compresión donde secuencias de datos con el mismo valor consecutivas son almacenadas como un único valor más su recuento' pertenece a:
La definición 'los símbolos se ordenan por probabilidad y se dividen en 2 conjuntos cuya suma de probabilidades sean tan iguales como sea posible' pertenece a:
La descompresión por medio del algoritmo de Huffman es imposible sin:
La descompresión por medio del algoritmo de Huffman implica la reconstrucción del archivo original:
La diferencia fundamental entre la codificación de Shannon-Fano y la de Huffman radica en:
La estructura de datos tipo árbol mejor preparada para almacenar grandes volúmenes de datos en disco es:
La inserción en un árbol AA se realiza siempre:
La inserción en un árbol BST consiste en:
La altura en el peor caso de un árbol AVL de n nodos nunca excede en más de un 44% a la del árbol binario de búsqueda perfectamente balanceado. Este valor proviene del análisis de su relación con:
La mejor forma de buscar anagramas en un diccionario es:
La mezcla de 2 archivos por intercalación (merge) presupone que:
La rotación doble en un árbol AVL es conceptualmente:
La rotación simple en un árbol es una operación de cambio de estructura donde:
La rutina 'reverse' aplicada a un sub-vector es útil para:
La solución óptima para rotar (shift circular) un vector 'k' posiciones es:
La solución de ordenamiento que hace una sola lectura del archivo de entrada, utilizando un bit por cada posible elemento, se llama:
La técnica de bitmaping consta de 3 fases: 1) Inicializar el vector de bits a cero; 2) Leer cada elemento y poner a 1 el bit correspondiente; 3)...
La técnica de bitmaping es especialmente útil para:
La técnica de computar las 'firmas' de las palabras es un método eficaz para:
Las 2 operaciones básicas para mantener el equilibrio en los árboles AA son:
Las iteraciones en la fase de construcción del árbol de Huffman terminan cuando:
Las operaciones de reequilibrado de un árbol AVL consisten en:
Las reglas de los árboles rojinegros garantizan que:
Los algoritmos evolutivos, que se basan en postulados de la evolución biológica (selección, cruce, mutación) para encontrar soluciones a problemas, son:
Los árboles AA se diferencian de los árboles rojinegros en que:
Los árboles AA... (Seleccione 4 respuestas correctas)
Los árboles B satisfacen 5 propiedades fundamentales, entre las que se incluye:
Se considera que los árboles rojinegros son más eficientes en la práctica (que los AVL) porque:
¿Es cierto que los archivos de acceso aleatorio consisten en registros que se pueden acceder en cualquier secuencia, pero que deben ser de tamaño fijo?
Los archivos pueden ser abiertos en diferentes modos, como:
Los casos de borrado en un árbol ARN se simplifican manejando la eliminación de:
Los métodos de compresión con pérdida, que eliminan información no perceptible, son también llamados:
Los métodos de ordenamiento interno tienen un rendimiento más alto que los externos porque:
El proceso de segmentación, extracción de características y descripción, donde cada objeto queda representado por descriptores, se refiere a:
Los siguientes son métodos de ordenamiento externo: (Seleccione 4 respuestas correctas)
Los dos tipos fundamentales de manejo o acceso a archivos son: (Seleccione 2 respuestas correctas)
Los valores aceptables del Factor de Equilibrio en un nodo de un árbol AVL son:
¿Por qué el tiempo de acceso a los archivos puede ser un factor crítico en el ordenamiento externo?
¿Por qué en los árboles AA podemos decir que los enlaces horizontales son equivalentes a enlaces 'rojos' de lado derecho?
Si al realizar una inserción en un árbol B+, el nodo hoja está lleno, ¿qué acción debe tomarse?
¿Qué es la compresión de datos?
La estructura que dio origen a los árboles Rojinegros fue creada por Rudolf Bayer en 1972 y se llamaba 'árboles-B binarios simétricos'. ¿Qué atributos y conceptos introdujeron Guibas y Sedgewick? (Seleccione 3)
Se denomina algoritmo de compresión sin pérdida (lossless) a cualquier procedimiento de codificación que:
Según el método de inserción ascendente para los árboles rojinegros, el nuevo elemento siempre debe insertarse como:
Según el teorema de la altura de los árboles AVL, la altura en el peor caso es aproximadamente un 44% mayor que la mínima posible. Esto significa que un AVL es:
Según las propiedades de inserción en árboles rojinegros, una vez que se encuentra el punto de inserción, el nuevo elemento:
Según los árboles AA, la conexión entre un nodo y un hijo suyo del mismo nivel se define como:
Según las reglas de los árboles rojinegros, si un nodo es rojo, se debe cumplir que:
Según los métodos de Ordenamiento Externo, podemos decir que el método de mezcla directa es:
En los árboles AA, en lugar de almacenar explícitamente la información sobre el color, cada nodo almacena:
Si codificamos un algoritmo de compresión construyendo un árbol de la raíz hacia las hojas, dividiendo probabilidades, estamos hablando de:
Si codificamos un algoritmo de compresión construyendo un árbol de las hojas hacia la raíz, fusionando los nodos de menor probabilidad, estamos hablando de:
Si poseemos un árbol rojinegro con una raíz negra y un único hijo rojo, y deseamos borrar la raíz, el resultado será:
Si se tiene el desafío de ordenar archivos de gran tamaño con memoria muy limitada, una técnica de ordenamiento externo efectiva es:
Respecto a los archivos secuenciales en disco... (Seleccione 4 respuestas correctas)
Técnicamente, ¿cómo se llama al proceso de codificar información usando menos bits que una representación sin codificar?
Teniendo en cuenta las propiedades de los árboles AA, en un enlace horizontal se debe cumplir que:
Un árbol-B se mantiene balanceado porque una de sus propiedades fundamentales es que:
Un árbol B de grado M... (Seleccione 4 respuestas correctas)
Un árbol BST se diferencia de un árbol binario común en que:
Un árbol BST, al estar ordenado, facilita la búsqueda de un elemento. Esta se realiza:
Un árbol BST, al estar ordenado, facilita la búsqueda del elemento mayor, que se realiza:
Un árbol BST, al estar ordenado, facilita la búsqueda del elemento menor, que se realiza:
Un árbol BST (Árbol Binario de Búsqueda) es... (Seleccione 4 respuestas correctas)
Una 'cadena de bloques' (Blockchain), aplicada por primera vez en Bitcoin, provee de forma descentralizada: (Seleccione 3 respuestas correctas)
Una característica fundamental de los ARN es que cada camino desde un nodo a cualquiera de sus hojas descendientes:
Una de las propiedades inviolables de los árboles rojinegros es que la raíz:
Una de las propiedades de los árboles rojinegros dice que si un nodo es rojo, sus hijos:
Una de las siguientes afirmaciones corresponde a una propiedad principal de los árboles B. ¿Cuál es?
Una de las técnicas utilizadas en el proceso de compresión con pérdida (lossy) es:
Una estructura de árbol que es un índice multinivel, dinámico, donde toda la información se guarda en las hojas y estas se encuentran unidas como una lista enlazada es un:
Uno de los campos de aplicación donde es crucial utilizar un algoritmo de compresión SIN pérdida es:
En un árbol AVL, una rotación simple (como RSD) sirve para tratar los casos de desequilibrio donde la inserción ocurrió en: