Lenguaje C | conjunto 5

Se han hecho las siguientes preguntas en el examen GATE CS 2008.

1. ¿Qué imprime el siguiente programa en C?

int f(int x, int *py, int **ppz)
{ 
  int y, z; 
  **ppz += 1;  
   z  = **ppz; 
  *py += 2; 
   y = *py;
   x += 3;
   return x + y + z;
}
  
void main()
{
   int c, *b, **a;
   c = 4; 
   b = &c;
   a = &b;  
   printf( "%d", f(c,b,a));
   getchar();
}

(A) 18
(B) 19
(C) 21
(D) 22

Respuesta (B)

/* Explanation for the answer */
  
  /*below line changes value of c to 5. Note that x remains unaffected 
    by this change as x is a copy of c and address of x is different from c*/
  **ppz += 1 
  
  /* z is changed to 5*/
  z  = **ppz;
  
  /* changes c to 7, x is not changed */ 
  *py += 2;
  
   /* y is changed to 7*/
  y = *py;   
  
  /* x is incremented by 3 */
   x += 3;   
  
  /* return 7 + 7 + 5*/
  return x + y + z; 

2. Elija la opción correcta para llenar ?1 y ?2 para que el programa a continuación imprima una string de entrada en orden inverso. Suponga que la string de entrada termina con un carácter de nueva línea.

void reverse(void)
 {
  int c;
  if (?1) reverse() ;
  ?2
}
main()
{
  printf ("Enter Text ") ;
  printf ("\n") ;
  reverse();
  printf ("\n") ;
}

(A) ?1 es (getchar() != ‘\n’)
?2 es getchar(c);
(B) ?1 es (c = getchar() ) != ‘\n’)
?2 es getchar(c);
(C) ?1 es (c != ‘\n’)
?2 es putchar(c);
(D) ?1 es ((c = getchar()) != ‘\n’)
?2 es putchar(c);

Answer(D)
getchar() se usa para obtener el carácter de entrada del usuario y putchar() para imprimir el carácter ingresado, pero antes de imprimir se llama a reverse una y otra vez hasta que se ingresa ‘\n’. Cuando se ingresa ‘\n’, las funciones de la pila de funciones ejecutan declaraciones putchar() una por una. Por lo tanto, el último carácter ingresado se imprime primero.
Puede intentar ejecutar el siguiente programa

void reverse(void); /* function prototype */
  
void reverse(void)
 {
  int c;
  if (((c = getchar()) != '\n')) 
    reverse();  
  putchar(c);
}
main()
{
  printf ("Enter Text ") ;
  printf ("\n") ;
  reverse();
  printf ("\n") ;
  getchar();
}

Para las preguntas 3 y 4, considere las siguientes funciones de C:

int f1(int n)
{
  if(n == 0 || n == 1)
    return n;
  else
    return (2*f1(n-1) + 3*f1(n-2));
}
  
int f2(int n)
{
  int i;
  int X[N], Y[N], Z[N] ;
  X[0] = Y[0] = Z[0] = 0;
  X[1] = 1; Y[1] = 2; Z[1] = 3;
  for(i = 2; i <= n; i++)
  {
    X[i] = Y[i-1] + Z[i-2];
    Y[i] = 2*X[i];
    Z[i] = 3*X[i];
  }
  return X[n] ;
}

3. El tiempo de ejecución de f1(n) y f2(n) son
(A) Θ(n) y Θ(n)
(B) Θ(2^n) y Θ(n)
(C) Θ(n) y Θ(2^n)
(D) Θ(2^n) y Θ(2^n)

Respuesta (B)
Para f1() , sea T(n) la función para la complejidad del tiempo.

  T(n) = T(n-1) + T(n-2) 

La recursividad anterior es una estándar para los números de Fibonacci . Después de resolver la recursividad, obtenemos

 T(n) = 1/sqrt(5)[(1 + sqrt(5))/2]^n - 1/sqrt(5)[(1 - sqrt(5))/2]^n 

La recursividad anterior también se puede escribir como Θ(1.618.^n)
(Consulte this ).

En f2() , hay un solo bucle, por lo que la complejidad del tiempo es Θ(n)

Entre las 4 opciones dadas, (B) parece la más cercana.

4. f1(8) y f2(8) devuelven los valores
(A) 1661 y 1640
(B) 59 y 59
(C) 1640 y 1640
(D) 1640 y 1661

Ambas funciones realizan la misma operación, por lo que la salida es la misma, significa que (B) o (C) es correcta.
f1(2) = 2*f1(1) + 3*f1(0) = 2
f1(3) = 2*f1(2) + 3*f1(1) = 2*2 + 3*1 = 7
f1( 4) = 2*f1(3) + 3*f1(2) = 2*7 + 3*2 = 20
f1(5) = 2*f1(4) + 3*f1(3) = 2*20 + 3 *7 = 40 + 21 = 61

Podemos omitir después de esto ya que la única opción restante es (C)
f1(6) = 2*f1(5) + 3*f1(4) = 2*61 + 3*20 = 122 + 60 = 182
f1(7) = 2*f1(6) + 3*f1(5) = 2*182 + 3*61 = 364 + 183 = 547
f1(8) = 2*f1(7) + 3*f1(6) = 2*547 + 3*182 = 1094 + 546 = 1640

Escriba comentarios si encuentra que alguna de las respuestas/explicaciones es incorrecta, o si desea compartir más información sobre los temas discutidos anteriormente.