EDP 2º Parcial (T4,T5,T6,T7,T8)

Respecto a la búsqueda binaria en un conjunto con representación contigua y ordenado en forma creciente de sus valores, ¿con qué probabilidad un elemento del conjunto interviene en alguna operación de comparación durante el proceso de búsqueda?. El elemento central tiene una probabilidad de comparación del 50%, los centrales de los subespacios en que éste divide el espacio de búsqueda la tienen del 25%, y así sucesivamente. El elemento central tiene una probabilidad de comparación del 100%, los centrales de los subespacios en que éste divide el espacio de búsqueda la tienen del 50%, y así sucesivamente. El elemento central tiene una probabilidad de comparación del 60%, los centrales de los subespacios en que éste divide el espacio de búsqueda la tienen del 30%, y así sucesivamente. El elemento central y los centrales de los subespacios en que éste divide el espacio de búsqueda tienen una probabilidad de comparación del 100%.

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.

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

Como ejemplo de la representación secuencial contigua para árboles binarios completos, en la figura se presentan cuatro posibilidades, ¿qué opción considera la correcta?. A. B. C. D.

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: Es un árbol perfectamente equilibrado. Ambas soluciones son correctas. Es un AVL. Ninguna de las otras respuestas es verdadera.

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

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

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

Respecto a la evitación de la degeneración de un árbol binario de búsqueda, ¿cuál de las siguientes respuestas considera verdadera?. Las reorganizaciones necesarias para la reestructuración completa de un árbol binario de búsqueda pueden mantenerse bajo control. 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 operaciones de mantenimiento en un árbol AVL son O( n ).

Desde el punto de vista de la interrelación entre las estructuras, cabe pensar que una lista lineal podría considerarse como: Un árbol 1-ario en el que la relación sucesor se expresa como hermano. Un árbol 2-ario en el que la relación sucesor se expresa como padre o abuelo. Un árbol 1-ario en el que la relación sucesor se expresa como hijo. Un árbol 2-ario en el que la relación sucesor se expresa como hijo derecho o izquierdo.

¿En cuántos pasos se resuelve una extracción en un árbol AVL?. En O(n^2) pasos. En O(log2 (n)) pasos. En O(nlog2 (n)) pasos. En O(n) pasos.

En el árbol AVL desequilibrado tras una inserción en el subárbol izquierdo del nodo B, se hace una rotación simple II para restablecer el equilibrio, ¿cuál es el árbol resultante correcto?. A. B. C. D.

Con los siguientes valores: 18, 50, 100 ¿Cuál de las siguientes opciones sería un árbol Rojo-Negro correcto?. 50-ráiz negra; 18-hijo izquierdo rojo, 100-hijo derecho negro. 50-ráiz negra; 18-hijo izquierdo negro, 100-hijo derecho rojo. 50-ráiz negra; 18-hijo izquierdo rojo, 100-hijo derecho rojo. 50-ráiz roja; 18-hijo izquierdo rojo, 100-hijo derecho rojo.

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 no 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 descartado hasta localizar el elemento o determinar que no se encuentra.

¿Qué árbol tiene un equilibrado más estricto?. El árbol AVL. El Rojo-Negro.

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. A cada nodo del árbol binario le corresponde un nodo del no binario, pero no a la inversa. El hijo derecho de un nodo en el árbol binario será el correspondiente al segundo hijo del nodo equivalente del árbol no binario. A cada nodo del árbol no binario le corresponde un nodo del binario y viceversa.

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

¿Cuál es el peor árbol AVL posible de una altura dada?. El que tiene menor número de nodos. El que tiene todos los nodos con factor de equilibrio +1. El que tiene todos los nodos con factor de equilibrio -1. El que tiene mayor número de nodos.

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

Respecto a las enumeraciones secuenciales para árboles binarios, ¿qué respuesta considera verdadera?. 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 alguno de los posibles órdenes de recorrido. Consiste en enumerar los elementos del árbol según el orden de sus valores.

En un árbol binario, ¿qué respuesta considera verdadera?. Un árbol binario perfecto es un árbol binario en el cual cada nodo es de grado cero o dos. Un árbol binario perfecto es uno que tiene todos los nodos que puede tener en función de su altura, con k niveles 2^(k)-1 nodos. Un árbol binario lleno es aquel en el cual todos los nodos de grado cero o uno están en los dos últimos niveles, de forma que las hojas del último nivel ocupan las posiciones más a la izquierda de dicho nivel. Un árbol binario completo es un conjunto finito de m nodos (m≥0), tal que: Si m=0, el árbol está vacío. Si m>0 entonces existe un nodo raíz. El resto de los nodos se reparten entre m árboles binarios.

Respecto de los recorridos en un contenedor, ¿qué respuesta considera verdadera?. En una estructura lineal se hace según su ordenación natural de primero a último, según la relación de sucesión. En un árbol se hace según la relación padre/hijo que se establece entre parejas de nodos por lo que sólo 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 predecesor/sucesor que se establece entre parejas de nodos por lo que sólo hay una línea posible de recorrido.

Respecto a los árboles binarios de búsqueda como contenedores, ¿qué respuesta considera verdadera?. Ninguna de las otras respuestas se considera verdadera. 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. 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 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.

¿Qué respuesta considera verdadera?. Siempre 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. Con bastante frecuencia 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.

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

La estructura arbórea de la figura, ¿qué expresión representa de forma implícita en un ordenador?. B * C + D – H / Z. (B * C) + D – (H / Z). (B * C) + D – H / Z. (B * C) + (D – H / Z).

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 que altera su factor de equilibrio. Antes de la inserción el factor de equilibrio de N es 0. Entonces: Es necesario reequilibrar en N con una rotación doble. Es necesario un reequilibrado en N . El nodo crítico a considerar es N y no N. Ninguna de las otras respuestas es verdadera.

Respecto a los árboles binarios de búsqueda como contenedores, ¿qué respuesta considera verdadera?. Todas las otras respuestas se consideran verdaderas. Buscar devuelve el subárbol del que es raíz el elemento buscado. Buscar facilita la realización de ulteriores operaciones. Buscar permite saber si un elemento está, o no, en el árbol.

Respecto a los árboles binarios, ¿qué respuesta considera verdadera?. La implementación más común para los árboles binarios es una estructura encadenada en memoria dinámica protegida contra escritura. Cada nodo almacena: La información propia y dos enlaces que referencian a sus hijos. Cada nodo almacena: La información propia y uno dos o tres enlaces que referencian a sus hijos. La implementación más común para los árboles binarios es una estructura encadenada en memoria externa.

Dado un árbol AVL, el factor de equilibrio de un nodo es 0, si se elimina un nodo por su izquierda. Entonces: Es necesario reequilibrar con una rotación I. Es necesario reequilibrar con una rotación D. Ninguna de las otras respuestas es verdadera. No es necesario ningún reequilibrado.

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: Es necesario un reequilibrado en N . Ninguna de las otras respuestas es verdadera. El nodo crítico a considerar es N y no N . Es necesario reequilibrar en N.

¿Qué reestructuraciones hay que hacer en el árbol de la figura para restablecer sus propiedades después de extraer el valor 717?. Ninguna, después la extracción se mantienen 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. Una rotación doble seguida de una recoloración para restablecer las propiedades del árbol.

¿Cuál de los árboles binarios de la figura es un árbol binario completo?. A. B. C. D.

¿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 simple + Recoloración + Solucionado. Rotación doble + Recoloración + Solucionado.

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, 2, 1, 3. Ninguna de las otras respuestas es verdadera. 4, 3, 5, 2, 1, 7. 5, 3, 1, 4, 7.

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

Respecto de las precedencias entre operadores, ¿qué ventaja adicional tiene el que una expresión aritmética o lógica pueda representarse por su árbol binario implícito?. Que quedan recogidas en la estructura, por lo que no es necesario representar paréntesis. Que quedan recogidas en los nodos hojas de la estructura, por lo que no es necesario jugar con demasiados nodos internos. Que quedan recogidas en los paréntesis de la estructura, por lo que no es necesario jugar con demasiados nodos. No presenta ventaja adicional alguna.

Respecto a los árboles binarios de búsqueda como contenedores, ¿qué respuesta considera verdadera?. Buscar actúa en la raíz y continúa por los dos subárboles. Buscar o actúa en la raíz o continúa por los dos subárboles. Buscar actúa en la raíz y continúa por uno de los 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.

¿Qué respuesta considera verdadera?. Cada nodo almacena: La información propia, las de sus predecesores y dos enlaces que referencian a sus hijos. La implementación más común para los árboles binarios es una estructura encadenada en memoria externa. La implementación más común para los árboles binarios es una estructura encadenada en memoria dinámica protegida contra escritura. Es posible representar un árbol en un espacio secuencial; en ocasiones puede ser lo más adecuado.

Respecto a la búsqueda binaria, ¿qué respuesta considera verdadera?. Como en cada iteración el espacio de búsqueda se reduce a la mitad con respecto a la iteración previa, se puede encontrar un elemento o determinar que no está con un número de comparaciones del orden de log N, donde N es el número de elementos del conjunto. Como en cada iteración el espacio de búsqueda se reduce a la mitad con respecto a la iteración previa, se puede encontrar un elemento o determinar que no está con un número de comparaciones del orden de 2*N, donde N es el número de elementos del conjunto. Como en cada iteración el espacio de búsqueda se reduce a la mitad con respecto a la iteración previa, se puede encontrar un elemento o determinar que no está con un número de comparaciones del orden de N/2, donde N es el número de elementos del conjunto. Ninguna de las otras respuestas se considera verdadera.

En el árbol AVL de la figura, tras la inserción de ENERO, ¿qué nodo se considera crítico?. MARZO. AGOSTO. FEBRERO. MAYO.

Cuando la extracción en un árbol AVL provoca una disminución de altura 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 un árbol binario, ¿qué respuesta considera verdadera?. Si se restringe a dos el grado máximo de un nodo, surge el árbol binario. Un árbol binario es un conjunto finito de m nodos (m≥0), tal que: Si m=0, el árbol está vacío. Si m>0 entonces existe más de un nodo raíz. El resto de los nodos se reparten entre dos árboles binarios. Si se restringe a uno el grado máximo de un nodo surge el árbol binario. Un árbol binario es un conjunto finito de m nodos (m≥0), tal que: Si m=0, el árbol está vacío. Si m>0 entonces existe un nodo raíz. El resto de los nodos se reparten entre m árboles binarios.

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

La altura del árbol AVL formado por la inserción sucesiva de los enteros 10, 7, 8, 9, 5, 15, 18, es: Ninguna de las otras respuestas es verdadera. 4. 3. 5.

Respecto de los árboles, ¿qué respuesta considera verdadera?. En un árbol existe un nodo especialmente designado que se llama raíz. Los restantes nodos se distribuyen en una serie de subconjuntos disjuntos, cada uno de los cuales es, a su vez, un árbol. En un árbol existe un nodo especialmente designado que se llama raíz. Los restantes nodos forman, a su vez, un árbol. En un árbol existe un nodo especialmente designado que se llama raíz. Los restantes nodos se distribuyen en una serie de subconjuntos no necesariamente disjuntos, cada uno de los cuales es, a su vez, un árbol. En un árbol existe una pareja de nodos especialmente designados que se llaman raíces. Los restantes nodos se distribuyen en una serie de subconjuntos disjuntos, cada uno de los cuales es, a su vez, un árbol.

Respecto de los árboles, ¿qué respuesta considera verdadera?. Un conjunto de árboles separados (los que quedaran si un árbol perdiera su raíz) recibe el nombre de arbusto. El nodo raíz de un árbol que no sea subárbol de otro, puede tener algún ascendiente y no es punto de partida de la jerarquía representada en la estructura. El nodo raíz de un árbol que no sea subárbol de otro, no tiene ningún ascendiente y constituye el punto de partida de la jerarquía representada en la estructura. La relación que conecta un padre con un hijo es un vértice del árbol.

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

¿Cuál es el valor máximo, en valor absoluto, que puede tener el factor de equilibrio en un árbol Rojo-Negro?. El factor de equilibrio de un árbol Rojo-Negro no puede ser mayor que 2 en valor absoluto. El factor de equilibrio de un árbol Rojo-Negro puede llegar a 3, al ser más laxo que el AVL. El árbol Rojo-Negro no usa el concepto de factor de equilibrio.

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

Respecto a la búsqueda binaria en un conjunto con representación contigua y ordenado en forma creciente de sus valores, ¿qué respuesta considera verdadera?. Una extracción requiere que los elementos mayores que el extraído se desplacen para cubrir el hueco que aquél deja. Una extracción requiere que los elementos menores que el extraído se desplacen para cubrir el hueco que aquél deja. Una extracción no requiere desplazamiento alguno para cubrir el hueco que se deja. Ninguna de las otras respuestas se considera verdadera.

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

En un árbol binario equivalente a uno no binario, ¿qué respuesta considera verdadera?. El hijo izquierdo de un nodo en el árbol binario será el correspondiente al segundo hijo del nodo equivalente del árbol no binario. A cada nodo del árbol no binario le corresponde un nodo del binario, pero no a la inversa. El hijo derecho de un nodo en el árbol binario será el correspondiente al primer 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.

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

Cuando la extracción en un árbol AVL provoca una disminución de altura de la rama de donde se extrajo el nodo: Siempre es necesario realizar al menos dos operaciones de rotación. No queda más remedio que realizar una reorganización global. Siempre existe un tipo de rotación que con una sola aplicación resuelve el desequilibrio. Ninguna de las otras respuestas es verdadera.

Respecto a los árboles binarios, ¿qué respuesta considera verdadera?. La implementación más común para los árboles binarios es una estructura encadenada en memoria externa. Cada nodo almacena: La información propia, la de sus predecesores y uno dos o tres enlaces que referencian a sus hijos. La implementación más común para los árboles binarios es una estructura encadenada en memoria dinámica. Cada nodo almacena: La información propia y uno dos o tres enlaces que referencian a sus hijos.

Antes de la inserción, el nodo discriminante (hijo del crítico) de un árbol AVL debe tener un factor de equilibrio: +1 ó -1. Ninguna de las otras respuestas es verdadera. 0. +2 ó -2.

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

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

¿Por qué el árbol rojo negro debe cumplir ciertas propiedades?. Para tener operaciones con una complejidad de tiempo lineal. Para tener operaciones con una complejidad de tiempo constante. Para tener operaciones con una complejidad de tiempo logarítmica. Para tener operaciones con una complejidad de tiempo exponenxial.

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: Ti y Td son AVL. Ninguna de las otras respuestas es verdadera. H(Ti) - H(Td) = -1, 0, +1. Ti y Td son AVL y H(Ti) - H(Td) = -1, 0, +1.

En los recorridos en profundidad de un árbol, ¿qué respuesta considera verdadera?. El tratamiento del nodo se puede hacer cuando se accede por primera vez, o cuando se regresa de cada uno de sus hijos para acceder al siguiente o al volver al padre, lo que da lugar a tres variantes: los recorridos en preorden, inorden y postorden. Optar entre los recorridos en preorden, inorden y postorden depende exclusivamente del orden en que fueron insertados los nodos. Los recorridos en preorden, inorden y postorden no dependen del momento que se elija para tratar el nodo. Contrariamente a lo que podría pensarse, los recorridos en preorden, inorden y postorden no entrañan ninguna preferencia por algún cierto orden.

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

Como ejemplo de la técnica de enumeraciones de árboles binarios en preorden con información sobre el rango de cada nodo, en la figura se presentan cuatro posibilidades, ¿qué opción considera la correcta?. A. B. C. D.

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.

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

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 de la rotación es distinta. Después de la rotación, los factores de equilibrio de los nodos crítico y discriminante son 0. Antes de la inserción el factor de equilibrio del nodo discriminante es distinto de 0. Se necesita examinar el resto del árbol.

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. 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 rama del árbol.

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

¿En cuál de los siguientes campos se usan árboles Rojo-Negro?. Algoritmos eficientes de ordenación. Planificación de procesos. Almacenamiento eficiente de strings.

Respecto a los árboles binarios de búsqueda como contenedores, ¿qué respuesta considera verdadera?. Buscar devuelve el subárbol del que es raíz el elemento buscado. Buscar facilita la realización de ulteriores operaciones. Todas las otras respuestas se consideran verdaderas. Buscar permite saber si un elemento está, o no, en el árbol.

¿Qué reestructuraciones hay que hacer en el árbol de la figura para restablecer sus propiedades después de extraer el valor 738?. Una rotación doble seguida de una recoloración 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. Una rotación simple con dos recoloraciones para restablecer las propiedades del árbol.

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. Antes de la inserción el factor de equilibrio del nodo discriminante es distinto de 0. Se necesita examinar el resto del árbol. La altura del subárbol antes de la inserción y después de la rotación es la misma.

Respecto de los árboles, ¿qué respuesta considera verdadera?. Á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 n. Árbol n-ario es aquel en el que el grado máximo de sus nodos es dos.

Respecto a las enumeraciones secuenciales para árboles binarios ¿qué respuesta considera verdadera?. 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. Consiste en enumerar los elementos del árbol según alguno de los posibles órdenes de recorrido.

En un árbol AVL, se necesita una rotación cuando: Aumenta la altura del subárbol de mayor altura. Aumenta la altura del subárbol de menor altura. Ninguna de las otras respuestas es verdadera. El factor de equilibrio pasa de 0 a -1 ó +1.

Respecto al árbol binario de búsqueda, ¿qué respuesta considera verdadera?. Si un árbol binario de búsqueda se implementa con una estructura encadenada, se pueden tener las ventajas de la búsqueda dicotómica, pero no solventa los inconvenientes de la ubicación contigua a la hora de insertar o extraer. Si un árbol binario de búsqueda se implementa con una estructura encadenada, se ralentiza la búsqueda dicotómica aunque se salvan los inconvenientes de la ubicación contigua a la hora de insertar o extraer. Si un árbol binario de búsqueda se implementa con una estructura encadenada, se pueden tener las ventajas de la búsqueda dicotómica sin los inconvenientes de la ubicación contigua a la hora de insertar o extraer. Ninguna de las otras respuestas se considera verdadera.

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

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

En un árbol binario equivalente a uno no binario, ¿qué respuesta considera verdadera?. El hijo izquierdo de un nodo en el árbol binario será el correspondiente al primer hijo del nodo equivalente del árbol no binario. A cada nodo del árbol no binario le corresponde un nodo del binario, pero no a la inversa. El hijo derecho de un nodo en el árbol binario será el correspondiente al ú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.

¿Qué reestructuraciones hay que hacer en el árbol de la figura para restablecer sus propiedades después de extraer el valor 99?. Una recoloración para restablecer las propiedades del árbol. Ninguna, después la extracción se mantienen las propiedades del árbol. Una rotación simple para restablecer las propiedades del árbol. Una rotación doble para restablecer las propiedades del árbol.

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. 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. Ninguna de las otras respuestas es verdadera.

En los recorridos en profundidad de un árbol, ¿qué respuesta considera verdadera?. 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. Se trata de alcanzar todos los posibles caminos desde la raíz nivel a nivel.

En los recorridos en profundidad de un árbol, ¿qué respuesta considera verdadera?. Implica que por un nodo se pasa una sola vez. Implica que por un nodo se pasa varias veces: cuando se accede por primera vez y cuando se regresa de cada uno de sus hijos para acceder al siguiente o volver al padre. Implica que por un nodo se pasa dos veces: cuando se accede por primera vez y cuando se regresa de cada uno de sus hijos para acceder al siguiente, nunca para volver al padre. Implica que por un nodo se pasa siempre dos veces: cuando se accede por primera vez y para volver al padre.

Respecto a la representación contigua para árboles binarios completos, ¿qué respuesta considera verdadera?. Es conveniente un espacio secuencial homogéneo y aleatoriamente direccionable. Se hace con una estructura encadenada en memoria dinámica protegida contra escritura. Obliga a una estructura con ramificación múltiple. Necesita de un árbol binario explícito.

Respecto de los árboles, ¿qué respuesta considera verdadera?. Los nodos que no tienen ningún descendiente se conocen como no terminales. 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. 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.

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 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. 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. Ninguna de las otras respuestas se 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.

Respecto a los árboles binarios de búsqueda sin elementos repetidos, ¿qué respuesta considera verdadera?. Es un árbol binario con la restricción de "menores a la izquierda, mayores a la derecha". Ninguna de las otras respuestas se considera verdadera. Es un árbol binario con la restricción de "menores a la izquierda, mayores e iguales a la derecha". Es un árbol binario con la restricción de "menores e iguales a la izquierda, mayores a la derecha".

Un árbol binario interesa en aplicaciones que dan solución a problemas cuya estructura: Binaria degenere con facilidad a una lista lineal. Es esencialmente no binaria. Es esencialmente binaria. Es multidimensional.

Respecto a la búsqueda binaria, ¿qué respuesta considera verdadera?. Si los elementos se hallan ordenados en un espacio de almacenamiento contiguo y direccionable aleatoriamente (como un vector) una opción mejor que la búsqueda secuencial es la búsqueda binaria. Si en un espacio de almacenamiento contiguo y direccionable aleatoriamente (como un vector), los elementos se hallan no ordenados una opción mejor que la búsqueda secuencial es la búsqueda binaria o dicotómica. Ninguna de las otras respuestas se considera verdadera. Si los elementos se hallan ordenados en un espacio de almacenamiento contiguo y direccionable aleatoriamente (como un vector) una opción mejor que la búsqueda binaria es la búsqueda secuencial.

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

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.

Si en el árbol AVL equilibrado de la figura 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. 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. 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.

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

¿Qué encuentra significativamente diferente entre el tratamiento de los desequilibrios durante la inserción y la extracción en un árbol AVL?. En la inserción nunca se produce propagación después de una rotación y en la extracción sí se puede producir. En la inserción siempre se produce propagación después de una rotación y en la extracción sólo con cierta frecuencia. Ninguna de las otras respuestas es verdadera. Nada, tanto en la inserción como en la extracción siempre se produce propagación.

Respecto a los árboles binarios de búsqueda como contenedores, ¿qué respuesta considera verdadera?. 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. Extraer se completa sólo cuando el elemento no se encuentra en el árbol. Extraer se completa sólo cuando el elemento se encuentra en el á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?. A. B. C. D.

En las rotaciones dobles tras una inserción en un árbol AVL: La altura antes de la inserción y después de la rotación es distinta. Se necesita examinar el resto del árbol. Ninguna de las otras respuestas es verdadera. Antes de la inserción el factor de equilibrio del nodo discriminante es distinto de 0.

¿Qué rotaciones dobles son posibles tras una extracción en un árbol AVL?. II, DI, DD. II, DD. Ninguna de las otras respuestas es verdadera. ID, DI.

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. Necesita un árbol binario explícito. 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. Obliga a una estructura con ramificación múltiple.

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

En el árbol AVL de la figura, tras la inserción de SEPTIEMBRE, ¿qué rotación se debe realizar para restablecer el equilibrio?. No se necesita reequilibrar el árbol. No se puede determinar por existir demasiados nodos críticos. Simple II. Simple DD.

¿Cuál de los árboles binarios de la figura es un árbol binario lleno?. A. B. C. D.

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?. Hasta un ascendiente que no quede desequilibrado. Nunca se producirán propagaciones. Necesariamente hasta la raíz. Hasta que cubra por completo el árbol.

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

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: 0 antes de la inserción. +2 ó -2 antes de la inserción. Ninguna de las otras respuestas es verdadera. +1 ó -1 antes de la inserción.

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

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

Respecto a la búsqueda binaria en un conjunto con representación contigua y ordenado en forma creciente de sus valores, ¿qué respuesta considera verdadera?. Ninguna de las otras respuestas se considera verdadera. Una inserción requiere el desplazamiento de todos los que sean mayores que el insertado para abrir hueco en la posición de inserción. Una inserción requiere el desplazamiento de todos los que sean menores que el insertado para abrir hueco en la posición de inserción. Una inserción no requiere desplazamiento alguno para abrir hueco.

Se define árbol compacto como: 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 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 no se permite la existencia de subárboles vacíos que sean hermanos por la derecha 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 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. En un árbol se hace según la relación predecesor/sucesor que se establece entre parejas de nodos, por lo que sólo hay una línea posible de recorrido.

En el árbol AVL de la figura, tras la inserción de DICIEMBRE, ¿qué nodo se considera crítico?. MARZO. Ninguna de las otras respuestas es verdadera. MAYO. AGOSTO.

SI O NO. SI PERO NO. NO PERO SI.

En los árboles Rojo-Negro ¿Qué postula la propiedad del camino?. Todo camino desde un nodo hasta cada uno de los nodos externos descendientes de él tiene el mismo número de nodos negros. Todo camino desde un nodo hasta cada uno de los nodos externos descendientes de él tiene el mismo número de nodos rojos. Todo camino desde el nodo raíz hasta cada uno de los nodos externos descendientes de él tiene el mismo número de nodos negros.

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

¿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 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. Ninguna de las otras respuestas es verdadera.

Determinar cuál de las siguientes armaciones es cierta en relación con la extracción en los árboles AVL: 1. Cuando se elimina un nodo a la derecha de un nodo con factor de equilibrio +1 puede necesitarse una rotación simple II. 2. Cuando se elimina un nodo a la derecha de un nodo con factor de equilibrio +1 puede necesitarse una rotación doble ID. 1: sí, 2: sí. 1: sí, 2: no. 1: no, 2: sí. 1: no, 2: no.

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

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