Функция merge слияния двух упорядоченных массивов применяется к двум массивам длины 10 и 20. Может ли в процессе ее выполнения быть сделано ровно 28 сравнений?

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

• # Пусть расположенный в статической памяти целочисленный массив a описан как static int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 }; Пусть в программе задана функция суммирования массива с прототипом int sum(const int *m, int n); где m - константный указатель на начало массива, n - число его элементов. Укажите, чему будет равно значение переменной s в результате выполнения следующего фрагмента программы: int s = sum(a+4, 4);
• # Следующий фрагмент программы вычисляет разность d между максимальным и минимальным элементами непустой числовой последовательности. xmin = ... xmax = ... цикл пока в последовательности есть непрочитанные элементы |выполнять | прочесть очередной элемент посл-ти в <вых: x> | если x < xmin | | то xmin = x | конец если | | если x > xmax | | то xmax = x | конец если конец цикла d = xmax - xmin Какими значениями надо инициализировать переменные xmin и xmax, чтобы программа работала правильно?
• # Последовательность вещественных чисел w содержит коэффициенты многочлена по возрастанию степеней. Функция F(w) равна значению производной многочлена в фиксированной точке t=2. Среди указанных ниже функций отметьте те, которые являются индуктивным расширением функции F.
• # Алгоритм быстрой сортировки реализован с помощью комбинированной схемы, использующей рекурсию и цикл while, а также вспомогательную функцию partition, которая разделяет текущий отрезок массива на 3 части (элементы, меньшие либо равные медиане, медиана, элементы, большие либо равные медиане): void quickSort(double* a, int n) { if (n <= 1) { return; } else if (n == 2) { if (a[0] > a[1]) swap(&(a[0]), &(a[1])); return; } int beg = 0; int k = n; while (k > 1) { int m = k / 2; partition(a+beg, k, &m); int left = m; int right = k - left - 1; if (left <= right) { // Рекурсивно применяем алг. к левой части quickSort(a+beg, left); beg += left + 1; k -= left + 1; } else { // Рекурсивно применяем алг. к правой части quickSort(a+beg+m+1, right); k -= right + 1; } } } Сколько раз будет вызвана функция partition при выполнении алгоритма быстрой сортировки для массива размера 95? Дайте наиболее точную оценку снизу этого числа.
• # Пусть целочисленный массив содержит элементы 10, 16, 12, 8, 11, 7, 5 в указанном порядке. Услове пирамиды нарушается только для элемента 10, стоящего в вершине пирамиды. Для исправления пирамиды выполняется процедура просеивания, при которой элемент 10 опускается на свое место. Каким будет содержимое массива после окончания этой процедуры?