Considere un enfoque de hashing dinámico para claves enteras de 4 bits:
- (A) Hay una tabla hash principal de tamaño 4.
- (B) Los 2 bits menos significativos de una clave se utilizan para indexar en la tabla hash principal.
- (C) Inicialmente, las entradas de la tabla hash principal están vacías.
- (D) A partir de entonces, cuando se agregan más claves, para resolver colisiones, el conjunto de todas las claves correspondientes a una entrada principal de la tabla hash se organiza como un árbol binario que crece según la demanda.
- (E) Primero, el tercer bit menos significativo se usa para dividir las claves en subárboles izquierdo y derecho.
- (F) Para resolver más colisiones, cada Node del árbol binario se subdivide en subárboles izquierdo y derecho en función del cuarto bit menos significativo.
- (G) Se hace un split solo si es necesario, es decir, solo cuando hay una colisión.
Considere el siguiente estado de la tabla hash.
¿Cuál de las siguientes secuencias de inserciones de claves puede causar el estado anterior de la tabla hash (suponiendo que las claves están en notación decimal)?
(A) 5,9,4,13,10,7
(B) 9,5,10,6,7,1
(C) 10,9,6,7,5,13
(D) 9,5,13 ,6,10,14
Respuesta: (C)
Explicación: La secuencia dada en la opción (A) no es posible debido a la entrada 4 (= 0100) que no está en la tabla hash final.
La secuencia proporcionada en la opción (B) no es posible debido a que las entradas 1 (=0001) y 9 (=1001) resuelven la colisión en el lado 0 en función del tercer LSB.
La secuencia dada en la opción (C) es la secuencia correcta para obtener la tabla hash final.
La secuencia dada en la opción (D) no es posible, debido a la entrada 6 (=0110), 10 (=1010) y 14 (=1110) en la tercera columna, la secuencia 3 no se da en la tabla hash final.
Cuestionario de esta pregunta
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