Estructuras de datos y algoritmos | conjunto 12

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

1. Considere el siguiente segmento de programa C donde CellNode representa un Node en un árbol binario: 

struct CellNode
{
  struct CellNOde *leftChild;
  int element;
  struct CellNode *rightChild;
};
 
int GetValue(struct CellNode *ptr)
{
  int value = 0;
  if (ptr != NULL)
  {
   if ((ptr->leftChild == NULL) &&
        (ptr->rightChild == NULL))
      value = 1;
   else
      value = value + GetValue(ptr->leftChild)
                   + GetValue(ptr->rightChild);
  }
  return(value);
}

El valor devuelto por GetValue() cuando se pasa un puntero a la raíz de un árbol binario como argumento es: 
(A) el número de Nodes en el árbol 
(B) el número de Nodes internos en el árbol 
(C) el número de Nodes de hoja en el árbol 
(D) la altura del árbol
Respuesta (C) 
Para obtener una explicación, consulte nuestra publicación https://www.geeksforgeeks.org/?p=2755 para contar los Nodes de hoja.

2. Considere el proceso de insertar un elemento en Max Heap, donde Max Heap está representado por una array. Supongamos que realizamos una búsqueda binaria en la ruta desde la nueva hoja hasta la raíz para encontrar la posición del elemento recién insertado, el número de comparaciones realizadas es: 
(A) Θ(logn) 
(B) Θ(LogLogn) 
(C) Θ(n) 
(D) Θ(nLogn)
Respuesta (B) 
La altura de Max Heap es Θ(logn). Si realizamos una búsqueda binaria para encontrar la posición correcta, entonces necesitamos hacer comparaciones Θ(LogLogn).

3. Sea w el peso mínimo entre todos los pesos de las aristas en un grafo conexo no dirigido. Sea e una arista específica de peso w. ¿Cuál de las siguientes es FALSA?  
(A) Hay un árbol de expansión mínimo que contiene e. 
(B) Si e no está en un árbol generador mínimo T, entonces en el ciclo formado al sumar e a T, todas las aristas tienen el mismo peso. 
(C) Todo árbol de expansión mínima tiene una arista de peso w . 
(D) e está presente en todo árbol de expansión mínimo.
Respuesta (D) 
(A), (B) y (C) son correctas. 
(D) es incorrecta ya que puede haber muchos bordes de peso w en el gráfico y es posible que e no se recoja en algunos de los árboles de expansión mínimos.

4. Se da una array de n números, donde n es un número par. Es necesario determinar el máximo, así como el mínimo de estos n números. ¿Cuál de las siguientes es VERDADERA sobre el número de comparaciones necesarias?  
(A) Se necesitan al menos 2n – c comparaciones, para alguna constante c. 
(B) Se necesitan como máximo 1,5n – 2 comparaciones. 
(C) Se necesitan al menos comparaciones nLog2n. 
(Re. Ninguna de las anteriores.
Respuesta (B)
Consulte la publicación https://www.geeksforgeeks.org/?p=4583 para obtener más detalles.

5. Considere el siguiente segmento de código C:  

int IsPrime(n)
{
  int i,n;
  for(i=2;i<=sqrt(n);i++)
   if(n%i == 0)
     {printf(“Not Prime\n”); return 0;}
  return 1;
}

Sea T(n) el número de veces que el programa ejecuta el bucle for en la entrada n. ¿Cual de los siguientes es verdadero?  
(A) T(n) = O(raíz cuadrada(n)) y T(n) = Ω(raíz cuadrada(n)) 
(B) T(n) = O(raíz cuadrada(n)) y T(n) = Ω (1) 
(C) T(n) = O(n) y T(n) = Ω(sqrt(n)) 
(D) Ninguna de las anteriores
Respuesta (B) 
La notación Big O describe el límite superior y la notación Big Omega describe el límite inferior de un algoritmo.
El bucle for en la pregunta se ejecuta un máximo de sqrt(n) veces y un mínimo de 1 vez. Por lo tanto, T(n) = O(sqrt(n)) y T(n) = Ω(1)
Consulte GATE Corner para ver todos los trabajos/soluciones/explicaciones del año anterior, plan 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.