Estructuras de datos y algoritmos | Conjunto 23

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

1. ¿Cuál de los siguientes es un factor clave para preferir los árboles B a los árboles de búsqueda binarios para indexar las relaciones de la base de datos?
(a) Las relaciones de la base de datos tienen una gran cantidad de registros
(b) Las relaciones de la base de datos se ordenan según la clave principal
(c) Los árboles B requieren menos memoria que los árboles de búsqueda binarios
(d) Los discos de formulario de transferencia de datos se realizan en bloques.

Respuesta (d)
Un bloque de disco contiene un número bastante grande de claves. A diferencia de BST, donde cada Node contiene solo una clave, B-Tree está diseñado para contener una gran cantidad de claves, por lo que la altura del árbol es pequeña.

2. ¿Cuántos árboles de búsqueda binarios distintos se pueden crear a partir de 4 claves distintas?
(a) 5
(b) 14
(c) 24
(d) 42

Respuesta (b)

Aquí hay una forma sistemática de enumerar estos BST. Considere todos los árboles de búsqueda binarios posibles con cada elemento en la raíz. Si hay n Nodes, entonces para cada opción de Node raíz, hay n – 1 Nodes no raíz y estos Nodes no raíz deben dividirse en aquellos que son menores que una raíz elegida y aquellos que son mayores que la raíz elegida .

Digamos que se elige el Node i para que sea la raíz. Luego hay i – 1 Nodes más pequeños que i y n – i Nodes más grandes que i. Para cada uno de estos dos conjuntos de Nodes, existe un cierto número de subárboles posibles.

Sea t(n) el número total de BST con n Nodes. El número total de BST con i en la raíz es t(i – 1) t(n – i). Los dos términos se multiplican juntos porque los arreglos en los subárboles izquierdo y derecho son independientes. Es decir, para cada arreglo en el árbol de la izquierda y para cada arreglo en el árbol de la derecha, obtienes un BST con i en la raíz.

Sumar sobre i da el número total de árboles de búsqueda binarios con n Nodes.

El caso base es t(0) = 1 y t(1) = 1, es decir, hay un BST vacío y hay un BST con un Node.

3. En un árbol k-ario completo, cada Node interno tiene exactamente k hijos. El número de hojas en tal árbol con n Nodes internos es:
(a) nk
(b) (n – 1) k+ 1
(c) n( k – 1) + 1
(d) n(k – 1)

Respuesta (c)

4) Supongamos que T(n) = 2T(n/2) + n, T(0) = T(1) = 1
¿Cuál de las siguientes es falsa?
a) T(n) = O(n^2)
b) T(n) = Θ(nLogn)
c) T(n) = Ω(n ² )
d) T(n) = O(nLogn)

Respuesta (c)
La relación de recurrencia dada se puede resolver usando el Teorema del Maestro . Se encuentra en el caso 2 del Teorema del Maestro. O, si recuerda la relación de recurrencia de Merge Sort o, en el mejor de los casos, Quick Sort, puede adivinar el valor de T(n).

T(n) = Θ(nLog)

Por definición de la notación Big O , podemos decir.
Θ(nLogn) = O(nLogn) = O(n^2)

Θ(nLogn) puede ser igual a Ω(n) o Ω(nLogn), pero no Ω(n^2)

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.