Интерполяционный многочлен в форме Ньютона, построенный по узлам x0, x1, ..., xn, представляется формулой p_n(x) = a₀ + a₁(x-x₀) + a₁(x-x₀)(x-x₁) + ... + a_n(x-x₀)(x-x₁)...(x-x_n-1) Сколько действий необходимо выполнить, чтобы вычислить его значение в некоторой точке x=t?

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

• # При вычислении (x+y)7 раскрываются скобки и приводятся подобные члены. Чему будет равен коэффициент при x3y4?
• # При представлении целых чисел в формате Big Endian байты внутри слова нумеруются слева направо, в формате Little Endian - справа налево. Пусть компьютер использует архитектуру Big Endian. Укажите, чему будет равно значение переменной n в результате выполнения следующего фрагмента программы: int k = (-256); int n; signed char *p = (signed char *) &k; n = *p;
• # Какие смещения относительно регистра FP (Frame Pointer - указатель кадра) имеют адреса локальных переменных, описанных внутри функции, в языке C/C++?
• # Пусть элементы массива a нестрого возрастают (соседние элементы могут быть равными). Дано произвольное значение x, требуется найти максимальный индекс i такой, что a[i] <= x. Используется идея алгоритма бинарного поиска. Каким должен быть инвариант цикла, в котором рассматривается основной случай после отбрасывания исключительных ситуаций? (Условие завершения цикла end == beg+1.)
• # Алгоритм быстрой сортировки упорядочивает случайный массив из тысячи элементов в среднем за 0.01 секунду. За какое примерно время тот же алгоритм упорядочит случайный массив из миллиона элементов?