Parcial PED

Las operaciones constructoras modificadoras permiten generar, por aplicaciones sucesivas, todos los valores del TAD a especificar. V. F.

Dada la sintaxis de la función IC(lista,item)  lista, que inserta un elemento a la cabeza de la lista pasada como parámetro y crear() lista, que crea una lista vacía. La siguiente secuencia: IC(IC(IC (crear(),a),b),c), daría como resultado una lista con los elementos en este orden: abc (siendo a el primer elemento de la lista). V. F.

La complejidad temporal (en su caso promedio) del siguiente fragmento de código es omega(n2) int i, length, n, i1, i2, k; n=20; 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.

Paso de programa es una secuencia de operaciones con contenido semántico cuyo coste es dependiente de la talla del problema. V. F.

La semántica de la operación base (vista en clase) que actúa sobre una pila y devuelve el primer elemento apilado es la siguiente (p: pila, x: ítem): base(crear())=error_item() base(apilar(crear(),x))=x base(apilar(p,x))=base(p. V. F.

Las colas también se conocen como listas FIFO. V. F.

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

La profundidad de un subárbol es la longitud del único camino desde la raíz a dicho subárbol. V. F.

Cuando realizamos un recorrido por niveles en un árbol binario de búsqueda las etiquetas aparecen ordenadas de menor a mayor. V. F.

Suponiendo que tenemos un árbol binario de búsqueda lleno con n elementos (siendo n impar), la búsqueda del elemento que ocupa la posición n/2(parte entera)+1 según la relación de orden, se realiza en tiempo logarítmico. V. F.

Según la especificación algebraica del ABB vista en clase, esta ecuación que forma parte del borrado de un elemento es correcta: si ( y==x ) y no esvacio( d ) y no esvacio( i ) entonces borrar( enraizar( i, x, d ), y ) = enraizar(borrar(i, max(i)) , max(i) , d ) fsi Siendo max(i) una operación que se aplica sobre un ABB y devuelve el ítem mayor de dicho ABB. V. F.

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

En el vector de dimensión n (siendo el número de elementos del árbol) que representa de forma secuencial un árbol binario completo pueden existir posiciones vacías. V. F.

La semántica de la operación multiplicación de números naturales vista en clase es la siguiente: mult(cero, x) = cero mult(x, cero) = cero mult(suc(y), x) = suma(mult(y, x), 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ónde números naturales son las siguientes:VAR x, y: natural;mult(cero, x) = ceromult(x, cero) = ceromult(suc(y), x) = suma(mult(y, x), x). V. F.

En la especificación algebraica, para el tratamiento de errores se añade una constante a la signatura que modeliza un valor de error, por ejemplo ERRORnat-> natural. V. F.

En C++, si se declara un objeto a(p. ej. TPoro a;) cuando la variable ase sale de ámbito entonces se invoca automáticamente al destructor de ese objeto. V. F.

Las ecuaciones (vistas en clase) para la operación recude un vector son las siguientes:recu( crear( ), i ) = error( )recu( asig(v, i, x ), j ) si ( i == j ) entoncesjsi norecu( v, j ) fsi. 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 complejidad temporal 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.

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

Las ecuaciones (vistas en clase) para la operación desencola rson las siguientes: desencolar( crear( ) ) = crear( ) si esvacia( c ) entonces desencolar( encolar( c, x ) ) = crear ( ) si no desencolar( encolar( c, x ) ) = encolar( desencolar ( c ), x ). 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, ..., asde árboles tal que para todo i {1, ..., s-1}, aies subárbol de ai+1. V. F.

A los árboles generales también se les llama árboles multicamino de búsqueda. 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.

Profundidad de un subárbol es la longitud del único camino desde la raíz a dicho subárbol. V. F.