estructuras de datos y progamacion examen 2

Supóngase que se insertan un conjunto de elementos en un árbol B en un *0/1 determinado orden. Indicar cuál de las siguientes afirmaciones es cierta. I. La altura del árbol B que resulta es independiente del orden en que se han insertado los elementos. II. El número de nodos del árbol B que resulta es independiente del orden en que se han insertado los elementos. I: sí, II: sí. I: sí, II: no. I: no, II: sí. I: no, II: no.

Cuando la extracción en un árbol AVL provoca una disminución de altura 0/1 de la rama de donde se extrajo el nodo: Siempre existe una tipo de rotación que con una sola aplicación resuelve el desequilibrio. Ninguna de las otras respuestas es verdadera. Necesariamente, la disminución de altura y la consiguiente corrección de los factores de equilibrio y las posibles rotaciones se propagan desde el lugar donde se produce la extracción hasta llegar a la raíz. La disminución de altura y la consiguiente corrección de los factores de equilibrio y las posibles rotaciones se pueden propagar desde el lugar donde se produce la extracción hasta llegar a la raíz.

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.

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.

Al recorren en posorden el árbol, ¿en qué secuencia se tratan los nodos?. P,D,R,A,G,L,F,H,J. A,D,F,G,H,J,L,P,R. A,F,H,G,J,L,D,R,P. P,D,A,G,F,H,L,J,R.

En un árbol B, cuando durante la inserción se *0/1 produce propagación que se resuelve con Partición-‐1/2 ¿cuántos accesos se han de contar?. Tantos como el valor de la altura del árbol B más el número de nodos que se subdividen. Tantos como el número de nodos que se subdividen. Tantos como el doble de la altura del árbol B. Tantos como el valor de la altura del árbol B más el doble del número de nodos que se subdividen más uno.

En el árbol multirrama, ¿qué respuesta considera verdadera?. Sus nodos no pueden contener más de un valor de clave. Ningún nodo puede disponer de más de dos enlaces. Los enlaces son direcciones de memoria externa. Los enlaces son direcciones de memoria interna.

Al recorren en inorden el árbol, ¿en qué secuencia se tratan los nodos?. P,D,R,A,G,L,F,H,J. A,D,F,G,H,J,L,P,R. A,F,H,G,J,L,D,R,P. P,D,A,G,F,H,L,J,R.

Determinar cuál de las siguientes afirmaciones es cierta: I. Un árbol AVL es siempre más adecuado que un árbol binario de búsqueda. II. Un árbol binario de búsqueda que por construcción es perfectamente balanceado es el que presenta mejor coste computacional en la búsqueda. I: sí, II: sí. I: no, II: sí. I: sí, II: no. I: no, II: no.

En el árbol AVL de la figura, tras la inserción de SEPTIEMBRE ¿qué rotación se debe realizar para restablecer el equilbrio. Simple D. No se necesita reequilibrar el arbol. No se puede determinar por existir demasiados nodos criticos. Simple I.

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 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 B+, ¿qué relación guardan los valores de clave presentes en el contenedor con los valores que figuran en el árbol B?. Los valores que figuran en el árbol B no tienen por qué ser los valores de las claves presentes en el contenedor. Siempre el número de valores que figuran en el árbol B tiene que coincidir con el de los valores de clave presentes en el contenedor. Los valores que figuran en el árbol B tienen que coincidir con los valores de clave presentes en el contenedor. Ninguna de las otras respuestas es verdadera.

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

En un árbol B+, ¿qué ocurre en la inserción si el nodo hoja que recibe el 0/1 valor de clave contiene m valores de clave después de la inserción?. Se sobrecarga y es necesario realizar una recombinación. Ninguna de las otras respuestas es verdadera. Se sobrecarga y es necesario realizar una rotación o una partición. Finaliza el proceso.

En un árbol B+, para resolver una sobrecarga de un nodo hoja si no tiene hermano inmediato izquierdo y el derecho está lleno,¿qué operación se aplica?. Una recombinación. Una Partición 2/3+ con el hermano derecho. Ninguna de las otras respuestas es verdadera. Una rotación de izquierda a derecha.

En una rotación hacia la izquierda entre nodos de un árbol B durante la *1/1 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 los recorridos en profundidad de un árbol ¿qué respuesta considera correcta?. Se trata de alcanzar todos los posibles caminos desde la raíz nivel a nivel. Se trata de alejarse de la raíz hasta alcanzar un nodo hoja, una vez alcanzado se da un paso atrás para intentar alejarse por un camino alternativo. Se trata de alejarse un nivel de la raíz se da un paso atrás para intentar alejarse por un camino alternativo. Se trata de alejarse algunos niveles de la raíz se dan pasos atrás para intentar alejarse por un camino alternativo.

En un árbol B+, durante la recuperación en rango,¿cuándo finaliza el proceso?. Cuando se trata el nodo de la lista doblemente encadenada que contiene el último valor de clave incluido en el rango. Ninguna de las otras respuestas es verdadera. Cuando empiecen a aparecer valores de clave sin información asociada. Cuando los enlaces que contienen los nodos terminales del árbol B no permitan navegar más por la lista doblemente encadenada.

En un árbol B, si después de la extracción, un nodo se encuentra bajo mínimo, ¿cómo se intenta solucionar la situación si no resulta posible una rotación con ninguno de sus hermanos inmediatos?. Con una nueva extracción. Con una recombinación. Con una Partición-‐2/3. Con una Partición-‐1/2.

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.

En un árbol B, cuando durante la inserción se produce propagación que se resuelve con Partición-‐2/3, ¿con cuántos accesos a disco hay que contar si se subdivide 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 valor de la altura menos uno, más tres de la Partición-‐1/2 de la raíz.

En un árbol AVL, ¿por qué conviene implementar las rotaciones dobles en 0/1 lugar de aplicar las dos simples correspondientes?. Porque se evita colapsar la memoria dinámica. Porque es conteptualmente conveniente. Ninguna de las otras respuestas es verdadera. Porque se evita recalcular enlaces.

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

En un árbol B+, durante la recuperación en rango, en cada nodo visitado de la lista doblemente encadenada, ¿cómo se procede?. Se recupera la información asociada a cada valor de clave. Se descarta la información asociada a cada valor de clave. Se navega por la lista doblemente encadenada gracias a los enlaces que contienen los nodos terminales del árbol B. Ninguna de las otras respuestas es verdadera.

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.

Respecto de la Partición-‐1/2 y la Partición-‐2/3 durante la inserción en *0/1 un árbol B, ¿qué respuesta considera verdadera?. Ninguna de las otras respuestas es verdadera. La Partición-‐1/2 produce un nuevo nodo y la Partición-‐2/3 produce tres nuevos nodos. La Partición-‐1/2 produce un nuevo nodo y la Partición-‐2/3 produce dos nuevos nodos. Ambas particiones producen un nuevo nodo.

¿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+, 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 las rotaciones dobles tras una inserción en un árbol AVL: La altura antes de la inserción y después del reequilibrado es distinta. Antes de la inserción el factor de equilibrio del nodo discriminante es distinto de 0. Ninguna de las otras respuestas es verdadera. Se necesita examinar el resto del árbol.

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 B, si se encuentra el valor de clave a insertar, ¿cuántos accesos se han de contar?. Tantos como el valor de la altura del árbol B. Tantos como el número de nodos que resten para llegar al nodo hoja más cercano al nodo donde se encuentre el valor de clave. Un sólo acceso. Tantos como el valor del nivel del nodo donde se encuentre el valor de clave.

En un árbol B+, ¿cuál es el objetivo de las rotaciones para resolver la sobrecarga?. Convertir los nodos hojas en no hojas. Ninguna de las otras respuestas es verdadera. Reducir la frecuencia de partición de un nodo hoja gracias a una rotación local. Aumentar el número de nodos hoja.

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.

Indicar cuál de las siguientes afirmaciones es cierta: I. Los árboles binarios de búsqueda son un caso particular de los árboles B cuando el grado es 3. II. Los árboles B se aplican a problemas de búsqueda de datos en registros almacenados en memoria secundaria. I: sí, II: sí. I: sí, II: no. I: no, II: sí. I: no, II: no.

Una característica fundamental en los árboles B es *. No se garantiza un factor mínimo de utilización de la memoria externa. Se garantiza que en el peor caso el número de accesos a páginas es cuadrático. Se garantiza que el número de reequilibrios en las extracciones es cero. Su altura depende del orden de inserción de los valores de clave.

En un árbol B+, ¿cuándo se lleva a efecto la Partición--1/2+?. Siempre que se sobrecargue el nodo hoja más a la derecha del árbol B+. Sólo se utiliza cuando se sobrecarga el único nodo hoja del árbol B+. Siempre que se sobrecargue el nodo hoja más a la izquierda del árbol B+. Ninguna de las otras respuestas es verdadera.

¿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 B+, para resolver una sobrecarga de un nodo hoja por medio de una rotación hacia la izquierda, ¿qué ocurre con la clave del nodo padre que media entre los enlaces que referencian a los nodos hojas implicados?. Se reemplaza por una copia del valor de clave mayor que quede después de la rotación en el nodo derecho. Ninguna de las otras respuestas es verdadera. Se reemplaza por una copia del valor de clave mayor que emigre del nodo derecho hacia el nodo izquierdo. Se hace una copia en el nodo izquierdo.

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.

Respecto de los árboles ¿qué respuesta considera correcta?. Los nodos pertenecientes a cada subárbol se dice que son descendientes de la raíz, en particular, la raíz de cada uno de esos subárboles es un hijo de la raíz del árbol, su padre. Los nodos que no tienen ningún descendiente se conocen como no terminales. La relación que conecta un padre con un hijo es una hoja del árbol. Un conjunto de árboles separados (los que quedarían si un árbol perdiera su raíz) recibe el nombre de arbusto.

¿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.

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+?. Se hace fluir hacia el hermano inmediato izquierdo y derecho los valores de clave y los enlaces del nodo que quedó bajo mínimo. Ninguna de las otras respuestas es verdadera. 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+, si después de una extracción, el nodo se encuentra bajo *0/1 mínimo, ¿qué condiciones se requieren para realizar una Recombinación-‐3/2+?. Ninguna de las otras respuestas es verdadera. Que sus hermanos inmediatos izquierdo y derecho tengan un número de claves igual al mínimo. Que sus hermanos inmediatos izquierdo y derecho tengan un número de claves superior al mínimo. Que sus hermanos inmediatos izquierdo y derecho se encuentren bajo mínimo.

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.

Tras la inserción en un árbol B, ¿en qué condiciones se usan las rotaciones?. Cuando los hermanos del nodo que se acaba de sobrecargar tengan m-1 valores de clave. Cuando un hermano del nodo sobrecargado tenga menos de m-1 valores de clave. Inmediatamente después de realizar una Partición-‐1/2 en el nodo sobrecargado si su hermano tiene menos de m-1 valores de clave. Cuando los hermanos del nodo que se acaba de sobrecargar estén también sobrecargados.

En una rotación entre nodos de un árbol B durante la extracción, ¿qué clave del padre fluye hacia el nodo bajo mínimo?. 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.

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.

En el algoritmo de inserción en un árbol B con Partición-‐2/3, si es necesario dividir el nodo raíz, ¿qué operación se aplica?. Partición 1/2. Partición 2/3. Partición 3/4. Rotación.

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 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.

Tras la extracción en un árbol B, ¿con qué propósito se usan las rotaciones?. Para reducir la altura del árbol B. Para disminuir la ocupación promedio de los nodos. Para resolver la situación de bajo mínimo. Para partir más adecuadamente los nodos sobrecargados.

En un árbol multirrama de orden * m, ¿qué respuesta considera verdadera?. Los subárboles extremos de cada nodo son biselados y el resto de los subárboles son árboles multirramas de orden m. Todos sus subárboles son árboles multirramas de orden m. Ninguna de las otras respuestas es verdadera. Los subárboles extremos de cada nodo son AVL y el resto de los subárboles son árboles multirramas de orden m.

Respectode la Partición-‐2/3 durante la inserción en un árbol B, ¿qué respuesta considera verdadera?. Ninguna de las otras respuestas es verdadera. Inserta dos valores de clave en su padre y pasa uno de su padre al nodo nuevo. Inserta dos valores de clave en el padre y pasa dos de su padre al nodo nuevo. Inserta dos valores de clave en el padre y pasa tres de su padre al nodo nuevo.

En un árbol multirrama, ¿qué respuesta considera verdadera?. Buscar un valor de clave implica determinar si se encuentra en el nodo raíz, y si no continuar la búsqueda en el subárbol apropiado. Buscar un valor de clave implica determinar si se encuentra en un nodo hoja y si no continuar la búsqueda en el subárbol apropiado. Ninguna de las otras respuestas es verdadera. Buscar un valor de clave implica determinar si se encuentra en el nodo raíz, y si no comunicar que la búsqueda ha fallado.

En un árbol B+, ¿qué se inserta en el nuevo nodo raíz cuando se lleva a efecto la Particion--1/2+ para solucionar la sobrecarga del único nodo hoja?. Se inserta en la nueva raíz una copia del valor de clave mayor del nuevo nodo hoja y la dirección del nodo hoja que se acaba de partir. Se inserta en la nueva raíz una copia del valor de clave menor del nodo hoja que se acaba de partir y la dirección del nuevo nodo hoja. Ninguna de las otras respuestas es verdadera. Se inserta en la nueva raíz la dirección del nodo hoja que se acaba de partir, una copia del valor de clave mayor de este nodo hoja y la dirección del nuevo nodo hoja.

Una característica fundamental en los árboles B es *. Se garantiza un factor de utilización de memoria externa mínimo del 50%. Se garantiza que en el peor caso el número de accesos a páginas es cuadrático. Se garantiza que el número de reequilibrios en las extracciones es cero. Su altura es independiente del orden de inserción de los valores de clave.