PUERTA | PUERTA CS 1996 | Pregunta 63

Inserte los caracteres de la string KRPCSNYTJM en una tabla hash de tamaño 10.
Utilice la función hash

h(x) = ( ord(x) – ord("a") + 1 ) mod10

Si se usa sondeo lineal para resolver colisiones, entonces la siguiente inserción causa colisión
(A) Y
(B) C
(C) M
(D) P

Respuesta: (C)
Explicación:
(a) La tabla hash con tamaño 10 tendrá índice de 0 a 9.
función hash = h(x) = ((ord(x) – ord(A) + 1)) mod 10
Entonces, para la string KRPCSNYTJM:
K se insertará en el índice: (11-1+1) mod 10 = 1
R en índice: (18-1+1) mod 10 = 8
P en índice: (16-1+1) mod 10 = 6
C en índice: (3-1+1) mod 10 = 3
S en índice: (19-1+1) mod 10 = 9
N en índice: (14-1+1) mod 10 = 4
Y en índice (25-1+1) mod 10 = 5
T en índice (20-1+ 1) módulo 10 = 0
J en el índice (10-1+1) mod 10 = 0 // ocurre la primera colisión.
M en el índice (13-1+1) mod 10 = 3 //ocurre la segunda colisión.

Solo J y M están causando la colisión.

(b) La tabla hash final será:

0    T
1    K
2    J
3    C
4    N
5    Y
6    P
7    M
8    R
9    S

Cuestionario de esta pregunta