examen edp2.1

Respecto a la búsqueda binaria, ¿qué respuesta considera verdadera?. 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. 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. 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 secuencial es la búsqueda binaria.

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

Qué intenta hacer el siguiente trozo de pseudocódigo?. a. Buscar un valor. b. Insertar un valor. c. Borrar un valor.

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

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

Sea N el nodo raíz... factor de equilibrio 1, y sea $N_i$ su hijo izquierdo (factor 0). Se inserta un elemento en el subárbol izquierdo de $N_i$. a. Ninguna de las otras respuestas es verdadera. b. Es necesario reequilibrar en N con una rotación doble. c. El nodo crítico a considerar es $N_i$, no N. d. Es necesario un reequilibrado en $N_i$.

Si en el árbol AVL equilibrado... se practica una extracción en el subárbol derecho de A y una rotación simple izquierda... ¿qué característica relevante destacaría?. a. 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. b. 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. c. 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. d. 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.

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

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

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

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

¿Qué hay que hacer para restablecer las propiedades del árbol en la situación de la figura? (Árbol con nodos P y N rojos). a. Rotación simple + Recoloración + Solucionado. b. Recoloración + Propagación. c. Recoloración + Solucionado. d. Rotación doble + Recoloración + Solucionado.

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

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

¿En cuántos pasos se resuelve una extracción en un árbol AVL?. a. En O(n^2) pasos. b. En O(log_2 n) pasos. c. En O(n) pasos. d. En O(n\log_2 n) pasos.

En un árbol binario, ¿qué respuesta considera verdadera?. a. Si se restringe a uno el grado máximo de un nodo surge el árbol binario. b. Un árbol binario es un conjunto finito de m nodos $(m\ge0)$, 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. c. Un árbol binario es un conjunto finito de m nodos $(m\ge0)$, 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. d. Si se restringe a dos el grado máximo de un nodo, surge el árbol binario.

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

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.

Respecto a la búsqueda binaria, ¿qué respuesta considera verdadera?. a. Ninguna de las otras respuestas se 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 $N/2$, donde N es el número de elementos del conjunto. c. 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. d. 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_{2}N. donde N es el número de elementos del conjunto.

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

A partir de un árbol AVL vacío, insertar la secuencia: 1, 3, 5, 7, 9, 4. I. ¿Qué clave ocupa la raíz? II. ¿Cuál es su factor de equilibrio?. a. I: 5, II: 0. b. 1: 3, II: 1. c. 1: 5, II: 1. d. 1: 3, II: -1.

La estructura arbórea de la figura, ¿qué expresión representa de forma implícita en un ordenador?. a. $(B^{*}C)+(D-H/Z).$. b. $(B^{*}C)+D-H/Z$. c. $(B^{*}C)+D-(H/Z).$. d. $B^{*}C+D-H/Z.$.

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

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?. a. Que quedan recogidas en los nodos hojas de la estructura, por lo que no es necesario jugar con demasiados nodos internos. b. Que quedan recogidas en la estructura, por lo que no es necesario representar paréntesis. c. Que quedan recogidas en los paréntesis de la estructura, por lo que no es necesario jugar con demasiados nodos. d. No presenta ventaja adicional alguna.

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

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

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.

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

Respecto a la extracción en los árboles binarios de búsqueda como contenedores, ¿qué respuesta considera verdadera?. a. 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. b. 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 cercano y así alterar el árbol lo menos posible. c. Cuando ninguno de los subárboles del nodo a extraer esté vacío lo menos adecuado es sustituir el valor del nodo a extraer por el valor del sucesor o del predecesor en orden símétrico. d. 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.