Рубрики

ВОРОТА | GATE-CS-2014- (Set-1) | Вопрос 65

Рассмотрим хеш-таблицу с 9 слотами. Хеш-функция ℎ (k) = k mod 9 . Столкновения разрешаются цепочкой. Следующие 9 ключей вставляются в порядке: 5, 28, 19, 15, 20, 33, 12, 17, 10. Максимальная, минимальная и средняя длины цепей в хеш-таблице, соответственно,

(А) 3, 0 и 1
(B) 3, 3 и 3
(С) 4, 0 и 1
(D) 3, 0 и 2

Ответ: (А)
Объяснение: Ниже приведены значения хэш-функции для всех ключей.

 5 --> 5
28 --> 1
19 --> 1  [Chained with 28]
15 --> 6
20 --> 2
33 --> 6  [Chained with 15]
12 --> 3
17 --> 8
10 --> 1 [Chained with 28 and 19]

Максимальная длина цепи равна 3. Ключи 28, 19 и 10 идут в один и тот же слот 1 и образуют цепь длиной 3.
Минимальная длина цепи 0, есть пустые слоты (0, 4 и 7).
Средняя длина цепи составляет (0 + 3 + 1 + 1 + 0 + 1 + 2 + 0 + 1) / 9 = 1
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2014- (Set-1) | Вопрос 65

0.00 (0%) 0 votes