Estructuras de datos y algoritmos | Conjunto 15

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

1. El algoritmo más eficiente para encontrar el número de componentes conectados en un gráfico no dirigido en n vértices y m aristas tiene complejidad temporal.
(A) Θ(n)
(B) Θ(m)
(C) Θ(m + n)
(D) Θ(mn)

Respuesta (C)
Los componentes conectados se pueden encontrar en O(m + n) usando el algoritmo de Tarjan . Una vez que hemos conectado los componentes, podemos contarlos.

2. Considere el algoritmo Quicksort. Supongamos que existe un procedimiento para encontrar un elemento pivote que divide la lista en dos sublistas, cada una de las cuales contiene al menos una quinta parte de los elementos. Sea T(n) el número de comparaciones necesarias para clasificar n elementos. Entonces
(A) T(n) <= 2T(n/5) + n (B) T(n) <= T(n/5) + T(4n/5) + n (C) T(n) < = 2T(4n/5) + n (D) T(n) <= 2T(n/2) + n Respuesta (B) Para el caso donde n/5 elementos están en un subconjunto, T(n/5) comparaciones son necesarios para el primer subconjunto con n/5 elementos, T(4n/5) es para el resto 4n/5 elementos, y n es para encontrar el pivote. Si hay más de n/5 elementos en un conjunto, el otro conjunto tendrá menos de 4n/5 elementos y la complejidad del tiempo será menor que T(n/5) + T(4n/5) + n porque el árbol de recurrencia será más equilibrado.

3 El algoritmo de ruta más corta de fuente única de Dijkstra cuando se ejecuta desde el vértice a en el siguiente gráfico, calcula la distancia de ruta más corta correcta a (A) solo el vértice a (B) solo los vértices a, e, f, g, h (C) solo los vértices a , b, c, d (D) todos los vértices

Respuesta (D)
No se garantiza que la ruta más corta de fuente única de Dijkstra funcione para gráficos con bordes de peso negativos, pero funciona para el gráfico dado.
Dejanos ver…

Ejecutemos el primer paso
b 1
b es mínimo, por lo que la distancia más corta a b es 1.

Después del 1er paso, las distancias son
c 3, e -2.
e es mínimo, por lo que la distancia más corta a e es -2

Después del segundo paso, las distancias son
c 3, f 0.
f es mínima, por lo que la distancia más corta a f es 0

Después del tercer paso, las distancias son
c 3, g 3.
Ambas son iguales, tomemos g. entonces la distancia más corta a g es 3.

Después del cuarto paso, las distancias son
c 3, h 5
c es el mínimo, por lo que la distancia más corta a c es 3

Después del quinto paso, las distancias son
h -2
h es el mínimo, por lo que la distancia más corta a h es -2

4. La siguiente función de C toma una lista de enteros con un solo enlace como parámetro y reorganiza los elementos de la lista. La función se llama con la lista que contiene los números enteros 1, 2, 3, 4, 5, 6, 7 en el orden dado. ¿Cuál será el contenido de la lista después de que la función complete su ejecución?

struct node 
{
  int value;
  struct node *next;
};
void rearrange(struct node *list)
{
  struct node *p, * q;
  int temp;
  if ((!list) || !list->next) 
      return;
  p = list;
  q = list->next;
  while(q) 
  {
     temp = p->value;
     p->value = q->value;
     q->value = temp;
     p = q->next;
     q = p?p->next:0;
  }
}

(A) 1,2,3,4,5,6,7
(B) 2,1,4,3,6,5,7
(C) 1,3,2,5,4,7,6
(D ) 2,3,4,5,6,7,1

Respuesta (B)
La función reorganizar() intercambia datos de cada Node con su siguiente Node. Comienza a intercambiar datos desde el primer Node.

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.