PED - Tests

En la inserción de un elemento en un árbol 2-3, la altura del árbol resultado siempre crece (con respecto al árbol original) cuando la raíz del árbol original es un 3-nodo. V. F.

En la inserción de un elemento en un árbol 2-3-4, la altura del árbol resultado siempre crece (con respecto al árbol original) cuando laraíz del árbol original es un 4-nodo. V. F.

En el algoritmo de borrado de un elemento en un árbol 2-3-4, siempre queel nodo “q” sea 2-nodo hay que hacer reestructuraciones. V. F.

La complejidad temporal de la operación desapilar(vista en clase) utilizando vectores (con un índice que indica la cima de la pila) o utilizando listas enlazadas es la misma. V. F.

La semántica de la operación quita_hojasque actúa sobre un árbol binario y devuelve el árbol binario original sin sus hojas es la siguiente: VAR i, d: arbin; x: item; quita_hojas(crea_arbin( )) = crea_arbin( ) quita_hojas(enraizar(crea_arbin(), x, crea_arbin()) =enraizar(crea_arbin(), x, crea_arbin()) quita_hojas(enraizar(i, x, d)) = enraizar(quita_hojas(i), x, quita_hojas(d)). V. F.

Todo árbol mínimo es un árbol binario de búsqueda. V. F.

El grado de los árboles AVL puede ser +1, 0 ó -1. V. F.

Todo árbol binario de búsqueda es un árbol 2-3. V. F.

En un árbol 2-3-4 el máximo número elementos del nivel N es 3*2^(2N-2). V. F.

La especificación algebraica de la siguiente operación indica que se devolverá el número de elementos del conjunto multiplicado por 3 (C: Conjunto; x: Ítem): Operación(Crear) = 0 Operación (Insertar(C, x)) = 3 + Operación(C). V. F.

En el TAD Diccionario con dispersión cerrada, con función de redispersión “hi(x)=(H(x) + k(x)*i) MOD B”, con B=6 se puede dar la situación de que en una búsqueda no se acceda a todas las posiciones de la tabla. V. F.

En un Hash cerrado con factor de carga α, se cumple que 0 <= α <= 1. V. F.

En un montículo doble, un elemento “j” del montículo máximo es el simétrico de un único elemento “i” del montículo mínimo. V. F.

Un multigrafo es un grafo que no tiene ninguna restricción: pueden existir arcos reflexivos y múltiples ocurrencias del mismo arco. V. F.

:). V. F.

Para el tratamiento de errores en la especificación algebraica, se añaden funciones constantes que devuelven un valor del tipo que causa el error. V. F.

La complejidad temporal (en su caso peor) del siguiente fragmento de código es O(n2) int i, j, n, sum; for (i = 4; i < n; i++) { for (j = i–3, sum = a[i-4]; j <= i; j++) sum += a[j]; cout << “La suma del subarray “ << i-4 << “ es “ << sum << endl; }. V. F.

Es posible obtener una representación enlazada de una cola utilizando un único puntero que apuntará al fondo de la cola. V. F.

Dado un único recorrido de cualquier árbol, siemprees posible reconstruir dicho árbol. V. F.

El coste temporal en su peor caso de insertar una etiqueta en un árbol binario de búsqueda es logarítmica respecto a la altura del árbol. V. F.

La complejidadtemporal en el peor caso y en el mejor caso de la operación inserción en un AVL son lineal y logarítmica respecto al número de nodos en el árbol. V. F.

El borrado en un árbol AVL puede requerir una rotación en todos los nodos del camino de búsqueda. V. F.

Dado un árbol 2-3 de altura h con n items: 2^h -1 <= n <= 3^h -1. V. F.

Los nodos hoja de un árbol 2-3 han de estar en el mismo nivel del árbol. V. F.

Para que decrezca la altura de un árbol 2-3-4 en una operación de borrado, el nodo raíz y sus hijos tienen que ser 2-nodo. V. F.

Un árbol 2-3-4 es un árbol 4-camino de búsqueda. V. F.

La especificación algebraica de la siguiente operación indica que se devolverá el número de elementos del conjunto multiplicado por 3 (Operación(Conjunto) -> Natural; Var: C: Conjunto; x: Ítem): Operación(Crear) = 1 Operación (Insertar(C, x)) = 3 + Operación(C). V. F.

En un montículo el número de claves en el hijo izquierda de la raíz es mayor o igual que en su hijo derecha. V. F.

El siguiente árbol es un árbol máximo. V. F.

La siguiente secuencia de nodos de un grafo es un ciclo: 1,2,3,2,1. V. F.

Un bosque extendido en profundidad de un grafo dirigido al que se le añaden los arcos de retroceso es un grafo acíclico dirigido. V. F.

Se puede reconstruir un único árbol binario de búsqueda teniendo sus recorridos en preorden y postorden. V. F.

En C++, el puntero this se tiene que declarar en todos los constructores de la clase. V. F.

Para el siguiente fragmento de código C++ de un posible método perteneciente a la conocida clase TCoordenada, la línea “delete [ ] b;" liberaría correctamente la memoria dinámica de b. void TCoordenada::Funcion(void) { TCoordenada *a =new TCoordenada; TCoordenada *b = new TCoordenada[5]; (. . . . . . .) delete [ ] b; }. V. F.

En la especificación algebraica de los números naturales vista en clase, la sintaxis y la semántica de la operación de multiplicación (mult) es la siguiente: mult : natural natural --> natural VAR x, y: natural; mult(cero, x) = cero mult(x, cero) = cero mult(suc(y), x) = suma(mult(y, x), x). V. F.

La complejidad temporal en su peor caso de la operación apilar en una pila utilizando una representación enlazada siempre es lineal. V. F.

El resultado del cálculo de la complejidad temporal en el mejor caso de un algoritmo X, da como resultado n + n*log(n). Por lo tanto, diremos que la complejidad del algoritmo X cuando n -> ∞ pertenece a Ω (n). V. F.

La operación Examen que se aplica sobre cualquier pila y devuelve el segundo elemento que fue apilado en la pila es la siguiente: Examen(pila) -> item VAR p: pila, e,x: item; examen( crear( ) ) = error_item( ) examen( apilar(crear( ), x )) = error_item( ) examen( apilar( apilar (p,e ), x) ) = e. V. F.

El grado de un árbol es el máximo nivel que pueden tener sus subárboles. V. F.

Existe un único árbol binario completo que se puede construir a partir del recorrido en postorden. V. F.

La especificación algebraica vista en clase para el recorrido preorden, pero visitando primero la derecha y después la izquierda (RDI) es la siguiente: preorden( arbin ) -> lista VAR i, d: arbin; x: item; preorden( crea_arbin( ) ) = crea_lista( ) preorden( enraizar( i, x, d ) ) = concatenar( insiz( x, preorden( d ) ), preorden( i ) ). V. F.

Existe un único árbol binario de búsqueda que se puede construir a partir del recorrido en inorden. V. F.

La operación de buscar un elemento en un árbol binario de búsqueda tiene una complejidad temporal lineal en el mejor caso. V. F.

A los árboles multicamino de búsqueda también se les llama árboles generales. V. F.

Sea un árbol binario lleno cuyo recorrido en Inorden es: 10,15,17,20,21,28,35. La secuencia de árboles cuyas etiquetas son 35,28,20 es un CAMINO en el mencionado árbol. V. F.

Todo árbol completo cumple las condiciones para ser un árbol AVL. V. F.

Las rotaciones que hay que realizar en los árboles AVL para mantenerlos balanceados tienen un coste temporal (en su peor caso) lineal con respecto al número de items del árbol. V. F.

El número de nodos en un árbol AVL siempre es menor o igual que (2^h – 1) siendo h la altura del árbol. V. F.

Cuando se realiza una inserción en un árbol AVL, en el camino de vuelta atrás para actualizar los factores de equilibrio, como máximo solo se va a efectuar 1 rotación. V. F.

Las ecuaciones (vistas en clase) que permiten realizar la multiplicación de números naturales son las siguientes: VAR x, y: natural; mult(x, cero) = cero mult(suc(y), x) = suma(mult(y, x), x). V. F.

Para el siguiente fragmento de código C++ de un posible método perteneciente a la conocida clase TCoordenada, “delete [] a;" liberaría correctamente la memoria dinámica de a. void Funcion(void) { TCoordenada *a = new TCoordenada; TCoordenada *b = new TCoordenada[5]; (. . . . . . .) }. V. F.

La complejidad temporal del siguiente fragmento de código es O(n+p). int i, j, n, p, sum; for (i = 1; i < n; i++); for (j = 1, sum = a[i-4]; j <= p; j++) sum += a[j]; cout << “La suma del subarray “ << i-4 << “ es “ << sum << endl;. V. F.

La función de búsqueda BINARIA de un elemento en una lista ordenada con acceso por posición (utilizando una representación enlazada) que tiene “n” elementos tiene una complejidad temporal en su mejor caso de Ω(1). V. F.

Sea un árbol binario lleno cuyo recorrido en inorden es: 10,15,17,20,21,28,35. La representación secuencial de dicho árbol sería un vector de tamaño 8, en el que la posición 3 quedaría vacía. V. F.

En los árboles binarios de búsqueda, en el borrado de un elemento que tiene dos hijos, la siguiente ecuación de su especificación algebraica indica que dicho elemento se sustituye por el menor del subárbol izquierdo: si ( y==x ) y no esvacio( d ) y no esvacio( i ) entonces borrar( enraizar( i, x, d ), y ) = enraizar( i, min( d ), borrar( d, min( d ) ) ) fsi. V. F.

El número mínimo de nodos que tiene un árbol AVL de altura 4 es 7. V. F.

Dado un árbol 2-3 de altura 4, el menor elemento almacenado siempre estará en un nodo hoja. V. F.

Si h es la altura de un árbol 2-3-4 con n elementos se cumple que: log2 (n+1) ≤ h ≤ log4 (n+1). V. F.

La especificación algebraica de la inserción de un elemento en un conjunto sin claves repetidas sería la siguiente (C: Conjunto; x, y: Ítem): Insertar(Insertar(C, x), y) = Insertar(Insertar(C,y), x). V. F.

La dispersión abierta es más eficiente en cuanto al espacio en comparación con la dispersión cerrada, para el caso de almacenar 5 elementos y un tamaño de la tabla de B=10. V. F.

La raíz de un Heap máximo de n elementos representado como un vector de n posiciones (numeradas de 1 a n) estará en la posición número 1 del vector. V. F.

El número máximo de arcos que pueden existir en un grafo dirigido de n vértices son: n (n-1) + n. V. F.

Un bosque extendido en profundidad de un grafo dirigido al que se le añaden los arcos de avance es un grafo acíclico dirigido. V. F.

El algoritmo de intercambio directo o burbuja estudiado en clase (ordenación de los elementos de un vector) tiene una complejidad de Omega(n2), siendo n el número de elementos del vector. V. F.

La cota promedio de complejidad es el resultado de hacer la media entre la cota superior y la cota inferior. V. F.

La complejidad temporal (en su caso mejor) del siguiente fragmento de código es Omega(n) int i, length, n, i1, i2, k; for (i = 0, length = 1; i < n-1; i++) { for (i1 = i2 = k = i; k < n-1 && a[k] < a[k+1]; k++, i2++); if (length <i2 –i1 + 1) length = i2 –i1 + 1; }. V. F.

La complejidad temporal (en su peor caso) de la operación de insertar un elemento en una cola circular enlazada que no admite elementos repetidos es O(n), siendo n el número de elementos de la cola. V. F.

Un árbol con un único nodo es un árbol completo. V. F.

El nivel de la raíz en un árbol binario es 0. V. F.

Todo árbol binario mínimo es un árbol binario de búsqueda. V. F.

Un árbol binario de búsqueda completo es un AVL. V. F.

El número de rotaciones que se nos pueden dar en el borrado de un elemento en un AVL son como máximo 3 menos que la altura del árbol. V. F.

Dado un árbol 2-3 con n itemscon todos sus nodos del tipo 2-Nodo. La complejidad de la operación de búsqueda de un ítem en el mencionado árbol es O(log2n). V. F.

En un árbol 2-3-4 los nodos pueden tener 1, 2, 3 ó 4 hijos. V. F.

La mejor representación de los conjuntos siempre es el vector de bits porque es la más eficiente espacialmente. V. F.

Sea una tabla de dispersión cerrada con estrategia de redispersión hi(x)=(H(x) + C*i) MOD B, con B=1000 y C=74. Para cualquier clave “x” que se desee insertar, se recorrerán todas lasposiciones de la tabla buscando una posición libre. V. F.

El siguiente vector representa un montículo máximo: 10 5 3 1 2. V. F.

V. F.

Un digrafo es un multigrafo que no contiene arcos reflexivos. V. F.

La especificación algebraica de la operación longitud definida en clase para el tipo lista es la siguiente: VAR L1: lista; x: item; longitud( crear( ) ) = 0 longitud( inscabeza( L1, x ) ) = 1 + inscabeza(longitud( L1 ), x ). V. F.

En la especificación algebraica de un tipo de datos las operaciones modificadoras devuelven un valor de un tipo diferente al que se está definiendo. V. F.

Es posible reconstruir un único árbol binario de búsqueda de n elementos (n>1), a partir de su recorrido en inorden. V. F.

Sea un árbol binario lleno cuyo recorrido en inorden es: 10,15,17,20,21,28,35. La secuencia de árboles cuyas etiquetas son 35,28,20 es un camino en el mencionado árbol. V. F.

Un multigrafo es un grafo que no tiene ninguna restricción: pueden existir arcos reflexivos y múltiples ocurrencias del mismo arco. V. F.

El número máximo de arcos que pueden existir en un grafo dirigido de n vértices son: n (n-1) + n. V. F.

En un grafo dirigido, un ciclo es un camino simple en el que el vértice primero y último coinciden. V. F.

En la especificación algebraica, para definir la semántica de una operación de un tipo de datos sólo se pueden utilizar las operaciones generadoras constructoras. V. F.

El resultado del cálculo de la complejidad temporal en el mejor caso de un algoritmo X, da como resultado n + n*log(n). Por lo tanto, diremos que la complejidad del algoritmo X cuando n -> § pertenece a Omega(n). V. F.

El TAD vector visto en clase se define como un conjunto ordenado de pares <índice, valor>. Para cada índice definido dentro de un rango finito existe asociado un valor. V. F.

En un árbol AVL cuyo nodo raíz tiene un factor de equilibrio +1 siempre que se inserte un nuevo elementohay que realizar una rotación. V. F.

Todo árbol completo es un árbol completamente equilibrado. V. F.

En un árbol 2-3, la altura siempre disminuye si la raíz es de tipo 2-nodo y al efectuar el borrado de un elemento es necesario realizar una combinación con el nodo raíz. V. F.

La operación de borrar un elemento en un árbol 2-3-4 finaliza cuando el nodo p es el nodo que contiene al elemento que se desea borrar. V. F.

La complejidad en su caso peor, de la unión de dos conjuntos implementados como listas no ordenadas de tamaño “n” y “m” respectivamente es de O(n*m). V. F.

Cuando implementamos un TAD Tabla de dispersión cerrada se usa una función de dispersión H tal que H(x) devolverá un valor comprendido entre 0 y B, siendo B el número finito de clases en las que dividimos el conjunto. V. F.

El montículo mínimo o HEAP mínimo es un árbol binario completo que además es árbol mínimo. V. F.