Estructuras de datos y algoritmos | conjunto 10

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

1. La altura de un árbol binario es el número máximo de aristas en cualquier camino de raíz a hoja. El número máximo de Nodes en un árbol binario de altura h es:
(A) 2^h -1
(B) 2^(h-1) – 1
(C) 2^(h+1) -1
(D) 2 *(h+1)

Respuesta (C)
Habrá un número máximo de Nodes para un árbol completo.
Número de Nodes en un árbol completo de altura h = 1 + 2 + 2^2 + 2*3 + …. 2^h = 2^(h+1) – 1

2: El número máximo de árboles binarios que se pueden formar con tres Nodes sin etiquetar es:
(A) 1
(B) 5
(C) 4
(D) 3

Respuesta (B)

             O
          /     \
        O        O
           (i)

            O             
          /                             
       O                 
     /                      
   O                         
        (ii)

         O
       / 
     O
        \
          O
       (iii)

  O                      
     \                        
       O                     
          \                  
           O                                                         
    (iv)

       O
          \
            O
          /
       O               
    (v)

Tenga en cuenta que los Nodes no están etiquetados. Si los Nodes están etiquetados, obtenemos más árboles.

3. ¿Cuál de los siguientes algoritmos de clasificación tiene la menor complejidad en el peor de los casos?
(A) Clasificación por combinación
(B) Clasificación por burbujas
(C) Clasificación rápida
(D) Clasificación por selección

Respuesta (A)

Las complejidades del peor de los casos para los algoritmos de ordenación anteriores son las siguientes:
Ordenación por combinación — nLogn Ordenación por
burbujas — n^2 Ordenación
rápida — n^2 Ordenación por
selección — n^2

4. La siguiente expresión de sufijo con operandos de un solo dígito se evalúa usando una pila:

              8 2 3 ^ / 2 3 * + 5 1 * - 

Tenga en cuenta que ^ es el operador de exponenciación. Los dos elementos superiores de la pila después de evaluar el primer * son:
(A) 6, 1
(B) 5, 7
(C) 3, 2
(D) 1, 5

Respuesta (A)
El algoritmo para evaluar cualquier expresión de sufijo es bastante sencillo:

1. While there are input tokens left
    o Read the next token from input.
    o If the token is a value
       + Push it onto the stack.
    o Otherwise, the token is an operator 
      (operator here includes both operators, and functions).
       * It is known a priori that the operator takes n arguments.
       * If there are fewer than n values on the stack
        (Error) The user has not input sufficient values in the expression.
       * Else, Pop the top n values from the stack.
       * Evaluate the operator, with the values as arguments.
       * Push the returned results, if any, back onto the stack.
2. If there is only one value in the stack
    o That value is the result of the calculation.
3. If there are more values in the stack
    o (Error)  The user input has too many values.

Fuente del algoritmo: http://en.wikipedia.org/wiki/Reverse_Polish_notation#The_postfix_algorithm

Ejecutemos el algoritmo anterior para la expresión dada.
Los primeros tres tokens son valores, por lo que simplemente se empujan. Después de empujar 8, 2 y 3, la pila es la siguiente

    8, 2, 3  

Cuando se lee ^, se abren los dos primeros y se calcula la potencia (2^3)

    8, 8 

Cuando se lee /, se abren los dos primeros y se realiza la división (8/8)

    1 

Los siguientes dos tokens son valores, por lo que simplemente se empujan. Después de empujar 2 y 3, la pila es la siguiente

    1, 2, 3

Cuando aparece *, se abren los dos primeros y se realiza la multiplicación.

    1, 6

5. Los recorridos en orden y en preorden de un árbol binario son dbeafcg y abdecfg, respectivamente. El recorrido posterior al orden del árbol binario es:
(A) debfgca
(B) edbgfca
(C) edbfgca
(D) defgbca

Respuesta (A)

Below is the given tree.
                              a 
                           /    \
                        /          \
                      b             c
                   /   \          /   \
                 /       \      /       \
               d         e    f          g

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.