Estructuras de datos y algoritmos | conjunto 22

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

1) Un programa P lee 500 números enteros en el rango [0..100] que representan las puntuaciones de 500 estudiantes. Luego imprime la frecuencia de cada puntaje por encima de 50. ¿Cuál sería la mejor manera para que P almacenara las frecuencias?
(a) Una array de 50 números
(b) Una array de 100 números
(c) Una array de 500 números
(d) Una array de 550 números asignados dinámicamente

Respuesta (a)
Una array de tamaño 50 parece la mejor opción para almacenar el número de estudiantes para cada puntaje. Necesitamos almacenar frecuencias de puntuaciones superiores a 50. Podemos ignorar las puntuaciones inferiores a 50 y para indexar las puntuaciones superiores a 50, podemos restar 50 del valor de la puntuación/

2) Un grafo no dirigido G tiene n Nodes. Su array de adyacencia viene dada por una array cuadrada de n × n cuyos (i) elementos diagonales son 0 y (ii) elementos no diagonales son 1. ¿Cuál de las siguientes es VERDADERA?
(a) El gráfico G no tiene un árbol de expansión mínimo (MST)
(b) El gráfico G tiene un MST único de costo n-1
(c) El gráfico G tiene múltiples MST distintos, cada uno de costo n-1
(d) El gráfico G tiene múltiples árboles de expansión de diferentes costos

Respuesta (c)
Si todos los elementos no diagonales son 1, entonces cada vértice está conectado a todos los demás vértices en el gráfico con un borde de peso 1. Tal gráfico tiene múltiples MST distintos con costo n-1. Vea el siguiente ejemplo.

El gráfico conectado:

A continuación se muestran tres árboles de expansión mínimos, cada uno de costo 2.0.
Árbol de expansión mínimo 1

Minimum Spanning Tree 2

Minimum Spanning Tree 3

3) Se sabe que la complejidad temporal de calcular el cierre transitivo de una relación binaria en un conjunto de n elementos es:
a) O(n)
b) O(nLogn)
c) O(n^(3/2))
d ) O(n^3)

Respuesta (d)
En matemáticas, la clausura transitiva de una relación binaria R en un conjunto X es la relación transitiva más pequeña en X que contiene a R. Si la relación original es transitiva, la clausura transitiva será esa misma relación; de lo contrario, la clausura transitiva será una relación diferente.

En informática, se puede pensar en el concepto de cierre transitivo como la construcción de una estructura de datos que hace posible responder preguntas de accesibilidad. Es decir, ¿se puede ir del Node a al Node b en uno o más saltos? Una relación binaria solo le dice que el Node a está conectado al Node b, y que el Node b está conectado al Node c, etc. Después de construir el cierre transitivo en una operación O(1), se puede determinar que el Node c es accesible desde el Node una.

El algoritmo de Warshall se puede utilizar para construir el cierre transitivo de grafos dirigidos(). En la formulación original del algoritmo de Warshall, el gráfico no está ponderado y está representado por una array de adyacencia booleana. Entonces la operación de suma se reemplaza por la conjunción lógica (AND) y la operación de mínimo por la disyunción lógica (OR).

Referencias:
http://en.wikipedia.org/wiki/Floyd%E2%80%93Warshall_algorithm
http://en.wikipedia.org/wiki/Transitive_closure

4. Se implementa una Priority-Queue como Max-Heap. Inicialmente, tiene 5 elementos. El recorrido de orden de nivel del montón se da a continuación:
10, 8, 5, 3, 2
Dos nuevos elementos ‘1’ y ‘7’ se insertan en el montón en ese orden. El recorrido de orden de nivel del montón después de la inserción de los elementos es:
(a) 10, 8, 7, 5, 3, 2, 1
(b) 10, 8, 7, 2, 3, 1, 5
(c ) 10, 8, 7, 1, 2, 3, 5
(d) 10, 8, 7, 3, 2, 1, 5

Respuesta (D)

Max-Heap original es:

        10
       /  \
      8    5
     / \
    3   2

Después de la inserción de 1.

         10
       /    \
      8      5
     / \    /
    3   2 1 

Después de la inserción de 7.

         10
       /   \
      8     7
    / \    / \ 
   3   2  1   5

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.