Estructuras de datos y algoritmos | Conjunto 38

Este tema contiene preguntas básicas de algoritmo que pueden ser útiles para la preparación de GATE CS . Por lo tanto, se recomienda resolver cada una de estas preguntas si se está preparando para GATE.

Pregunta-1: ¿Cuál de los siguientes determina correctamente la solución de la relación de recurrencia dada a continuación con T(1) = 1?

T(n)= 2T(n/4) + n1/2 

(A) O(n ² )
(B) O(n)
(C) O(n ^1/2 log n)
(D) O(log n)

Explicación:
Según el Teorema del Maestro ,

T(n)= 2T(n/4) + n1/2 

Aplicando el teorema de Masters,
aquí,

a = 2, b = 4, K = 1/2, and p = 0 

So, bK = 41/2 = 2 
Thus, a = bK and (p > -1) 

Entonces, la fórmula es,

T(n)= O(nlogba log(P+1)n)

Por lo tanto,

T(n) = O(nlog 42 log(0 + 1)n) = O(n1/2 log n)

Entonces, la opción (C) es correcta.

Ques-2: para fusionar dos listas sin clasificar de tamaño p y q en una lista ordenada de tamaño (p + q). La complejidad del tiempo en términos de número de comparaciones es:

(A) O(log p + log q)
(B) O(p log p) + q log q)
(C) O(p + q)
(D) Ninguno

Explicación:
para ordenar la array de tamaño p individualmente, se necesita O (p log p) y la array de tamaño q toma O (q log q) tiempo, luego la fusión tomará O (m + n) tiempo.
Por lo tanto, el número total de comparaciones

= O(p log p) + O(q log q) + p + q
= O(p log p) + O(q log q) 

Entonces, la opción (B) es correcta.

Pregunta 3: ¿Cuál de los siguientes algoritmos de clasificación tiene la mayor complejidad de tiempo en el mejor de los casos utilizando una estructura de datos de array?

(A) Clasificación de montón
(B) Clasificación de inserción
(C) Clasificación de burbuja
(D) Clasificación de selección

Explicación:
En el mejor de los casos, la complejidad temporal de la clasificación Heap es O(n log n) En el
mejor caso, la complejidad temporal de la clasificación por inserción es O(n) En el
mejor caso, la complejidad temporal de la clasificación Bubble es O(n) En el
mejor caso, la complejidad temporal de la clasificación por selección es O( n ² ).
Entonces, la opción (D) es correcta.

Ques-4: ¿Cuál de las siguientes entradas proporciona el mejor tiempo de caso para la ordenación por selección?

(A) 1 2 3 4 5 6 7 8 9
(B) 2 3 1 5 9 7 8 6
(C) 9 8 7 6 5 4 3 2 1
(D) Todo lo anterior toma la misma cantidad de tiempo.

Explicación:
La ordenación por selección en el peor y mejor de los casos toma el mismo tiempo.
Entonces, la opción (D) es correcta.

Ques-5: ¿Cuál es la complejidad temporal de la función recursiva que se indica a continuación?

T(n)= 4T(n/2) + n2 

(A) O(n ² )
(B) O(n)
(C) O(n ² log n)
(D) O(n log n)

Explicación:
Según el teorema del maestro ,
aquí,

a = 4, b = 2, k = 2, p = 0 

So, bk = 4 i.e., a = bk 

Por lo tanto, la fórmula es

T(n) = O(nlog ba log(P+1)n)

So, T(n)= O(nlog 24 log(0 + 1)n) = O(n2 log n)

Entonces, la opción (C) es correcta.