Estructuras de datos y algoritmos | Conjunto 31

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

1) ¿Cuál es el valor de retorno de f(p, p) si el valor de p se inicializa a 5 antes de la llamada? Tenga en cuenta que el primer parámetro se pasa por referencia, mientras que el segundo parámetro se pasa por valor.

int f(int &x, int c) {
   c  = c - 1;
   if (c == 0) return 1;
   x = x + 1;
   return f(x, c) * x;
} 

(A) 3024
(B) 6561
(C) 55440
(D) 161051

Respuesta (B)
Dado que c se pasa por valor yx se pasa por referencia, todas las funciones tendrán la misma copia de x, pero diferentes copias de c.

f(5, 5) = f(x, 4)*x = f(x, 3)*x*x = f(x, 2)*x*x*x = f(x, 1)*x*x *x*x = 1*x*x*x*x = x^4

Dado que x se incrementa en cada llamada de función, se convierte en 9 después de la llamada f(x, 2). Entonces, el valor de la expresión x^4 se convierte en 9^4, que es 6561.

#include <stdio.h>
  
int f(int &x, int c)
{
    c  = c - 1;
    if (c == 0) return 1;
    x = x + 1;
    return f(x, c) * x;
}
int main()
{
    int p = 5;
    printf("%d", f(p, p));
}

1) La secuencia transversal de orden previo de un árbol de búsqueda binaria es 30, 20, 10, 15, 25, 23, 39, 35, 42. ¿Cuál de las siguientes es la secuencia transversal de orden posterior del mismo árbol?
(A) 10, 20, 15, 23, 25, 35, 42, 39, 30
(B) 15, 10, 25, 23, 20, 42, 35, 39, 30
(C) 15, 20, 10, 23 , 25, 42, 35, 39, 30
(D) 15, 10, 23, 25, 20, 35, 42, 39, 30

Respuesta (D)
El siguiente es el árbol construido

            30
         /      \
        20       39 
       /  \     /  \
     10    25  35  42  
      \   /
      15 23

3) Considere la siguiente función

 int unknown(int n) {
    int i, j, k = 0;
    for (i  = n/2; i <= n; i++)
        for (j = 2; j <= n; j = j * 2)
            k = k + n/2;
    return k;
 }

¿Cuál es el valor devuelto de la función anterior?
(A) Θ(n^2)
(B) Θ(n^2Log)
(C) Θ(n^3)
(D) Θ(n^3Log)

Respuesta (B)
El bucle exterior se ejecuta n/2 o Θ(n) veces. El bucle interno ejecuta Θ (Logn) veces (tenga en cuenta que j se divide por 2 en cada iteración). Así que la declaración «k = k + n/2;» ejecuta Θ(nLogn) veces. La declaración aumenta el valor de k en n/2. Entonces el valor de k se convierte en n/2*Θ(nLogn) que es Θ(n^2Logn)

4) El número de elementos que se pueden ordenar en tiempo Θ(logn) usando la ordenación de heap es
(A) Θ(1)
(B) Θ(sqrt(logn))
(C) Θ(Log n/(Log Log n) )
(d) Θ(Log n)

Respuesta (C)
La complejidad temporal de Heap Sort es Θ(mLogm) para m elementos de entrada. Para m = Θ(Log n/(Log Log n)), el valor de Θ(m * Logm) será Θ( [Log n/(Log Log n)] * [Log (Log n/(Log Log n) )] ) que será Θ( [Log n/(Log Log n)] * [ Log Log n – Log Log Log n] ) que es Θ(Log n)

5) El procedimiento que se indica a continuación es necesario para buscar y reemplazar ciertos caracteres dentro de una string de caracteres de entrada proporcionada en la array A. Los caracteres que se reemplazarán se proporcionan en la array oldc, mientras que sus respectivos caracteres de reemplazo se proporcionan en la array newc. La array A tiene una longitud fija de cinco caracteres, mientras que las arrays oldc y newc contienen tres caracteres cada una. Sin embargo, el procedimiento es defectuoso.

void find_and_replace(char *A, char *oldc, char *newc) {
    for (int i = 0; i < 5; i++)
       for (int j = 0; j < 3; j++)
           if (A[i] == oldc[j]) A[i] = newc[j];
}

El procedimiento se prueba con los siguientes cuatro casos de prueba
(1) oldc = «abc», newc = «dab»
(2) oldc = «cde», newc = «bcd»
(3) oldc = «bca», newc = » cda»
(4) oldc = «abc», newc = «bac»
El probador ahora prueba el programa en todas las strings de entrada de longitud cinco que constan de los caracteres ‘a’, ‘b’, ‘c’, ‘d’ y ‘e ‘ con duplicados permitidos. Si el probador lleva a cabo esta prueba con los cuatro casos de prueba dados anteriormente, ¿cuántos casos de prueba podrán capturar la falla?
(A) Solo uno
(B) Solo dos
(C) Solo tres
(D) Los cuatro

Respuesta (B)
Los casos de prueba 3 y 4 son los únicos casos que capturan la falla. El código no funciona correctamente cuando un carácter antiguo se reemplaza por un carácter nuevo y el carácter nuevo se reemplaza nuevamente por otro carácter nuevo. Esto no sucede en los casos de prueba (1) y (2), sucede solo en los casos (3) y (4).

6) Si se hace que la array A contenga la string «abcde», ¿cuál de los cuatro casos de prueba anteriores tendrá éxito al exponer la falla en este procedimiento?
(A) Ninguno
(B) Solo 2
(C) Solo 3 y 4
(D) Solo 4

Respuesta (C)

#include <stdio.h>
#include <string.h>
  
void find_and_replace(char *A, char *oldc, char *newc) {
    for (int i = 0; i < 5; i++)
       for (int j = 0; j < 3; j++)
           if (A[i] == oldc[j]) A[i] = newc[j];
}
  
int main()
{
    char *oldc1 = "abc", *newc1 = "dab";
    char *oldc2 = "cde", *newc2 = "bcd";
    char *oldc3 = "bca", *newc3 = "cda";
    char *oldc4 = "abc", *newc4 = "bac";
  
    char test[] =  "abcde";
  
    printf("Test 2\n");
    printf("%s\n", test);
    find_and_replace(test, oldc2, newc2);
    printf ("%s\n", test);
  
    printf("\nTest 3\n");
    strcpy(test, "abcde");
    printf("%s\n", test);
    find_and_replace(test, oldc3, newc3);
    printf ("%s\n", test);
  
    printf("\nTest 4\n");
    strcpy(test, "abcde");
    printf("%s\n", test);
    find_and_replace(test, oldc4, newc4);
    printf ("%s\n", test);
}

Producción:

Test 2
abcde
abbcd

Test 3
abcde
addde

Test 4
abcde
aacde

Consulte GATE Corner para ver todos los documentos/soluciones/explicaciones del año anterior, programa de estudios, fechas importantes, notas, etc.

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.