PED tests

Utilizando la especificación algebraica de los números naturales vista en clase, la sintaxis y la semántica de la operación de división que calcula el cociente de dos números naturales es la siguiente (Nota: se asume que para resta y división el primer argumento es mayor que el segundo y que el cociente de la división es entero y exacto): resta, division: natural , natural  natural VAR x, y: natural; resta(x, cero) = x resta(suc(x),suc(y)) = resta(x,y) division(x,cero)=error_natural division(x,x)=suc(cero) division(x,y)=division(resta(x,y),y). V. F.

En C++, un destructor devuelve 0 si el objeto se destruye correctamente y un valor distinto de 0 en caso contrario. V. F.

La función de búsqueda BINARIA de un elemento en un vector desordenado tiene una complejidad temporal O(log2 n). V. F.

La operación subconjunto_impares que se aplica sobre un conjunto de números naturales, definida a continuación, devuelve el subconjunto formado por los números impares que existen en el conjunto original (Nota: Se asume que está definida la operación MOD para calcular el resto de la división entera): subconjunto_impares: conjunto  conjunto Var C: conjunto; x: natural; subconjunto_impares(crear_conjunto()) = crear_conjunto() subconjunto_impares(Insertar(C,x))= si (x MOD 2 ==suc(cero)) entonces Insertar(subconjunto_impares(C),x) si no subconjunto_impares(C) division(x,y)=division(resta(x,y),y). V. F.

Se puede reconstruir un único árbol binario de búsqueda teniendo su recorrido en preorden. V. F.

Un árbol binario de búsqueda con 3 elementos siempre será un árbol completo. V. F.

Un árbol binario de búsqueda equilibrado respecto a la altura tiene una complejidad temporal en su peor caso en la operación de búsqueda de O(log2(n)), con n el número de elementos del árbol. V. F.

En la operación de borrado de un elemento en un árbol AVL, si se realiza una rotación doble siempre decrece la altura del subárbol sobre el que se ha realizado la rotación. V. F.

La altura de un árbol 2-3 únicamente crece cuando se inserta un elemento y todos los nodos del árbol son 3-nodo. V. F.

Dado un árbol 2-3 con n items con todos sus nodos del tipo 3-nodo: la complejidad temporal en su peor caso de la operación de búsqueda de un ítem es O(log3 (n+1)). V. F.

Todo árbol binario completo es un árbol 2-3-4 donde todos sus nodos son 2-nodo. V. F.

En el borrado de un elemento en un árbol 2-3-4 sólo se reduce la altura del árbol cuando p, q y r son 2-nodo. V. F.

La complejidad temporal en su peor caso de la diferencia de dos conjuntos de cardinalidad “n”, representados como listas ordenadas, es de O(n). V. F.

La dispersión abierta elimina el problema del clustering secundario. V. F.

Cuando utilizamos una tabla de dispersión abierta de tamaño B, el número máximo de elementos que se pueden almacenar está limitado a B elementos. V. F.

La definición de un Heap Mínimo indica que ha de ser un árbol binario que además es árbol mínimo. V. F.

Una aplicación de los Grafos Acíclicos Dirigidos es la representación de órdenes parciales. V. F.

En la definición de Tipo Abstracto de Datos: "La manipulación de los datos sólo depende del comportamiento descrito en su especificación (qué hace) y es independiente de su implementación (cómo se hace)". V. F.

En una cola representada a partir de una lista enlazada simple con un único puntero al principio de la lista (cabeza de la cola), todas las operaciones de la cola (Cabeza, Encolar, Desencolar y EsVacía) tienen una complejidad de O(1). V. F.

El máximo número de nodos en un árbol binario de altura k-1 es 2k - 1, k > 1. V. F.

Dado el recorrido por niveles de un árbol binario de altura 7 y 64 hojas es posible reconstruir un único árbol binario. V. F.

Un árbol está equilibrado respecto a la altura si y solo si para cada uno de sus nodos ocurre que las alturas de los dos subárboles difieren como mucho en 1. V. F.

Dado un árbol 2-3 de altura h con n items se cumple que: 3h -1 < n < 2h -1. V. F.

En el algoritmo de borrado en un árbol 2-3-4 siempre que q sea 2-nodo hay que hacer una COMBINACIÓN o una ROTACIÓN. V. F.

Utilizando la representación de conjuntos mediante vectores de bits, la operación de búsqueda de un elemento tiene una complejidad espacial equivalente al tamaño del conjunto universal. V. F.

La especificación algebraica de la siguiente operación eliminaría todas las ocurrencias de un determinado ítem (C: ConjuntoConClavesRepetidas; x, y: Ítem): Eliminar(Crear, x)  Crear Eliminar(Insertar(C, x), y)  si (x == y) entonces Eliminar(C, y) sino Insertar(Eliminar(C, y), x). V. F.

Sea una tabla de dispersión cerrada con función de dispersión H(x)=x MOD B, con B=100 y “x” un número natural entre 1 y 2000. Sólo hay un valor de “x” que haga H(x)=4. V. F.

En la dispersión abierta sólo se producen colisiones entre claves sinónimas. V. F.

El TAD Cola de Prioridad representado por una lista desordenada, tendrá coste O(1) para la operación de borrado de un elemento. V. F.

En un montículo de altura k el número total de elementos es 2k -1. V. F.

Al representar un grafo de N vértices y K aristas con una lista de adyacencia, la operación de hallar la adyacencia de entrada de un vértice tiene una complejidad de O(K). V. F.

Un bosque extendido en profundidad de un grafo no dirigido es un grafo acíclico. V. F.

En la especificación algebraica de un TAD sólo las operaciones constructoras generadoras y las operaciones consultoras necesitan definir su semántica. V. F.

La complejidad temporal en su peor caso de las operaciones apilar y desapilar de una pila utilizando una representación enlazada (con punteros a nodo) es lineal respecto al tamaño de la pila. V. F.

La semántica de la operación anterior vista en clase es la siguiente: VAR L1: lista; x: item; p: posicion; anterior( L1, primera( L1 ) ) = error_posicion( ); si p != ultima( L1 ) entonces anterior( L1, siguiente( L1, p ) ) = p anterior( inscabeza( L1, x ), primera( L1 ) ) = primera( inscabeza( L1, x ) ). V. F.

El grado de un árbol 2-3-4 es el máximo número de etiquetas que puede tener un nodo de dicho árbol más uno. V. F.

La semántica de la operación nodos del tipo arbin vista en clase es la siguiente: VAR i, d: arbin; x: item; nodos( crea_arbin( ) ) = 0 nodos( enraizar( i, x, d ) ) = nodos( i ) + nodos( d ). V. F.

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

Dado un recorrido en postorden se puede reconstruir más de un árbol AVL. V. F.

Dado un árbol 2-3 de altura h con n items con todos sus nodos del tipo 2-Nodo: la complejidad de la operación de búsqueda de un ítem en su peor caso es O(log2 h). V. F.

En un árbol 2-3-4 de altura h, el máximo número de nodos se da cuando todos los nodos son de tipo 2-nodo. V. F.

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

El factor de carga (α) de una tabla hash con dispersión cerrada cumple que 0  α  1. V. F.

En la tabla hash con dispersión cerrada, con función de redispersión “hi(x)=(H(x) + k(x)*i) MOD B”, “B=10” y “k(x)=(x MOD B-1)+1”, para la clave x=2 se recorrerán todas las posiciones de la tabla buscando una posición libre. V. F.

El TAD Cola de Prioridad en el que no se permiten elementos repetidos, representado por una lista ordenada, tendrá coste O(n) para la inserción, con n el número de elementos del TAD. V. F.

En un montículo doble de altura h se pueden almacenar como máximo 2h -1 claves. V. F.

Al representar un grafo no dirigido con una matriz de adyacencia, su diagonal principal siempre tendrá valores FALSO. V. F.

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 la raí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 que el 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_hojas que 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.

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 un árbol 2-3-4 el máximo número elementos del nivel N es 3*2^(2N-2). 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.

Sea G=(V,A) un grafo dirigido. Diremos que G”=(V”,A”) es un árbol extendido de G  V”=V, A” A,  vV”  gradoE(v)  1. V. F.

La complejidad temporal (en su caso mejor) del siguiente fragmento de código es (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 items con 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(log2 n). 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 las posiciones 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.

Sea G=(V,A) un grafo dirigido. Diremos que G”=(V”,A”) es un árbol extendido de G  V”=V, A” A,  vV”  gradoE(v)  1. 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.

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, siempre es 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 complejidad temporal 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 montículo 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.