Estructuras de datos y algoritmos | Conjunto 29

Las siguientes preguntas se han hecho en el examen GATE 2012. 

1) La relación de recurrencia que captura el tiempo óptimo del problema de la Torre de Hanoi con n discos es 
(A) T(n) = 2T(n – 2) + 2 
(B) T(n) = 2T(n – 1) + norte 
(C) T(n) = 2T(n/2) + 1 
(D) T(n) = 2T(n – 1) + 1 

Respuesta (D) 

Los siguientes son los pasos a seguir para resolver el problema de la Torre de Hanoi de forma recursiva. 
 

Let the three pegs be A, B and C. The goal is to move n pegs from A to C.
To move n discs from peg A to peg C:
    move n-1 discs from A to B. This leaves disc n alone on peg A
    move disc n from A to C
    move n?1 discs from B to C so they sit on disc n

La función de recurrencia T(n) para la complejidad temporal de la solución recursiva anterior se puede escribir de la siguiente manera. 

T(n) = 2T(n-1) + 1 

2) Considere el gráfico dirigido que se muestra en la siguiente figura. Hay múltiples caminos más cortos entre los vértices S y T. ¿Cuál será informado por el algoritmo de camino más corto de Dijkstra? Suponga que, en cualquier iteración, la ruta más corta a un vértice v se actualiza solo cuando se descubre una ruta estrictamente más corta a v. 

(A) SDT 
(B) SBDT 
(C) SACDT 
(D) SACET 

Respuesta (D) 

3) Suponga que se implementa una cola circular de elementos de capacidad (n – 1) con una array de n elementos. Suponga que la operación de inserción y eliminación se lleva a cabo utilizando REAR y FRONT como variables de índice de array, respectivamente. Inicialmente, REAR = FRONT = 0. Las condiciones para detectar cola llena y cola vacía son 
(A) Full: (REAR+1) mod n == FRONT, empty: REAR == FRONT 
(B) Full: (REAR+1) mod n == DELANTERO, vacío: (FRONTAL+1) mod n == TRASERO 
(C) Completo: TRASERO == DELANTERO, vacío: (TRASERO+1) mod n == DELANTERO 
(D) Completo: (FRONTAL+1) mod n == TRASERO, vacío: TRASERO == DELANTERO 

Respuesta (A) 
Ver esto para más detalles. 

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.