Estructuras de datos y algoritmos | Conjunto 28

Las siguientes preguntas se han hecho en el examen GATE 2012. 

1) Deje que w(n) y A(n) denoten respectivamente, el peor caso y el tiempo promedio de ejecución del caso de un algoritmo ejecutado en una entrada de tamaño n. ¿Cuál de las siguientes es SIEMPRE CIERTA?  
(A) A(n) = Ω(W(n)) 
(B) A(n) = Θ(W(n)) 
(C) A(n) = O(W(n)) 
(D) A( n) = o(W(n)) 

Respuesta (C) 
La complejidad de tiempo del peor de los casos siempre es mayor o igual que la complejidad de tiempo del caso promedio. 

2) El peor tiempo de ejecución para buscar un elemento en un árbol de búsqueda binario equilibrado con n2^n elementos es 
(A) Θ(n log n) 
(B) Θ(n2 ⁿ ) 
(C) Θ(n) 
(D) Θ(log n) 

Respuesta (C) 
El tiempo necesario para buscar un elemento es Θ(h), donde h es la altura del árbol de búsqueda binaria (BST). El crecimiento de la altura de un BST equilibrado es logarítmico en términos de número de Nodes. Entonces, el peor momento para buscar un elemento sería Θ(Log(n*2^n)) que es Θ(Log(n) + Log(2^n)) Que es Θ(Log(n) + n) que se puede escribir como Θ(n). 

3) Suponiendo que P != NP, ¿cuál de las siguientes es verdadera?  
(A) NP-completo = NP 
(B) NP-completo ∩ P = Φ 
(C) NP-duro = NP 
(D) P = NP-completo 

Respuesta (B) 
La respuesta es B (ningún problema NP-Completo se puede resolver en tiempo polinomial). Porque, si un problema NP-Completo se puede resolver en tiempo polinomial, entonces todos los problemas NP se pueden resolver en tiempo polinomial. Si ese es el caso, entonces NP y P se vuelven iguales, lo que contradice la condición dada. 

4) La altura de un árbol se define como el número de aristas en el camino más largo del árbol. La función que se muestra en el pseudocódigo a continuación se invoca como altura (raíz) para calcular la altura de un árbol binario con raíz en la raíz del puntero del árbol. 

La expresión apropiada para los dos cuadros B1 y B2 son 
(A) B1 : (1 + altura(n->derecha)), B2 : (1 + max(h1,h2)) 
(B) B1 : (altura(n- >derecha)), B2 : (1 + max(h1,h2)) 
(C) B1 : altura(n->derecha), B2 : max(h1,h2) 
(D) B1 : (1 + altura(n- >derecha)), B2 : max(h1,h2) 

Respuesta (A) 
El cuadro B1 se ejecuta cuando el subárbol izquierdo de n es NULL y el subárbol derecho no es NULL. En este caso, la altura de n será la altura del subárbol derecho más uno. 
El cuadro B2 se ejecuta cuando los subárboles izquierdo y derecho de n no son NULL. En este caso, la altura de n será el máximo de las alturas de los subárboles izquierdo y derecho de n más 1. 

5) Una lista de n strings, cada una de longitud n, se clasifica en orden lexicográfico utilizando el algoritmo de clasificación por combinación. El peor tiempo de ejecución de este cálculo es 
(A) O(n log n ) 
(B) O(n ² log n) 
(C) O(n^2 + log n) 
(D) O(n^2) 

Respuesta (B) 
El árbol de recurrencia para la ordenación por combinación tendrá una altura Logn. Y el trabajo O(n ² ) se realizará en cada nivel del árbol de recurrencia (Cada nivel implica n comparaciones y una comparación toma O(n) tiempo en el peor de los casos). Entonces, la complejidad del tiempo de esta ordenación combinada será O (n ² log n). 

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.