segundo parcial edp 5

¿Puede una expresión aritmética o lógica representase por un árbol binario?. Los operadores y los operandos se distribuyen en los nodos hoja, los nodos internos sirven de discriminadores. Los nodos internos serían operandos y los nodos hoja operadores. Los nodos internos serían operadores y los nodos hoja operandos. Lo operadores y los operandos se distribuyen entre los nodos internos y los nodos hoja.

Se define árbol compacto como: Aquel en el que no se permite la existencia de subárboles vacíos que sean hermanos por la derecha de subárboles no vacíos. Aquel en el que todos los nodos son de grado cero o dos. Aquel en el que no se permite la existencia de subárboles vacíos que sean hermanos por la izquierda de subárboles no vacíos. Aquel en el que se permite la existencia de subárboles vacíos que sean hermanos por la izquierda de subárboles no vacíos.

Respecto de los recorridos en un contenedor ¿qué respuesta considera verdadera?. En una estructura lineal no se puede hacer según su ordenación natural de primero a último. en un árbol se hace según la relación predecesor/sucesor que se establece entre parejas de nodos, por lo que solo hay una línea posible de recorrido. En una estructura lineal se hace según la relación predecesor/(sucesor derecho, sucesor izquierdo), por lo que hay más de una línea posible de recorrido. En un árbol se hace según la relación padre/hijo pero un padre puede tener varios hijos, por lo que se multiplican las posibilidades de recorrido.

El árbol que se muestra en las figuras no es un árbol AVL por tener un nodo con factor de equilibrio no permitido ¿qué figura muestra marcado con x el nodo desequilibrado. A. B. C. D.

¿Con qué objetivo tiene que cumplir un árbol B?. Con realizar inserciones y extracciones con el menor número de accesos a disco con independencia del cualquier sobrecosto en búsquedas. Con realizar búsquedas con el menor número de accesos a disco, con independencia de cualquier sobrecosto en inserciones y extracciones. Con realizar inserciones, extracciones y búsquedas con la menor ocupación de memoria interna. Con realizar inserciones, extracciones y búsquedas con el menor número de accesos a disco.

En un árbol B, cuando el valor de clave se inserta en un nodo hoja y se produce una sobrecarga que se resuelve con una Partición-­‐1/2, ¿a qué altura del árbol B se detendrá la propagación de la sobrecarga si se continúan resolviendo con particiones-­‐1/2?. A la altura de un nodo ancestro que tenga menos de m-­1 valores de clave. Ninguna de las otras respuestas es verdadera. Siempre a la altura de la raíz. Siempre a la altura de los nodos hojas.

En un árbol B, ¿qué ventaja consigue el uso de las rotaciones durante la inserción?. Que aumente la altura del árbol B. Que disminuya el número de claves por nodo. Que el árbol B no se desequilibre. Que la altura del árbol B crezca más despacio.

En un árbol B+, ¿cuándo finaliza el proceso de búsqueda?. Cuando se acceda al nodo primero o último de la lista doblemente encadenada. Apenas se encuentra el valor de clave en el árbol B. Cuando se procese el correspondiente nodo hoja. Cuando se acceda a un nodo terminal del árbol B.

¿Dónde figuran los nodos terminales del árbol B en un árbol B+?. No guardan relación alguna con la lista doblemente encadenada. Un nivel por encima de la lista doblemente encadenada. Se van entremezclando en altura con los nodos de la lista doblemente encadenada. En el ramal derecho del árbol B+.

En un árbol AVL, el antecesor más cercano con factor de equilibro +2 ó -­2 después de la inserción es: El antecesor más cercano con factor de equilibrio 0 antes de la inserción. El antecesor más cercano con factor de equilibrio ‐2 ó +2 antes de la inserción. Ninguna de las otras respuestas es verdadera. El antecesor más cercano con factor de equilibrio +1 ó ­‐1 antes de la inserción.

Respecto de los árboles ¿qué respuesta considera correcta?. Árbol n-ario es aquel que el grado máximo de sus nodos es n. Árbol general es aquel en el que el grado máximo de sus nodos es dos. Ärbol n-ario es aquel en el que no se considera ninguna limitación en el grado máximo de sus nodos. Árbol n-ario es aquel en el que el grado máximo de sus nodos es dos.

Si en un árbol AVL antes de la extracción y después de la rotación correspondiente la altura del subárbol disminuye, ¿hasta dónde se propagan las rotaciones?. Nunca se producirán propagaciones. Hasta que su ascendiente no quede desequilibrado. Necesariamente hasta la raíz. Hasta que cubra por completo el árbol.

Si T es un árbol binario no vacío con subárboles izquierdo Ti y derecho Td, T es AVL si y sólo si: Ninguna de las otras respuestas es verdadera.. Ti y Td son AVL y H(Ti) ‐ H(Td) = ­‐1, 0, +1. Ti y Td son AVL. H(Ti) ‐ H(Td) = -­1, 0, +1.

En una rotación hacia la derecha entre nodos de un árbol B durante la extracción, ¿qué claves del hermano del nodo bajo mínimo fluyen hacia el nodo bajo mínimo?. Un conjunto de claves más a la izquierda y otro más a la derecha. Las que estén más a la izquierda. Las que estén más a la derecha. Las claves centrales.

En un árbol B+, durante la recuperación en rango, ¿cómo se procede?. Si se busca el mínimo valor del rango, se avanza por el enlace apropiado hasta alcanzar el nodo de la lista doblemente encadenada que contenga el valor máximo del rango o lo supere. Si se busca el mínimo valor del rango, se retrocede por el enlace apropiado hasta alcanzar el nodo de la lista doblemente encadenada que contenga el valor máximo del rango o lo supere. Si se busca el mínimo valor del rango del rango, se avanza por el enlace apropiado hasta alcanzar el nodo de la lista doblemente encadenada que contenga el valor mínimo y si no lo contiene proporciona un mensaje de error. Ninguna de las otras respuestas es verdadera.

Frente a inserciones y extracciones, ¿por qué se prefieren las propiedades del árbol B a las del multirrama óptimo?. Por razones de facilidad de programación. Ninguna de las otras respuestas es verdadera. Porque son más elegantes. Porque son más fáciles de mantener.

¿Cómo se define un árbol B?. Un árbol multirrama, perfectamente equilibrado en altura y que crece hacia arriba. Un árbol multirrama que crece hacia arriba, pero que no tiene por qué cumplir con un equilibrado perfecto en altura. Un árbol multirrama, perfectamente equilibrado en altura y crece hacia abajo. Un árbol binario de búsqueda, perfectamente equilibrado en altura y que crece hacia abajo.

En un árbol B+, si después de la extracción, el nodo se encuentra bajo mínimo y no es posible realizar rotación alguna, ¿qué operación se requiere?. Una recombinación. Una Partición-­‐1/2. Una Partición-­-2/3. Ninguna de las otras respuestas es verdadera.

En un árbol B+, si después de una extracción, el nodo se encuentra bajo mínimo, ¿qué condiciones se requieren para realizar una Recombinación-­-2/1+ con su hermano inmediato izquierdo?. Ninguna de las otras respuestas es verdadera. Que no tenga hermano inmediato derecho y que su hermano inmediato izquierdo tenga un número de claves igual al mínimo. Que tenga ambos hermanos inmediatos con un número de claves igual al mínimo. Que no tenga hermano inmediato derecho y que su hermano inmediato izquierdo se encuentre lleno.

En un árbol B+, si durante la búsqueda se accede a un nodo no hoja que no contiene el valor de clave buscado, ¿cómo se procede?. Como en el árbol B. Siempre se elije el ramal más a la derecha. Se toma un camino alternativo que se decide según el número de valores de clave de ese nodo. Siempre se elije el ramal más a la izquierda.

En un árbol B, cuando durante la inserción se produce propagación que se resuelve con Partición-­‐2/3 sin poder hacer ninguna rotación,¿con cuántos accesos a disco hay que contar si no se sobrecarga la raíz?. Con el valor de la altura del árbol B más el número de nodos que se subdividen. Con el número de nodos que se subdividen. Con el doble de la altura del árbol B. Con el valor de la altura del árbol B más el quíntuplo del número de nodos que se subdividen más uno para la actualización del ancestro que no se sobrecarga.

¿Con qué objetivo se introduce el árbol B+?. Aprovechar la eficiencia discriminante del árbol B y la facilidad de la iteración secuencial de las listas doblemente encadenadas. Aprovechar la eficiencia discriminante del árbol B y la facilidad de la iteración jerárquica de los árboles de búsqueda binarios. Aumentar la eficiencia del árbol B con el apoyo de otro árbol B invertido. Reducir la altura de un árbol B gracias a las listas doblemente encadenadas.

¿Por qué interesa un árbol binario equivalente a uno no binario?. Porque se reduce el número de nodos a tratar. Porque suele resultar más fácil implementar un árbol binario que uno no binario. Porque la altura del árbol binario siempre resulta menor que la del no binario. Por paliar la posibilidad de que el no binario degenere en una lista lineal.

En un árbol B, ¿qué respuesta considera verdadera?. El número de nodos de un árbol B puede ser mayor que el del mejor árbol de búsqueda multirrama posible para ese orden. Ninguna de las otras respuestas es verdadera. Nunca el número de nodos de un árbol B puede ser mayor que el del mejor árbol de búsqueda multirrama posible para ese orden.

¿Antes de la extracción y después de qué tipos de rotaciones en un árbol AVL la altura del subárbol se mantiene invariante?. En un caso de rotación simple y en uno de la doble. Ninguna de las otras respuestas es verdadera. En dos casos de la rotación simple. En todos los casos de la rotación doble.

Indicar cuál de las siguientes afirmaciones es cierta cuando el número de elementos es muy elevado: I. El coste promedio de la búsqueda en un árbol binario de búsqueda es siempre mejor que en una lista encadenada. II. El coste promedio de la búsqueda en un árbol AVL es siempre mejor que en una lista encadenada. I: sí, II: sí. I: no, II: sí. I: sí, II: no. I: no, II: no.

En las rotaciones simples tras una inserción en un árbol AVL: La altura del subárbol antes de la inserción y después del reequilibrado es la misma. Se necesita examinar el resto del árbol. La altura del subárbol antes de la inserción es menor que la altura del subárbol después del reequilibrado. Después del reequilibrado, los factores de equilibrio de los nodos crítico y discriminante son distintos de 0.

Cuando en un árbol AVL se quiere eliminar un nodo con sus dos enlaces no nulos, ¿qué se ha de hacer?. Sustituir el nodo a extraer por su sucesor o predecesor en orden simétrico ya que tiene ambos hijos a nulo. Sustituir el nodo a extraer por su hijo derecho o izquierdo con independencia de a cuántos nulos apunte. Sustituir el nodo a extraer por su sucesor o predecesor en orden simétrico ya que tiene un hijo nulo. Sustituir el nodo a extraer por su sucesor o predecesor en preorden ya que tiene un hijo nulo.

En un árbol multirrama 2­‐3-­4, una vez localizado el nodo hoja donde insertar el valor, ¿qué respuesta considera verdadera?. Se rechaza la inserción. Siempre se realiza una partición. Si es un 2-­nodo o un 3-­nodo, se inserta directamente. Siempre se añade a un 2-­nodo que se convierte en un 3-­nodo.

En un árbol B+, si después de una extracción, el nodo está bajo mínimo, ¿qué se ha de hacer para realizar una Recombinación-­‐2/1+ con su hermano inmediato izquierdo?. Ninguna de las otras respuestas es verdadera. Se sitúan en el nodo las claves y los enlaces de él y de su hermano inmediato izquierdo, se extrae del padre la clave que los separaba. Se sitúan en el nodo las claves y los enlaces de él y de su hermano inmediato izquierdo, se deja en el padre la clave que los separaba. Se amplía su hermano inmediato izquierdo con las claves del nodo.