Se han hecho las siguientes preguntas en el examen GATE CS 2007.
1. Considere una tabla hash de tamaño siete, con índice inicial cero y una función hash (3x + 4) mod7. Suponiendo que la tabla hash está inicialmente vacía, ¿cuál de los siguientes es el contenido de la tabla cuando la secuencia 1, 3, 8, 10 se inserta en la tabla usando hash cerrado? Tenga en cuenta que ‘_’ indica una ubicación vacía en la tabla.
(A) 8, _, _, _, _, _, 10
(B) 1, 8, 10, _, _, _, 3
(C) 1, _, _, _, _, _,3
(D ) 1, 10, 8, _, _, _, 3
Respuesta (B)
Consulte http://lcm.csa.iisc.ernet.in/dsa/node38.html para conocer el hash y el sondeo cerrados.
Pongamos los valores 1, 3, 8, 10 en el hash de tamaño 7.
Inicialmente, la tabla hash está vacía
- - - - - - -
0 1 2 3 4 5 6
El valor de la función (3x + 4) mod 7 para 1 es 0, entonces pongamos el valor en 0
1 - - - - - -
0 1 2 3 4 5 6
El valor de la función (3x + 4) mod 7 para 3 es 6, así que pongamos el valor en 6
1 - - - - - 3
0 1 2 3 4 5 6
El valor de la función (3x + 4) mod 7 para 8 es 0, pero 0 ya está ocupado, pongamos el valor (8) en el siguiente espacio disponible (1)
1 8 - - - - 3
0 1 2 3 4 5 6
El valor de la función (3x + 4) mod 7 para 10 es 6, pero 6 ya está ocupado, pongamos el valor (10) en el siguiente espacio disponible (2)
1 8 10 - - - 3
0 1 2 3 4 5 6
2. En un grafo conectado no dirigido y no ponderado, la ruta más corta desde un Node S a todos los demás Nodes se calcula de manera más eficiente, en términos de complejidad de tiempo, mediante
(A) el algoritmo de Dijkstra que comienza en S.
(B) el algoritmo de Warshall
(C) Realización un DFS a partir de S.
(D) Realización de un BFS a partir de S.
Respuesta (D)
* Time Complexity of the Dijkstra’s algorithm is O(|V|^2 + E) * Time Complexity of the Warshall’s algorithm is O(|V|^3) * DFS cannot be used for finding shortest paths * BFS can be used for unweighted graphs. Time Complexity for BFS is O(|E| + |V|)
3. Un árbol n-ario completo es un árbol en el que cada Node tiene n hijos o no tiene hijos. Sea I el número de Nodes internos y L el número de hojas en un árbol n-ario completo. Si L = 41 e I = 10, ¿cuál es el valor de n?
(A) 3
(B) 4
(C) 5
(D) 6
Respuesta (C)
Para un árbol n-ario donde cada Node tiene n hijos o ningún hijo, se cumple la siguiente relación
L = (n-1)*I + 1
Donde L es el número de Nodes hoja e I es el número de Nodes internos.
Averigüemos el valor de n para los datos dados.
L = 41 , I = 10 41 = 10*(n-1) + 1 (n-1) = 4 n = 5
4. En la siguiente función C, sea n >= m.
c
int gcd(n,m)
{
if (n%m ==0) return m;
n = n%m;
return gcd(m,n);
}
¿Cuántas llamadas recursivas realiza esta función?
(A) Θ(inicio de sesión)?
(B) Ω(n)
(C) Θ(loglogn)
(D) Θ(sqrt(n))
Respuesta (A) El
código anterior es una implementación del algoritmo euclidiano para encontrar el máximo común divisor (GCD).
Consulte http://mathworld.wolfram.com/EuclideanAlgorithm.html para conocer la complejidad del tiempo.
5. ¿Cuál es la complejidad temporal de la siguiente función recursiva:
c
int DoSomething (int n)
{
if (n <= 2)
return 1;
else
return (DoSomething (floor(sqrt(n))) + n);
}
(A) Θ(n)
(B) Θ(nlogn)
(C) Θ(logn)
(D) Θ(loglogn)
Respuesta (D)
La relación recursiva para DoSomething() es
T(n) = T(√n) + C1 if n > 2
Hemos ignorado la parte del piso() ya que aquí no importa si es un piso o un techo.
Let n = 2^m, T(n) = T(2^m)
Let T(2^m) = S(m)
From the above two, T(n) = S(m)
S(m) = S(m/2) + C1 /* This is simply binary search recursion*/
S(m) = O(logm)
= O(loglogn) /* Since n = 2^m */
Now, let us go back to the original recursive function T(n)
T(n) = S(m)
= O(LogLogn)
Consulte GATE Corner para ver todos los trabajos/soluciones/explicaciones del año anterior, plan 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.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA