Пусть 2 многочлена p(x) и q(x) степени 4 принимают в четырех попарно различных узлах x0, x1, x2, x3 одни и те же значения y0, y1, y2, y3. Следует ли из этого, что многочлены p(x) и q(x) равны?

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

• # Дан массив длины n, содержащий элементы некоторого упорядоченного типа (их можно сравнивать между собой, определяя, какой из них больше или их равенство). Требуется удалить из массива повторяющиеся элементы так, чтобы каждый элемент содержался в массиве ровно 1 раз (при этом n может уменьшиться). Приведите асимптотическую оценку времени работы наилучшего алгоритма, решающего данную задачу.
• # Рассмотрим следующий фрагмент программы на C/C++: double x = 1.0; double y = 1e-20; double z = y - x + x; double t = x - x + y; Равны ли значения переменных z и t после его выполнения?
• # Сколько в сумме операций сложения и умножения будет выполнено при вычислении значения многочлена степени 3, коэффициенты которого заданы в последовательности по убыванию степеней, при использовании схемы вычисления индуктивной функции?
• # Оценить сверху время работы (т.е. количество выполнений тела цикла) алгоритма быстрого возведения в степень: int fastPow(double a, int n) { // дано: основание a и показатель степени n >= 0 // надо: вычислить a в степени n double b = a, p = 1.0; int k = n; while (k > 0) { // Invariant: b^k * p == a^n if (k%2 == 0) { // k четное k /= 2; b *= b; } else { // k нечетное --k; p *= b; } } return p; }
• # Массив длины 5 содержит элементы 5, 4, 1, 2, 3 в указанном порядке. К нему применяется алгоритм сортировки методом прямого выбора, использующий сравнение элементов с помощью функции compare и обмен элементов с помощью функции swap. Сколько раз будет вызвана функция swap?