Экзаменационный вопрос о хеш-таблицах

Question

Я был озадачен формулировкой конкретного экзаменационного вопроса о хеш-таблицах. Насколько я понимаю, может быть два разных ответа в зависимости от интерпретации. Поэтому мне было интересно, если кто-то может помочь определить, какое понимание является правильным. Вопрос ниже:

У нас есть хеш-таблица размером 7 для хранения целочисленных ключей с хеш-функцией h (x) = x mod 7. Если мы используем линейное зондирование и вставляем элементы в порядке 1, 15, 14, 3, 9, 5 , 27, сколько раз элемент попытается переместиться на занятое место?

Я сломаю мои два разных понимания этого вопроса. Прежде всего начальные индексы каждого элемента будут:

1: 1
15: 1
14:00
3: 3
9: 2
5: 5
27: 6

Первое толкование:
1: вставляется в индекс 1
15: пытается перейти к индексу 1, но из-за столкновения перемещается влево к индексу 0. Количество столкновений = 1
14: пытается перейти к индексу 0, но из-за столкновения перемещается влево к индексу 6. Количество столкновений = 2
3: вставляется в указатель 3
9: вставляется в указатель 2
5: вставляется в указатель 5
27: пытается перейти к индексу 6, но из-за столкновений переходит к индексу 5, а затем к 4, который является пустым. Количество столкновений = 4

Ответ: 4?

Вторая интерпретация:
Считайте только время, когда 27 пытается перейти к занятому индексу 5 из-за столкновения с элементом в индексе 6.

Ответ: 1?

Какой ответ будет правильным?

Спасибо.

Answer 1

Глупая формулировка.

Учитель, возможно, хочет № 1, но я бы сказал, что № 2 педантически правильный , потому что элемент когда-либо только попытается переместить в занятую точку один раз , как указано. В других случаях он не перемещает в занятую точку, а скорее из занятой точки в свободную точку.

Тесты в школе довольно глупы - учитель (или ТА) уже знает, чего он хочет. Существует грань между «быть педантично правильным » и «давать учителю то, что он хочет». (Просто никогда, никогда не поддавайся доказуемо неправым!)

Одна вещь, у которой никогда (по крайней мере, что я помню ;-) провалила меня в тесте или домашнем задании, - это предоставление ответа с твердым и правильным обоснованием за ответ; это может также включать объяснение «другого» ответа.

Учитель / окружение, репертуар, гордыня и класс (если назвать несколько) должны быть сбалансированы.

Счастливого обучения.

Answer 2

Интерпретация 1 верна. Столкновение с 6 означает, что слот 6 занят, так почему бы вам не посчитать его?