МИНИСТЕРСТВО ЦИФРОВОГО РАЗВИТИЯ, СВЯЗИ И МАССОВЫХ КОММУНИКАЦИЙ РОССИЙСКОЙ ФЕДЕРАЦИИ

Ордена Трудового Красного Знамени федеральное государственное бюджетное образовательное учреждение высшего образования

«Московский технический университет связи и информатики»

Кафедра «Сетевые информационные технологии и сервисы»

Дисциплина «Принципы построения систем управления базами данных и знаний»

Практическая работа 7

Выполнил:

студент группы БСТ2104

Станишевский И.А.

Вариант №19

Проверил: Гадасин Д. В.

Москва, 2023 г.

Содержание

1 Задание 1 3

2 Ход выполнения задания 1 4

1 Задание 1 3

2 Ход выполнения задания 1 4

1 Задание 1

Рисунок 1 – Пример хеш-таблицы

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

При условии, что блок может содержать 3 записи. Решение оформить в виде рисунка и дать подробное описание действий.

2 Ход выполнения задания 1

Исходные данные для задачи:

19 Вставляются записи w-y, затем записи а и w удаляются. При условии, что блок может содержать 3 записи.

Вариант	d	e	c	b	a	f	w	x	y
19	0	1	1	2	3	3	2	0	0

При вставке записи «w» у нее хеш-индекс равен 2, запись вставляется в соответствующий блок. В блоке 2 есть запись «b», запись «w» встает на следующее свободное место. На рисунке 2 представлена хеш-таблица после вставки записи «w».

Рисунок 2 – Хеш-таблица после вставки записи «w»

При вставке записи «x» у нее хеш-индекс равен 0, запись вставляется в соответствующий блок. В блоке 0 есть запись «d», запись «x» встает на следующее свободное место. На рисунке 3 представлена хеш-таблица после вставки записи «x».

Рисунок 3 – Хеш-таблица после вставки записи «x»

При вставке записи «y» у нее хеш-индекс равен 0, запись вставляется в соответствующий блок. В блоке 0 есть записи «d» и «x», запись «y» встает на следующее свободное место. На рисунке 4 представлена хеш-таблица после вставки записи «y».

Рисунок 4 – Хеш-таблица после вставки записи «y»

Далее мы удаляем запись «a». Запись «a» имеет хеш-индекс 3 и удаляется из блока 3. При этом запись «f» после удаления записи «a» встает на первое свободное место. На рисунке 5 представлена хеш-таблица после удаления записи «a».

Рисунок 5 – Хеш-таблица после удаление записи «a»

Далее мы удаляем запись «w». Запись «w» имеет хеш-индекс 2 и удаляется из блока 2. При этом запись «b» после удаления записи «w» остается на своем месте. На рисунке 6 представлена хеш-таблица после удаления записи «w», она же является и итоговой.

Рисунок 6 – Хеш-таблица после удаления записи «w»