Estructuras de datos y algoritmos | conjunto 9

Siga las preguntas que se han hecho en el examen GATE CS.

1 En un montón con n elementos con el elemento más pequeño en la raíz, el séptimo elemento más pequeño se puede encontrar en el tiempo (GATE CS 2003)
a) Θ(n log n)
b) Θ(n)
c) Θ(log n)
d) Θ(1)

Respuesta (d)
El séptimo elemento más pequeño debe estar en los primeros 7 niveles. El número total de Nodes en cualquier montón binario en los primeros 7 niveles es como máximo 1 + 2 + 4 + 8 + 16 + 32 + 64, que es una constante. Por lo tanto, siempre podemos encontrar el séptimo elemento más pequeño en el tiempo Θ(1).

2. Suponga que los números 7, 5, 1, 8, 3, 6, 0, 9, 4, 2 se insertan en ese orden en un árbol de búsqueda binario inicialmente vacío. El árbol de búsqueda binario utiliza el orden habitual de los números naturales. ¿Cuál es la secuencia transversal en orden del árbol resultante? (GATE CS 2003)
a) 7 5 1 0 3 2 4 6 8 9
b) 0 2 4 3 1 6 5 9 8 7
c) 0 1 2 3 4 5 6 7 8 9
d) 9 8 6 4 2 3 0 1 5 7

Respuesta (c)
El recorrido en orden de un BST da elementos en orden creciente. Entonces la respuesta c es correcta sin ninguna duda.

3. Sea S una pila de tamaño n >= 1. Comenzando con la pila vacía, supongamos que empujamos los primeros n números naturales en secuencia y luego realizamos n operaciones pop. Suponga que la operación Push y Pop toman X segundos cada una, y que transcurren Y segundos entre el final de una de esas operaciones de pila y el comienzo de la siguiente operación. Para m >= 1, defina la vida útil de la pila de m como el tiempo transcurrido desde el final de Push(m) hasta el inicio de la operación pop que elimina m de S. La vida útil promedio de la pila de un elemento de esta pila es (GATE CS 2003)
a) n(X+ Y)
b) 3Y + 2X
c) n(X + Y)-X
d) Y + 2X

Respuesta (c)
Podemos llegar fácilmente al resultado tomando algunos ejemplos.

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.