Estructuras de datos y algoritmos | Conjunto 17

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

1. A continuación se muestra una implementación de una cola Q, utilizando dos pilas S1 y S2:

void insert(Q, x) {
   push (S1, x);
}
  
void delete(Q){
   if(stack-empty(S2)) then 
      if(stack-empty(S1)) then {
          print(“Q is empty”);
          return;
      }
      else while (!(stack-empty(S1))){
          x=pop(S1);
          push(S2,x);
      }
   x=pop(S2);
}

Sean realizadas n operaciones de inserción y m (<=n) de eliminación en un orden arbitrario en una cola vacía Q. Sean x e y el número de operaciones push y pop realizadas respectivamente en el proceso. ¿Cuál de los siguientes es cierto para todo m y n?
(A) n+m <= x < 2n y 2m <= y <= n+m (B) n+m <= x < 2n y 2m<= y <= 2n (C) 2m <= x < 2n y 2m <= y <= n+m (D) 2m <= x <2n y 2m <= y <= 2n Respuesta (A) Aquí importa el orden en que se realizan las operaciones de inserción y eliminación.
El mejor de los casos: las operaciones de inserción y eliminación se realizan alternativamente. En cada operación de eliminación, se realizan 2 operaciones pop y 1 push. Por lo tanto, se realizan operaciones totales m + n push (n push para insertar() y m push para eliminar()) y 2 millones de operaciones emergentes.

El peor caso:Primero se insertan n elementos y luego se eliminan m elementos. En la primera operación de eliminación, se realizan n + 1 operaciones pop yn operaciones push. Aparte de primero, en todas las operaciones de eliminación, se realiza 1 operación emergente. Por lo tanto, se realizan un total de m + n operaciones pop y 2n operaciones push (n push para insertar() y m push para eliminar())

2. Considere el siguiente gráfico: ¿Cuál de los siguientes no puede ser la secuencia de aristas agregadas, en ese orden, a un árbol de expansión mínimo usando el algoritmo de Kruskal? (A) (a—b),(d—f),(b—f),(d—c),(d—e) (B) (a—b),(d—f),(d— c),(b—f),(d—e) (C) (d—f),(a—b),(d—c),(b—f),(d—e) (D) ( d-f),(a-b),(b-f),(d-e),(d-c)

Respuesta (D)
El borde (de) no se puede considerar antes de (dc) en el algoritmo de árbol de expansión mínimo de Kruskal porque el algoritmo de Kruskal elige el borde con el peso mínimo del conjunto actual de bordes en cada paso.

3. La mediana de n elementos se puede encontrar en tiempo O(n). ¿Cuál de los siguientes es correcto sobre la complejidad de la ordenación rápida, en la que la mediana se selecciona como pivote?
(A) Θ(n)
(B) Θ(nlogn)
(C) Θ(n^2)
(D) Θ(n^3)

Respuesta (B)
Si la mediana siempre se usa como pivote, entonces la recurrencia sigue siendo T(n) = 2T(n/2) + cn para todos los casos donde cn es el tiempo combinado para encontrar la mediana y dividir. Entonces, la complejidad del tiempo en el peor de los casos de este tipo rápido se convierte en Θ (nlogn). En implementaciones prácticas, sin embargo, esta variante es considerablemente más lenta en promedio (consulte http://en.wikipedia.org/wiki/Quicksort#Selection-based_pivoting )

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.