Внешние сортировки и хеширование

Файл, содержащий записи

37, 74, 58, 82, 17, 89, 81, 39, 80, 20, 72, 66, 10, 55, 48, 11

сортируется методом прямого слияния по возрастанию. Найти число, стоящее на 10-й позиции в последовательности, являющейся результатом второго слияния.

• 66

• 20

• 82

• 72

• 80

Файл, содержащий записи

37, 74, 58, 82, 17, 89, 81, 39, 80, 20, 72, 66, 10, 55, 48, 11

сортируется методом естественного слияния по возрастанию. Найти число, стоящее на 10-й позиции в последовательности, являющейся результатом слияния на первом шаге.

• 72

• 80

• 66

• 20

• 82

Файл, содержащий записи

37, 74, 58, 82, 17, 89, 81, 39, 80, 20, 72, 66, 10, 55, 48, 11

сортируется методом двухпутевого сбалансированного слияния по возрастанию. Обозначим пары файлов, используемых во время сортировки B_1, B_2 и C_1, С_2. На очередном шаге сортировки данные из одной пары файлов переносятся в другую пару файлов, при этом первенство использования принадлежит файлу c именем, оканчивающимся на 1.

Укажите через пробел содержимое файла C_2 после завершения сортировки.

• 11, 48

• 10, 11, 20, 48, 55, 66, 72, 80

• 10, 20, 39, 55, 66, 72, 80

• 10, 17, 20, 37, 39, 55, 58, 66, 74, 72, 80, 81, 82, 89

Файл, содержащий записи

37, 74, 58, 82, 17, 89, 81, 39, 80, 20, 72, 66, 10, 55, 48, 11

сортируется методом трехпутевого сбалансированного слияния по возрастанию.

Укажите содержимое файла, в котором было меньше всего данных на шаге, предшествующем окончанию сортировки.

• 11

• 10, 11, 48, 55

• 20, 39, 66, 72, 80

• 17, 37, 58, 74, 81, 89

При каком порядке сортировки понадобится меньше шагов для сортировки методом трехпутевого сбалансированного слияния файла, содержащего записи:

37, 74, 58, 82, 17, 89, 81, 39, 80, 20, 72, 66, 10, 55, 48, 11

• по возрастанию

• по убыванию

• одинаково

Использование хеширования, позволяет ускорить процесс

• поиска данных

• сортировки данных

• вывода данных

• модификации данных

• вычисления формул, связанных с данными

Пусть коды букв имеют следующие значения: A-1, B-2, C-3, D-4.

Хеш-функция равна сумме кодов букв. Дан набор идентификаторов:

DA, ACBC, ACC, CB, D, BD, ACB, ADA, BADD, BBAD, ADCB, DDD, BC.

Выполнить хеширование с размером хеш-таблицы N=10, используя при рехешировании метод цепочек. В качестве ответа указать количество элементов в самой длинной цепочке. Если таких цепочек несколько, указать суммарное количество элементов во всех таких цепочках.

• 3

• 6

• 4

• 2

Пусть коды букв имеют следующие значения: A-1, B-2, C-3, D-4.

Хеш-функция равна сумме кодов букв. Дан набор идентификаторов:

DA, ACBC, ACC, CB, D, BD, ACB, ADA, BADD, BBAD, ADCB, DDD, BC. Выполнить хеширование, используя случайное рехеширование с последовательностью случайных чисел 4, 7, 1, 13 и N = 16. В качестве ответа указать номер (хеш) ячейки, в которой будет находиться идентификатор BC, если идентификаторы из набора добавляются в таблицу последовательно, а нумерация строк в хеш-таблице начинается с 0.

• 2

• 5

• 9

• 12

• 6

Пусть коды букв имеют следующие значения: A-1, B-2, C-3, D-4.

Хеш-функция равна сумме кодов букв. Дан набор идентификаторов:

DA, ACBC, ACC, CB, D, BD, ACB, ADA, BADD, BBAD, ADCB, DDD, BC. Указать первый идентификатор, для которого не найдется места в таблице, если используется квадратичное рехеширование при c = 1 и N = 16, строки хеш-таблицы нумеруются с 0, количество попыток рехеширования не превышает 10.

• ADA

• BBAD

• ADCB

• BC

Пусть коды букв имеют следующие значения: A-1, B-2, C-3, D-4.

Хеш-функция равна сумме кодов букв. Дан набор идентификаторов:

DA ACBC ACC CB D BD ACB ADA BADD BBAD ADCB DDD BC. Выполнить хеширование, используя случайное рехеширование с последовательностью случайных чисел 11, 15, 8, 10 и N = 16. В качестве ответа указать номер (хеш) ячейки, в которой будет находиться идентификатор BC, если идентификаторы из набора добавляются в таблицу последовательно, а нумерация строк в хеш-таблице начинается с 0.

• 13

• 15

• 4

• 0

• 5