Se han hecho las siguientes preguntas en el examen GATE CS
1. Sea LASTPOST, LASTIN y LASTPRE el último vértice visitado en un recorrido en postorder, inorder y preorder. Respectivamente, de un árbol binario completo. ¿Cuál de las siguientes es siempre cierta? (GATE CS 2000)
(a) LASTIN = LASTPOST
(b) LASTIN = LASTPRE
(c) LASTPRE = LASTPOST
(d) Ninguna de las anteriores
Respuesta (d)
Se da que el árbol dado es un árbol binario completo . Para un árbol binario completo, el último Node visitado siempre será el mismo para el recorrido en orden y en orden previo. Nada de lo anterior es cierto incluso para un árbol binario completo.
La opción (a) es incorrecta porque el último Node visitado en el recorrido Inorder es el hijo derecho y el último Node visitado en el recorrido Postorder es el root.
La opción (c) es incorrecta porque el último Node visitado en el recorrido Preorder es el hijo derecho y el último Node visitado en el recorrido Postorder es root.
Para la opción (b), consulte el siguiente ejemplo de contador. Gracias a Hunaif Muhammed por proporcionar la explicación correcta.
1 / \ 2 3 / \ / 4 5 6 Inorder traversal is 4 2 5 1 6 3 Preorder traversal is 1 2 4 5 3 6
2. La combinación más adecuada para los siguientes pares
X: depth first search 1: heap Y: breadth-first search 2: queue Z: sorting 3: stack
es (GATE CS 2000):
(a) X—1 Y—2 Z-3
(b) X—3 Y—1 Z-2
(c) X—3 Y—2 Z-1
(d) X—2 Y —3 Z-1
Respuesta: (c) La
pila se usa para la búsqueda en profundidad primero . La
cola se usa para la búsqueda primero en amplitud. El
montón se usa para ordenar.
3. Considere la siguiente representación anidada de árboles binarios: (XYZ) indica que Y y Z son las subtensiones izquierda y derecha, respectivamente, del Node X. Tenga en cuenta que Y y Z pueden ser NULL o anidados. ¿Cuál de los siguientes representa un árbol binario válido?
(a) (1 2 (4 5 6 7))
(b) (1 (2 3 4) 5 6) 7)
(c) (1 (2 3 4)(5 6 7))
(d) (1 ( 2 3 NULO) (4 5))
Respuesta (c)
4. Sea s una array ordenada de n enteros. Sea t(n) el tiempo que tarda el algoritmo más eficiente en determinar si hay dos elementos con una suma menor que 1000 en s. ¿Cuál de las siguientes afirmaciones es verdadera? (GATE CS 2000)
a) t (n) es 0 (1)
b) n < t (n) < n log 2 n
c) n log 2 n < t (n) < n C 2
d) t (n) = n C 2
Respuesta (a)
Deje que la array se ordene en orden ascendente, si la suma de los dos primeros elementos es menor que 1000, entonces hay dos elementos con una suma menor que 1000; de lo contrario, no. Para una array ordenada en orden descendente, debemos verificar los dos últimos elementos. Para una estructura de datos de array, el número de operaciones es fijo en ambos casos y no depende de n, la complejidad es O (1)
5. Los árboles B+ son preferibles a los árboles binarios en las bases de datos porque (GATE CS 2000)
(a) Las capacidades del disco son mayores que las capacidades de la memoria
(b) El acceso al disco es mucho más lento que el acceso a la memoria
(c) Las tasas de transferencia de datos del disco son mucho menores que las de la memoria tasas de transferencia de datos
(d) Los discos son más confiables que la memoria
Respuesta (b)
El acceso al disco es lento y B+ Tree proporciona búsqueda en menos visitas al disco. Esto se debe principalmente a que, a diferencia de los árboles de búsqueda binarios, los árboles B+ tienen un abanico muy alto (normalmente del orden de 100 o más), lo que reduce el número de operaciones de E/S necesarias para encontrar un elemento en el árbol.
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