К массиву длины 5 применяется алгоритм сортировки методом прямого выбора, использующий сравнение элементов с помощью функции compare и обмен элементов с помощью функции swap. Какое максимальное количество раз может быть вызвана функция swap?

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

• # К массиву a длины 30 применяется восходящая схема двунаправленного алгоритма сортировки слиянием с использованием дополнительной памяти. В процессе выполнения алгоритма многократно вызывается функция merge слияния двух упорядоченных массивов длины n и m. Каковы длины массивов, которые сливаются при самом последнем вызове функции merge?
• # Какова асимптотическая оценка времени работы алгоритма Гаусса приведения матрицы к ступенчатому виду для случая квадратной матрицы размера n?
• # Интерполяционный многочлен в форме Ньютона, построенный по узлам x0, x1, ..., xn и принимающий в этих узлах значения y0, y1, ..., yn, представляется формулой pn(x) = a0 + a1(x-x0) + a1(x-x0)(x-x1) + ... + an(x-x0)(x-x1)...(x-xn-1) Пусть коэффициенты a0, a1, ..., an многочлена pn(x) уже вычислены. Мы добавляем новый узел xn+1, значение в котором должно быть равно yn+1, и строим новый многочлен Ньютона pn+1(x) на единицу большей степени по узлам x0, x1, ..., xn, xn+1 и значениям y0, y1, ..., yn, yn+1. Сколько действий нужно выполнить, чтобы вычислить все коэффициенты нового многочлена?
• # Функция F последовательности цифр в десятичной записи числа n ставит в соответстие единицу, если n делится на 14, и ноль в противном случае. Какая из приведенных ниже функций на последовательности десятичных цифр числа n является индуктивным расширением функции F?
• # Пусть a - целочисленный массив размера n (индекс элементов меняется от 0 до n-1), элементы которого строго возрастают: a[0] < a[1] <... < a[n-1]. Определить, содержит ли следующий фрагмент программы ошибку (т.е. действительно ли тело цикла сохраняет инвариант): // Программа Поиск int n; int *a; . . . // дано: целое n; // целочисленный массив a[n], // элементы которого строго возрастают // a[0] < a[1] < ... < a[n-1] // надо: найти элемент x в массиве int x; // искомый элемент . . . // рассматриваются исключительные случаи // общий случай // утверждение: a[0] < x && x <= a[n-1]; int b = 0; int e = n - 1; while (e - b > 1) { Invariant: a[b] < x && x <= a[e] int c := (a + b)/2; // c - целая часть (a+b)/2 if (x < a[c]) { e = c; // выбираем левую половину отрезка } else { b = c; // выбираем правую половину } } // утверждение: b == e - 1 && // a[b] < x && x <= a[e]