Рубрики

Структуры данных | Хэш | Вопрос 4

Структуры данных

Рассмотрим хеш-таблицу седьмого размера с начальным индексом ноль и хеш-функцией (3x + 4) mod7. Предполагая, что хеш-таблица изначально пуста, что из следующего является содержимым таблицы, когда последовательность 1, 3, 8, 10 вставляется в таблицу с использованием закрытого хеширования? Обратите внимание, что «_» обозначает пустое место в таблице.
(A) 8, _, _, _, _, _, 10
(B) 1, 8, 10, _, _, _, 3
(C) 1, _, _, _, _, _, 3
(D) 1, 10, 8, _, _, _, 3

Ответ: (Б)
Объяснение: Пожалуйста, смотрите http://lcm.csa.iisc.ernet.in/dsa/node38.html для закрытого хеширования и зондирования.

Положим значения 1, 3, 8, 10 в хэш размера 7.

Изначально хеш-таблица пуста

    -    -    -   -   -   -   -
    0    1   2   3   4   5   6

Значение функции (3x + 4) mod 7 для 1 равно 0, поэтому давайте поместим значение в 0

    1    -    -   -   -   -   -
    0    1   2   3   4   5   6

Значение функции (3x + 4) mod 7 для 3 равно 6, поэтому давайте поместим значение в 6

    1    -    -   -   -   -   3
    0    1   2   3   4   5   6

Значение функции (3x + 4) mod 7 для 8 равно 0, но 0 уже занято, поместим значение (8) в следующее доступное пространство (1)

    1    8    -   -   -   -   3
    0    1   2   3   4   5   6

Значение функции (3x + 4) mod 7 для 10 равно 6, но 6 уже занято, поместим значение (10) в следующее доступное пространство (2)

    1    8   10   -   -   -   3
    0    1   2    3   4   5   6

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

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

Структуры данных | Хэш | Вопрос 4

0.00 (0%) 0 votes