Estructuras de datos y algoritmos | Conjunto 21

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

1. El problema de suma de subconjuntos se define de la siguiente manera. Dado un conjunto de n enteros positivos, S = {a1 ,a2 ,a3 ,…,an} y el entero positivo W, ¿existe un subconjunto de S cuyos elementos suman W? Un programa dinámico para resolver este problema utiliza una array booleana bidimensional X, con n filas y W+1 columnas. X[i, j],1 <= i <= n, 0 <= j <= W, es VERDADERO si y solo si hay un subconjunto de {a1,a2,…,ai} cuyos elementos suman j . ¿Cuál de los siguientes es válido para 2 <= i <= n y ai <= j <= W?
(A) X[i, j] = X[i – 1, j] VX[i, j -ai]
(B) X[i, j] = X[i – 1, j] VX[i – 1, j – ai]
(C) X[i, j] = X[i – 1, j] VX[i, j – ai]
(D) X[i, j] = X[i – 1, j] VX[ i-1, j-ai]

Respuesta (B)

X[I, j] (2 <= i <= n y ai <= j <= W), es verdadero si cualquiera de los siguientes es verdadero 1) La suma de los pesos excluyendo ai es igual a j, es decir, si X[ i-1, j] es verdadera. 2) La suma de los pesos que incluye ai es igual a j, es decir, si X[i-1, j-ai] es cierto, obtenemos (j – ai) + ai como j.
2. En la pregunta 1, ¿qué entrada del arreglo X, si es VERDADERA, implica que hay un subconjunto cuyos elementos suman W?
(A) X[1, W]
(B) X[n,0]
(C) X[n, W]
(D) X[n -1, n]

Respuesta (C)
Si obtenemos la entrada X[n, W] como verdadera, entonces hay un subconjunto de {a1, a2, .. an} cuya suma es W.

Referencia: http://en.wikipedia.org/wiki/Subset_sum_problem

3. Considere el siguiente programa en C que intenta ubicar un elemento x en una array Y[] mediante la búsqueda binaria. El programa es erróneo.

1.   f(int Y[10], int x) {
2.     int i, j, k;
3.     i = 0; j = 9;
4.     do {
5.             k =  (i + j) /2;
6.             if( Y[k] < x)  i = k; else j = k;
7.         } while(Y[k] != x && i < j);
8.     if(Y[k] == x) printf ("x is in the array ") ;
9.     else printf (" x is not in the array ") ;
10. }

¿En cuál de los siguientes contenidos de Y y x falla el programa?
(A) Y es [1 2 3 4 5 6 7 8 9 10] y x < 10 (B) Y es [1 3 5 7 9 11 13 15 17 19] y x < 1 (C) Y es [2 2 2 2 2 2 2 2 2 2] y x > 2
(D) Y es [2 4 6 8 10 12 14 16 18 20] y 2 < x < 20 y x es par Respuesta (C) El programa anterior no funciona para los casos en los que el elemento a buscar es el último elemento de Y[] o mayor que el último elemento (o elemento máximo) en Y[]. Para tales casos, el programa entra en un bucle infinito porque a i se le asigna un valor como k en todas las iteraciones, y i nunca se vuelve igual o mayor que j. Entonces, mientras que la condición nunca se vuelve falsa.

4. En la pregunta 3, la corrección necesaria en el programa para que funcione correctamente es
(A) Cambie la línea 6 a: si (Y[k] < x) i = k + 1; de lo contrario j = k-1; (B) Cambie la línea 6 a: si (Y[k] < x) i = k – 1; de lo contrario j = k+1; (C) Cambie la línea 6 a: if (Y[k] <= x) i = k; de lo contrario j = k; (D) Cambie la línea 7 a: } while ((Y[k] == x) && (i < j)); Respuesta (A) A continuación se muestra la función corregida

f(int Y[10], int x) {
   int i, j, k;
   i = 0; j = 9;
   do {
           k =  (i + j) /2;
           if( Y[k] < x)  i = k + 1; else j = k - 1;
       } while(Y[k] != x && i < j);
   if(Y[k] == x) printf ("x is in the array ") ;
   else printf (" x is not in the array ") ;
}

Referencia: http://en.wikipedia.org/wiki/Binary_search_algorithm#Implementations

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.