EJERCICIOS A DESARROLLAR DEL ECAES

7. Dada la siguiente instrucción for (A y D son condiciones; C y E son instrucciones; A, D, C, E

no modifican el valor de i):

for (i= 1; i<=1000; i= i+1)

    if (A) C;

      else if (D) E;

          else C;

Si A es cierta con probabilidad 0.6 y D es cierta con probabilidad 0.8, el número esperado de ejecuciones de C, es

A. 80

B. 480

C. 600

D. 920

E. 680

 La respuesta es E. 680 , la justificación es la siguiente:

 P(A) =0,6 ,  P(A^C)=0.4

 P(D) =0.8 ,  P(D^C)=0.2

 C ocurre cuando se da A y cuando no se da D, después de no haberse llevado acabo A, es  decir, se tiene la suma:  

10. Indique cuál de los siguientes fragmentos de programa es correcto con respecto a la especificación

(x mod y es el residuo de la división entera de x por y):

Pre: Existe k (k>=0): pot == 2^k

Pos: pot == 1

A. while (pot/2 == 0) pot= pot mod 2;

B. while (pot mod 2 == 0) pot= pot/2;

C. while (2 mod pot == 0) pot= pot/2;

D. if (pot mod 2 == 0) pot= 1;

else pot= 0;

E. if (pot/2 == 0) pot= 1;

else pot= 0;

 La respuesta es B , la justificación es la siguiente:

Si tomamos la precondición pot == 2^k    con k=0 y la aplicamos al programa en B obtenemos pot=2⁰ = 1 se cumple la postcondicion.

Si k=n , entonces pot == 2ⁿ y en el primer ciclo se tiene

while(2ⁿ mod 2= =0){

pot = 2ⁿ/2 = 2^n-1 }

en el segundo ciclo pot = 2^n-1/2 = 2^n-2 . Hasta llegar a 2^n-n =2⁰=1 cumpliendose la postcondicion .

12. María escoge un número entre 1 y 64. Pedro debe identificar el número haciendo preguntas que se responden con un «sí» o con un «no».

Pedro sabe que María siempre responde con la verdad. Si Pedro usa una estrategia óptima ¿cuántas preguntas debe hacer en el peor de los casos?

A. 1

B. 32

C. 6

D. 5

E. 7

La respuesta es C , la justificación es la siguiente:

Si pedro utiliza el algoritmo de búsqueda binaria para el peor de los casos, tiene un problema de tamaño   n= ultimo-primero +1

               n = 64- -1+1= 64

con w(n)  comparaciones   , W(n)= ┌ lg(n) ┐   es decir  W(64)= ┌ lg(64) ┐  =┌6┐  =6

13. El siguiente programa calcula en r el producto de dos números a y b mediante

sumas:

/* Q: b > 0 */

r= 0;

n= b;

while (n!=0){

r= r+a;

n= n-1;

}

/* R: r == ab */

De las siguientes aserciones, es un invariante para el ciclo

 A. r == b(a-n)

B. r == a(b-n)

C. r == b 2 -bn

D. r == ab-n

E. r == an-ab

La respuesta es B , la justificación es la siguiente:

La condición  r == a(b-n)   se cumple antes , durante y después del ciclo.

 Veamos :

 Antes  :

r =0 =a*0=a*(b-b)=a*(b-n)

 Durante :

r= r+a=0+a= a*1=a*( b-n)    donde n=n-1 y n= b  , entonces 1=b-n

Después:

r = a(b-(b-1))=a*(1)=a