Estructuras de datos y algoritmos | Conjunto 30

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

1) ¿Cuál de las siguientes afirmaciones es/son VERDADERAS para un gráfico no dirigido?
P: El número de vértices de grado impar es par
Q: La suma de los grados de todos los vértices es par

A) Solo P
B) Solo Q
C) Tanto P como Q
D) Ni P ni Q

Respuesta (C)
Q es verdadero: dado que el gráfico no está dirigido, cada borde aumenta la suma de grados en 2.
P es verdadero: si consideramos la suma de grados y restamos todos los grados pares, obtenemos un número par (porque Q es verdadero ). Entonces, el número total de vértices de grado impar debe ser par.

2) Considere un gráfico aleatorio no dirigido de ocho vértices. La probabilidad de que haya una arista entre un par de vértices es 1/2. ¿Cuál es el número esperado de ciclos desordenados de longitud tres?
(A) 1/8
(B) 1
(C) 7
(D) 8

Respuesta (C)
Se puede formar un ciclo de longitud 3 con 3 vértices. Puede haber un total de 8C3 formas de elegir 3 vértices de 8. La probabilidad de que haya una arista entre dos vértices es 1/2. Así que el número esperado de ciclos desordenados de longitud 3 = (8C3)*(1/2)^3 = 7

3) ¿Cuál es la complejidad temporal del algoritmo de ruta más corta de fuente única de Bellman-Ford en un gráfico completo de n vértices?
(A) Θ(n ² )
(B) Θ(n ² Logn)
(C) Θ(n ³ )
(D) Θ(n ³ Logn)

Respuesta (C).
La complejidad temporal del algoritmo de Bellman-Ford es Θ(VE) donde V es el número de vértices y E es el número de aristas (ver esto ). Si el gráfico está completo, el valor de E se convierte en Θ(V ² ). Entonces la complejidad del tiempo total se convierte en Θ(V ³ )

4) ¿Cuáles de las siguientes afirmaciones son VERDADERAS?
(1) El problema de determinar si existe un ciclo en un grafo no dirigido está en P.
(2) El problema de determinar si existe un ciclo en un grafo no dirigido está en NP.
(3) Si un problema A es NP-Completo, existe un algoritmo de tiempo polinomial no determinista para resolver A.

(A) 1, 2 y 3
(B) 1 y 2 únicamente
(C) 2 y 3 únicamente
(D) 1 y 3 únicamente

La respuesta (A)
1 es verdadera porque la detección de ciclos se puede realizar en tiempo polinomial usando DFS (Ver esto ).
2 es cierto porque P es un subconjunto de NP.
3 es cierto porque NP completo también es un subconjunto de NP y NP significa que existe una solución de tiempo polinomial no determinista . (Ver esto )

5) ¿Cuál de los siguientes es el límite superior más ajustado que representa la complejidad temporal de insertar un objeto en un árbol de búsqueda binaria de n Nodes?
(A) O(1)
(B) O(log n)
(C) O(n)
(D) O(n log n)

Respuesta (C)
El peor de los casos ocurre con un árbol sesgado. En un árbol sesgado, cuando se inserta un nuevo Node como hijo del Node inferior, el tiempo de inserción requiere recorrer todos los Nodes. Por ejemplo, considere el siguiente árbol y el caso cuando se inserta algo más pequeño que 70.

             100
            /
           90
          /
        80
       /
     70   

6) ¿Cuál de los siguientes es el límite superior más ajustado que representa el número de intercambios necesarios para clasificar n números utilizando la clasificación por selección?
(A) O(log n)
(B) O(n)
(C) O(n log n)
(D) O(n^2)

Respuesta (B)
La ordenación por selección requiere solo intercambios O(n). Vea esto para más detalles.

7) Considere la siguiente operación junto con las operaciones Enqueue y Dequeue en las
colas, donde k es un parámetro global

MultiDequeue(Q){
   m = k
   while (Q is not empty and m  > 0) {
      Dequeue(Q)
      m = m - 1
   }
}

¿Cuál es la complejidad temporal en el peor de los casos de una secuencia de n operaciones MultiDequeue() en una cola inicialmente vacía?
(A) Θ(n)
(B) Θ(n + k)
(C) Θ(nk)
(D) Θ(n ² )

Respuesta (A)
Dado que la cola está vacía inicialmente, la condición del bucle while nunca se cumple. Entonces la complejidad del tiempo es Θ(n)

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.