Контрольная Контрольная работа по информатике (3 задачи), номер: 244332

"11.1- 3. Предложите способ реализации таблицы с прямой адресацией, в которой ключи хранящихся элементов могут совпадать, а сами элементы — иметь сопутствующие данные. Все словарные операции — вставки, удаления и поиска — должны выполняться за время 0(1). (Не забудьте, что ар¬гументом процедуры удаления является указатель на удаляемый объект, а не ключ.)
11.2- 3. Профессор предполагает, что можно повысить эффективность хеширова¬ния с разрешением коллизий методом цепочек, если поддерживать спис¬ки в упорядоченном состоянии. Каким образом такое изменение алгорит¬ма повлияет на время выполнения успешного поиска, неудачного поиска, вставки и удаления?
11.2- 4. Предложите способ хранения элементов внутри самой хеш-таблицы, при котором неиспользуемые ячейки связываются в один список свободных мест. Считается, что в каждой ячейке может храниться флаг и либо один элемент и указатель, либо два указателя. Все словарные операции и опе-рации над списком свободных мест должны выполняться за время О (1). Должен ли список свободных мест быть двусвязным или можно обойтись односвязным списком?
11.1-4. Предположим, что мы хотим реализовать словарь с использованием пря¬мой адресации очень большого массива. Первоначально в массиве может содержаться “мусор”, но инициализация всего массива нерациональна в силу его размера. Разработайте схему реализации словаря с прямой адресацией при описанных условиях. "