APROBAR PED

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

Concatenar(lista,lista), inscabeza(lista,item) y crear_lista() son operaciones constructoras modificadores de tipo lista. V. F.

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

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

La complejidad temporal, en su peor caso, del recorrido por niveles en un árbol binario es la misma que las de los recorridos in-pre-post orden. V. F.

Un árbol binario completo en un AVL. V. F.

El número máximo de nodos de un árbol AVL de altura 10 sería de 1023. V. F.

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

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

La estructura de un árbol 2-3-4 con 2^h -1 elementos, donde "h" es la altura del árbol, se corresponde con la estructura de un árbol binario de búsqueda lleno. V. F.

Tras la inserción en un árbol 2-3, la altura del árbol sólo aumenta cuando todos los nodos del árbol tienen dos hijos. V. F.

Dado un árbol 2-3, si la clave a borrar "x" está en un nodo hoja, "x" se tendría que sustituir por la clave siguiente a "x" en el recorrido en inorden del árbol. V. F.

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

En los conjuntos representado como listas no ordenadas, la complejidad temporal de la operación "diferencia de conjuntos" es 0(n), siendo n el número de elementos de cada conjunto. V. F.

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

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

La complejidad temporal del caso peor de la inserción en un Heap de altura h será de 0(h). V. F.

En C++, la forma canónica de una clase debe contener el operador "==". V. F.

La complejidad temporal (en su peor caso) del siguiente fragmento de código es 0(n^2) 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 << "MISCO JONES << endl;. V. F.

crear_pila(), cima(pila), apilar(pila,item) y desapilar(pila) son operaciones constructoras del tipo pila. V. F.

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

La siguiente operación borrar definida para listas borra el elemento que está a la derecha del elemento apuntado por la posición p: borrar(lista, posición)->lista VAR L1,L2: lista; x: item; p:posicion; borrar(crear(),p) = crear() si p == primera(inscabeza(L1,x)) entonces borrar(inscabeza(L1,x),p) = inscabeza(L1,x) si no borrar(inscabeza(L1,x),p) = inscabeza(borrar(L1,p),x). V. F.

En C++, cuando se sobrecarga un operador que modifica al operando izquierda(por ejemplo, el operador asignación), no se debe crear un objeto temporal que luego el método devuelva por valor. V. F.

El ítem medio (según la relación de orden de los elementos) almacenado en un árbol binario de búsqueda lleno siempre se encuentra en la raiz. V. F.

En un árbol AVL cuya raíz tiene un factor de equilibrio de +1, al insertar un elemento en el subárbol izquierdo de la raíz, el árbol siempre vuelve al estado de equilibrio (FE == 0). V. F.

Un árbol AVL completo es un árbol completamente equilibrado. V. F.

En el algoritmo del borrado de un elemento en un árbol 2-3-4 siempre que "p" sea 2-nodo hay que hacer reestructuración. V. F.

La complejidad temporal en el peor caso de la operación inserción en un árbol 2-3-4 es log2(n+1). 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.

El TAD Cola de prioridad en el que no se permiten elementos repetido, representado por una lista desordenada, tendrá coste 0(n) para la inserción, con n el número de elementos del TAD. 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.

La representación de un grafo mediante una lista de adyacencia siempre va a ser mejor tanto espacial como temporalmente que la representación que la representación mediante una matriz de adyacencia. V. F.

Un árbol binario de búsqueda completo con 4 elementos también es un montículo o HEAP mínimo. V. F.

Un árbol extendido en anchura de un grafo dirigido tiene el mismo números de vértices que el grafo original. V. F.

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

En C++, el constructor de copia se puede invocar:(1) de forma explícita en la declaración de una variable; (2) en el paso por valor de un objeto en una función; (3) en la devolución de un objeto por valor en una función. V. F.

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

Sea el conjunto de los números naturales definidos en clase. La sintaxis y la semántica de la operación factorial de un número natural es la siguiente: Var x: natural factorial: natural -> natural factorial(cero) = suc(cero) factorial(suc(x)) = suc(multiplicación(x, factorial(x)). V. F.

Sea la operación mismalongitud que actúa sobre dos instancias del TAD pila definido en clase. Dicha operación determina si las dos instancias contiene el mismo número de elementos. La especificación algebraica para misma longitud es la siguiente: mismalongitud: pila, pila -> booleano; VAR p1, p2: pila, x, y : item mismalongitud(crear_pila, crear_pila) = VERDADERO mismalongitud(apilar(p1,x), crear_pila) = FALSO mismalongitud(crear_pila, apilar(p1, y)) = FALSO mismalongitud(apilar(p1,x), apilar(p2, y)) ) = mismalongitud(p1,p2). V. F.

Sea el vector de números naturales definido en clase. La operación EliminaImpares, que borra las posiciones impares del vector marcándolas con "0", se define así: (Nota: se asume que existen las operaciones básicas de los números naturales incluida MOD) EliminaImpares: vector-> vector EliminarImpares(crear_vector()) = crear_vector() si (i MOD 2 ) == 1 entonces EliminaImpares(asig(v,i,x)) = asig(EliminaImpares(v),i,0) si no EliminaImpares(asign(v,i,x)) = asig(EliminaImpares(v),i,x). V. F.

Las operaciones constructoras generadoras de un TAD permiten obtener, por aplicaciones sucesivas, cualquier valor de dicho TAD. V. F.

La complejidad temporal (en su caso promedio) del siguiente fragmento de código es Θ(n^2) (La varibable a representa un vector de enteros de tamaño n) int i, lenght, n, i1, i2, k; n = 20; for(i = 0, lenght = 1; i < n-1; i++) for(i1 = i1 = k = i; k < n-1 && a[k] < a[k+1]; k++, i2++) if(lenght <i2-i1+1) length = i2 - i1+1. V. F.

En una cola circular enlazada, el elemento apuntado por fondo es el primero a desencolar. V. F.

El subárbol que representa la raíz de un árbol binario tiene un ascendiente propio. V. F.

El grado de un árbol es el grado mínimo de todos los nodos de ese árbol. V. F.

El nivel de un nodo en un árbol coincide con la longitud del camino desde la raíz a dicho nodo. V. F.

El máximo número de nodos en un nivel i-1 de un árbol binario es 2î-2, i >= 2. V. F.

Es posible reconstruir un único árbol binario de búsqueda con altura 5 y 30 nodos teniendo su recorrido en preorden. 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(i)), preorden(d)). V. F.

Siempre es posible reconstruir un único árbol binario teniendo sus recorridos en preorden, postorden y niveles. V. F.

La siguiente especificación corresponde a la operación de borrar una arista en un multigrafo: VAR G: grafo; a, b, z, t: Vértice; p: Ítem; BorrarArista( crearGrafo(), z, t) = crearGrafo() BorrarArista( InsertarArista(G,a,b,p),z,t) = si ( a==z) y (b == t) entonces borrarArista(G,z,t) si no InsertarArista(BorrarArista(G,z,t),a,b,p). V. F.

Los árboles extendidos en anchuras de un grafo dirigido tienen que ser necesariamente árboles binario. V. F.

Dado un digrafo implementado meidante lista de adyacencia en el que sabemos que nunca habrá más de 2n arcos (siendo n el número de vértices), el cálculo de la adyacencia de entrada de un vértice tiene una cota de complejidad temporal 0(n). V. F.

La siguiente especificación corresponde a la operación unión de conjuntos: VAR a, b: Conjuntos; x:item Union(crear(), A) = A Union(insertar(a,x),b) = si(pertenece(b,x)) entonces Union(a,b) si no Insertar(Union(A,b),x). V. F.

La función de redispersión en una tabla de dispersión abierta(hash abierto), para que se recorran en todas las posiciones del vector, tiene que cumplir que el valor de B sea primo. V. F.

En una tabla de dispersión cerrada(hash cerrado), al insertar un elemento, se puede producir colisiones con claves sinónimas y con claves no sinónimas. V. F.

En un montículo doble todas las claves del montículo máximo son mayores que las del montículo mínimo. V. F.

Para todos los nodos de un montículo simple, se cumple que el número de nodos de un subárbol derecho es menor o igual que el número de nodos de un subárbol izquierdo. V. F.

Según el algoritmo de borrado de un árbol 2-3-4 visto en clase, la altura de un árbol 2-3-4 sólo decrece cuando al borrar un ítem, los punteros p, q y r son 2-nodo. V. F.

Según el algoritmo de inserción de un árbol 2-3-4 visto en clase, la altura de un árbol 2-3-4 sólo crece cuando al insertar un ítem, todos los nodos del camino de búsqueda desde la raíz hasta la hoja donde se inserta el ítem son 4-nodo. V. F.

Existe un único árbol 2-3 de altura 3 que representa a las etiquetas del 1 al 9. V. F.

Siempre es posible reconstruir un único árbol AVL teniendo su recorrido en postorden. V. F.

La función de búsqueda BINARIA de un elemento en una lista ordenada podría alcanzar una complejidad temporal 0(log2n). V. F.

El algoritmo de intercambio directo o burbuja estudiando en clase (ordenación de los elementos de un vector) tiene una complejidad promedio de Θ(n^2), siendo n el número de elementos del vector. V. F.

La semántica de la operación obtener en una lista con acceso por posición es la siguiente(IC = InsertarCabeza(Lista, Ítem), p: posicion, l1:lista, x:ítem): obtener(crear(), p) = error_item() si p == primera(IC(l1,x)) entonces obtener(IC(l1,x),p)=x si no obtener(IC(l1,x),p) = IC(obtener(l1,p),x). V. F.

En la especificación algebraica, una operación es una función que toma como parámetros(entrada) uno o más valores de diversos tipos, y produce como resultado un solo valor de otro tipo. V. F.

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

En C++, si se declara un objeto a (p. ej. TPoro a;) cuando la variable a se sale de ámbito entonces se invoca automáticamente al destructor de ese objeto. 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 en las misma. V. F.

En las colas circulares enlazadas vistas en clase, las operaciones encolar y desencolar tienen complejidad temporal Θ(1). V. F.

Es posible reconstruir un único árbol binario de búsqueda a partir de un recorrido en preorden. V. F.

Un camino en un árbol, es una secuencia a1,a2... de árboles tal que para todo i € {1,...,s-1} a1 es subárbol de ai+1. V. F.

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

Profundidad de un subárbol es la longitud del único camino desde la raíz a dicho subárbol. 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.

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

El grado de los árboles AVL puedes ser +1,0 o -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 de elementos del nivel N es 3*2^2n-n. V. F.

En un Hash cerrado con factor de carga alfa, se cumple que 0 <= alfa <= 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 de un mismo arco. V. F.