Домашнее задание №3.

Задача 1 (30 баллов).

Пусть задана хэш-функция h(k)=k%32, т. е. остаток от деления значения ключевого атрибута записи k на 32. Хэш - значение состоит из 5 бит. Будем считать, что блок может содержать до трех записей включительно. Рассматриваются следующие ключевые значения:

222, 500, 319, 215, 591, 51, 101, 130, 6, 42, 185, 177.

а) Провести и описать процесс вставки значений в расширяемую хэш – структуру.

б) Провести и описать процесс вставки значений в линейную хэш – структуру с пороговым значением 2.25.

Задача 2 (15 баллов).

Пусть дана линейная хэш-структура с пороговым значением 3.2. Блок хэш - структуры содержит до пяти записей. На текущий момент для хэш – структуры было выделено 15 блоков. Пусть m – наибольший номер сегмента хэш - структуры. Каково будет значение m в случаях, когда для поиска записи требуется выполнить минимальное и максимальное число операций ввода/вывода?

Задача 3 (45 баллов).

Пусть имеется следующие данные о расположении географических объектов (object). Один блок данных может содержать 2 записи. Опишите процесс построения на основе этих данных:

а) сеточного файла;

б) kd – дерева;

в) квадратичного дерева.

Объект

(object)

Координата

x

Координата

y

1001

400

150

1002

1100

530

1003

210

760

1004

870

1350

1005

1000

250

1006

130

290

1007

1400

830

1008

630

1260

1009

1200

500

1010

920

320

1011

1150

860

1012

700

650