Estructuras de datos y algoritmos | conjunto 13

Se han hecho las siguientes preguntas en el examen GATE CS 2002

1. El número de Nodes hoja en un árbol enraizado de n Nodes, donde cada Node tiene 0 o 3 hijos es:
a) n/2
b) (n-1)/3
c) (n-1)/2
d) (2n+1)/3

Respuesta (d)

Sea L el número de Nodes de hoja y yo el número de Nodes internos, luego la siguiente relación se cumple para el árbol anterior (para obtener más detalles, consulte la pregunta 3 de https://www.geeksforgeeks.org/data-structures-and- algoritmos-set-11/ )

  L = (3-1)I + 1 = 2I + 1

El número total de Nodes (n) es la suma de los Nodes hoja y los Nodes internos

  n = L + I 

Después de resolver los dos anteriores, obtenemos L = (2n+1)/3

2. El tiempo de ejecución del siguiente algoritmo

  Procedure A(n)  
  If n <= 2 return(1) else return A();

se describe mejor mediante
a) O(n)
b) O(log n)
c) O(1og log n)
d) O(1)

Respuesta (c)
Para obtener una explicación, consulte la pregunta 5 de https://www.geeksforgeeks.org/data-structures-and-algorithms-set-11/

3. Un árbol de peso equilibrado es un árbol binario en el que para cada Node. El número de Nodes en el subárbol izquierdo es al menos la mitad y como máximo el doble del número de Nodes en el subárbol derecho. ¿Cuál de las siguientes describe mejor la altura máxima posible (número de Nodes en el camino desde la raíz hasta la hoja más lejana) de tal árbol en n Nodes?
a) log ₂ n
b) log _4/3 n
c) log ₃ n
d) log _3/2 n

Respuesta (d)

Sea H(n) la máxima altura posible de un árbol con n Nodes.

El valor máximo posible de H(n) se puede escribir aproximadamente usando la siguiente recursión:

   H(n) = H(2n/3) + 1     

La solución de la recurrencia anterior es log _3/2 n. Simplemente podemos obtenerlo dibujando un árbol de recurrencia.

4. Considere el siguiente algoritmo para buscar un número dado x en una array sin clasificar A[1..n] que tiene n valores distintos:

1)    Choose an i uniformly at random from 1..n; 
2)    If A[i] = x then Stop else Goto 1; 

Suponiendo que x está presente en A, ¿cuál es el número esperado de comparaciones realizadas por el algoritmo antes de que termine?
a) n
b) nl
c) 2n
d) n/2

Respuesta (a)

Si recuerdas las preguntas sobre monedas y dados, puedes adivinar la respuesta a las anteriores.

A continuación se muestra la prueba de la respuesta.

Sea E el número esperado de comparaciones. El valor de E es la suma de la siguiente expresión para todos los casos posibles.

number_of_comparisons_for_a_case * probability_for_the_case 

Caso 1

  If A[i] is found in the first attempt 
  number of comparisons = 1
  probability of the case  = 1/n

Caso 2

  If A[i] is found in the second attempt 
  number of comparisons = 2
  probability of the case  = (n-1)/n*1/n

Caso 3

  If A[i] is found in the third attempt 
  number of comparisons = 2
  probability of the case  = (n-1)/n*(n-1)/n*1/n

En realidad, hay infinitos casos de este tipo. Entonces, tenemos las siguientes series infinitas para E.

E  = 1/n + [(n-1)/n]*[1/n]*2 + [(n-1)/n]*[(n-1)/n]*[1/n]*3 + ….  (1)

Después de multiplicar la ecuación (1) por (n-1)/n, obtenemos

E (n-1)/n = [(n-1)/n]*[1/n] + [(n-1)/n]*[(n-1)/n]*[1/n]*2 + 
                                 [(n-1)/n]*[(n-1)/n]*[(n-1)/n]*[1/n]*3 ……….(2)

Restando (2) de (1), obtenemos

E/n = 1/n + (n-1)/n*1/n + (n-1)/n*(n-1)/n*1/n + …………

La expresión del lado derecho es un GP con infinitos elementos. Apliquemos la fórmula de la suma (a/(1-r))

  E/n = [1/n]/[1-(n-1)/n]  = 1
  E = n

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.