Estructuras de datos y algoritmos | conjunto 14

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

1. Tenemos un montón binario en n elementos y deseamos insertar n elementos más (no necesariamente uno tras otro) en este montón. El tiempo total requerido para esto es
(A) Θ(logn)
(B) Θ(n)
(C) Θ(nlogn)
(D) Θ(n ² )

La complejidad de tiempo del peor de los casos para la inserción en un montón binario es O (Inicio de sesión) (Consulte Wiki ). Por lo tanto, insertar n elementos en un montón de tamaño n debería llevar un tiempo Θ(nlogn).
Pero la opción (B) parece ser la respuesta más apropiada. Una de las soluciones de la complejidad O(n) puede ser tomar los elementos ‘n’ del montón y otros elementos ‘n’ juntos y construir el montón en O(2n) = O(n). Gracias a pankaj por sugerir esta solución.

2. El algoritmo Breadth First Search se implementó utilizando la estructura de datos de la cola. Un orden posible para visitar los Nodes del siguiente gráfico es

(A) MNOPQR
(B) NQMPOR
(C) QMNPRO
(D) QMNPOR

Respuesta (C)

3. Considere las siguientes funciones:

  f(n)   = 2^n
  g(n)   = n!
  h(n)   = n^logn 

¿Cuál de las siguientes afirmaciones sobre el comportamiento asintótico de f(n), g(n) y h(n) es verdadera?
(A) f(n) = O(g(n)); g(n) = O(h(n))
(B) f(n) = Ω(g(n)); g(n) = O(h(n))
(C) g(n) = O(f(n)); h(n) = O(f(n))
(D) h(n) = O(f(n)); g(n) = Ω(f(n))

Respuesta (D)

Según el orden de crecimiento: h(n) < f(n) < g(n) (g(n) es asintóticamente mayor que f(n) y f(n) es asintóticamente mayor que h(n) ) Fácilmente podemos vea el orden anterior tomando registros de las 3 funciones dadas

   lognlogn < n < log(n!)  (logs of the given f(n), g(n) and h(n)).

Tenga en cuenta que log(n!) = Θ(nlogn)

4. El número mínimo de comparaciones requeridas para determinar si un entero aparece más de n/2 veces en una array ordenada de n enteros es
(A) Θ(n)
(B) Θ(logn)
(C) Θ(log*n )
(D) Θ(n)

Respuesta (B)

Consulte la publicación Comprobar el elemento mayoritario en una array ordenada para obtener más detalles.

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.