Estructuras de datos y algoritmos | conjunto 7

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

1. En un montón máximo binario que contiene n números, el elemento más pequeño se puede encontrar en el tiempo (GATE CS 2006)
(A) 0(n)
(B) O(logn)
(C) 0(loglogn)
(D) 0( 1)

Respuesta (A)
En un montón máximo, el elemento más pequeño siempre está presente en un Node hoja. Entonces, debemos verificar todos los Nodes de hoja para el valor mínimo. La complejidad del peor de los casos será O(n)

         12
        /  \
      /      \
    8         7
   / \        / \
 /     \    /     \
2      3   4       5

2. Un esquema para almacenar árboles binarios en una array X es el siguiente. La indexación de X comienza en 1 en lugar de 0. la raíz se almacena en X[1]. Para un Node almacenado en X[i], el hijo izquierdo, si lo hay, se almacena en X[2i] y el hijo derecho, si lo hay, en X[2i+1]. Para poder almacenar cualquier árbol binario en n vértices, el tamaño mínimo de X debe ser. (GATE CS 2006)
(A) log2n
(B) n
(C) 2n + 1
(D) 2^n — 1

Respuesta (D)
Para un árbol binario sesgado a la derecha, el número de Nodes será 2^n – 1. Por ejemplo, en el árbol binario siguiente, el Node ‘A’ se almacenará en el índice 1, ‘B’ en el índice 3, ‘C ‘ en el índice 7 y ‘D’ en el índice 15.

A
 \
   \
    B
      \
        \
         C
           \
             \
              D

3. ¿Cuál de los siguientes algoritmos de clasificación en el lugar necesita la cantidad mínima de intercambios? (GATE CS 2006)
(A) Clasificación rápida
(B) Clasificación por inserción
(C) Clasificación por selección
(D) Clasificación en montón

Respuesta (C)
Para la ordenación por selección, el número de intercambios requeridos es mínimo ( Θ(n) ).

4. Un elemento en un arreglo X se llama líder si es mayor que todos los elementos a su derecha en X. El mejor algoritmo para encontrar todos los líderes en un arreglo (GATE CS 2006)
(A) Lo resuelve en tiempo lineal usando un pase de izquierda a derecha del arreglo
(B) Lo resuelve en tiempo lineal usando un pase de derecha a izquierda del arreglo
(C) Lo resuelve usando divide y vencerás en el tiempo 8(nlogn)
(D) Lo resuelve en el tiempo 8( n2)

Respuesta (B)
Consulte esta publicación para obtener una explicación.

5. Considere un gráfico completo ponderado G en el conjunto de vértices {v1, v2, ..vn} tal que el peso de la arista (vi, vj) es 2|ij|. El peso de un árbol de expansión mínimo de G es: (GATE CS 2006)
(A) n — 1
(B) 2n — 2
(C) nC2
(D) 2

Respuesta (B)
El árbol de expansión mínimo de dicho gráfico es

v1
  \
    v2
      \
       v3
         \
          v4
            .
              .
                .
                 vn
 

Peso del árbol de expansión mínimo
= 2|2 – 1| + 2|3 – 2| + 2|4 – 3| + 2|5 – 4| …. + 2| n – (n-1) |
= 2n – 2

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.