Estructuras de datos y algoritmos | conjunto 8

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

1. Considera las siguientes funciones

¿Cuál de las siguientes es verdadera? (GATE CS 2000)
(a) h(n) es 0(f(n))
(b) h(n) es 0(g(n))
(c) g(n) no es 0(f(n) )
(d) f(n) es 0(g(n))

Respuesta (d)
g(n) = 2 ^{√n Log n} = n ^√n

f(n) y g(n) son del mismo orden asintótico y las siguientes declaraciones son verdaderas.
f(n) = O(g(n))
g(n) = O(f(n)).

(a) y (b) son falsas porque n! es de orden asintóticamente más alto que n ^√n .

2. Sea G un grafo conexo no dirigido con distinto peso de arista. Sea emax la arista con peso máximo y emin la arista con peso mínimo. ¿Cuál de las siguientes afirmaciones es falsa? (GATE CS 2000)
(a) Cada árbol de expansión mínimo de G debe contener emin
(b) Si emax está en un árbol de expansión mínimo, entonces su eliminación debe desconectar G
(c) Ningún árbol de expansión mínimo contiene emax
(d) G tiene un árbol de expansión mínimo único

Las respuestas (c)
(a) y (b) son siempre verdaderas.
(c) es falsa porque (b) es verdadera.
(d) es verdadera porque todos los pesos de los bordes son distintos para G.

3. Sea G un grafo no dirigido. Considere un recorrido de G primero en profundidad, y sea T el árbol de búsqueda primero en profundidad resultante. Sea u un vértice en G y sea v el primer vértice nuevo (no visitado) visitado después de visitar u en el recorrido. ¿Cuál de las siguientes afirmaciones es siempre cierta? (GATE CS 2000)
(a) {u,v} debe ser una arista en G, y u es un descendiente de v en T
(b) {u,v} debe ser una arista en G, y v es un descendiente de u en T
(c) Si {u,v} no es una arista en G entonces u es una hoja en T
(d) Si {u,v} no es una arista en G entonces u y v deben tener el mismo padre en T

Respuesta (c)
Consulte http://geeksquiz.com/data-structures-graph-question-20/ para obtener una explicación.

4. Considere un grafo no ponderado no dirigido G. Haga un recorrido de G en anchura comenzando desde un Node r. Sean d(r, u) y d(r, v) las longitudes de los caminos más cortos de r a u y v respectivamente, en G. Si se visita u antes que v durante el recorrido primero en anchura, ¿cuál de las siguientes afirmaciones ¿es correcto? (GATE CS 2001)
a) d(r, u) < d (r, v) b) d(r, u) > d(r, v)
c) d(r, u) <= d (r, v ) d) Ninguna de las anteriores Respuesta (c) d(r, u) y d(r, v) serán iguales cuando u y v estén al mismo nivel, de lo contrario d(r, u) será menor que d(r , v)

5. ¿Cuántos grafos no dirigidos (no necesariamente conexos) se pueden construir a partir de un conjunto dado V= {V 1, V 2,…V n} de n vértices? (GATE CS 2001)
a) n(nl)/2
b) 2^n
c) n!
d) 2^(n(n-1)/2)

Respuesta (d)
En un gráfico no dirigido, puede haber un máximo de n(n-1)/2 aristas. Podemos elegir tener (o no tener) cualquiera de las n(n-1)/2 aristas. Entonces, el número total de grafos no dirigidos con n vértices es 2^(n(n-1)/2).

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.