Se han hecho las siguientes preguntas en el examen GATE CS 2009.
1. Considere un montón máximo binario implementado usando una array. ¿Cuál de las siguientes arrays representa un montón máximo binario?
(A) 25,12,16,13,10,8,14
(B) 25,14,13,16,10,8,12
(C) 25,14,16,13,10,8,12
(D ) 25,14,12,13,10,8,16
Respuesta (C)
Un árbol es max-heap si los datos en cada Node del árbol son mayores o iguales que los datos de sus hijos.
En la representación de array del árbol del montón, un Node en el índice i tiene su hijo izquierdo en el índice 2i + 1 y su hijo derecho en el índice 2i + 2.
25
/ \
/ \
14 16
/ \ / \
/ \ / \
13 10 8 12
2. ¿Cuál es el contenido de la array después de dos operaciones de eliminación en la respuesta correcta a la pregunta anterior?
(A) 14,13,12,10,8
(B) 14,12,13,8,10
(C) 14,13,8,12,10
(D) 14,13,12,8,10
Respuesta (D)
Para los árboles Heap, la eliminación de un Node incluye las siguientes dos operaciones.
1) Reemplace la raíz con el último elemento en el último nivel.
2) Comenzando desde la raíz, apile el árbol completo de arriba a abajo.
Borremos los dos Nodes uno por uno:
1) Borrado de 25:
Reemplace 25 con 12
12
/ \
/ \
14 16
/ \ /
/ \ /
13 10 8
Dado que la propiedad del montón se viola para la raíz (16 es mayor que 12), haga que 16 sea la raíz del árbol.
16
/ \
/ \
14 12
/ \ /
/ \ /
13 10 8
2) Eliminación de 16:
Reemplace 16 con 8
8
/ \
/ \
14 12
/ \
/ \
13 10
Apile de raíz a abajo.
14
/ \
/ \
8 12
/ \
/ \
13 10
14
/ \
/ \
13 12
/ \
/ \
8 10
3. En la ordenación rápida, para ordenar n elementos, el elemento más pequeño (n/4) se selecciona como pivote usando un algoritmo de tiempo O(n). ¿Cuál es la complejidad de tiempo en el peor de los casos del tipo rápido?
(A) Θ(n)
(B) Θ(n Log n)
(C) Θ(n^2)
(D) Θ(n 2 log n)
Respuesta (B)
La expresión recursiva se convierte en:
T(n) = T(n/4) + T(3n/4) + cn
Después de resolver la recursividad anterior, obtenemos Θ(nLogn).
4. ¿Cuál es la altura máxima de cualquier árbol AVL con 7 Nodes? Suponga que la altura de un árbol con un solo Node es 0.
(A) 2
(B) 3
(C) 4
(D) 5
Respuesta (B)
Los árboles AVL son árboles binarios con las siguientes restricciones.
1) la diferencia de altura de los niños es como máximo 1.
2) ambos niños son árboles AVL
a
/ \
/ \
b c
/ \ /
/ \ /
d e g
/
/
h
Referencias:
http://en.wikipedia.org/wiki/AVL_tree
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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA