Estructuras de datos y algoritmos | Conjunto 37

Pregunta: 1. Para 8 claves y 6 ranuras en una tabla hash con hash y enstringmiento uniformes, ¿cuál es la cantidad esperada de elementos que generan hash en una ubicación en particular? 
(A) 2,33 
(B) 0,75 
(C) 1,33 
(D) 2 

Solución: 
Probabilidad de que key1 termine en la ranura 1 = 1/6 
Probabilidad de que key2 termine en la ranura 1 = 1/6 
Probabilidad de que key3 termine en la ranura x = 1/6 
Probabilidad de que key4 termine en la ranura x = 1/6 
Probabilidad de que la clave 5 termine en la ranura x = 1/6 
Probabilidad de que la clave 6 termine en la ranura x = 1/6 
Número esperado de elementos que generan hash en una ubicación particular = 8/6 
La opción (C) es correcta. 

Que – 2. Para n claves y m ranuras en una tabla hash, ¿cuál de las siguientes es la cantidad esperada de ubicaciones vacías? 
(A) n((m-1)/m)^n 
(B) m((m-1)/m)^n 
(C) n((n-1)/m)^n 
(D) n( (n-1)/n)^m 

Solución: 
cantidad esperada de elementos que se desplazan a una ubicación determinada = n/m 
Probabilidad de que la ranura 1 esté vacía después de insertar n claves = ((m-1)/m)^n 
Probabilidad de que la ranura 2 esté vacía después de insertar n claves = ((m-1)/m)^n 
Probabilidad de que la ranura 3 esté vacía después de insertar n llaves = ((m-1)/m)^n 
Entonces, para m ranuras, número esperado de ubicaciones vacías = m((m- 1)/m)^n 
La opción (B) es correcta. 

Que – 3. ¿Cuál es el número de árboles de búsqueda binarios con 20 Nodes con elementos 1, 2, 3,…..20 tal que la raíz del árbol es 12 y la raíz del subárbol izquierdo es 7? 
(A) 2634240 
(B) 1243561 
(C) 350016 
(D) 2642640 

Solución: 
Número de Nodes en el subárbol izquierdo = 11 {1, 2, 3, 4….11} 
Número de Nodes en el subárbol derecho = 8 {13, 14,….20} 
Ya que para el subárbol izquierdo la raíz es 7 
Número de elementos en la parte izquierda del subárbol izquierdo = 6 {1, 2, 3..6} 
Número de elementos en la parte derecha del subárbol izquierdo = 4 {8, 9, 10, 11} 
Conocemos el número de árboles de búsqueda binaria con n Nodes = (C(2n,n)/n+1) 
Número de BST con 6 Nodes = (C(12,6)/7) = 132 
Número de BST con 4 Nodes = (C(8,4)/5) = 14 
Número de BST con 8 Nodes = (C(16,8)/9) =1430 
Número total de BST = 2642640 
La opción (D) es correcta. 

Que – 4. Para un gráfico con aristas E y vértices V, ¿cuál es la complejidad temporal del algoritmo de Dijkstra que usa una array como estructura de datos para almacenar vértices no finalizados? ¿El gráfico no está dirigido y se representa como una lista de adyacencia? 
(A) O(VE) 
(B) O(ElogV) 
(C) O(V^2 ) 
(D) O(E^2log V) 

Solución: 
dado que la estructura de datos utilizada es una array, por lo que la inicialización de todos los Nodes en la array (estableciendo infinito en todos los Nodes que no son accesibles), esta operación toma O (V) 
En cada paso, debemos eliminar el mínimo de la array. Para una de estas operaciones se necesita O(V), utilizando el primer pase de ordenación por selección. Tenemos V tales pasos. Entonces, la complejidad total debido a la eliminación del elemento mínimo en cada paso = V * O (V) = O (V ^ 2) 
Después de seleccionar un mínimo en cada paso, debemos verificar su adyacente y realizar una tecla de disminución para los vecinos del Node seleccionado . Se necesita un total de O(2E) para verificar los adyacentes en todos los pasos. También la clave de disminución de todos los pasos es E. O(1) = O(E) . Dado que la array no está ordenada, no tenemos que ordenar la array en cada paso. 
Complejidad total = O(V) + O(V^2) + O(2E) + O(E) = O(V^2) 
Nota: Para un gráfico simple, V^2 siempre es >= E 
La opción (C) es correcta. 

Que – 5. ¿Cuál es el resultado del siguiente programa? 
 

int a = 5;
main()
{
   extern int a;
   extern int a;
   printf(a);
}

(A) Error de tiempo de compilación. 
(B) Error de tiempo de ejecución. 
(C) 0 
(D) 5 

Solución: 
el programa anterior no causa ningún error de tiempo de compilación ya que extern no asigna ninguna memoria. Entonces, dentro de una declaración de función de la misma variable que extern no causa ningún error siempre que la variable se declare globalmente. La salida es 5. 
La opción (D) es correcta.