Estructuras de datos y algoritmos | Conjunto 18

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

1. Considere el polinomio p(x) = a0 + a1x + a2x^2 +a3x^3, donde ai != 0, para todo i. El número mínimo de multiplicaciones necesarias para evaluar p en una entrada x es:

(A) 3
(B) 4
(C) 6
(D) 9

Respuesta (A)

Las multiplicaciones se pueden minimizar usando el siguiente orden para evaluar la expresión dada.
p(x) = a0 + x(a1 + x(a2 + a3x))

2. Para implementar el algoritmo de ruta más corta de Dijkstra en gráficos no ponderados para que se ejecute en tiempo lineal, la estructura de datos que se utilizará es:
(A) Cola
(B) Pila
(C) Heap
(D) B-Tree

Respuesta (A)
El camino más corto en un gráfico no ponderado significa el menor número de aristas que se deben atravesar para llegar al destino en el gráfico. Este es el mismo problema que resolver la versión ponderada donde todos los pesos son 1. Si usamos Queue (FIFO) en lugar de Priority Queue (Min Heap), obtenemos la ruta más corta en tiempo lineal O(|V| + | E|). Básicamente, hacemos un recorrido BFS del gráfico para obtener los caminos más cortos.

3. Un montón máximo de 3 arios es como un montón máximo binario, pero en lugar de 2 hijos, los Nodes tienen 3 hijos. Un montón de 3 arios se puede representar mediante una array de la siguiente manera: la raíz se almacena en la primera ubicación, a[0], los Nodes en el siguiente nivel, de izquierda a derecha, se almacenan de a[1] a a[3 ]. Los Nodes del segundo nivel del árbol de izquierda a derecha se almacenan desde una ubicación [4] en adelante. Un elemento x se puede insertar en un montón tripartito que contiene n elementos colocando x en la ubicación a[n] y empujándolo hacia arriba en el árbol para satisfacer la propiedad del montón.

¿Cuál de las siguientes es una secuencia válida de elementos en una array que representa un montón máximo de 3 arios?
(A) 1, 3, 5, 6, 8, 9
(B) 9, 6, 3, 1, 8, 5
(C) 9, 3, 6, 8, 5, 1
(D) 9, 5, 6 , 8, 3, 1

Respuesta (D)

                                      9
                                   /  |   \
                                /     |     \
                              5       6      8
                           /  |
                         /    |
                       3      1

4. Suponga que los elementos 7, 2, 10 y 4 se insertan, en ese orden, en el montón máximo 3-ario válido que se encuentra en la pregunta anterior. ¿Cuál de las siguientes es la secuencia de elementos en la array que representa el montón resultante? ?
(A) 10, 7, 9, 8, 3, 1, 5, 2, 6, 4
(B) 10, 9, 8, 7, 6, 5, 4, 3, 2, 1
(C) 10, 9 , 4, 5, 7, 6, 8, 2, 1, 3
(D) 10, 8, 6, 9, 7, 2, 3, 4, 1, 5

Respuesta (A)

After insertion of 7
                                          9
                                      /   |   \
                                    /     |     \
                                  7       6       8
                               / | \
                             /   |  \
                            3    1    5    

Después de la inserción de 2

                                           9
                                      /    |   \
                                    /      |     \
                                  7        6       8
                               / | \       /
                             /   |  \     /
                            3    1    5  2

Después de la inserción de 10

                                 10
                             /    |   \
                           /      |     \
                        7         9       8
                    / | \       / |
                  /   |  \     /  |
                3    1    5  2    6

Después de la inserción de 4

                                 10
                             /   |   \
                           /     |     \
                         7        9       8
                      / | \      / | \
                    /   |  \    /  |   \
                  3    1    5  2   6    4

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.