segundo parcial edp 2

En un árbol B, si después de la extracción, el nodo se encuentra bajo mínimo y sus hermanos inmediatos izquierdo y derecho se hallan al mínimo, ¿cómo opera una Recombinación-­‐3/2?. Ninguna de las otras respuestas es verdadera. Se dejan en sus hermanos inmediatos izquierdo y derecho sus valores de clave y enlaces; se reparten entre ellos los valores de clave y enlaces del nodo bajo mínimo, se dejan en el padre las dos claves que aparecen entre los enlaces de los hermanos inmediato izquierdo y derecho. Se dejan en sus hermanos inmediatos izquierdo y derecho sus valores de clave y enlaces; todos los valores de clave y enlaces del nodo bajo mínimo suben al padre. Se dejan en sus hermanos inmediatos izquierdo y derecho sus valores de clave y enlaces; se reparten entre ellos los valores de clave y enlaces del nodo bajo mínimo, se bajan del padre las dos claves que aparecían entre los enlaces de los hermanos inmediato izquierdo y derecho, se sube al padre el valor de clave central de los tres nodos.

En un árbol B, cuando el valor de clave se inserta en un nodo hoja, se produce una sobrecarga sin propagación que se resuelve con una Partición--2/3, ¿cuántos accesos se han de contar?. Tantos como el valor de la altura del árbol B. Tantos como el valor de la altura del árbol B más dos accesos para comprobar que no es posible hacer la rotación, más tres de la partición más uno para la actualización del padre. Ninguna de las otras respuestas es verdadera. Tantos como el valor de la altura del árbol B más dos accesos para comprobar que no es posible hacer la rotación, más dos de la partición.

Sea N el nodo raíz de un subárbol AVL, tal que antes de una inserción su factor de equilibrio es ‐1, y sea Ni su hijo izquierdo. Se inserta un elemento en el subárbol izquierdo de Ni. Antes de la inserción el factor de equilibrio de Ni es ­‐1. Entonces: Es necesario un reequilibrado en Ni. Es necesario reequilibrar en N. El nodo crítico a considerar es N y no Ni. Ninguna de las otras respuestas es verdadera.

En el árbol AVL de la figura tras la inserción de JUNIO, ¿qué rotación se ha realizado para reestablecer el equilibrio?. Simple D. Doble DI. Simple I. Doble ID.

En un árbol multirrama, si dentro de un nodo no se encuentra el valor de clave buscado,¿qué se hace?. Se emite un mensaje de búsqueda infructuosa. Se desciende por el subárbol cuya raíz viene dada por el primer enlace. Ninguna de las otras respuestas es verdadera. Se desciende por el subárbol adecuado a la clave que se busca.

¿Qué rotaciones son posibles tras una inserción en un árbol AVL?. I, D, ID, DI. I, D, II, DD. I, D. I, D, ID, II, DI, DD.

Si para resolver la sobrecarga en un nodo de un árbol B durante la inserción no es posible realizar una rotación hacia la derecha ni una rotación hacia la izquierda con su hermano correspondiente, ¿qué operación sería conveniente llevar adelante?. Una partición. Una recombinación. Una extracción. Una rotación con su padre.

En el peor caso, los cálculos del número de accesos durante la inserción en un árbol B: En ningún caso superan el valor de la altura del árbol B. Son independientes de si intervienen o no las rotaciones. Son peores cuando intervienen las rotaciones que cuando no aparecen. Son mejores cuando intervienen las rotaciones que cuando no aparecen.

En un árbol binario equivalente a uno no binario ¿qué respuesta considera verdadera?. A cada nodo del árbol no binario le corresponde un nodo del binario pero no a la inversa. El hijo izquierdo de un nodo de un árbol binario corresponde con el primer hijo del nodo equivalente del árbol no binario. El hijo derecho de un nodo de un árbol binario corresponde con el último hermano por la derecha del nodo equivalente del árbol no binario. A cada nodo del árbol binario le corresponde un nodo del no binario pero no a la inversa.

¿En cuántos pasos se resuelve una extracción en un árbol AVL?. En O(n2) pasos. En O(n) pasos. En O(log2n) pasos. En O(nlog2n)pasos.

Respecto de la propagación de la sobrecarga al nivel superior durante la inserción en un árbol B, ¿qué respuesta considera verdadera?. Ninguna de las otras respuestas es verdadera. La evitan tanto la Partición-­‐1/2 como la Partición-­‐2/3. No la evitan ni la Partición-­‐1/2 ni la Partición-­‐2/3. La Partición-­‐1/2 no la evita, mientras que la Partiición-­‐2/3 sí la evita.

Respecto de los árboles ¿qué respuesta considera verdadera?. La altura de un árbol es la de su nodo hoja más alto. La altura de un nodo se define uno más la longitud del camino más largo desde ese nodo a una hoja. La altura de un árbol es la de su nodo hoja más bajo. La altura de un nodo se define como la longitud del camino más corto desde ese nodo a una hoja.

Tras la inserción en un árbol B, ¿con qué propósito se usan las rotaciones?. Para hacer crecer la altura del árbol. Para disminuir la ocupación promedio de los nodos. Para reducir la frecuencia de partición de los nodos sobrecargados. Ninguna de las otras respuestas es verdadera.

En la Partición-­‐2/3 durante la inserción en un árbol B: Se parte un nodo en tres. Se parten dos nodos en tres. Se parten tres nodos en dos. Se parten tres nodos en tres.

Respecto a la evitación de la degeneración de un árbol binario de búsqueda, ¿cuál de las siguientes respuestas considera verdadera?. La reestructuración completa de un árbol binario de búsqueda requiere excesivas reorganizaciones. Las reorganizaciones en un árbol AVL afectan a todo el árbol. Las reorganizaciones necesarias para la reestructuración completa de un árbol binario de búsqueda pueden mantenerse bajo contro. Las operaciones de mantenimiento en un árbol AVL son O(n).

Durante la inserción en un árbol B, ¿en qué difieren la Partición-­‐1/2 y la Partición-­‐2/3?. La Partición-­‐2/3 deja sus tres nodos más llenos que los dos nodos de la Partición-­‐1/2. La Partición-­‐2/3 deja sus dos nodos más llenos que los dos nodos de la Partición-­‐1/2. La Partición-­‐2/3 deja sus tres nodos más vacíos que los dos nodos de la Partición-­‐1/2. La Partición-­‐2/3 deja sus dos nodos más vacíos que los dos nodos de la Partición-­‐1/2.

En un árbol multirrama, cada nodo del camino de búsqueda y su posición de descenso o de localización se almacenan en una: Cola. Semipila. Pila. Semicola.

En el árbol multirrama, ¿qué respuesta considera verdadera?. Cada acceso recupera una página con varios valores de clave. Cada acceso recupera una página con un sólo valor de clave. Cada acceso recupera varias páginas con varios valores de clave.

Determinar cuál de las siguientes afirmaciones es cierta en relación con los árboles AVL: I. La inserción de un nodo puede producir como máximo una rotación, simple o doble. II. La extracción de un nodo puede producir como máximo una rotación, simple o doble. I: sí, II: sí. I: sí, II: no. I: no, II: sí. I: no, II: no.

En un árbol B+, si después de una extracción, el nodo está bajo mínimo, ¿qué se ha de hacer con sus hermanos inmediatos para realizar una Recombinación-­-3/2+?. Ninguna de las otras respuestas es verdadera. Se hace fluir hacia el hermano inmediato izquierdo y derecho los valores de clave y los enlaces del nodo que quedó bajo mínimo. Se hace fluir hacia el nodo que quedó bajo mínimo los valores de clave y los enlaces de sus hermanos inmediatos izquierdo y derecho. Se hace fluir hacia el hermano inmediato izquierdo los valores de clave y los enlaces del nodo que quedó bajo mínimo y los del hermano inmediato derecho.

En un árbol B+, ¿qué se guarda en la lista doblemente encadenada?. Ninguna de las otras respuestas es verdadera. Un valor de clave junto a la información asociada o, más habitualmente, la dirección para acceder al registro donde se encuentre. Sólo una dirección para acceder a un registro. Sólo un valor de clave, porque la dirección para acceder a un registro se almacena en su correspondiente lugar en los nodos del árbol B.

En un árbol AVL, el factor de equilibrio del nodo crítico: Antes de la inserción es -­1 ó +1 y después es ‐2 ó +2. Antes de la inserción es 0 y después es ­‐1 ó +1. Antes de la inserción es ‐2 ó +2 y después es ‐1 ó +1. Antes de la inserción es -­1 ó +1 y después es 0.

En un árbol multirrama de orden m, ¿qué respuesta considera verdadera?. Todos los nodos tienen m-1 valores de clave. Todos los nodos tienen m hijos. Cada nodo tiene como máximo m hijos y m-1 valores de clave. El número de valores de clave por nodo no está limitado.

En un árbol B+, si después de la extracción un nodo está bajo mínimo, ¿cuándo se realiza una rotación de derecha a izquierda?. Cuando su hermano inmediato derecho tiene más de redondeo superior de m/2 menos 1 valores de clave. Ninguna de las otras respuestas es verdadera. Cuando su hermano inmediato derecho se encuentra sobrecargado. Cuando su hermano inmediato derecho se encuentra bajo mínimo.

En las rotaciones dobles tras una inserción en un árbol AVL: Antes de la inserción el factor de equilibrio del nodo crítico es 0. Se necesita examinar el resto del árbol. La altura del subárbol antes de la inserción y después del reequilibrado es la misma. Antes de la inserción el factor de equilibrio del nodo discriminante es distinto de 0.

Respecto a las enumeraciones secuenciales para árboles binarios, para poder conocer la estructura exacta del árbol ¿qué respuesta considera verdadera?. No es necesario saber en qué orden se recorrió el árbol. Debe incluirse información adicional al orden de recorrido que se usó. Solo es necesario conocer el orden de recorrido que se usó. Solo es necesario saber en qué lugar se encuentra la raíz.

En un árbol multirrama 2‐3-­4, ¿qué respuesta considera verdadera?. Los nodos internos pueden tener enlaces nulos. Son árboles multirrama de orden 4 no equilibrados. Todo nodo tiene que contener tres valores de clave. Todos los caminos desde la raíz a las hojas tienen la misma longitud.

En un árbol B, si es necesario dividir el nodo raíz. Se crea una nueva raíz que contendrá siempre el primer valor de clave y dos direcciones -la de la antigua raíz y la del nuevo nodo. La altura del árbol no aumenta. Ninguna de las otras respuestas es verdadera. Se crea una nueva raíz que contendrá únicamente el valor de clave central y dos direcciones -la de la antigua raíz y la del nuevo nodo.

Cuando en la definición de árbol se dice que "... se distribuyen en una serie de subconjuntos disyuntos", ¿qué significa?. Que todo árbol garantiza un desorden implícito. Que todo árbol tiene un orden implícito. Que ningún árbol guarda orden alguno. Que el árbol es el mismo aunque se varíe el orden de sus hijos.

En una rotación entre nodos de un árbol B durante la inserción, ¿qué clave del padre fluye hacia el hermano no sobrecargado?. La clave siguiente o anterior a la que aparece entre los enlaces que referencian a los hijos implicados en la rotación. Siempre la clave más a la derecha. Siempre la clave más a la izquierda. La clave que aparece entre los enlaces que referencian a los hijos implicados en la rotación.