Назовем функцию y = f(p) на последовательности p элементов некоторого типа индуктивной, если при добавлении в конец последовательности p еще одного элемента x новое значение функции y1 = f(p&x) можно вычислить, зная только старое значение y и добавленный элемент x. Среди перечисленных ниже функций на последовательностях вещественных чисел укажите индуктивные.

Правильный ответ:

• # Сортируемый массив содержит составные ключи из 20 десятичных цифр (например, идентификаторы банковских счетов). Массив имеет длину 1000. Надо выбрать один из двух алгоритмов сортировки: сортировку кучей HeapSort или RADIX-сортировку. Какой из двух алгоритмов будет в среднем работать быстрее в данной ситуации?
• # В алгоритме сортировки слиянием "In Place Merge Sort", не использующем дополнительной памяти, применяется функция mergeBlocks слияния двух упорядоченных блоков, т.е. подмассивов длины m и n, реализованная рекурсивно. Пусть сумма длин блоков m+n=512. При реализации функции mergeBlocks вызывается функция перестановки двух блоков swapBlocks. Какой может быть максимальная суммарная длина блоков переставляемых блоков?
• # Можно ли сохранить целое число типа int (4 байта) в переменной типа double без потери точности? То есть, если мы имеем целочисленную переменную n типа int, то она не изменит своего значения в результе выполнения следующего фрагмента программы: int n; . . . double x = (double) n; n = (int) x;
• # Среди перечисленных ниже чисел отметьте простые.
• # Целочисленный массив содержит элементы 30, 25, 23, 15, 10, 20, 16, 7, 12, 5, 11, 9 в указанном порядке. Образуют ли они бинарную кучу (пирамиду)?