EDP ULPGC Tema 2

¿Qué respuesta considera verdadera?. Con bastante frecuencia es posible establecer una relación de equivalencia entre cualquier árbol no binario y un árbol binario. Raras veces es posible establecer una relación de equivalencia entre cualquier árbol no binario y un árbol binario. Siempre es posible establecer una relación de equivalencia entre cualquier árbol no binario y un árbol binario. Nunca es posible establecer una relación de equivalencia entre cualquier árbol no binario y un árbol binario.

En el esquema donde un árbol binario resulta equivalente a uno no binario, ¿qué respuesta considera verdadera?. Puede ser extendido fácilmente para encontrar la forma binaria equivalente de un bosque. Basta considerar las raíces de los distintos árboles como hermanas. A cada nodo del árbol no binario le corresponde un nodo del binario, pero no a la inversa. Puede ser extendido fácilmente para encontrar la forma binaria equivalente de un bosque. Basta considerar los hijos izquierdos de las raíces de los distintos árboles como hermanos. Puede ser extendido fácilmente para encontrar la forma binaria equivalente de un bosque. Basta considerar los hijos derechos de las raíces de los distintos árboles como hermanos.

Al recorrer el árbol de la figura en la secuencia que señala la numeración, ¿de qué tipo de recorrido se trata?. Preorden. Postorden. Por niveles. Inorden.

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: no, II: sí. I: sí, II: sí. I: sí, II: no. I: no, II: no.

¿Qué hay que hacer para restablecer las propiedades del árbol en la situación de la figura?. Rotación doble + Recoloración + Solucionado. Recoloración + Solucionado. Recoloración + Propagación. Rotación simple + Recoloración + Solucionado.

En la inserción sucesiva en un árbol AVL de la serie alfabética: "A", "B", "C", ¿qué nodo resulta desequilibrado al insertar "C"?. B. Ninguna de las otras respuestas es verdadera. A. C.

Respecto a las longitudes de los caminos de búsqueda: Las del AVL no exceden en más del 45% a las del árbol óptimo. Ninguna de las otras respuestas es verdadera. Son similares en el AVL y en el árbol óptimo. Las del AVL superan en más de un 50% a las del árbol óptimo.

¿Qué hay que hacer para restablecer las propiedades del árbol en la situación de la figura?. Recoloración + Propagación. Recoloración + Solucionado. Rotación doble + Recoloración + Solucionado. Rotación simple + Recoloración + Solucionado.

¿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?. Ninguna de las otras respuestas es verdadera. En todos los casos de la rotación doble. En un caso de rotación simple y en uno de la doble. En dos casos de la rotación simple.

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 N su hijo izquierdo. Se inserta un elemento en el subárbol izquierdo de N. Antes de la inserción el factor de equilibrio de N es -1. Entonces: El nodo crítico a considerar es N y no Nᵢ. Es necesario un reequilibrado en Nᵢ. Ninguna de las otras respuestas es verdadera. Es necesario reequilibrar en N.

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

Respecto a las enumeraciones secuenciales para árboles binarios, ¿qué respuesta considera verdadera?. Consiste en enumerar los elementos del árbol según alguno de los posibles órdenes de recorrido. Consiste en enumerar los elementos del árbol según un orden binario. Consiste en enumerar los elementos del árbol según un orden polinómico. Consiste en enumerar los elementos del árbol según el orden de sus valores.

Según la secuencia que señala la numeración, ¿cuál de las figuras mostradas representa un recorrido del árbol en anchura?. A. C. D. B.

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 sucesor o predecesor en preorden ya que tiene un hijo nulo. 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 hijo derecho o izquierdo con independencia de a cuántos nulos apunte.

Respecto a los árboles binarios de búsqueda como contenedores, ¿qué respuesta considera verdadera?. Extraer se completa sólo cuando el elemento se encuentra en el árbol. El nuevo elemento siempre se inserta como raíz. Insertar sólo se completa cuando el elemento se encuentra en el árbol. Extraer se completa sólo cuando el elemento no se encuentra en el árbol.

Se dispone del árbol AVL formado por la inserción sucesiva de los enteros: 5, 2, 7, 1, 4, 3. El nodo cuyo dato es 5 tiene un factor de equilibrio: -1. Ninguna de las otras respuestas es verdadera. 0. +1.

Respecto de los árboles, ¿qué respuesta considera verdadera?. Una estructura lineal caracteriza una relación anárquica entre sus nodos. Un árbol caracteriza una relación jerárquica entre sus nodos. Un árbol caracteriza una relación no jerárquica entre sus nodos. Una estructura lineal caracteriza una relación jerárquica entre sus nodos.

El árbol binario de búsqueda formado por la introducción sucesiva de los elementos 16, 12, 32, 10, 22, 14, 69, 4, 13, 18, 42, 9, 15, 23, 99, 2, 17: Ambas soluciones son correctas. Es un AVL. Ninguna de las otras respuestas es verdadera. Es un árbol perfectamente equilibrado.

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 y viceversa. A cada nodo del árbol binario le corresponde uno del no binario, pero no a la inversa. A cada nodo del árbol no binario le corresponde uno del binario, pero no a la inversa. El hijo derecho representa al segundo hijo.

¿Qué reestructuraciones hay que hacer tras eliminar el valor 242?. Ninguna, después la extracción se mantienen las propiedades del árbol. Una rotación doble para restablecer las propiedades del árbol. Una recoloración para restablecer las propiedades del árbol. Una rotación simple para restablecer las propiedades del árbol.

Respecto a los árboles binarios de búsqueda como contenedores: Se tiene sólo una operación (Linealizar) que refleja el carácter del árbol binario de búsqueda como estructura de representación de contenedores asociativos de claves ordenables. Ninguna de las otras respuestas se considera verdadera. Se tienen tres operaciones (Linealizar, Desechar y Equilibrar) que reflejan el carácter del árbol binario de búsqueda como estructura de representación de contenedores asociativos de claves ordenables. Se tienen tres operaciones (Insertar, Extraer y Buscar) que reflejan el carácter del árbol binario de búsqueda como estructura de representación de contenedores asociativos de claves ordenables.

Respecto a la operación Buscar en árboles binarios de búsqueda: Buscar actúa en la raíz y continúa por los dos subárboles. Buscar actúa en un nodo hoja y si no está la clave correspondiente continúa su ascensión por el subárbol apropiado. Buscar actúa en la raíz y continúa por uno de los subárboles. Buscar o actúa en la raíz o continúa por los dos subárboles.

Respecto de los árboles: El nivel de un nodo es uno más la longitud de su camino desde la raíz. El nivel de la raíz es indefinido. No cabe hablar del nivel de la raíz. El nivel de la raíz es dos.

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. Ninguna de las otras respuestas es verdadera. El antecesor más cercano con factor de equilibrio +1 ó -1 antes de la inserción. El antecesor más cercano con factor de equilibrio -2 ó +2 antes de la inserción.

Se dispone del árbol AVL formado por la inserción sucesiva de los enteros: 5, 2, 7, 1, 4, 3. El árbol resultante es el mismo que el árbol binario de búsqueda formado por la inserción sucesiva de: 5,3,1,4,7. Ninguna es verdadera. 4,3,5,2,1,7. 4,5,7,2,1,3.

Respecto al árbol binario de búsqueda, ¿qué respuesta considera verdadera?. El subárbol izquierdo es un árbol binario de búsqueda que sólo contiene elementos mayores que la raíz. El subárbol derecho es un árbol binario de búsqueda que sólo contiene elementos menores que la raíz. Ninguna de las otras respuestas se considera verdadera. El subárbol izquierdo es un árbol binario de búsqueda que sólo contiene elementos menores que la raíz. El subárbol derecho es un árbol binario de búsqueda que sólo contiene elementos mayores que la raíz. El subárbol izquierdo es un árbol binario de búsqueda que sólo contiene elementos menores que la raíz. El subárbol central es un árbol binario de búsqueda que contiene elementos iguales que la raíz. El subárbol derecho es un árbol binario de búsqueda que sólo contiene elementos mayores que la raíz.

¿Cuándo es preferible un árbol Rojo-Negro frente a AVL?. Cuando la operación más frecuente es la búsqueda. Cuando se necesitan tiempos de orden logarítmico. Cuando hay muchas inserciones y extracciones. Cuando el árbol debe estar equilibrado.

Respecto de los árboles, ¿qué respuesta considera verdadera?. Las hojas tienen grado uno. Las hojas tienen grado dos. Se denomina grado de un nodo al número de hijos que tiene. No hay grado en hojas.

¿Qué operaciones pueden realizarse en un árbol Rojo-Negro con una complejidad en tiempo de orden O(logN)?. Inserción, extracción y búsqueda del predecesor o del sucesor. Sólo la búsqueda del predecesor o del sucesor. Solo la operación de Las inserción. Las operaciones de ordenación.

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?. B. D. C. A.

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

Respecto a los árboles binarios de búsqueda como contenedores, ¿qué respuesta considera verdadera?. Insertar sólo se completa cuando el elemento no se encuentra en el árbol. Extraer se completa sólo cuando el elemento no se encuentra en el árbol. El nuevo elemento siempre se inserta como raíz, lo que facilita mucho la operación. Insertar sólo se completa cuando el elemento se encuentra en el árbol.

Indicar cuál de las siguientes a rmaciones 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: no. I: sí, II: sí. I: no, II: no. I: no, II: sí.

En un árbol AVL, los factores de equilibrio que están en el camino desde el nodo crítico al nuevo punto de inserción deben ser: +1 ó -1 antes de la inserción. Ninguna de las otras respuestas es verdadera. +2 ó -2 antes de la inserción. 0 antes de la inserción.

Si en el árbol AVL equilibrado de la gura izquierda se practica una extracción en el subárbol derecho del nodo A y una rotación simple izquierda para restablecer el equilibrio, ¿qué característica relevante destacaría en el árbol AVL reequilibrado frente al AVL equilibrado antes de la extracción?. La altura del árbol reequilibrado ha disminuido respecto a la altura del árbol equilibrado antes de la extracción aunque bajo ninguna circunstancia se puede propagar hacia la raíz el desequilibrio. Los factores de equilibrio de los nodos A y B en el árbol reequilibrado son distintos de los factores de equilibrio de los nodos A y B en el árbol equilibrado antes de la extracción. La altura del árbol reequilibrado ha disminuido respecto a la altura del árbol equilibrado antes de la extracción y por tanto se puede propagar hacia la raíz el desequilibrio. La suma de los factores de equilibrio de los nodos A y B en el árbol reequilibrado es menor que la suma de los factores de equilibrio de los nodos A y B en el árbol equilibrado antes de la extracción.

Determinar cuál de las siguientes a rmaciones es cierta: I. El árbol AVL conserva una altura logarítmica, con un coste logarítmico para sus operaciones de mantenimiento. II. El árbol binario de búsqueda puede degenerar hasta alcanzar una altura lineal. I: sí, II: no. I: no, II: no. I: sí, II: sí. I: no, II: sí.

Tras una rotación después de una inserción en un árbol AVL, ¿qué respuesta considera verdadera?. Los únicos nodos que pueden variar su factor de equilibrio son los implicados en la rotación. La altura antes de la inserción y después del reequilibrado es distinta. Ninguna de las otras respuestas es verdadera. Se necesita recalcular los factores de equilibrio del resto del árbol.

En el árbol AVL desequilibrado tras una extracción en el subárbol derecho del nodo A, se hace una rotación doble izquierda derecha para restablecer el equilibrio, ¿cuál es el árbol resultante correcto?. D. C. A. B.

Respecto de los árboles, ¿qué respuesta considera verdadera?. Los árboles representan estructuras no lineales. Las estructuras arbóreas expresan relaciones no jerárquicas. Los árboles representan estructuras lineales. Las estructuras lineales expresan relaciones jerárquicas.

En un árbol Rojo-Negro, los hijos de un nodo negro deben ser... de color rojo. de color negro. de color rojo o negro.

¿Qué reestructuraciones hay que hacer en el árbol de la gura para restablecer sus propiedades después de extraer el valor 717?. Una rotación doble seguida de una recoloración para restablecer las propiedades del árbol. Una rotación simple con dos recoloraciones para restablecer las propiedades del árbol. Dos rotaciones simples con dos recoloraciones intercaladas para restablecer las propiedades del árbol. Ninguna, después la extracción se mantienen las propiedades del árbol.

Respecto a la representación contigua para árboles binarios completos, ¿qué respuesta considera verdadera?. La raíz ocupa cualquier posición i y los hijos izquierdo y derecho las posiciones 2*i y 2*i+1. La raíz ocupa la primera posición, los hijos izquierdo y derecho del nodo que ocupa la posición i ocupan las posiciones 2*i y 2*i+1. Necesita un árbol binario explícito. Obliga a una estructura con rami cación múltiple.

Al recorrer en inorden el árbol de la gura, ¿en qué secuencia se tratan los nodos?. A, E, H, G, J, L, D, R, P. A, D, E, G, H, J, L, P, R. P, D, A, G, E, H, L, J, R. P, D, R, A, G, L, E, H, J.

Respecto de los árboles, ¿qué respuesta considera verdadera?. La relación que conecta un padre con un hijo es una hoja del árbol. Un conjunto de árboles separados (los que quedaran si un árbol perdiera su raíz) recibe el nombre de arbusto. Un conjunto de árboles separados (los que quedaran si un árbol perdiera su raíz) recibe el nombre de bosque. La relación que conecta un padre con un hijo es un vértice del árbol.

Respecto a la extracción en los árboles binarios de búsqueda como contenedores, ¿qué respuesta considera verdadera?. Si el nodo a extraer tuviera uno de sus hijos vacío, basta con que el otro hijo pase a ocupar el lugar de su padre. Cuando ninguno de los subárboles del nodo a extraer esté vacío lo más adecuado es sustituir el valor del nodo a extraer por el valor más lejano y así alterar el árbol lo menos posible. Si el nodo a extraer tuviera los dos subárboles vacíos, basta con que el nodo pasara a ocupar el lugar del nodo raíz. Si el nodo a extraer tuviera los dos subárboles no vacíos, basta con que los hijos pasaran a ocupar el lugar de su padre.

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

Respecto a la enumeración secuencial en preorden con información de rango, ¿qué representa el rango de un elemento?. La posición donde comienza en la representación secuencial el subárbol que sigue en preorden al recorrido del subárbol izquierdo del elemento. La posición donde termina en la representación secuencial el subárbol que sigue en preorden al recorrido del subárbol derecho del elemento. La posición donde comienza en la representación secuencial el subárbol que sigue en preorden al recorrido del subárbol derecho del elemento. La posición donde termina en la representación secuencial el subárbol que sigue en preorden al recorrido del subárbol izquierdo del elemento.

Se define árbol compacto como: 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 derecha 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. 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.

Respecto de los árboles, ¿qué respuesta considera verdadera?. La relación que conecta un padre con un hijo es una rama del árbol. Los nodos que no tienen ningún descendiente se conocen como no terminales. Un conjunto de árboles separados (los que quedaran si un árbol perdiera su raíz) recibe el nombre de arbusto. La relación que conecta un padre con un hijo es una hoja del árbol.

Se dispone del árbol AVL formado por la inserción sucesiva de los enteros: 5, 2, 7, 1, 4, 3. El árbol resultante es el mismo que el árbol binario de búsqueda formado por la inserción sucesiva de: 4, 5, 7, 3, 1, 2. 5, 3, 1, 4, 7, 2. Ninguna de las otras respuestas es verdadera. 4, 2, 5, 1, 3, 7.

Al recorrer el árbol de la gura en la secuencia que señala la numeración, ¿de qué tipo de recorrido se trata?. Preorden. Postorden. Inorden. Por niveles.

Respecto a la búsqueda binaria, ¿qué respuesta considera verdadera?. Comienza por comparar el valor que se busca con el elemento que está en el centro del espacio de almacenamiento. Si el elemento buscado es mayor que el central quedan descartados todos los siguientes. Si el elemento buscado es menor que el central quedan descartados todos los anteriores. La búsqueda continúa comparando con el elemento central del subespacio no descartado hasta localizar el elemento o determinar que no se encuentra. Ninguna de las otras respuestas se considera verdadera. Comienza por comparar el valor que se busca con el elemento que está en el centro del espacio de almacenamiento. Si el elemento buscado es mayor que el central quedan descartados todos los anteriores. Si el elemento buscado es menor que el central quedan descartados todos los siguientes. La búsqueda continúa comparando con el elemento central del subespacio descartado hasta localizar el elemento o determinar que no se encuentra. Comienza por comparar el valor que se busca con el elemento que está en el centro del espacio de almacenamiento. Si el elemento buscado es mayor que el central quedan descartados todos los anteriores. Si el elemento buscado es menor que el central quedan descartados todos los siguientes. La búsqueda continúa comparando con el elemento central del subespacio no descartado hasta localizar el elemento o determinar que no se encuentra.

¿Qué hay que hacer para restablecer las propiedades del árbol en la situación de la figura?. Recoloración + Propagación. Rotación simple + Recoloración + Propagación. Rotación doble + Recoloración + Solucionado. Rotación simple + Recoloración + Solucionado.

Al recorrer en postorden el árbol de la figura, ¿en qué secuencia se tratan los nodos?. A, E, H, G, J, L, D, R, P. P, D, R, A, G, L, E, H, J. P, D, A, G, E, H, L, J, R. A, D, E, G, H, J, L, P, R.

¿Qué hay que hacer para restablecer las propiedades del árbol en la situación de la figura?. Recoloración + Solucionado. Rotación doble + Recoloración + Solucionado. Rotación simple + Recoloración + Solucionado. Recoloración + Propagación.