Рубрики

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

Рассмотрим хеш-таблицу с 100 слотами. Столкновения разрешаются с использованием цепочки. Предполагая простое равномерное хеширование, какова вероятность того, что первые 3 слота будут незаполненными после первых 3 вставок?
(А) (97 × 97 × 97) / 100 3
(В) (99 × 98 × 97) / 100 3
(С) (97 × 96 × 95) / 100 3
(D) (97 × 96 × 95) / (3! × 100 3 )

Ответ: (А)
Пояснение: Простая Унифицированная хеш-функция — это гипотетическая хеш-функция, которая равномерно распределяет элементы в ячейках хеш-таблицы. Более того, каждый хешируемый элемент имеет равную вероятность помещения в слот, независимо от других уже размещенных элементов. (Источник: https://en.wikipedia.org/wiki/SUHA_%28computer_science%29 ).

Probability that the first 3 slots are unfilled after the first 3 insertions = 
                (probability that first item doesn't go in any of the first 3 slots)*
                (probability that second item doesn't go in any of the first 3 slots)*
                (probability that third item doesn't go in any of the first 3 slots)

                 = (97/100) * (97/100) * (97/100) 

Тест на этот вопрос

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

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

0.00 (0%) 0 votes