Estructuras de datos y algoritmos | Conjunto 33

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

1) Considere los arcos de árbol de un recorrido BFS desde un Node fuente W en un gráfico no dirigido, conectado y no ponderado. El árbol T formado por los arcos del árbol es una estructura de datos para computación.
(A) el camino más corto entre cada par de vértices.
(B) el camino más corto desde W a cada vértice en el gráfico.
(C) los caminos más cortos de W a solo aquellos Nodes que son hojas de T.
(D) el camino más largo en el gráfico

Respuesta: (B)
BFS siempre produce las rutas más cortas desde el origen hasta todos los demás vértices en un gráfico no ponderado. La razón es simple, en BFS, primero exploramos todos los vértices que están a 1 arista de la fuente, luego exploramos todos los vértices que están a 2 aristas de la fuente y así sucesivamente. Esta propiedad de BFS lo hace útil en muchos algoritmos como el algoritmo de Edmonds-Karp.

2) Considere el siguiente pseudocódigo. ¿Cuál es el número total de multiplicaciones a realizar?

D = 2
for i = 1 to n do
   for j = i to n do
      for k = j + 1 to n do
           D = D * 3 

(A) La mitad del producto de los 3 enteros consecutivos.
(B) Un tercio del producto de los 3 enteros consecutivos.
(C) Un sexto del producto de los 3 enteros consecutivos.
(Re. Ninguna de las anteriores.
Respuesta (C)
La declaración «D = D * 3» se ejecuta n*(n+1)*(n-1)/6 veces. Veamos cómo.

Para i = 1, la instrucción de multiplicación se ejecuta (n-1) + (n-2) + .. 2 + 1 veces.
Para i = 2, la sentencia se ejecuta (n-2) + (n-3) + .. 2 + 1 veces
………………………..
……………………….
Para i = n-1, la instrucción se ejecuta una vez.
Para i = n, la declaración no se ejecuta en absoluto

Entonces, en general, la declaración se ejecuta después
de [(n-1) + (n-2) + .. 2 + 1] + [(n-2) + (n-3) + .. 2 + 1] + … + 1 + 0

La serie anterior se puede escribir como
S = [n*(n-1)/2 + (n-1)*(n-2)/2 + ….. + 1]

La suma de la serie anterior se puede obtener mediante el truco de restar la serie de la serie estándar S1 = n ² + (n-1) ² + .. 1 ² . La suma de esta serie estándar es n*(n+1)*(2n+1)/6

S1 – 2S = n + (n-1) + … 1 = n*(n+1)/2
2S = n*(n+1)*(2n+1)/6 – n*(n+1)/ 2
S = n*(n+1)*(n-1)/6

3) Considere una tabla hash con 9 ranuras. La función hash es h(k) = k mod 9. Las colisiones se resuelven enstringndo. Las siguientes 9 claves se insertan en el orden: 5, 28, 19, 15, 20, 33, 12, 17, 10. Las longitudes de string máxima, mínima y promedio en la tabla hash, respectivamente, son
(A) 3, 0 y 1
(B) 3, 3 y 3
(C) 4, 0 y 1
(D) 3, 0 y 2

Respuesta: (A)
Los siguientes son valores de la función hash para todas las claves

 5 --> 5
28 --> 1
19 --> 1  [Chained with 28]
15 --> 6
20 --> 2
33 --> 6  [Chained with 15]
12 --> 3
17 --> 8
10 --> 1 [Chained with 28 and 19]

La longitud máxima de string es 3. Las llaves 28, 19 y 10 van a la misma ranura 1, y forman una string de longitud 3.
La longitud mínima de string 0, hay ranuras vacías (0, 4 y 7).
La longitud promedio de la string es (0 + 3 + 1 + 1 + 0 + 1 + 2 + 0 + 1)/9 = 1

4) Se implementa una cola de prioridad como Max-Heap. Inicialmente, tiene 5 elementos. El recorrido de orden de nivel del montón es: 10, 8, 5, 3, 2. Dos nuevos elementos 1 y 7 se insertan en el montón en ese orden. El recorrido de orden de nivel del montón después de la inserción de los elementos es:
(A) 10, 8, 7, 3, 2, 1, 5
(B) 10, 8, 7, 2, 3, 1, 5
(C ) 10, 8, 7, 1, 2, 3, 5
(D) 10, 8, 7, 5, 3, 2, 1

Respuesta: (A)

Initially heap has 10, 8, 5, 3, 2
    10
   /  \ 
  8    5
 / \
3   2

After insertion of 1
     10
   /   \ 
  8     5
 / \   /
3   2 1 
No need to heapify as 5 is greater than 1.


After insertion of 7
     10
   /   \ 
  8     5
 / \   / \
3   2 1   7
Heapify 5 as 7 is greater than 5
     10
   /   \ 
  8     7
 / \   / \
3   2 1   5
No need to heapify any further as 10 is
greater than 7 

5) ¿Cuál de los siguientes determina correctamente la solución de la relación de recurrencia con T(1) = 1?

T(n) = 2T(n/2) + Logn 

(A) Θ(n)
(B) Θ(nLogn)
(C) Θ(n*n)
(D) Θ(log n)

Respuesta: (A)
Esto se puede resolver usando el método maestro . Cae en el caso 1.

7) Suponga que la implementación admite una instrucción REVERSE, que invierte el orden de los elementos en la pila, además de las instrucciones PUSH y POP. ¿Cuál de las siguientes afirmaciones es VERDADERA con respecto a esta pila modificada?
(A) No se puede implementar una cola usando esta pila.
(B) Se puede implementar una cola donde ENQUEUE toma una sola instrucción y DEQUEUE toma una secuencia de dos instrucciones.
(C) Se puede implementar una cola donde ENQUEUE toma una secuencia de tres instrucciones y DEQUEUE toma una sola instrucción.
(D) Se puede implementar una cola donde ENQUEUE y DEQUEUE toman una sola instrucción cada uno.

Respuesta: (C)
Para QUITAR un artículo, simplemente POP.
Para ENQUEUE un artículo, podemos hacer las siguientes 3 operaciones
1) REVERSE
2) PUSH
3) REVERSE

Consulte GATE Corner para ver todos los documentos/soluciones/explicaciones del año anterior, plan de estudios, fechas importantes, notas, etc.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.