Главная / Программирование / Программирование

Программирование - ответы на тесты Интуит

Правильные ответы выделены зелёным цветом.
Все ответы: Курс механико-математического факультета МГУ им. М.В. Ломоносова предназначен для обучения основам программирования на языках C и C++.

Смотрите также:

Алгоритмы и дискретные структуры

Какой максимальный адрес машинного слова в 32-разрядной архитектуре?

(1) 2³²

(2) 2³²-4

(3) 2³²-3

(4) 2¹⁶

(5) 32²

Алгоритм сортировки называется стабильным, если он сохраняет относительный порядок равных элементов. Среди перечисленных ниже алгоритмов сортировки (имеются в виду их классические варианты) отметьте все стабильные.

(1) Пузырьковая сортировка.

(2) Сортировка прямым выбором.

(3) Быстрая сортировка QuickSort.

К массиву a длины 64 применяется восходящая схема двунаправленного алгоритма сортировки слиянием с использованием дополнительной памяти — массива b такого же размера. В каком из этих массивов мы получим результат после окончательного шага слияния, т.е. будет ли вызвана функция copyArray, чтобы скопировать результат из вспомогательного массива b в массив a?

(1) Результат будет в массиве a, функция copyArray вызвана не будет.

(2) Результат будет в массиве b, будет вызвана функция copyArray.

Дан массив длины n, требуется циклически сдвинуть его элементы вправо на одну позицию. Какое минимальное число операций копирования выполняется в любом алгоритме, решающем данную задачу? Имеются в виду операции копирования одного элемента массива в другой, элемента массива в простую переменную, одной простой переменной в другую.

(1) Минимум n операций.

(2) Минимум n+1 операция.

(3) Минимум 3n операций.

(4) Минимум n-1 операций.

(5) Минимум 2n операций.

Сколько единиц в двоичной записи числа 10?

(1) 1.

(2) 2.

(3) 3.

При представлении целых чисел в формате Big Endian байты внутри слова нумеруются слева направо, в формате Little Endian - справа налево. Укажите, в каких случаях из перечисленных ниже используется формат Big Endian.

(1) В протоколах сети Internet.

(2) В процессоре Intel-80x86

(3) В процессоре Motorola 68k.

(4) В процессоре DEC Alpha.

(5) В процессоре PowerPC.

Рассмотрим 8 байтов, в которых записан некоторый двочный код. Всегда ли он представляет вещественное число, записанное в плавающей форме, т.е. значение типа double?

(1) Да, всегда.

(2) Нет, не всегда.

Какие из из перечисленных ниже объектно-ориентированных языков программирования продолжают линию языка С, используя близкий синтаксис?

(1) C++

(2) Visual Basic

(3) Java

(4) Delphi

(5) C#

Рассмотрим следующий фрагмент программы на C++: int a[2][3]; const int *p = (const int *) a; int n; for (int i = 0; i < 2; ++i) { for (int j = 0; j < 3; ++j) { a[i][j] = 10*i + j; } } n = p[4]; Чему равно значение n после выполнения этого фрагмента?

(1) n = 2

(2) n = 3

(3) n = 10

(4) n = 11

Какова степень интерполяционного многочлена, построенного по трем узлам x₀, x₁, x₂, принимающего в этих узлах значения y₀, y₁, y₂?

(1) Степень 1 (линейная функция).

(2) Степень 2 (парабола).

(3) Степень 3 (кубическая парабола).

Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел. Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.

Программа должна содержать функцию, которая получает в качестве параметра имя файла и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.

Задание: посчитать среднее арифметическое чисел из последовательности.

Свой ответ

Постановка задачи: программа должна содержать функцию, которая получает в качестве параметров имя массива и его длину (или нескольких массивов, если этого требуют условия задачи) и выполняет необходимые действия. При решении не разрешается создавать или резервировать в программе дополнительную память, соизмеримую по размерам с объемом исходных данных. То есть, нельзя создавать дополнительные массивы, если это явно не оговорено в задаче.

Функция main должна заполнить массив числами из файла. Для определения длины массива предусматривается два варианта: 1) по значению первого числа в файле, 2) непосредственным подсчетом количества чисел в файле. Результат также выводится в файл.

Задание: симметричны ли значения элементов массива целых чисел относительно середины массива?

Свой ответ

Каков диапазон целочисленного типа unsigned char?

(1) -128 ... 127

(2) 0 ... 255

(3) 0 ... 65535

(4) -32768 ... 32767

Сколько раз будет выполнено тело цикла в алгоритме Евклида int gcd(int m, int n) { while (n != 0) { int r = m % n; m = n; n = r; } return m; } при следующих входных значениях аргументов: m=13, n=17?

Пусть расположенный в статической памяти целочисленный массив 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);

Какая из приведенных ниже строк языка С/С++ описывает массив указателей на тип char?

(1) char (*a)[100];

(2) char *a[100];

(3) char (&a)[100];

(4) char &a[100];

Левым нейтральным элементом (левой единицей) для бинарной операции называется элемент e такой, что для всякого другого элемента x "произведение" e на x равно x: e x = x. Какие элементы будут нейтральными для операций суммы и максимума чисел соответственно?

(1) 0, 0.

(2) 0, +

(3) 0, -

(4) -, +

Рассмотрим следующий фрагмент программы: утверждение: A(x) цикл пока B(x) | инвариант: A(x) | x := T(x) конец цикла Здесь через A(x) и B(x) обозначены условия, зависящие от переменной x. Какое условие выполняется по окончании цикла?

(1) Условие (не A(x) и B(x)).

(2) Условие (A(x) и B(x)).

(3) Условие (A(x) и не B(x)).

(4) Условие (не A(x) и не B(x)).

В массиве, содержащем 1000 элементов, выполняется последовательный поиск элемента x. При этом x содержится в массиве с вероятностью 0.25. Сколько в среднем операций сравнения будет выполнено?

(1) 625

(2) 750

(3) 875

(4) 550

(5) 900

Массив a размера 4 содержит элементы 4, 3, 2, 1 в указанном порядке. К нему применяется алгоритм пузырьковой сортировки, использующий сравнение элементов с помощью функции compare и обмен элементов с помощью функции swap. Сколько раз будет вызвана функция swap?

Алгоритм быстрой сортировки использует вспомогательную функцию partition, которая разделяет массив на 3 части: в начале элементы, меньшие либо равные медиане, затем медиана, в конце элементы, большие либо равные медиане. Рассмотрим следующую реализацию функции partition: void partition(double* a, int n, int *m) { if (*m != 0) // Ставим медиану в начало swap(&(a[0]), &(a[*m])); double x = a[0]; // Значение медианы int i = 0; int j = n; while (j-i > 1) { // Инв: a[1], a[2], ..., a[i] <= x // a[j], a[j+1], ..., a[n-1] > x if (a[i+1] <= x) { ++i; } else if (a[j-1] > x) --j; } else { ++i; --j; swap(&(a[i]), &(a[j])); } } if (i > 0) swap(&(a[0]), &(a[i])); *m = i; } Правильна ли подобная реализация, или она может привести к катастрофическому замедлению алгоритма быстрой сортировки в некоторых случаях?

(1) Реализация правильная.

(2) Реализация неправильная.

Назовем алгоритм сортировки оптимальным, если он работает за время O(n log₂ n) даже при самом плохом входе. Среди перечисленных ниже алгоритмов сортировки отметьте оптимальные.

(1) Пузырьковая сортировка.

(2) Сортировка прямым выбором.

(3) Быстрая сортировка QuickSort.

(4) Сортировка кучей HeapSort.

В чем главный недостаток языка Ассемблер?

(1) Сложность написания программ большого объема.

(2) Зависимость от архитектуры компьютера.

К трехзначным десятичным числам (строкам длины 3 из десятичных цифр) применяется алгоритм RADIX-сортировки сначала по младшей цифре, затем по средней и в конце по старшей. Исходный массив содержит следующие числа: 122, 232, 171, 198, 401, 035, 077, 201, 199, 400. Каким будет содержимое массива после выполнения первых двух шагов сортировки (т.е. после сортировки по младшей и средней цифрам)?

(1) 400, 201, 401, 122, 232, 035, 171, 077, 198, 199

(2) 400, 401, 201, 122, 035, 232, 171, 077, 198, 199

(3) 400, 401, 201, 122, 232, 035, 171, 077, 198, 199

(4) 400, 401, 201, 122, 171, 232, 035, 077, 198, 199

(5) 400, 401, 201, 122, 232, 035, 171, 077, 198, 199

К массиву a длины 28 применяется восходящая схема двунаправленного алгоритма сортировки слиянием с использованием дополнительной памяти — массива b такого же размера. В каком из этих массивов мы получим результат после окончательного шага слияния, т.е. будет ли вызвана функция copyArray, чтобы скопировать результат из вспомогательного массива b в массив a?

(1) Результат будет в массиве a, функция copyArray вызвана не будет.

(2) Результат будет в массиве b, будет вызвана функция copyArray.

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

(1) Минимум 12 операций.

(2) Минимум 13 операций.

(3) Минимум 36 операции.

(4) Минимум 11 операции.

(5) Минимум 24 операции.

Для записи n-значных чисел в системе счисления с основанием b требуется n разрядов, каждый из которых может находиться в b состояниях. Таким образом, суммарное число состояний равно произведению n*b. Рассмотрим двоичную (b=2), восьмеричную (b=8) и шестнадцатеричную (b=16) системы счисления. Какая из них наиболее экономна по суммарному числу состояний для записи чисел в диапазоне 0..N, где N - некоторое достаточно большое число?

(1) Двоичная.

(2) Восьмеричная.

(3) Шестнадцатеричная.

Пусть для представления вещественных чисел мы используем десятичные целые числа с фиксированной позицией десятичной точки, отделяющей ровно 3 знака дробной части. Например, целое число 2718 представляет вещественное число 2.718. Рассмотрим два числа с фиксированной точкой, представленные целыми числами 10500 и 1010. Каким числом будет представлено их произведение?

(1) 10605.

(2) 1060500.

(3) 10605000.

Функция arctg(x) раскладывается в ряд Тейлора следующим образом: arctg(x) = x - x³/3 + x⁵/5 - x⁷/7 + ... Рассмотрим реализованную на C/C++ функцию myAtan(x), вычисляющую значение arctg(x) с точностью до одной миллионной: static const double EPS = 1e-6; double myAtan(double x) { double s = 0.; double p = x; double n = 1.; double a = x; while (fabs(a) > EPS) { s += a; p = (-p*x*x); n += 2.; a = p/n; } return s; } Для каких значений x ее можно применять? Укажите все правильные ответы из числа перечисленных ниже.

(1) Для небольших по абсолютной величине значений x, например, |x| < 10.

(2) Для значений x в интервале -0.75<x<0.75

(3) Для x = 1.0001.

(4) Для x = -2.

Какая из конструкций цикла потенциально безопаснее?

(1) Цикл с предусловием while (...) { . . . }

(2) Цикл с постусловием do { . . . } while (...);

Рассмотрим реализацию матрицы вещественных чисел, размеры которой определяются в процессе работы программы, через массив указателей на начала строк, захватываемый в динамической памяти. Каждая строка также представляет собой отдельный массив в динамической памяти: typedef double* doubleptr; int m, n; // Размеры матрицы: число строк, столбцов . . . doubleptr* a = new doubleptr[m]; for (int i = 0; i < m; ++i) { a[i] = new double[n]; } // a[i][j] -- элемент i-й строки и j-го столбца Сколько обращений к памяти необходимо сделать, чтобы прочесть элемент матрицы в i-й строке и j-м столбце (считая, что значения i и j уже находятся в регистрах процессора)?

(1) одно обращение

(2) 2 обращения

(3) 3 обращения

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

(1) O(n).

(2) O(n²).

(3) O(n³).

Отметьте, какие из перечисленных ниже целочисленных значений помещаются в переменную типа int (для удобства триады цифр разделяются запятыми).

(1) 4,000,000

(2) 2,000,000,000

(3) 10,000,000,000

(4) -1,000,000,000

Укажите, чему будет равно значение переменной k в результате выполнения следующего фрагмента программы: int n=11, k, *p; p = &n; ++*p; k = 4-*p*2+n;

-8

Пусть переменные a, p, q, n описаны следующим образом: double a[10]; double *p; const double *q; int n; Отметьте, какие из приведенных ниже операторов языка C/C++ корректны.

(1) p = &a[7] + n;

(2) q = &p[3] + 2;

(3) p = &q[2] + 3;

(4) n = p - a;

(5) n = q - a;

Чему будет равно значение переменной n в результате выполнения следующего фрагмента программы? Процессор имеет 32-разрядную архитектуру. double a[4][3]; int n, m; n = (int)(a+1); m = (int) a; n -= m;

Какие константы можно в практическом программировании использовать в качестве воображаемого значения "минус бесконечность" при работе с вещественными числами типа double? Укажите все правильные варианты.

(1) Число -DBL_MAX (константа DBL_MAX описана в стандартном заголовочном файле float.h).

(2) Константу DBL_MIN, заданную в стандартном заголовочном файле float.h.

(3) Константу -1e+30.

Пусть целочисленная переменная n содержит некоторое положительное целое число. Указать, что вычисляет следующая функция f(n): int f(int n) { int s = 2; int k = 0; while (s <= n) { // Invariant: s == 2^(k+1) s *= 2; ++k; } return k; }

(1) Целую часть квадратного корня из n.

(2) Целую часть от log₂ n.

(3) Целую часть кубического корня из n.

(4) Целую часть от eⁿ.

(5) Целую часть от 2ⁿ.

В массиве, содержащем 1000 элементов, выполняется последовательный поиск элемента x. При x содержится в массиве с вероятностью равна 0.1. Сколько в среднем операций сравнения будет выполнено?

(1) 550

(2) 900

(3) 950

(4) 650

(5) 600

Алгоритм пузырьковой сортировки упорядочивает массив из 10 тысяч элементов примерно за 1 секунду. За какое примерно время тот же алгоритм упорядочит массив из 100 тысяч элементов?

(1) 10 секунд

(2) 100 секунд

(3) 1000 секунд

(4) 10000 секунд

(5) 2 секунды

Алгоритм быстрой сортировки использует вспомогательную функцию partition, которая разделяет массив на 3 части: в начале элементы, меньшие либо равные медиане, затем медиана, в конце элементы, большие либо равные медиане. Рассмотрим следующую реализацию функции partition: void partition(double* a, int n, int *m) { if (*m != 0) // Ставим медиану в начало swap(&(a[0]), &(a[*m])); double x = a[0]; // Значение медианы int i = 0; int j = n; while (j-i > 1) { // Инв: a[1], a[2], ..., a[i] < x // a[j], a[j+1], ..., a[n-1] >= x if (a[i+1] < x) { ++i; } else if (a[j-1] >= x) --j; } else { ++i; --j; swap(&(a[i]), &(a[j])); } } if (i > 0) swap(&(a[0]), &(a[i])); *m = i; } Правильна ли подобная реализация, или она может привести к катастрофическому замедлению алгоритма быстрой сортировки в некоторых случаях?

(1) Реализация правильная.

(2) Реализация неправильная.

Целочисленный массив содержит элементы 25, 10, 20, 5, 9, 15, 19, 1, 3, 8, 7, 12 в указанном порядке. Образуют ли они бинарную кучу (пирамиду)?

(1) Да.

(2) Нет.

В каком случае выполняется тело цикла "while"?

(1) Когда условие после слова "while" в заголовке цикла истинно.

(2) Когда условие после слова "while" в заголовке цикла ложно.

(3) Когда условие до слова "while" в заголовке цикла ложно.

RADIX-сортировка применяется к составным ключам длины k, длина сортируемого массива равна n. Какова асимптотическая оценка времени работы алгоритма?

(1) t = O(k*n)

(2) t = O(k*log₂n)

(3) t = O(k²*n)

(4) t = O(k*n²)

(5) t = O(n)

К массиву a длины 12 применяется восходящая схема двунаправленного алгоритма сортировки слиянием с использованием дополнительной памяти. В процессе выполнения алгоритма многократно вызывается функция merge слияния двух упорядоченных массивов длины n и m. Каковы длины массивов, которые сливаются при самом последнем вызове функции merge?

(1) n=6, m=6

(2) n=8, m=4

(3) n=10, m=2

(4) n=8, m=6

(5) n=6, m=4

(6) n=10, m=4

Дан массив длины 26, требуется циклически сдвинуть его элементы вправо на 6 позиций. Существует ли алгоритм, который решает эту задачу, выполняя 28 операций копирования? Имеются в виду операции копирования одного элемента массива в другой, элемента массива в простую переменную, одной простой переменной в другую.

(1) Да.

(2) Нет.

В алгоритме получения записи числа n в системе счисления с основанием b мы вычисляем цифры числа справа налево, начиная с последней цифры. На очередном шаге мы делим n с остатком на b, получая частное q и остаток r; остаток представляет очередную цифру числа в порядке справа налево. Затем мы переменной n присваиваем значение частного q, и процесс повторяется, пока n не станет равным нулю. Сколько раз будет выполнена операция деления при переводе числа 1000000 (миллион) в шестнадцатеричную систему счисления?

(1) 3 раза.

(2) 4 раза.

(3) 5 раз.

(4) 6 раз.

При представлении вещественных чисел в плавающей форме мы выражаем вещественное число x в виде x = s 2^e m, где s - знак числа, принимающий значение плюс или минус единица, e - порядок, представляющий собой целое число (положительное, 0 или отрицательное), m - мантисса, представляющая собой вещественное число в диапазоне 1 m < 2. Чему равны порядок и мантисса для числа 12?

(1) e=2, m=1.75.

(2) e=3, m=1.2.

(3) e=3, m=1.5.

Функция ln(z) (натуральный логарифм z) представляется в виде степенного ряда следующим образом: ln(1+x) = x - x²/2 + x³/3 - x⁴/4 + ... (мы обозначили z=1+x). Этот ряд сходится лишь для значений x, по абсолютной величине не превосходящих 1, а эффективно вычислять его сумму можно только для еще более узкого интервала значений x. Какими свойствами функции ln(z) удобнее всего воспользоваться, чтобы свести ее вычисление к суммированию ряда?

(1) Свойством ln(z) = ln(z/n) + ln(n), где n - целая часть z.

(2) Свойствами ln(z) = 0.5*ln(z*z) при z < 0.5 и ln(z) = 2*ln(sqrt(z)) при z > 1.5.

(3) Свойствами ln(z) = ln(z/e) + 1 при z > 1.5 и ln(z) = ln(z*e) - 1 при z < 0.5.

Где следует описывать прототипы функций?

(1) В начале файла или в заголовочном файле (h-файле), который подключается с помощью директивы #include.

(2) Внутри функции, из которой вызывается функция с данным прототипом.

Рассмотрим реализацию матрицы вещественных чисел размера m строк на n столбцов при помощи линейного массива, в котором хранятся сначала элементы нулевой строки матрицы, затем первой, второй и т.д., в конце - элементы (m-1)-й строки: int m, n; // Размеры матрицы: число строк, столбцов . . . double* a = new double[m*n]; // a[i*n + j] -- элемент i-й строки и j-го столбца Правильно ли работает следующая функция транспонирования матрицы, при выполнении которой строки матрицы должны стать столбцами, столбцы - строками, а матрица размера m на n превратиться в матрицу размера n на m? void transp(double* a, int m, int n) { for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { int idx0 = i*n + j; int idx1 = j*m + i; if (idx0 < idx1) { // Меняем местами 2 элемента double tmp = a[idx0]; a[idx0] = a[idx1]; a[idx1] = tmp; } } } }

(1) Функция работает во всех случаях правильно.

(2) Функция работает правильно только для квадратных матриц.

(3) Функция работает правильно только для квадратных матриц и для матриц, в которых либо число строк, либо число столбцов равно единице.

Для приближения функции, заданной на отрезке [a, b], применяется сплайн-интерполяция. Для этого отрезок разбивается на n частей точками x₀, x₁, x₂, ..., x_n, в которых заданы значения функции y₀, y₁, y₂, ..., y_n, На каждом из этих маленьких отрезков [x_i, x_i+1] функция приближается многочленом степени d, который на концах отрезка принимает заданные значения. Пусть, помимо значений функции в узлах интерполяции y_i, заданы также и значения ее производной y'_i в узлах; производная каждого интерполяционного многочлена также должна принимать заданные значения на концах отрезка [x_i, x_i+1]. Чему должна быть равна степень d интерполяционных многочленов, из которых составляется искомый сплайн?

(1) Степень d = 1.

(2) Степень d = 2.

(3) Степень d = 3.

(4) Степень d = 4.

Чему равно значение выражения (-12)%5*10 в языке C?

-20

Укажите, чему будет равно значение переменной n в результате выполнения следующего фрагмента программы: double *p = 1000; double *q = 2000; int n = q - p;

125

Мы хотим реализовать функцию, которая находит индекс максимального элемента вещественного массива. Отметьте, какие из возможных прототипов данной функции корректны.

(1) int indmax(double a[], int n);

(2) int indmax(const double *a, int n);

(3) void indmax(const double a[], int n, int* idx);

(4) void indmax(double *a, int n, int* idx);

Укажите, какие из приведенных ниже строк языка C/C++ корректно описывают объекты языка.

(1) void *(*f(int x))[10];

(2) void (*f)(int x)[10];

(3) int (*f(int x))[10];

(4) char *(*f[10])(int x);

Является ли индуктивной функция, которая последовательности вещественных чисел ставит в соответствие сумму ее первого и последнего элементов?

(1) Является.

(2) Не является.

Рассмотрим следующую функцию, аргументами которой являются два целых неотрицательных числа: int f(int m, int n) { int a = m, b = n; int p = 0; while (b != 0) { if (b%2 == 0) { // b четное b /= 2; a *= 2; } else { // b нечетное --b; p += a; } } return p; } Какое условие является инвариантом цикла?

(1) Равенство a^b p = mⁿ

(2) Равенство a*b + p = m*n

(3) Равенство b^a p = mⁿ

(4) Равенство a/b + p = m*n

(5) Равенство a + b + p = m*n

Пусть дан массив a длины n, элементы которого нестрого возрастают, т.е. соседние элементы могут быть равными. Рассмотрим фрагмент программы бинарного поиска элемента x в массиве a длины n, где после отбрасывания особых ситуаций рассматривается основной случай: . . . // Утверждение: a[0] <= x && x < a[n-1] int beg = 0; int end = n-1; while (end-beg > 1) { // Инвариант: a[beg] <= x && x < a[end] int c = (beg + end) / 2; if (a[c] <= x) { beg = c; } else { end = c; } } if (a[beg] == x) { *idx = beg; } else { *idx = end; } . . . Пусть значение x содержится в массиве в нескольких экземплярах. Индекс какого элемента массива a будет записан в переменную *idx?

(1) Индекс первого элемента, равного x.

(2) Индекс поcледнего элемента, равного x.

(3) Может быть записан индекс любого элемента массива a, равного x.

(4) Может быть записан индекс любого элемента массива a, равного x+1.

(5) Может быть записан индекс любого элемента массива a, равного x-1.

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

(1) 4 раза

(2) 5 раз

(3) 6 раз

(4) 7 раз

(5) 8 раз

Алгоритм быстрой сортировки реализован с помощью комбинированной схемы, использующей рекурсию и цикл 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 при выполнении алгоритма быстрой сортировки для массива размера 47? Дайте наиболее точную оценку снизу этого числа.

(1) Не менее 4 раз.

(2) Не менее 7 раз.

(3) Не менее 15 раз.

(4) Не менее 31 раза.

Пусть целочисленный массив содержит элементы 11, 18, 10, 7, 15, 9, 8 в указанном порядке. Услове пирамиды нарушается только для элемента 11, стоящего в вершине пирамиды. Для исправления пирамиды выполняется процедура просеивания, при которой элемент 11 опускается на свое место. Каким будет содержимое массива после окончания этой процедуры?

(1) 18, 15, 10, 11, 7, 9, 8.

(2) 18, 15, 11, 7, 10, 9, 8.

(3) 18, 15, 10, 7, 11, 9, 8.

(4) 18, 15, 10, 11, 8, 9, 7.

(5) 11, 18, 15, 7, 10, 9, 8.

Сколько раз будет выполнено тело цикла в приведенной ниже программе? Многоточием обозначен фрагмент, не содержащий переменной x. int x = 0; while (x < 1000) { . . . x = x+1; }

1000

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

(1) Может.

(2) Не может.

К массиву a длины 10 применяется восходящая схема двунаправленного алгоритма сортировки слиянием с использованием дополнительной памяти такого же размера. Сколько раз будет вызвана функция слияния двух упорядоченных массивов merge?

(1) 5 раз

(2) 8 раз

(3) 9 раз

(4) 10 раз

(5) 11 раз

Дан массив длины n, содержащий элементы некоторого упорядоченного типа (их можно сравнивать между собой, определяя, какой из них больше или их равенство). Рассмотрим задачу нахождения множества различных элементов, содержащихся в массиве. Приведите асимптотическую оценку времени работы наилучшего алгоритма, решающего данную задачу.

(1) t = O(n)

(2) t = O(n log₂n)

(3) t = O(n²)

(4) t = O(n³)

(5) t = O(2ⁿ)

(6) t = O(log₂n)

Рассмотрим следующую запись числа в двоичной системе счисления (для удобства запись разбита запятыми на триады): 100,001,010,110,111,101,011. Укажите восьмеричную запись этого числа.

(1) 2136735.

(2) 2146775.

(3) 4126753.

Двоичный код, представляющий число типа float, хранит знак, смещенный порядок и дробную часть двоичного представления мантиссы. Сколько битов отводится под каждый элемент представления?

(1) Знак 1 бит, смещенный порядок 10 битов, дробная часть мантиссы 21 бит.

(2) Знак 1 бит, смещенный порядок 9 битов, дробная часть мантиссы 22 бита.

(3) Знак 1 бит, смещенный порядок 8 битов, дробная часть мантиссы 23 бита.

Функция arctg(x) (ее также обозначают arctg или atan) представляется рядом Тейлора: arctg(x) = x - x³/3 + x⁵/5 - x⁷/7 + ... Этот ряд сходится лишь для значений x, по модулю не превосходящих единицы, а эффективно вычислять его можно лишь для x, по модулю существенно меньших единицы - например, |x|<0.5. Чтобы свести задачу вычисления функции arctg(x) к суммированию ряда для малых значений x, можно воспользоваться формулой arctg(x) = 2*arctg(y), где y = x/(1 + sqrt(1 + x*x)), заменив вычисление ряда для x вычислением для y. Например, arctg(1)=2*arctg(1/(1+sqrt(2))). При этом нам придется воспользоваться функцией sqrt, вычисляющей квадратный корень. Какое максимальное число раз ее придется вызвать, чтобы свести вычисление arctg(x) для произвольного x к суммированию ряда для x в интервале |x|<0.5?

(1) 1 раз.

(2) 2 раза.

(3) 3 раза.

(4) 4 раза.

(5) Для очень больших x может потребоваться многократное применение отображения x->y, поэтому число вызовов sqrt не ограничено.

Цель - реализовать функцию fallTime, вычисляющую время падения камня с высоты h. Какой из приведенных ниже фрагментов кода правильно решает задачу?

(1) #include <stdio.h> #include <math.h> double fallTime(double); const double g=9.81; . . . double fallTime(double h) { return sqrt(2.*h/g); }

(2) #include <stdio.h> double fallTime(double h); const double g=9.81; . . . double fallTime(double h) { return g*h*h/2.; }

Чему равен ранг следующей матрицы: 1 2 3 4 5 6 7 8 9 10 11 12

(1) ранг равен 1

(2) ранг равен 2

(3) ранг равен 3

(4) ранг равен 4

Пусть f(x) - гладкая функция, заданная на отрезке [a, b], производная которой по абсолютной величине не превышает некоторой константы. Для приближенного вычисления интеграла от этой функции мы применяем формулу прямоугольников, разбивая отрезок [a, b] на n равных частей. Какова точность вычисления интеграла в зависимости от n?

(1) O(1/n).

(2) O((1/n)²).

(3) O((1/n)³).

Сколько различных значений x типа unsigned char удовлетворяют равенству x+x+x+x == 0?

(1) одно

(2) 2

(3) 4

(4) 8

(5) 16

Пусть переменные p, q, n описаны следующим образом: double *p, *q; int n; Отметьте, какие из перечисленных ниже выражений языка C/C++ являются корректными:

(1) p+q

(2) p-q

(3) 2*p

(4) p+n

(5) p-n

Рассмотрим следующий фрагмент программы на С/С++: static int *p = NULL; . . . p = (int *) malloc(sizeof(int)); *p = 123; Где хранится значение выражения "*p" (т.е. число 123)?

(1) В статической памяти.

(2) В динамической памяти.

(3) В стеке.

Эквивалентны ли в языке C/C++ типы PntAct и VectAct, заданные в приведенном ниже фрагменте программы? typedef double R3Point[3]; typedef double R3Vector[3]; typedef void (*PntAct)(R3Point); typedef void (*VectAct)(R3Vector);

(1) Эквивалентны.

(2) Не эквивалентны.

Функция F последовательности цифр в десятичной записи числа n ставит в соответстие единицу, если n делится на 7, и ноль в противном случае. Какая из приведенных ниже функций на последовательности десятичных цифр числа n является индуктивным расширением функции F?

(1) Остаток от деления числа n на 231.

(2) Пара (остаток от деления числа n на 100, остаток от деления числа n на 11).

(3) Пара (последняя цифра числа n, сумма цифр числа n).

(4) Пара (остаток от деления числа n на 100, остаток от деления числа n на 231).

Какое утверждение является инвариантом для следующего фрагмента программы (т.е. из справедливости утверждения до выполнения фрагмента программы вытекает справедливость утверждения после выполнения)? Предполагается, что значение переменной n неотрицательно. double r, x; int n; . . . r *= x*x; r /= ((n+1)*(n+2)); n += 2;

(1) Утверждение r == xⁿ/n!, где восклицательным знаком обозначен факториал числа n.

(2) Утверждение r == xⁿ/((n+1)*(n+2)).

(3) Утверждение r == (x+n)/n!, где восклицательным знаком обозначен факториал числа n.

(4) Утверждение r == xⁿ/(n+1)!.

Пусть элементы массива a нестрого возрастают (соседние элементы могут быть равными). Дано произвольное значение x, требуется найти максимальный индекс i такой, что a[i] <= x. Используется идея алгоритма бинарного поиска. Каким должен быть инвариант цикла, в котором рассматривается основной случай после отбрасывания исключительных ситуаций? (Условие завершения цикла end == beg+1.)

(1) a[beg] < x <= a[end], ответ в переменной end.

(2) a[beg] <= x < a[end], ответ в переменной beg.

(3) a[beg] < x <= a[end], ответ в переменной beg.

Для разных массивов фиксированной длины 1000 применяются алгоритмы пузырьковой сортировки и сортировки методом прямого выбора. Какой из этих двух алгоритмов работает в среднем быстрее?

(1) Пузырьковая сортировка.

(2) Сортировка методом прямого выбора.

Алгоритм быстрой сортировки упорядочивает случайный массив из 128 элементов в среднем за 0.0001 секунду. За какое примерно время тот же алгоритм упорядочит случайный массив из 1024 элементов?

(1) За 0.0011 секунды.

(2) За 0.0023 секунды.

(3) За 0.0054 секунды

(4) За 0.0075 секунды

(5) За 0.0099 секунды

К целочисленному массиву применяется алгоритм сортировки кучей. Пусть после первого этапа алгоритма пирамида (бинарная куча) уже построена и массив содержит элементы 16, 12, 11, 8, 7, 10, 6 в указанном порядке. Затем выполняется второй этап сортировки. На его первом шаге начальный и конечный элементы массива меняются местами, от пирамиды отрезается правая нижняя ветка (т.е. последний элемент массива), затем элемент в вершине пирамиды просеивается, благодаря чему восстанавливается условие пирамиды. Каким будет содержимое массива по окончании этого шага?

(1) 12, 7, 11, 8, 6, 10, 16.

(2) 12, 8, 11, 6, 7, 10, 16.

(3) 12, 8, 11, 7, 6, 10, 16.

Пусть

 - некоторое условие, не зависящее
от значения переменной x.
Укажите, чему может быть равно значение x
в результате выполнения следующего фрагмента программы
(многоточием обозначен текст, не содержащий
переменной x):

int x = 1;
while () {
    . . .
    if () {
        x = 2;
    } else {
        x = 3;
    }
}


                            
                                                                                                    
                                        (1) 
    Значение x равно 1.
                                        
                                                                    
                                        (2) 
    Значение x равно 2.
                                        
                                                                    
                                        (3) 
    Значение x равно 3.
                                        
                                                                    
                                        (4) 
    Значение x равно 1 или 2.
                                        
                                                                    
                                        (5) 
    Значение x равно 1 или 3.


                                            
                            
Рассмотрим алгоритм сортировки слиянием с использованием
дополнительной памяти. Используется нисходящая (рекурсивная)
схема реализации алгоритма. Алгоритм применяется к массиву
длины 1000000 (миллион). Какова максимально возможная
глубина рекурсии? Дайте наиболее точную оценку.

                            
                                                                                                    
                                        (1) 
    Не больше 10
                                        
                                                                    
                                        (2) 
    Не больше 20
                                        
                                                                    
                                        (3) 
    Не больше 50
                                        
                                                                    
                                        (4) 
    Не больше 100
                                        
                                                            
                        
                                            
                            
К массиву a длины 11 применяется восходящая схема
двунаправленного алгоритма сортировки
слиянием с использованием дополнительной памяти
такого же размера. Сколько раз будет вызвана
функция слияния двух упорядоченных массивов merge?

                            
                                                                                                    
                                        (1) 
    6 раз
                                        
                                                                    
                                        (2) 
    8 раз
                                        
                                                                    
                                        (3) 
    10 раз
                                        
                                                                    
                                        (4) 
    11 раз
                                        
                                                            
                        
                                            
                            
Дан массив длины n, содержащий
элементы некоторого упорядоченного типа (их можно
сравнивать между собой, определяя,
какой из них больше или их равенство).
Требуется определить, сколько различных
элементов содержится в массиве.
Приведите асимптотическую
оценку времени работы наилучшего алгоритма, решающего данную
задачу.

                            
                                                                                                    
                                        (1) 
    t = O(n)
                                        
                                                                    
                                        (2) 
    t = O(n log₂n)
                                        
                                                                    
                                        (3) 
    t = O(n²)
                                        
                                                                    
                                        (4) 
    t = O(n³)
                                        
                                                                    
                                        (5) 
    t = O(log₂n)
                                        
                                                            
                        
                                            
                            
Рассмотрим максимальное по абсолютной величине
целое число, которое в языке C/C++ представимо типом int.
Положительное оно или отрицательное?

                            
                                                                                                    
                                        (1) 
    Положительное.
                                        
                                                                    
                                        (2) 
    Отрицательное.
                                        
                                                            
                        
                                            
                            
Двоичный код, представляющий число типа double,
хранит знак, смещенный порядок и дробную часть
двоичного представления мантиссы.
Чему равен смещенный порядок в представлении числа 6.0?

                            
                                                                                                    
                                        (1) 
    1023.
                                        
                                                                    
                                        (2) 
    1024.
                                        
                                                                    
                                        (3) 
    1025.
                                        
                                                                    
                                        (4) 
    1026.
                                        
                                                            
                        
                                            
                            
Функция с прототипом

double root(double a, double b, double eps);

находит корень фиксированной функции

double f(double x);

на отрезке [a, b] методом деления отрезка пополам
с точностью eps. Сколько примерно раз будет выполнено
тело цикла при поиске корня, когда используется следующий вызов:

    double x = root(1., 2., 0.001);


                            
                                                                                                    
                                        (1) 
    Примерно 5 раз.
                                        
                                                                    
                                        (2) 
    Примерно 10 раз.
                                        
                                                                    
                                        (3) 
    Примерно 16 раз.
                                        
                                                                    
                                        (4) 
    Примерно 20 раз.
                                        
                                                                    
                                        (5) 
    Примерно 100 раз.
                                        
                                                                    
                                        (6) 
    Примерно 1000 раз.
                                        
                                                            
                        
                                            
                            
Какова асимптотическая оценка времени работы
алгоритма Гаусса приведения матрицы
к ступенчатому виду
для случая квадратной матрицы размера n?

                            
                                                                                                    
                                        (1) 
    O(n)
                                        
                                                                    
                                        (2) 
    O(n²)
                                        
                                                                    
                                        (3) 
    O(n³)
                                        
                                                            
                        
                                            
                            
Пусть функция
f(x) = p*x² + q*x + r
(многочлен степени 2), заданная на отрезке [a, b],
принимает значения
y₀, y₁, y₂
в точках a, (a+b)/2, b
(на концах и в середине отрезка). Чему равен интеграл от этой
функции по отрезку [a, b]?

                            
                                                                                                    
                                        (1) 
    1/4 * (y₀ + 2*y₁ + y₂) * (b - a).
                                        
                                                                    
                                        (2) 
    1/5 * (y₀ + 3*y₁ + y₂) * (b - a).
                                        
                                                                    
                                        (3) 
    1/6 * (y₀ + 4*y₁ + y₂) * (b - a).
                                        
                                                            
                        
                                            
                            
Сколько всего простых чисел, меньших 30?

                            
                                                                                                    
                                        10                                    
                                                            
                        
                                            
                            
Как подключаются внешние устройства к общей шине компьютера?

                            
                                                                                                    
                                        (1) 
    Последовательно.
                                        
                                                                    
                                        (2) 
    Параллельно.
                                        
                                                            
                        
                                            
                            
Среди указанных ниже операторов языка C/C++
отметьте корректные.

                            
                                                                                                    
                                        (1) 
    double x = new double;
                                        
                                                                    
                                        (2) 
    double* x = new double(1.5);
                                        
                                                                    
                                        (3) 
    double x = new double[100];
                                        
                                                                    
                                        (4) 
    double* x = (double *) malloc(100 * sizeof(double));
                                        
                                                            
                        
                                            
                            
Назовем функцию y = f(p) на последовательности p 
элементов некоторого типа индуктивной, если при добавлении в конец
последовательности p
еще одного элемента x новое значение функции
y1 = f(p&x) можно вычислить, зная только
старое значение y и добавленный элемент x.
Среди перечисленных ниже функций на последовательностях вещественных
чисел укажите индуктивные.

                            
                                                                                                    
                                        (1) 
    Сумма элементов последовательности.
                                        
                                                                    
                                        (2) 
    Произведение элементов последовательности.
                                        
                                                                    
                                        (3) 
    Значение максимального элемента последовательности.
                                        
                                                                    
                                        (4) 
    Значение многочлена в фиксированной точке t=2,
    коэффициенты многочлена заданы в последовательности 
    p = {a₀, a₁, a₂, ..., a_n}
    по возрастанию степеней:
    
y = a₀ + a₁*t + a₂*t² + ... + a_n*tⁿ
    
                                        
                                                                    
                                        (5) 
    Значение многочлена в фиксированной точке t=2,
    коэффициенты многочлена заданы в последовательности 
    p = {a₀, a₁, a₂, ..., a_n}
    по убыванию степеней:
    
y = a₀*tⁿ + a₁*t^n-1 + ... + a_n
    
                                        
                                                            
                        
                                            
                            
Сколько умножений будет выполнено при вычислении
значения многочлена степени 3, коэффициенты которого
заданы в последовательности по убыванию степеней,
при использовании схемы вычисления индуктивной функции?

                            
                                                                                                    
                                        (1) 
    3
                                        
                                                                    
                                        (2) 
    4
                                        
                                                                    
                                        (3) 
    5
                                        
                                                                    
                                        (4) 
    6
                                        
                                                            
                        
                                            
                            
Оценить сверху время работы (т.е. количество
выполнений тела цикла) алгоритма Евклида
вычисления наибольшего общего делителя двух целых чисел:

int gcd(int m, int n) {
    // дано: целые числа m, n, хотя бы одно отлично от нуля
    // надо: вычислить НОД пары (m, n)
    int a = m, b = n;
    while (b != 0) {
        // Invariant: НОД(a, b) == НОД(m, n)
        int r := a % b; // находим остаток от деления a на b
        a = b; b = r;   // заменяем пару (a, b) на (b, r)
    }
    return a;           // ответ = a
}


                            
                                                                                                    
                                        (1) 
    Время работы не больше, чем
    C*log₂max(m, n),
    где C - некоторая константа
    (т.е. время пропорционально количеству цифр в двоичной или
    десятичной записи максимального из чисел m, n).
                                        
                                                                    
                                        (2) 
    Время работы не больше, чем
    C*r, где C - некоторая константа,
    r -
    квадратный корень из max(m, n)
    (т.е. время пропорционально квадратному корню из максимального
    числа).
                                        
                                                                    
                                        (3) 
    Время работы не больше, чем
    C*max(m, n),
    где C - некоторая константа
    (т.е. время пропорционально максимальному из чисел
    m, n).
                                        
                                                            
                        
                                            
                            
Пусть элементы массива a
нестрого возрастают (соседние элементы могут быть равными).
Дано произвольное значение x, требуется
найти максимальный индекс i такой, что
a[i] <= x. Используется идея алгоритма
бинарного поиска. В приведенном ниже цикле
рассматривается основной случай после отбрасывания
исключительных ситуаций:

    while (end-beg > 1) {
        int c = (beg+end)/2;
        if (a[c] <= x)
            beg = c;
        else
            end = c;
    }
    // ответ в переменной beg

Какое утверждение является
инвариантом этого цикла?

                            
                                                                                                    
                                        (1) 
    a[beg] < x <= a[end].
                                        
                                                                    
                                        (2) 
    a[beg] <= x < a[end].
                                        
                                                                    
                                        (3) 
    a[beg] > x <= a[end].
                                        
                                                                    
                                        (4) 
    a[beg] < x >= a[end].
                                        
                                                            
                        
                                            
                            
В турнире участвуют 4 баскетбольные команды,
все матчи проводятся последовательно
в одном зале. По результатам турнира команды должны быть упорядочены в
соответствии с их силой. В зависимости от исхода матчей турнир может
завершиться раньше или позже; для всякого расписания турнира
можно определить максимально возможное количество матчей.
Приведите оценку снизу максимального количества матчей
для всех возможных расписаний турниров 4 команд.

                            
                                                                                                    
                                        (1) 
    4 матча
                                        
                                                                    
                                        (2) 
    5 матчей
                                        
                                                                    
                                        (3) 
    6 матчей
                                        
                                                                    
                                        (4) 
    3 матча
                                        
                                                            
                        
                                            
                            
Алгоритм быстрой сортировки упорядочивает случайный массив
из миллиона элементов в среднем за 40 секунд. За какое примерно
время тот же алгоритм упорядочит случайный массив
из тысячи элементов?

                            
                                                                                                    
                                        (1) 
    За 0.01 секунды.
                                        
                                                                    
                                        (2) 
    За 0.02 секунды.
                                        
                                                                    
                                        (3) 
    За 0.04 секунды.
                                        
                                                                    
                                        (4) 
    За 0.1 секунды.
                                        
                                                            
                        
                                            
                            
К целочисленному массиву применяется алгоритм сортировки
кучей. На первом этапе из элементов массива строится
пирамида (бинарная куча) путем просеивания элементов
по бинарному дереву в порядке справа налево и снизу вверх.
Пусть вначале массив содержал элементы
1, 2, 3, 4, 5, 6, 7
в указанном порядке.
Каким будет содержимое массива
после построения пирамиды?

                            
                                                                                                    
                                        (1) 
    7, 5, 6, 2, 4, 1, 3.
                                        
                                                                    
                                        (2) 
    7, 5, 6, 4, 2, 1, 3.
                                        
                                                                    
                                        (3) 
    7, 5, 6, 4, 2, 3, 1.
                                        
                                                                    
                                        (4) 
    7, 5, 4, 6, 2, 3, 1.
                                        
                                                                    
                                        (5) 
    7, 5, 6, 4, 3, 2, 1.
                                        
                                                            
                        
                                                                                
                            
Чему равно значение целочисленной переменной x
в результате выполнения приведенного ниже фрагмента программы?

    int x = 1;
    while (x < 100)
        x = -(x * 2);
    }


                            
                                                                                                    
                                        256                                    
                                                            
                        
                                            
                            
Из восьми человек надо выбрать четверых.
Сколько способов выбора возможно?

                            
                                                                                                    
                                        70                                    
                                                            
                        
                                            
                            
Какой двоичный код представляет
число -10 для типа signed char?

                            
                                                                                                    
                                        (1) 
    11111010.
                                        
                                                                    
                                        (2) 
    11111110.
                                        
                                                                    
                                        (3) 
    11110110.
                                        
                                                            
                        
                                            
                            
Двоичный код, представляющий число типа double,
хранит знак, смещенный порядок и дробную часть
двоичного представления мантиссы.
Сколько единичных битов в двоичном представлении
дробной части мантиссы для числа 10.0?

                            
                                                                                                    
                                        (1) 
    1.
                                        
                                                                    
                                        (2) 
    2.
                                        
                                                                    
                                        (3) 
    3.
                                        
                                                                    
                                        (4) 
    4.
                                        
                                                            
                        
                                            
                            
Сколько раз в алгоритме Гаусса будет выполнена операция
перестановки местами двух строк
(с изменением знака одной из них) при приведении к
ступенчатому виду следующей матрицы:

1  2  3  4
0  1  2  3
2  5  8 11


                            
                                                                                                    
                                        (1) 
    1 раз
                                        
                                                                    
                                        (2) 
    2 раза
                                        
                                                                    
                                        (3) 
    3 раза
                                        
                                                                    
                                        (4) 
    4 раза
                                        
                                                            
                        
                                            
                            
Какие переменные располагаются в языке C/C++ в статической памяти?

                            
                                                                                                    
                                        (1) 
    Локальные переменные функций.
                                        
                                                                    
                                        (2) 
    Глобальные переменные.
                                        
                                                                    
                                        (3) 
    Объекты, которые создаются с помощью оператора new.
                                        
                                                                    
                                        (4) 
    Таких переменных нет.
                                        
                                                            
                        
                                            
                            
Пусть процессор имеет 32-разрядную архитектуру
и в некоторый момент его работы регистр SP содержит значение
1000. Укажите, какое значение будет содержаться в SP
после выполнения команды push X.

                            
                                                                                                    
                                        (1) 
    1001
                                        
                                                                    
                                        (2) 
    1004
                                        
                                                                    
                                        (3) 
    999
                                        
                                                                    
                                        (4) 
    996
                                        
                                                            
                        
                                            
                            
Следующий фрагмент программы вычисляет разность d
между максимальным и минимальным элементами 
непустой числовой последовательности.

xmin = ...
xmax = ...

цикл пока в последовательности есть непрочитанные элементы
|выполнять
|  прочесть очередной элемент посл-ти в <вых: x>
|  если x < xmin
|  | то xmin = x
|  конец если
|
|  если x > xmax
|  | то xmax = x
|  конец если
конец цикла

d = xmax - xmin

Какими значениями надо инициализировать переменные
xmin и xmax, чтобы программа
работала правильно?

                            
                                                                                                    
                                        (1) 
    xmin = минус бесконечность,
    xmax = плюс бесконечность
                                        
                                                                    
                                        (2) 
    xmin = плюс бесконечность,
    xmax = минус бесконечность
                                        
                                                                    
                                        (3) 
    xmin = 0,
    xmax = 0
                                        
                                                                    
                                        (4) 
    xmin = 0,
    xmax = плюс бесконечность
                                        
                                                                    
                                        (5) 
    xmin = минус бесконечность,
    xmax = 0
                                        
                                                            
                        
                                            
                            
Назовем элемент x_i
числовой последовательности
w={x₁, x₂, ..., x_n}
локальным максимумом,
если он строго больше соседних элементов (для крайних
элементов рассматривается только 1 сосед, элемент последовательности
длины 1 считается локальным максимумом).
Пусть F(w)=числу локальных максимумов в w.
Какие из перечисленных ниже функций
являются индуктивным расширением функции F?
Укажите все правильные варианты.

                            
                                                                                                    
                                        (1) 
    Тройка (чиcло лок. максимумов в w;

    последний элемент последовательности w;

    1, если последний элемент является лок. максимумом, 0
    в противном случае).
                                        
                                                                    
                                        (2) 
    Тройка (чиcло лок. максимумов в w;

    последний элемент последовательности w;

    предпоследний элемент последовательности w).
                                        
                                                                    
                                        (3) 
    Тройка (0;

    последний элемент последовательности w;

    1, если последний элемент является лок. максимумом, 0
    в противном случае).
                                        
                                                                    
                                        (4) 
    Тройка (чиcло лок. максимумов в w;

    последний элемент последовательности w;

    0).
                                        
                                                            
                        
                                            
                            
Пусть f(x) - целочисленная функция от целочисленного
аргумента. Определить,
содержит ли следующий фрагмент программы ошибку
(т.е. действительно ли тело цикла сохраняет инвариант):

// Программа корень функции
    int a, b, c;
    . . .
    // утверждение: a < b  && f(a)*f(b) <= 0
    // Значения функции на концах отрезка [a,b] разных знаков

    while (b - a > 1) {
        // Invariant: f(a)*f(b) <= 0
        // Делим отрезок [a, b] пополам
        c = (a + b)/2; // c - целая часть (a+b)/2
        if (f(a) * f(c) < 0) {
            b = c;     // выбираем левую половину отрезка
        } else {
            a = c;     // выбираем правую половину
        }
    }

    // утверждение: a == b-1  &&
    //              f(a)*f(b) <= 0


                            
                                                                                                    
                                        (1) 
    Ошибки нет, фрагмент программы корректный.
                                        
                                                                    
                                        (2) 
    Фрагмент программы содержит ошибку.
                                        
                                                            
                        
                                            
                            
Программа, использующая последовательный поиск, ищет
элемент в массиве длины миллион в среднем за
одну секунду. Сколько примерно времени
потребуется на поиск, если мы заменим алгоритм поиска
с последовательного на бинарный?

                            
                                                                                                    
                                        (1) 
    0.0001 секунды
                                        
                                                                    
                                        (2) 
    0.0002 секунды
                                        
                                                                    
                                        (3) 
    0.00001 секунды
                                        
                                                                    
                                        (4) 
    0.00002 секунды
                                        
                                                            
                        
                                            
                            
Алгоритм  быстрой сортировки реализован с помощью комбинированной
схемы, использующей рекурсию и цикл while;
рекурсия применяется лишь к меньшему сегменту массива,
разделенного на части функцией partition.

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;
        }
    }
}

Алгоритм применяется к массиву размером 191. Какой может быть
максимальная глубина рекурсии?
(Под глубиной рекурсии мы подразумеваем количесто раз,
которое функция может вызвать сама себя в цепочке вызовов.
Если рекурсивный вызов отсутствует, то мы считаем глубину рекурсии
нулевой.)

                            
                                                                                                    
                                        6                                    
                                                            
                        
                                                                                
                            
Завершится ли когда-нибудь выполнение цикла
в приведенном ниже фрагменте программы?

    int x = 1;
    while (x != 56) {
        x = (x * 11) % 253;
    }


                            
                                                                                                    
                                        (1) 
    Завершится.
                                        
                                                                    
                                        (2) 
    Не завершится.
                                        
                                                            
                        
                                            
                            
Пусть n - переменная типа unsigned char.
Укажите значение n после выполнения оператора
n = (((3 << 4) | 3) & 0xF2);

                            
                                                                                                    
                                        (1) 
    19.
                                        
                                                                    
                                        (2) 
    34.
                                        
                                                                    
                                        (3) 
    50.
                                        
                                                                    
                                        (4) 
    98.
                                        
                                                            
                        
                                            
                            
Можно ли сохранить целое число

123456789012345678

в переменной типа double
без потери точности?

                            
                                                                                                    
                                        (1) 
    Можно.
                                        
                                                                    
                                        (2) 
    Нельзя.
                                        
                                                            
                        
                                            
                            
Отметьте, что из перечисленного ниже является дурным стилем
программирования на C/C++ (т.е. чего никогда не следует делать).

                            
                                                                                                    
                                        (1) 
    Описание массива большого размера внутри функции.
                                        
                                                                    
                                        (2) 
    Использование статических переменных для вспомогательных
    вычислений.
                                        
                                                                    
                                        (3) 
    Создание массива большого размера в динамической памяти
    с помощью оператора new.
                                        
                                                                    
                                        (4) 
    Создание небольших массивов ограниченного размера
    в динамической памяти с помощью оператора new
    в теле функции, которая работает быстро и вызывается часто.
                                        
                                                            
                        
                                            
                            
Отметьте, для каких из перечисленных ниже целей используется
аппаратный стек в языке C/C++.

                            
                                                                                                    
                                        (1) 
    Для сохранения адресов возврата из функций.
                                        
                                                                    
                                        (2) 
    Для передачи фактических параметров функциям.
                                        
                                                                    
                                        (3) 
    Для возврата значения функции.
                                        
                                                                    
                                        (4) 
    Для размещения локальных переменных функций.
                                        
                                                            
                        
                                            
                            
Последовательность вещественных чисел w
содержит коэффициенты многочлена по убыванию степеней.
Функция F(w) равна значению второй производной
многочлена в фиксированной точке t=2. Среди
указанных ниже функций отметьте те, которые являются индуктивным
расширением функции F.

                            
                                                                                                    
                                        (1) 
    Тройка
    (значение многочлена в точке t;
    значение первой производной многочлена в точке t;
    значение второй производной многочлена в точке t).
                                        
                                                                    
                                        (2) 
    Пара
    (значение второй производной многочлена в точке t;
    степень многочлена).
                                        
                                                                    
                                        (3) 
    Пара
    (значение первой производной многочлена в точке t;
    степень многочлена).
                                        
                                                                    
                                        (4) 
    Тройка
    (значение многочлена в точке 0;
    значение первой производной многочлена в точке 0;
    значение второй производной многочлена в точке 0).
                                        
                                                            
                        
                                                                                
                            
Рассмотрим следующий фрагмент программы на C/C++:

    double x = 1.0;
    double y = 1e-20;
    double z = -x + x + y;
    double t = x + y - x;

Равны ли значения переменных
z и t после его выполнения?

                            
                                                                                                    
                                        (1) 
    Равны.
                                        
                                                                    
                                        (2) 
    Не равны.
                                        
                                                            
                        
                                            
                            
Числами Ферма F_k называются числа вида
2^{2^k}+1. Например,
F₁=5, 
F₂=17, 
F₃=257,
F₄=65537. Отметьте, какие из
приведенных ниже утверждений являются верными.

                            
                                                                                                    
                                        (1) 
    Все числа Ферма простые.
                                        
                                                                    
                                        (2) 
    Числа Ферма удовлетворяют условию Малой теоремы Ферма
    для основания 2, т.е. если m - число Ферма, то
    2^m-11 (mod m)
                                        
                                                                    
                                        (3) 
    Числа Ферма F₁, F₃,
    F₅ простые.
                                        
                                                                    
                                        (4) 
    Числа Ферма F₂ и
    F₄ простые.
                                        
                                                            
                        
                                            
                            
Рассмотрим рекурсивную реализацию алгоритма Евклида:

int gcd1(int m, int n) {
    if (n == 0)
        return m;
    int r = m % n;
    return gcd1(n, r);
}

Укажите, какова будет глубина рекурсии (т.е. какое максимальное
количество кадров локальных переменных функции gcd1
будет размещено одновременно в аппаратном стеке) при следующем
вызове функции:

    int d = gcd1(25, 35);


                            
                                                                                                    
                                        (1) 
    2
                                        
                                                                    
                                        (2) 
    3
                                        
                                                                    
                                        (3) 
    4
                                        
                                                                    
                                        (4) 
    5


                        
                                                            
                            
Какой максимальный адрес байта в 32-разрядной
архитектуре?

                            
                                                                                                    
                                        (1) 
    2³²
                                        
                                                                    
                                        (2) 
    2³²-1
                                        
                                                                    
                                        (3) 
    2³²-4
                                        
                                                                    
                                        (4) 
    2³²-4
                                        
                                                                    
                                        (5) 
    32³²
                                        
                                                            
                        
                                            
                            
Алгоритм сортировки называется стабильным, если он
сохраняет относительный порядок равных элементов.
Среди перечисленных ниже алгоритмов сортировки
(имеются в виду их классические варианты) отметьте все стабильные.

                            
                                                                                                    
                                        (1) 
    Сортировка прямым выбором.
                                        
                                                                    
                                        (2) 
    Пузырьковая сортировка.
                                        
                                                                    
                                        (3) 
    Сортировка кучей HeapSort.
                                        
                                                            
                        
                                            
                            
К массиву a длины 50 применяется
восходящая схема двунаправленного алгоритма сортировки
слиянием с использованием дополнительной памяти — массива b
такого же размера. В каком из этих массивов мы получим результат после
окончательного шага слияния, т.е. будет ли вызвана
функция copyArray, чтобы
скопировать результат из вспомогательного массива
b в массив a?

                            
                                                                                                    
                                        (1) 
    Результат будет в массиве a, функция
    copyArray вызвана не будет.
                                        
                                                                    
                                        (2) 
    Результат будет в массиве b, будет вызвана функция
    copyArray.
                                        
                                                            
                        
                                            
                            
Дан массив длины 11, требуется циклически
сдвинуть его элементы вправо на 3 позиции. Какое минимальное
число операций копирования выполняется в любом алгоритме,
решающем данную задачу? Имеются в виду операции копирования
одного элемента массива в другой, элемента массива в простую
переменную, одной простой переменной в другую.

                            
                                                                                                    
                                        (1) 
    Минимум 11 операций.
                                        
                                                                    
                                        (2) 
    Минимум 12 операций.
                                        
                                                                    
                                        (3) 
    Минимум 33 операции.
                                        
                                                                    
                                        (4) 
    Минимум 22 операции.
                                        
                                                                    
                                        (5) 
    Минимум 10 операции.
                                        
                                                            
                        
                                            
                            
Сколько единиц в двоичной записи числа 13?

                            
                                                                                                    
                                        (1) 
    1.
                                        
                                                                    
                                        (2) 
    2.
                                        
                                                                    
                                        (3) 
    3.
                                        
                                                            
                        
                                            
                            
При представлении целых чисел в формате Big Endian
байты внутри слова нумеруются слева направо, в формате
Little Endian - справа налево. Пусть компьютер использует
архитектуру Big Endian. Укажите, чему будет равно значение
переменной n в результате выполнения
следующего фрагмента программы:

    int k = (-2); int n;
    signed char *p = (signed char *) &k;
    n = *p;


                            
                                                                                                    
                                        (1) 
    Значение n равно 0.
                                        
                                                                    
                                        (2) 
    Значение n равно -1.
                                        
                                                                    
                                        (3) 
    Значение n равно -2.
                                        
                                                                    
                                        (4) 
    Значение n равно 254.
                                        
                                                                    
                                        (5) 
    Значение n равно 255.
                                        
                                                            
                        
                                            
                            
Рассмотрим следующую программу на C/C++:

#include <stdio.h>
#include <math.h>

int main() {
    double x = pow(2., 1024.);
    double y = x / 2.;
    double z = pow(2., 1023.);
    if (y == z) {
        printf("y == z\n");
    } else {
        printf("y != z\n");
    }
    return 0;
}

(Функция pow(a, b) возводит
число a в степень b.)
Что будет напечатано в результате ее выполнения?

                            
                                                                                                    
                                        (1) 
    y == z.
                                        
                                                                    
                                        (2) 
    y != z.
                                        
                                                            
                        
                                            
                            
Какие из перечисленных ниже объектно-ориентированных
языков программирования поддерживаются фирмой Microsoft?

                            
                                                                                                    
                                        (1) 
    Objective C
                                        
                                                                    
                                        (2) 
    Visual Basic
                                        
                                                                    
                                        (3) 
    Delphi
                                        
                                                                    
                                        (4) 
    C#
                                        
                                                                    
                                        (5) 
    C++
                                        
                                                            
                        
                                            
                            
Рассмотрим следующий фрагмент программы  на C++:

    double a[5][3];
    const double *p = &(a[0][0]);
    const double *q = &(a[2][2]);
    int n = q - p;

Чему равно значение n
после выполнения этого фрагмента?

                            
                                                                                                    
                                        (1) 
    n = 8
                                        
                                                                    
                                        (2) 
    n = 12
                                        
                                                                    
                                        (3) 
    n = 64
                                        
                                                                    
                                        (4) 
    n = 96
                                        
                                                            
                        
                                            
                            
Какова степень интерполяционного многочлена,
построенного по четырем узлам
x₀, x₁,
x₂, x₃,
принимающего в этих узлах значения
y₀, y₁,
y₂, y₃?

                            
                                                                                                    
                                        (1) 
    Степень 2 (парабола).
                                        
                                                                    
                                        (2) 
    Степень 3 (кубическая парабола).
                                        
                                                                    
                                        (3) 
    Степень 4.
                                        
                                                            
                        
                                            
                            
Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел.
Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.
Программа должна содержать функцию, которая получает в качестве параметра имя файла  и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.
Задание: посчитать среднее геометрическое чисел из последовательности.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                            
                            
Постановка задачи: программа должна содержать функцию, которая получает в качестве параметров имя массива и его длину (или нескольких массивов, если этого требуют условия задачи) и выполняет необходимые действия.
При решении не разрешается создавать или резервировать в программе дополнительную память, соизмеримую по размерам с объемом исходных данных. То есть, нельзя создавать дополнительные массивы, если это явно не оговорено в задаче.
Функция main должна заполнить массив числами из файла. Для определения длины массива предусматривается два варианта: 1) по значению первого числа в файле, 2) непосредственным подсчетом количества чисел в файле. Результат также выводится в файл.
Задание: переставить элементы массива в обратном порядке.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                            
                            
Каков диапазон целочисленного типа signed char?

                            
                                                                                                    
                                        (1) 
    -128 ... 127
                                        
                                                                    
                                        (2) 
    0 ... 255
                                        
                                                                    
                                        (3) 
    0 ... 65535
                                        
                                                                    
                                        (4) 
    -32768 ... 32767
                                        
                                                            
                        
                                            
                            
Сколько раз будет выполнено тело цикла в алгоритме
Евклида

int gcd(int m, int n) {
    while (n != 0) {
        int r = m % n;
        m = n; n = r;
    }
    return m;
}

при следующих входных значениях аргументов:
m=24, n=30?

                            
                                                                                                    
                                        3                                    
                                                            
                        
                                            
                            
Пусть расположенный в статической памяти
целочисленный массив a описан как

static int a[] = {
    10, 9, 8, 7, 6, 5, 4, 3, 2, 1
};

Пусть в программе задана функция суммирования массива
с прототипом

int sum(const int *m, int n);

где m - константный указатель на начало
массива, n - число его элементов. Укажите,
чему будет равно значение переменной s в
результате выполнения следующего фрагмента программы:

    int s = sum(a+3, 4);


                            
                                                                                                    
                                        22                                    
                                                            
                        
                                            
                            
Какой объект описан в следующей строке программы
на C/C++?

    double (*a)[20];


                            
                                                                                                    
                                        (1) 
    Массив из 20 элементов типа указатель на double.
                                        
                                                                    
                                        (2) 
    Указатель на массив из 20 элемментов типа double.
                                        
                                                                    
                                        (3) 
    Указатель на первую переменную массива типа double.
                                        
                                                            
                        
                                            
                            
Левым нейтральным элементом (левой единицей) для бинарной операции
 называется элемент e такой, что для всякого
другого элемента x "произведение" e на
x равно x:
e  x = x. Какие элементы будут нейтральными
для операций произведения и минимума чисел соответственно?

                            
                                                                                                    
                                        (1) 
    1, 0.
                                        
                                                                    
                                        (2) 
    0, +
                                        
                                                                    
                                        (3) 
    1, -
                                        
                                                                    
                                        (4) 
    1, +
                                        
                                                            
                        
                                            
                            
Выполняется ли инвариант цикла в процессе выполнения
тела цикла?

                            
                                                                                                    
                                        (1) 
    Да, выполняется.
                                        
                                                                    
                                        (2) 
    Не обязательно.
                                        
                                                            
                        
                                            
                            
В массиве, содержащем 1000 элементов,
выполняется последовательный поиск элемента x.
При этом x содержится
в массиве с вероятностью 0.75. Сколько в среднем операций сравнения
будет выполнено?

                            
                                                                                                    
                                        (1) 
    625
                                        
                                                                    
                                        (2) 
    750
                                        
                                                                    
                                        (3) 
    875
                                        
                                                                    
                                        (4) 
    550
                                        
                                                                    
                                        (5) 
    900
                                        
                                                            
                        
                                            
                            
Массив a размера 4 содержит
элементы 4, 2, 1, 3 в указанном порядке.
К нему применяется алгоритм пузырьковой сортировки,
использующий сравнение элементов с помощью функции compare
и обмен элементов с помощью функции swap.
Сколько раз будет вызвана функция swap?

                            
                                                                                                    
                                        4                                    
                                                            
                        
                                            
                            
Алгоритм быстрой сортировки использует вспомогательную функцию
partition, которая разделяет массив на 3 части:
в начале элементы, меньшие либо равные медиане, затем медиана,
в конце элементы, большие либо равные медиане. Рассмотрим следующую
реализацию функции partition:

void partition(double* a, int n, int *m) {
    if (*m != 0)    // Ставим медиану в начало
        swap(&(a[0]), &(a[*m]));
    double x = a[0];    // Значение медианы
    int i = 0;
    int j = n;
    while (j-i > 1) {
        // Инв: a[1], a[2], ..., a[i] <= x
        //      a[j], a[j+1], ..., a[n-1] >= x
        if (a[i+1] <= x) {
            ++i;
        } else if (a[j-1] >= x)
            --j;
        } else {
            ++i; --j;
            swap(&(a[i]), &(a[j]));
        }
    }

    if (i > 0)
        swap(&(a[0]), &(a[i]));
    *m = i;
}

Правильна ли подобная реализация, или она может привести
к катастрофическому замедлению алгоритма быстрой
сортировки в некоторых случаях?

                            
                                                                                                    
                                        (1) 
    Реализация правильная.
                                        
                                                                    
                                        (2) 
    Реализация неправильная.
                                        
                                                            
                        
                                            
                            
Какие из перечисленных ниже алгоритмов сортировки
работают в среднем
за время O(n log₂ n)?
Отметьте все правильные ответы.

                            
                                                                                                    
                                        (1) 
    Пузырьковая сортировка.
                                        
                                                                    
                                        (2) 
    Сортировка прямым выбором.
                                        
                                                                    
                                        (3) 
    Быстрая сортировка QuickSort.
                                        
                                                                    
                                        (4) 
    Сортировка кучей HeapSort.
                                        
                                                            
                        
                                                                                
                            
Какой из перечисленных языков высокого уровня является
наиболее современным?

                            
                                                                                                    
                                        (1) 
    Algol
                                        
                                                                    
                                        (2) 
    Pascal
                                        
                                                                    
                                        (3) 
    Oberon
                                        
                                                                    
                                        (4) 
    Modula-2
                                        
                                                            
                        
                                            
                            
К трехзначным десятичным числам (строкам длины 3 из десятичных
цифр) применяется алгоритм RADIX-сортировки сначала по младшей цифре,
затем по средней и в конце по старшей. Исходный массив содержит следующие
числа:

232, 102, 307, 901, 835, 215, 105, 301, 323, 811.

Каким будет содержимое массива после выполнения первых двух шагов
сортировки (т.е. после сортировки по младшей и средней цифрам)?

                            
                                                                                                    
                                        (1) 
    301, 901, 102, 105, 307, 811, 215, 323, 232, 835
                                        
                                                                    
                                        (2) 
    901, 301, 102, 105, 307, 811, 215, 323, 232, 835
                                        
                                                                    
                                        (3) 
    901, 301, 102, 105, 307, 811, 215, 232, 323, 835
                                        
                                                                    
                                        (4) 
    901, 301, 102, 105, 307, 215, 811, 323, 232, 835
                                        
                                                                    
                                        (5) 
    901, 301, 102, 307, 105, 811, 215, 323, 232, 835
                                        
                                                            
                        
                                            
                            
К массиву a длины 30 применяется
восходящая схема двунаправленного алгоритма сортировки
слиянием с использованием дополнительной памяти.
В процессе выполнения алгоритма многократно
вызывается функция merge слияния двух упорядоченных
массивов длины n и m. Каковы
длины массивов, которые сливаются при самом последнем вызове
функции merge?

                            
                                                                                                    
                                        (1) 
    n=15, m=15
                                        
                                                                    
                                        (2) 
    n=16, m=14
                                        
                                                                    
                                        (3) 
    n=24, m=16
                                        
                                                                    
                                        (4) 
    n=24, m=15
                                        
                                                                    
                                        (5) 
    n=16, m=15
                                        
                                                                    
                                        (6) 
    n=15, m=14
                                        
                                                            
                        
                                            
                            
Дан массив длины 21, требуется циклически
сдвинуть его элементы вправо на 6 позиций.
Существует ли алгоритм, который решает эту задачу,
выполняя 22 операции копирования?
Имеются в виду операции копирования
одного элемента массива в другой, элемента массива в простую
переменную, одной простой переменной в другую.

                            
                                                                                                    
                                        (1) 
    Да.
                                        
                                                                    
                                        (2) 
    Нет.
                                        
                                                            
                        
                                            
                            
Для записи n-значных чисел в системе счисления с основанием
b требуется n разрядов,
каждый из которых может находиться
в b состояниях. Таким образом, суммарное число состояний
равно произведению n*b.
Рассмотрим двоичную (b=2), троичную
(b=3) и десятичную (b=10) системы счисления.
Какая из них
наиболее экономна по суммарному числу состояний для записи
чисел в диапазоне 0..N,
где N - некоторое достаточно большое число?

                            
                                                                                                    
                                        (1) 
    Двоичная.
                                        
                                                                    
                                        (2) 
    Троичная.
                                        
                                                                    
                                        (3) 
    Десятичная.
                                        
                                                            
                        
                                            
                            
Пусть для представления вещественных чисел
мы используем десятичные целые числа с фиксированной позицией
десятичной точки, отделяющей ровно 2 знака дробной части.
Например, целое число 314 представляет
вещественное число 3.14. Рассмотрим два числа
с фиксированной точкой, представленные целыми числами
240 и 20001. Каким числом будет представлено их произведение?

                            
                                                                                                    
                                        (1) 
    480.
                                        
                                                                    
                                        (2) 
    48002.
                                        
                                                                    
                                        (3) 
    480024.
                                        
                                                                    
                                        (4) 
    4800240.
                                        
                                                            
                        
                                            
                            
Функция ln(z) (натуральный логарифм z) представляется
в виде степенного ряда следующим образом:

    ln(1+x) = x - x²/2 + x³/3 - x⁴/4 + ...

(мы обозначили z=1+x).
Рассмотрим реализованную на C/C++ функцию myLog(z),
вычисляющую значение логарифма с точностью до одной миллионной:

static const double EPS = 1e-6;

double myLog(double z) {
    double x = z - 1.;
    double s = 0.;
    double p = x;
    double n = 1.;
    double a = x;
    while (fabs(a) > EPS) {
        s += a;
        p = (-p*x);
        n += 1.;
        a = p/n;
    }
    return s;
}

Для каких значений z ее можно применять так,
чтобы функция завершала работу за разумное время и
ошибка вычисления результата была бы не более 0.0001?
Укажите все правильные ответы из числа перечисленных ниже.

                            
                                                                                                    
                                        (1) 
    Для небольших положительных значений z,
    например, 0<z<10.
                                        
                                                                    
                                        (2) 
    Для любых значений z в интервале
    0<z<2.
                                        
                                                                    
                                        (3) 
    Для z = 10^-10.
                                        
                                                                    
                                        (4) 
    Для z = 2.0001.
                                        
                                                                    
                                        (5) 
    Для значений z в интервале
    0.1 <z<1.9.
                                        
                                                            
                        
                                            
                            
Какую из конструкций цикла в языке C удобнее всего использовать
для реализации арифметического цикла, в котором тело цикла
последовательно выполняется для всех значений переменной цикла,
представляющих арифметическую прогрессию?

                            
                                                                                                    
                                        (1) 
    цикл do-while
                                        
                                                                    
                                        (2) 
    цикл while
                                        
                                                                    
                                        (3) 
    цикл for
                                        
                                                            
                        
                                            
                            
Рассмотрим реализацию матрицы вещественных чисел,
размеры которой определяются
в процессе работы программы, через массив указателей на начала
строк, захватываемый в динамической памяти. Каждая строка
также представляет собой отдельный массив в
динамической памяти:

    typedef double* doubleptr;
    int m, n; // Размеры матрицы: число строк, столбцов
    . . .
    doubleptr* a = new doubleptr[m];
    for (int i = 0; i < m; ++i) {
        a[i] = new double[n];
    }
    // a[i][j] -- элемент i-й строки и j-го столбца

Сколько памяти требуется для хранения прямоугольной
матрицы размером в 10 строк и 20 столбцов
в 32-разрядной архитектуре
(без учета памяти, используемой под описатели фрагментов кучи)?

                            
                                                                                                    
                                        (1) 
    1600 байтов
                                        
                                                                    
                                        (2) 
    1640 байтов
                                        
                                                                    
                                        (3) 
    1680 байтов
                                        
                                                                    
                                        (4) 
    1760 байтов
                                        
                                                            
                        
                                            
                            
Интерполяционный многочлен в форме Ньютона, построенный
по узлам
x₀, x₁, ..., x_n и
принимающий в этих узлах значения
y₀, y₁, ..., y_n,
представляется формулой

p_n(x) = a₀ + a₁(x-x₀) + a₁(x-x₀)(x-x₁) + ... + a_n(x-x₀)(x-x₁)...(x-x_n-1)

Сколько действий нужно выполнить, чтобы вычислить все его коэффициенты
a₀, a₁, ..., a_n?

                            
                                                                                                    
                                        (1) 
    O(n).
                                        
                                                                    
                                        (2) 
    O(n²).
                                        
                                                                    
                                        (3) 
    O(n³).
                                        
                                                            
                        
                                            
                            
Отметьте, какие из перечисленных ниже целочисленных значений
помещаются в переменную типа unsigned int
(для удобства триады цифр разделяются запятыми).

                            
                                                                                                    
                                        (1) 
    4,000,000
                                        
                                                                    
                                        (2) 
    2,000,000,000
                                        
                                                                    
                                        (3) 
    4,000,000,000
                                        
                                                                    
                                        (4) 
    5,000,000,000
                                        
                                                                    
                                        (5) 
    10,000,000,000
                                        
                                                            
                        
                                            
                            
Укажите, чему будет равно значение переменной k
в результате выполнения следующего фрагмента программы:

    int n = (-7), k, *p;
    p = &n; ++*p; k = 3-*p*3+n;


                            
                                                                                                    
                                        15                                    
                                                            
                        
                                            
                            
Пусть переменные a, p,
q, n описаны следующим образом:

    double a[16]; double *p;
    const double *q; int n;

Отметьте, какие из приведенных ниже операторов языка C/C++
корректны.

                            
                                                                                                    
                                        (1) 
    q = a + 16;
                                        
                                                                    
                                        (2) 
    q = &p[3] + 2;
                                        
                                                                    
                                        (3) 
    p = &q[2] + 3;
                                        
                                                                    
                                        (4) 
    n = p - &a[2];
                                        
                                                                    
                                        (5) 
    n = q - a;
                                        
                                                            
                        
                                            
                            
Чему будет равно значение переменной n
в результате выполнения следующего фрагмента программы?
Процессор имеет 32-разрядную архитектуру.

    double (*a)[4]; int n, m;
    n = (int)(a+1); m = (int) a;
    n -= m;


                            
                                                                                                    
                                        32                                    
                                                            
                        
                                            
                            
Какие константы можно в практическом программировании использовать
в качестве воображаемого значения "минус бесконечность" при работе с
вещественными числами типа float? Укажите все правильные
варианты.

                            
                                                                                                    
                                        (1) 
    Число -FLT_MAX
    (константа FLT_MAX описана в стандартном заголовочном файле
    float.h).
                                        
                                                                    
                                        (2) 
    Константу FLT_MIN,
    заданную в стандартном заголовочном файле
    float.h.
                                        
                                                                    
                                        (3) 
    Константу -1e+30.
                                        
                                                            
                        
                                            
                            
Пусть целочисленная переменная n
содержит некоторое положительное целое число.
Указать, что вычисляет следующая функция f(n):

int f(int n) {
    int x = 1; int y = 4;
    while (y <= n) {
        // Invariant: y == (x+1)^2
        ++x;
        y += 2*x+1;
    }
    return x;
}


                            
                                                                                                    
                                        (1) 
    Целую часть от n/2;
                                        
                                                                    
                                        (2) 
    Целую часть квадратного корня из n.
                                        
                                                                    
                                        (3) 
    Целую часть от log₂ n.
                                        
                                                                    
                                        (4) 
    Целую часть кубического корня из n.
                                        
                                                                    
                                        (5) 
    Целую часть от eⁿ.
                                        
                                                                    
                                        (6) 
    Целую часть от 2ⁿ.
                                        
                                                            
                        
                                            
                            
Пусть дан массив a длины n,
элементы которого нестрого возрастают, т.е. соседние
элементы могут быть равными.
Рассмотрим фрагмент программы бинарного поиска
элемента x в массиве
a длины n, где
после отбрасывания особых ситуаций рассматривается
основной случай:

        . . .
        // Утверждение: a[0] < x && x <= a[n-1]
        int beg = 0; int end = n-1;
        while (end-beg > 1) {
            // Инвариант: a[beg] < x && x <= a[end]
            int c = (beg + end) / 2;
            if (a[c] < x) {
                beg = c;
            } else {
                end = c;
            }
        }
        *idx = end;
        . . .

Пусть значение x содержится в массиве
в нескольких экземплярах. Индекс какого элемента
массива a будет записан в переменную *idx?

                            
                                                                                                    
                                        (1) 
    Индекс первого элемента, равного
    x.
                                        
                                                                    
                                        (2) 
    Индекс поcледнего элемента, равного
    x.
                                        
                                                                    
                                        (3) 
    Может быть записан индекс любого элемента
    массива a, равного
    x.
                                        
                                                                    
                                        (4) 
    Индекс поcледнего элемента, равного
    x-1.
                                        
                                                                    
                                        (5) 
    Индекс первого элемента, равного
    x+1.
                                        
                                                            
                        
                                            
                            
Алгоритм пузырьковой сортировки упорядочивает массив
из 10 тысяч элементов примерно за 1 секунду. За какое примерно
время тот же алгоритм упорядочит массив из миллиона элементов?

                            
                                                                                                    
                                        (1) 
    За 1 минуту 40 секунд
                                        
                                                                    
                                        (2) 
    Около 17 минут
                                        
                                                                    
                                        (3) 
    Около 2 часов 47 минут
                                        
                                                                    
                                        (4) 
    Около 57 минут
                                        
                                                                    
                                        (5) 
    Около 37 минут
                                        
                                                            
                        
                                            
                            
Алгоритм сортировки называется стабильным,
если он сохраняет взаимный порядок равных элементов.
(Такое определение имеет смысл при сортировке массива записей,
состоящих из нескольких полей, которые сравниваются лишь
по значению одного конкретного поля - например, записи о людях
сортируются по их именам, при этом могут быть однофамильцы.)
Является ли алгоритм быстрой сортировки стабильным?

                            
                                                                                                    
                                        (1) 
    Да.
                                        
                                                                    
                                        (2) 
    Нет.
                                        
                                                            
                        
                                            
                            
Целочисленный массив содержит элементы
20, 18, 10, 15, 7, 7, 9, 8, 10, 6, 4, 5
в указанном порядке. Образуют ли они бинарную кучу (пирамиду)?

                            
                                                                                                    
                                        (1) 
    Да.
                                        
                                                                    
                                        (2) 
    Нет.
                                        
                                                            
                        
                                                                                
                            
Что можно сказать об условии, указанном в заголовке цикла "while",
после завершения цикла?

                            
                                                                                                    
                                        (1) 
    Условие истинно.
                                        
                                                                    
                                        (2) 
    Условие ложно.
                                        
                                                                    
                                        (3) 
    Условие может быть как истинным, так и ложным.
                                        
                                                            
                        
                                            
                            
Сортируемый массив содержит составные ключи из 20
десятичных цифр (например, идентификаторы банковских счетов).
Массив имеет длину 1000. Надо выбрать один из двух алгоритмов
сортировки: сортировку кучей HeapSort или RADIX-сортировку.
Какой из двух алгоритмов будет в среднем работать быстрее
в данной ситуации?

                            
                                                                                                    
                                        (1) 
    RADIX-сортировка.
                                        
                                                                    
                                        (2) 
    Сортировка кучей HeapSort.
                                        
                                                            
                        
                                            
                            
К массиву a длины 20 применяется
восходящая схема двунаправленного алгоритма сортировки
слиянием с использованием дополнительной памяти.
В процессе выполнения алгоритма многократно
вызывается функция merge слияния двух упорядоченных
массивов длины n и m. Каковы
длины массивов, которые сливаются при самом последнем вызове
функции merge?

                            
                                                                                                    
                                        (1) 
    n=10, m=10
                                        
                                                                    
                                        (2) 
    n=12, m=8
                                        
                                                                    
                                        (3) 
    n=16, m=4
                                        
                                                                    
                                        (4) 
    n=10, m=8
                                        
                                                                    
                                        (5) 
    n=12, m=4
                                        
                                                                    
                                        (6) 
    n=16, m=10
                                        
                                                            
                        
                                            
                            
Дан массив длины 15, требуется циклически
сдвинуть его элементы вправо на 6 позиций.
Существует ли алгоритм, который решает эту задачу,
выполняя 18 операций копирования?
Имеются в виду операции копирования
одного элемента массива в другой, элемента массива в простую
переменную, одной простой переменной в другую.

                            
                                                                                                    
                                        (1) 
    Да.
                                        
                                                                    
                                        (2) 
    Нет.
                                        
                                                            
                        
                                            
                            
В алгоритме получения записи числа n
в системе счисления с основанием b
мы вычисляем цифры числа справа налево,
начиная с последней цифры. На очередном шаге
мы делим n с остатком на b, получая
частное q и остаток r;
остаток представляет очередную цифру числа
в порядке справа налево.
Затем мы переменной n
присваиваем значение частного q,
и процесс повторяется, пока n не станет равным нулю.
Сколько раз будет выполнена операция деления
при переводе числа 2000000 (два миллиона)
в восьмеричную систему счисления?

                            
                                                                                                    
                                        (1) 
    6 раз.
                                        
                                                                    
                                        (2) 
    7 раз.
                                        
                                                                    
                                        (3) 
    8 раз.
                                        
                                                                    
                                        (4) 
    9 раз.
                                        
                                                            
                        
                                            
                            
При представлении вещественных чисел в плавающей форме
мы выражаем вещественное число x в виде

    x = s 2^e m,

где s - знак числа, принимающий значение
плюс или минус единица,
e - порядок, представляющий собой
целое число (положительное, 0 или отрицательное),
m - мантисса, представляющая собой
вещественное число в диапазоне
1  m < 2.
Чему равны порядок и мантисса для числа 20?

                            
                                                                                                    
                                        (1) 
    e=4, m=1.2.
                                        
                                                                    
                                        (2) 
    e=3, m=1.75.
                                        
                                                                    
                                        (3) 
    e=4, m=1.25.
                                        
                                                            
                        
                                            
                            
Формула Бинома Ньютона дает следующее разложение в ряд
для функции "квадратный корень из z":

(1+x)^0.5 = sqrt(1+x) =
    1 + 0.5 x + 0.5(-0.5)/2! x² + 0.5(-0.5)(-1.5)/3! x³ + 0.5(-0.5)(-1.5)(-2.5)/4! x⁴ + ...

(мы обозначили z=1+x). 
Этот ряд сходится лишь для значений 
x, по абсолютной величине не превосходящих 1, а эффективно вычислять
его сумму можно только для еще более узкого интервала значений 
x. 
Каким свойством функции sqrt(z)
удобнее всего воспользоваться, чтобы свести ее вычисление к суммированию ряда?

                            
                                                                                                    
                                        (1) 
    Свойством sqrt(z)=sqrt(n)*sqrt(z/n),
    где n - целая часть z.
                                        
                                                                    
                                        (2) 
    Свойствами 
    sqrt(z) = sqrt(2)*sqrt(z/2)
    при z > 1.5 и
    sqrt(z) = sqrt(z*2)/sqrt(2)
    при z < 0.5.
                                        
                                                                    
                                        (3) 
    Свойствами 
    sqrt(z) = 2*sqrt(z/4) при z > 1.5 и
    sqrt(z) = 0.5*sqrt(z*4) при z < 0.375.
                                        
                                                            
                        
                                            
                            
Где описан прототип функции sqrt(x), вычисляющий
квадратный корень вещественного числа x?

                            
                                                                                                    
                                        (1) 
    В стандартном заголовочном файле stdio.h
                                        
                                                                    
                                        (2) 
    В стандартном заголовочном файле stdlib.h
                                        
                                                                    
                                        (3) 
    В стандартном заголовочном файле math.h
                                        
                                                            
                        
                                            
                            
Рассмотрим реализацию матрицы вещественных чисел
размера m строк на n столбцов
при помощи линейного массива,
в котором хранятся сначала элементы нулевой строки матрицы,
затем первой, второй и т.д., в конце - элементы (m-1)-й строки:

    int m, n; // Размеры матрицы: число строк, столбцов
    . . .
    double* a = new double[m*n];
    // a[i*n + j] -- элемент i-й строки и j-го столбца

Пусть функция с прототипом

void transp(double* a, int m, int n);

реализует транспонирование
матрицы, при выполнении которого строки матрицы становятся
столбцами, столбцы - строками, а матрица размера
m на n
превращается в матрицу размера
n на m
Пусть эта функция применяется к прямоугольной матрице,
содержащей 2 строки и 4 столбца, элементы которой хранятся
в линейном массиве a Сколько элементов массива
a при этом останутся на своем месте?

                            
                                                                                                    
                                        (1) 
    2 элемента
                                        
                                                                    
                                        (2) 
    3 элемента
                                        
                                                                    
                                        (3) 
    4 элемента
                                        
                                                            
                        
                                            
                            
Пусть неизвестная функция определена на отрезке [a, b],
причем на концах отрезка заданы ее значения
y₀=f(a),
y₁=f(b),
а также значения ее производной
y'₀=f'(a),
y'₁=f'(b).
Нужно приблизить функцию многочленом так, чтобы на концах отрезка
его значения, а также значения его производной совпадали со
значениями и производной функции. Какой должна быть
степень такого многочлена? (Укажите минимальную
степень, достаточную для решения этой задачи.)

                            
                                                                                                    
                                        (1) 
    Степень 1.
                                        
                                                                    
                                        (2) 
    Степень 2.
                                        
                                                                    
                                        (3) 
    Степень 3.
                                        
                                                                    
                                        (4) 
    Степень 4.
                                        
                                                            
                        
                                            
                            
Чему равно значение выражения (-23)%6*10
в языке C?

                            
                                                                                                    
                                        -50                                    
                                                            
                        
                                            
                            
Укажите, чему будет равно значение переменной n
в результате выполнения следующего фрагмента программы:

    double *p = 1000;
    p += 1000;
    int n = (int) p;


                            
                                                                                                    
                                        9000                                    
                                                            
                        
                                            
                            
Мы хотим реализовать функцию product, которая находит
произведение элементов вещественного массива a
длины n.
Отметьте, какие из возможных прототипов данной функции
корректны.

                            
                                                                                                    
                                        (1) 
    double product(double *a, int n);
                                        
                                                                    
                                        (2) 
    double product(const double a[], int n);
                                        
                                                                    
                                        (3) 
    void product(const double *a, int n, double* prod);
                                        
                                                                    
                                        (4) 
    void product(double a[], int n, double* prod);
                                        
                                                            
                        
                                            
                            
Укажите, какие из приведенных ниже строк языка C/C++
корректно описывают объекты языка.

                            
                                                                                                    
                                        (1) 
    void (*f[10])(int x);
                                        
                                                                    
                                        (2) 
    void (*(*f)[10])(int x);
                                        
                                                                    
                                        (3) 
    void (*f)(int x)[10];
                                        
                                                                    
                                        (4) 
    char (*f(int x))[16];
                                        
                                                            
                        
                                            
                            
Является ли индуктивной функция, которая последовательности
коэффициентов многочлена по убыванию степеней ставит
в соответствие пару чисел:
(степень многочлена, интеграл многочлена по отрезку [0, 1])?

                            
                                                                                                    
                                        (1) 
    Является.
                                        
                                                                    
                                        (2) 
    Не является.
                                        
                                                            
                        
                                            
                            
Рассмотрим следующую функцию, аргументами которой
являются два целых неотрицательных числа:

int f(int m, int n) {
    // дано: m >= 0 и n >= 0
    int a = m; int b = n;
    int c = 1;
    while (a != 0 && b != 0) {
        if (a%2 == 0 && b%2 == 0) {
            // a и b четные
            a /= 2; b /= 2;
            c *= 2;
        } else if (a%2 == 0) {
            // a четное, b нечетное
            a /= 2;
        } else if (b%2 == 0) {
            // a нечетное, b четное
            b /= 2;
        } else {
            // a и b нечетные
            if (a > b) {
                a -= b;
            } else {
                b -= a;
            }
        }
    } // end while
    return c*(a + b);
}

Какое условие является инвариантом цикла?
(Через НОД и НОК обозначены наибольший общий делитель и
наименьшее общее кратное.)

                            
                                                                                                    
                                        (1) 
    Равенство НОД(a, b) = НОД(m, n)*c.
                                        
                                                                    
                                        (2) 
    Равенство НОК(m, n) = c*(a + b).
                                        
                                                                    
                                        (3) 
    Равенство НОД(a,b)*c = НОД(m, n).
                                        
                                                                    
                                        (4) 
    Равенство НОД(a,b) = НОД(m, n)*c.
                                        
                                                            
                        
                                            
                            
Пусть дан массив a длины n,
элементы которого нестрого возрастают, т.е. соседние
элементы могут быть равными.
Рассмотрим фрагмент программы бинарного поиска
элемента x в массиве
a длины n, где
после отбрасывания особых ситуаций рассматривается
основной случай:

        . . .
        // Утверждение: a[0] < x && x <= a[n-1]
        int beg = 0; int end = n-1;
        while (end-beg > 1) {
            // Инвариант: a[beg] < x && x <= a[end]
            int c = (beg + end) / 2;
            if (a[c] < x) {
                beg = c;
            } else if (a[c] > x) {
                end = c;
            } else {
                // Утверждение: x == a[c]
                *idx = c;
                return true;
            }
        }
        *idx = end;
        return (x >= a[end]);
        . . .

Пусть значение x содержится в массиве
в нескольких экземплярах. Индекс какого элемента
массива a будет записан в переменную *idx?

                            
                                                                                                    
                                        (1) 
    Индекс первого элемента, равного
    x.
                                        
                                                                    
                                        (2) 
    Индекс поcледнего элемента, равного
    x.
                                        
                                                                    
                                        (3) 
    Может быть записан индекс любого элемента
    массива a, равного
    x.
                                        
                                                                    
                                        (4) 
    Индекс первого элемента, равного
    x+1.
                                        
                                                                    
                                        (5) 
    Индекс поcледнего элемента, равного
    x-1.
                                        
                                                            
                        
                                            
                            
Массив длины 5 содержит элементы
5, 4, 1, 2, 3 в указанном порядке.
К нему применяется
алгоритм сортировки методом прямого выбора,
использующий сравнение элементов с помощью функции compare
и обмен элементов с помощью функции swap.
Сколько раз будет вызвана функция swap?

                            
                                                                                                    
                                        (1) 
    2 раза
                                        
                                                                    
                                        (2) 
    3 раза
                                        
                                                                    
                                        (3) 
    4 раза
                                        
                                                                    
                                        (4) 
    5 раз
                                        
                                                            
                        
                                            
                            
Алгоритм  быстрой сортировки реализован с помощью комбинированной
схемы, использующей рекурсию и цикл 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?
Дайте наиболее точную оценку снизу этого числа.

                            
                                                                                                    
                                        (1) 
    Не менее 5 раз.
                                        
                                                                    
                                        (2) 
    Не менее 7 раз.
                                        
                                                                    
                                        (3) 
    Не менее 15 раз.
                                        
                                                                    
                                        (4) 
    Не менее 31 раза.
                                        
                                                            
                        
                                            
                            
Пусть целочисленный массив содержит элементы
14, 20, 25, 15, 12, 22, 18
в указанном порядке. Услове пирамиды нарушается
только для элемента 14, стоящего в вершине пирамиды.
Для исправления пирамиды выполняется процедура просеивания,
при которой элемент 14 опускается на свое место.
Каким будет содержимое массива после окончания этой процедуры?

                            
                                                                                                    
                                        (1) 
    25, 20, 14, 15, 12, 22, 18.
                                        
                                                                    
                                        (2) 
    25, 20, 22, 15, 12, 14, 18.
                                        
                                                                    
                                        (3) 
    25, 15, 22, 14, 12, 20, 18.
                                        
                                                                    
                                        (4) 
    25, 20, 14, 14, 15, 22, 18.
                                        
                                                                    
                                        (5) 
    25, 15, 20, 14, 12, 22, 18.
                                        
                                                            
                        
                                                                                
                            
Сколько раз будет выполнено тело цикла в приведенной
ниже программе? Многоточием обозначен фрагмент,
не содержащий переменной x.

int x = 100;
while (x >= 0) {
    . . .
    x = x-1;
}


                            
                                                                                                    
                                        101                                    
                                                            
                        
                                            
                            
Функция merge слияния двух упорядоченных массивов
применяется к двум массивам длины 100 и 1000. Какое максимальное
число сравнений может быть сделано при выполнении этой функции?

                            
                                                                                                    
                                        (1) 
    100
                                        
                                                                    
                                        (2) 
    1000
                                        
                                                                    
                                        (3) 
    1099
                                        
                                                                    
                                        (4) 
    1100
                                        
                                                            
                        
                                            
                            
К массиву a длины 12 применяется восходящая схема
двунаправленного алгоритма сортировки
слиянием с использованием дополнительной памяти
такого же размера. Сколько раз будет вызвана
функция слияния двух упорядоченных массивов merge?

                            
                                                                                                    
                                        (1) 
    8 раз
                                        
                                                                    
                                        (2) 
    9 раз
                                        
                                                                    
                                        (3) 
    10 раз
                                        
                                                                    
                                        (4) 
    11 раз
                                        
                                                            
                        
                                            
                            
Дан массив длины n, содержащий
элементы некоторого упорядоченного типа (их можно
сравнивать между собой, определяя,
какой из них больше или их равенство).
Требуется удалить из массива повторяющиеся элементы так,
чтобы каждый элемент содержался в массиве ровно 1 раз
(при этом n может уменьшиться).
Приведите асимптотическую
оценку времени работы наилучшего алгоритма, решающего данную
задачу.

                            
                                                                                                    
                                        (1) 
    t = O(n)
                                        
                                                                    
                                        (2) 
    t = O(n log₂n)
                                        
                                                                    
                                        (3) 
    t = O(n²)
                                        
                                                                    
                                        (4) 
    t = O(n³)
                                        
                                                                    
                                        (5) 
    t = O(log₂n)
                                        
                                                            
                        
                                            
                            
Рассмотрим следующую запись числа
в двоичной системе счисления
(для удобства запись разбита запятыми на четверки):
1000,1010,0010,0110,1111,0101,0011.
Укажите шестнадцатеричную запись этого числа.

                            
                                                                                                    
                                        (1) 
    4C26F73.
                                        
                                                                    
                                        (2) 
    8A26F53.
                                        
                                                                    
                                        (3) 
    4B28F53.
                                        
                                                            
                        
                                            
                            
Двоичный код, представляющий число типа double,
хранит знак, смещенный порядок и дробную часть
двоичного представления мантиссы. Сколько битов
отводится под каждый элемент представления?

                            
                                                                                                    
                                        (1) 
    Знак 1 бит, смещенный порядок 8 битов,
    дробная часть мантиссы 55 битов.
                                        
                                                                    
                                        (2) 
    Знак 1 бит, смещенный порядок 10 битов,
    дробная часть мантиссы 53 бита.
                                        
                                                                    
                                        (3) 
    Знак 1 бит, смещенный порядок 11 битов,
    дробная часть мантиссы 52 бита.
                                        
                                                            
                        
                                            
                            
Функция arcsin(x) представляется рядом Тейлора:

    arcsin(x) = x +(1/2)x³/3 + (1/2)(3/4)x⁵/5 + (1/2)(3/4)(5/6)x⁷/7 + ...

Этот ряд сходится лишь для значений x, по модулю меньших
единицы, причем вблизи единицы сходится очень медленно и 
точность его вычисления низка. Поэтому эффективно вычислять 
сумму ряда можно лишь для x, по модулю
существенно меньших единицы - например, |x|<0.75. 
Каким свойством функции arcsin можно воспользоваться,
чтобы свести ее вычисление к суммированию ряда для значеий
x в интервале |x|<0.75? Укажите все
возможные правильные решения из числа перечисленных ниже.
(Предполагается, что мы умеем быстро и точно вычислять квадратный корень
sqrt(z), а также знаем константу pi.)

                            
                                                                                                    
                                        (1) 
    Воспользоваться нечетностью функции arcsin,
    сводящей ее вычисление к положительным значениям x.
    Для положительных значений x0.7 вычислить
    сумму указанного ряда.
    Для положительных значений x>0.7 воспользоваться
    формулой

    arcsin(x) = pi/2 - arcsin(sqrt(1 - x*x))

    которая сводит задачу к вычислению ряда 
    для значения y=sqrt(1-x*x).
                                        
                                                                    
                                        (2) 
    Свести вычисление функции arcsin к вычислению
    функции arctg, воспользовавшись формулой

    arcsin(x) = 2*arсtg( x / (1 + sqrt(1 - x*x)) ).

                                        
                                                                    
                                        (3) 
    При x = ±1 значение 
    arcsin(x) = ±pi/2. При других значениях x
    воспользоваться формулой

    arcsin(x) = arсtg(x / sqrt(1 - x*x))

    и для y=x/sqrt(1-x*x) 
    вычислить сумму ряда Тейлора функции arctg:

    arctg(y) = y - y³/3 + y⁵/5 - y⁷/7 + ...

                                        
                                                            
                        
                                            
                            
Камень, отпущенный с высоты 6-го этажа, падает на землю
примерно за 2 сек. За какое примерно время упадет камень с высоты
12-го этажа (в 2 раза большей)? Сопротивлением воздуха пренебречь.

                            
                                                                                                    
                                        (1) 
    2.4 секунды
                                        
                                                                    
                                        (2) 
    2.8 секунды
                                        
                                                                    
                                        (3) 
    3.2 секунды
                                        
                                                                    
                                        (4) 
    4.0 секунды
                                        
                                                            
                        
                                            
                            
Чему равен ранг следующей матрицы:

1  1  1  1
1 -1  1 -1
1  1 -1 -1


                            
                                                                                                    
                                        (1) 
    ранг равен 1
                                        
                                                                    
                                        (2) 
    ранг равен 2
                                        
                                                                    
                                        (3) 
    ранг равен 3
                                        
                                                                    
                                        (4) 
    ранг равен 4
                                        
                                                            
                        
                                            
                            
Пусть f(x) - гладкая функция,
заданная на отрезке [a, b], вторая производная которой
по абсолютной величине не превышает некоторой константы.
Для приближенного вычисления интеграла от этой функции мы
применяем формулу трапеций, разбивая отрезок
[a, b] на n равных частей.
Какова точность вычисления интеграла в зависимости от n?

                            
                                                                                                    
                                        (1) 
    O(1/n).
                                        
                                                                    
                                        (2) 
    O((1/n)²).
                                        
                                                                    
                                        (3) 
    O((1/n)³).
                                        
                                                                    
                                        (4) 
    O((1/n)⁴).
                                        
                                                            
                        
                                            
                            
Сколько различных значений x
типа int удовлетворяют равенству
x+x == 0?

                            
                                                                                                    
                                        (1) 
    одно
                                        
                                                                    
                                        (2) 
    4
                                        
                                                                    
                                        (3) 
    2
                                        
                                                                    
                                        (4) 
    8
                                        
                                                                    
                                        (5) 
    16
                                        
                                                            
                        
                                            
                            
Пусть переменные p, q 
описаны следующим образом:

    double *p, q[100];

Отметьте, какие из перечисленных ниже выражений языка C/C++
являются корректными:

                            
                                                                                                    
                                        (1) 
    *(p+2)-*q
                                        
                                                                    
                                        (2) 
    p[10]*q[10]
                                        
                                                                    
                                        (3) 
    *p-*(q+20)
                                        
                                                                    
                                        (4) 
    *p+*q[0]
                                        
                                                            
                        
                                            
                            
Рассмотрим следующий фрагмент программы на С++:

    static double *p = 0;
    . . .
    p = new double[100];
    *p = 1.5;

Где хранится значение выражения "*p" (т.е.
число 1.5)?

                            
                                                                                                    
                                        (1) 
    В статической памяти.
                                        
                                                                    
                                        (2) 
    В динамической памяти.
                                        
                                                                    
                                        (3) 
    В стеке.
                                        
                                                            
                        
                                            
                            
Эквивалентны ли в языке C/C++ типы 
Matrix и Transform,
заданные в приведенном ниже фрагменте программы?

typedef double Matrix[3][3];
typedef double Transform[3][3];


                            
                                                                                                    
                                        (1) 
    Эквивалентны.
                                        
                                                                    
                                        (2) 
    Не эквивалентны.
                                        
                                                            
                        
                                            
                            
Функция F последовательности цифр в десятичной записи числа
n ставит в соответстие единицу, если n делится на 15,
и ноль в противном случае. Какая из перечисленных
ниже функций на последовательности десятичных цифр числа n
является индуктивным расширением функции F?

                            
                                                                                                    
                                        (1) 
    Две последних цифры числа n.
                                        
                                                                    
                                        (2) 
    Остаток от деления числа n на 231.
                                        
                                                                    
                                        (3) 
    Пара (остаток от деления числа n на 20,
    остаток от деления числа n на 24).
                                        
                                                                    
                                        (4) 
    Пара (остаток от деления числа n на 100,
    остаток от деления числа n на 35).
                                        
                                                            
                        
                                            
                            
Какое утверждение является инвариантом для следующего
фрагмента программы (т.е. из справедливости утверждения
до выполнения фрагмента программы вытекает справедливость утверждения
после выполнения)? Предполагается, что n > 0.

    double r, x; int n;
    . . .
    r *= -x;
    r *= n/(n+1);
    ++n;


                            
                                                                                                    
                                        (1) 
    Утверждение
    r == (-1)ⁿ*xⁿ/n!,
    где восклицательным знаком обозначен факториал числа n.
                                        
                                                                    
                                        (2) 
    Утверждение
    r == (-1)^n-1*xⁿ/n.
                                        
                                                                    
                                        (3) 
    Утверждение
    r == (-1)ⁿ⁺¹*xⁿ/n!,
    где восклицательным знаком обозначен факториал числа n.
                                        
                                                                    
                                        (4) 
    Утверждение
    r == (-1)ⁿ⁺¹*xⁿ/n.
                                        
                                                            
                        
                                            
                            
Пусть элементы массива a
нестрого возрастают (соседние элементы могут быть равными).
Дано произвольное значение x, требуется
найти минимальный индекс i такой, что
a[i] >= x. Используется идея алгоритма
бинарного поиска. Каким должен быть инвариант цикла,
в котором рассматривается основной случай после отбрасывания
исключительных ситуаций?
(Условие завершения цикла
end == beg+1.)

                            
                                                                                                    
                                        (1) 
    a[beg] < x <= a[end],
    ответ в переменной end.
                                        
                                                                    
                                        (2) 
    a[beg] <= x < a[end],
    ответ в переменной beg.
                                        
                                                                    
                                        (3) 
    a[beg] < x <= a[end],
    ответ в переменной beg.
                                        
                                                            
                        
                                            
                            
Для конкретного массива длины 1000 применяются
алгоритмы пузырьковой сортировки и сортировки
методом прямого выбора. Какой из этих двух
алгоритмов работает быстрее?

                            
                                                                                                    
                                        (1) 
    Пузырьковая сортировка.
                                        
                                                                    
                                        (2) 
    Сортировка методом прямого выбора.
                                        
                                                                    
                                        (3) 
    Возможны оба варианта в зависимости от содержания массива
    (для каких-то массивов быстрее пузырьковая сортировка,
    для других - сортировка прямым выбором).
                                        
                                                            
                        
                                            
                            
Алгоритм быстрой сортировки упорядочивает случайный массив
из тысячи элементов в среднем за 0.01 секунду. За какое примерно
время тот же алгоритм упорядочит случайный массив
из миллиона элементов?

                            
                                                                                                    
                                        (1) 
    За 10 секунд
                                        
                                                                    
                                        (2) 
    За 20 секунд
                                        
                                                                    
                                        (3) 
    За 1 минуту 40 секунд
                                        
                                                                    
                                        (4) 
    За 30 секунд
                                        
                                                                    
                                        (5) 
    За 1 минуту 20 секунд
                                        
                                                            
                        
                                            
                            
К целочисленному массиву применяется алгоритм сортировки
кучей. Пусть после первого этапа алгоритма пирамида
(бинарная куча) уже построена и массив содержит элементы
20, 17, 12, 2, 10, 4, 8
в указанном порядке. Затем выполняется второй этап сортировки.
На его первом шаге начальный и конечный элементы массива
меняются местами, от пирамиды отрезается правая нижняя ветка
(т.е. последний элемент массива), затем элемент в вершине
пирамиды просеивается, благодаря чему восстанавливается
условие пирамиды. Каким будет содержимое массива по
окончании этого шага?

                            
                                                                                                    
                                        (1) 
    17, 10, 12, 2, 4, 8, 20.
                                        
                                                                    
                                        (2) 
    17, 12, 10, 2, 8, 4, 20.
                                        
                                                                    
                                        (3) 
    17, 10, 12, 2, 8, 4, 20.
                                        
                                                                    
                                        (4) 
    17, 2, 10, 12, 8, 4, 20.
                                        
                                                                    
                                        (5) 
    17, 10, 12, 20, 8, 4, 2.
                                        
                                                            
                        
                                                                                
                            
Пусть a = a(x) -
некоторое условие, зависящее только от
значения переменной x.
Укажите, чему может быть равно значение переменной y
в результате выполнения следующего фрагмента программы:

int x = 1;
int y = 1;
while (a(x)) {
    . . .
    if (y < 0) {
        x = 2;
        y = 10;
    } else {
        x = 1;
        y = 20;
    }
}


                            
                                                                                                    
                                        (1) 
    Значение y равно 1 или 10.
                                        
                                                                    
                                        (2) 
    Значение y равно 1 или 20.
                                        
                                                                    
                                        (3) 
    Значение y может быть равным любому из чисел
    1, 10, 20.
                                        
                                                                    
                                        (4) 
    Значение y не может быть равным любому из чисел
    1, 10, 20.
                                        
                                                            
                        
                                            
                            
Рассмотрим алгоритм сортировки слиянием с использованием
дополнительной памяти. Используется восходящая
схема реализации алгоритма. Алгоритм применяется к массиву
длины 100. На каждом шаге сливаются пары
соседних упорядоченных подмассивов длины
не больше k и получаются упорядоченные подмассивы
длины не больше 2k; первый шаг выполняется при
k=1.
Сколько всего шагов будет выполнено?

                            
                                                                                                    
                                        (1) 
    5
                                        
                                                                    
                                        (2) 
    6
                                        
                                                                    
                                        (3) 
    7
                                        
                                                                    
                                        (4) 
    8
                                        
                                                            
                        
                                            
                            
В алгоритме сортировки слиянием "In Place Merge Sort",
не использующем дополнительной памяти,
применяется функция mergeBlocks
слияния двух упорядоченных блоков, т.е. подмассивов длины
m и n, реализованная рекурсивно.
За какое время работает эта функция?

                            
                                                                                                    
                                        (1) 
    t=O(n+m)
                                        
                                                                    
                                        (2) 
    t=O((n+m)log₂(n+m))
                                        
                                                                    
                                        (3) 
    t=O((n+m)log²₂(n+m))
                                        
                                                                    
                                        (4) 
    t=O((n)log₂(m))
                                        
                                                                    
                                        (5) 
    t=O((m)log₂(n))
                                        
                                                            
                        
                                            
                            
На 3 вакансии имеется 10 претендентов.
Сколько способов выбора возможно?

                            
                                                                                                    
                                        120                                    
                                                            
                        
                                            
                            
Рассмотрим максимальное по абсолютной величине
целое число, которое в языке C/C++ представимо
типом signed char.
Чему оно равно?

                            
                                                                                                    
                                        (1) 
    -128.
                                        
                                                                    
                                        (2) 
    127.
                                        
                                                                    
                                        (3) 
    128.
                                        
                                                                    
                                        (4) 
    255.
                                        
                                                            
                        
                                            
                            
Двоичный код, представляющий число типа float,
хранит знак, смещенный порядок и дробную часть
двоичного представления мантиссы.
Чему равен смещенный порядок в представлении числа 9.0?

                            
                                                                                                    
                                        (1) 
    127.
                                        
                                                                    
                                        (2) 
    128.
                                        
                                                                    
                                        (3) 
    129.
                                        
                                                                    
                                        (4) 
    130.
                                        
                                                            
                        
                                            
                            
Функция с прототипом

double root(double a, double b, double eps);

находит корень фиксированной функции

double f(double x);

на отрезке [a, b] методом деления отрезка пополам
с точностью eps.
Пусть функция f(x) определена следующим
образом:

double f(double x) {
    return sin(x);
}

Каким будет приблизительное значение переменной x
в результате выполнения следующего фрагмента программы:

    double x = root(-1., 9., 0.000001);


                            
                                                                                                    
                                        (1) 
    Значение x примерно равно 0.
                                        
                                                                    
                                        (2) 
    Значение x примерно равно 3.141593
                                        
                                                                    
                                        (3) 
    Значение x примерно равно 6.283185
                                        
                                                                    
                                        (4) 
    Значение x примерно равно 1.570796
                                        
                                                            
                        
                                            
                            
Какое максимальное число операций деления может
быть выполнено в алгоритме Гаусса в процессе приведения
к ступенчатому виду квадратной матрицы размера
4?

                            
                                                                                                    
                                        (1) 
    5 операций деления
                                        
                                                                    
                                        (2) 
    6 операций деления
                                        
                                                                    
                                        (3) 
    7 операций деления
                                        
                                                                    
                                        (4) 
    8 операций деления
                                        
                                                            
                        
                                            
                            
Пусть функция
f(x) = p*x² + q*x + r
(многочлен степени 2) задана на отрезке [a, b].
Пусть отрезок [a, b] разделен на 4 равных части;
обозначим концы этих отрезков через
x₀, x₁,
x₂, x₃, x₄:

    h = (b-a)/4, x_i = a+i*h, i = 0,1,2,3,4.

Обозначим

    y_i = f(x_i).

Чему равен интеграл функции f(x)
по отрезку [a, b]? Отметьте все правильные ответы.

                            
                                                                                                    
                                        (1) 
    1/4 * (y₀ + 2*y₂ + y₄) * (b - a).
                                        
                                                                    
                                        (2) 
    1/6 * (y₀ + 4*y₂ + y₄) * (b - a).
                                        
                                                                    
                                        (3) 
    1/12 * (y₀ + 4*y₁ + 2*y₂ + 4*y₃ + y₄) * (b - a).
                                        
                                                            
                        
                                            
                            
Среди перечисленных ниже чисел отметьте простые.

                            
                                                                                                    
                                        (1) 
    101
                                        
                                                                    
                                        (2) 
    103
                                        
                                                                    
                                        (3) 
    117
                                        
                                                                    
                                        (4) 
    131
                                        
                                                                    
                                        (5) 
    153
                                        
                                                                    
                                        (6) 
    169
                                        
                                                            
                        
                                            
                            
Какой из перечисленных ниже регистров процессора содержит
адрес команды, которая будет выполнятся на очередном
шаге работы процессора?

                            
                                                                                                    
                                        (1) 
    Регистр FP (в процессоре Intel 80x86 он обозначается как BP).
                                        
                                                                    
                                        (2) 
    Регистр SP.
                                        
                                                                    
                                        (3) 
    Регистр флагов.
                                        
                                                                    
                                        (4) 
    Регистр PC (в процессоре Intel 80x86 он обозначается как IP).
                                        
                                                                    
                                        (5) 
    Регистр R0 (в процессоре Intel 80x86 он обозначается как AX).
                                        
                                                            
                        
                                            
                            
Среди указанных ниже операторов языка C/C++
отметьте корректные.

                            
                                                                                                    
                                        (1) 
    int x = new int;
                                        
                                                                    
                                        (2) 
    int* x = new int(1000);
                                        
                                                                    
                                        (3) 
    int* x = new int[1000];
                                        
                                                                    
                                        (4) 
    int* x = (int *) malloc(1000 * sizeof(int));
                                        
                                                            
                        
                                            
                            
Назовем функцию y = f(p) на последовательности p 
элементов некоторого типа индуктивной, если при добавлении в конец
последовательности p
еще одного элемента x новое значение функции
y1 = f(p&x) можно вычислить, зная только
старое значение y и добавленный элемент x.
Среди перечисленных ниже функций на последовательностях вещественных
чисел укажите индуктивные.

                            
                                                                                                    
                                        (1) 
    Сумма элементов последовательности.
                                        
                                                                    
                                        (2) 
    Среднее арифметическое значение элементов последовательности.
                                        
                                                                    
                                        (3) 
    Значение минимального элемента последовательности.
                                        
                                                                    
                                        (4) 
    Разность между максимальным и минимальным элементами последовательности.
                                        
                                                                    
                                        (5) 
    Значение многочлена в фиксированной точке t=2,
    коэффициенты многочлена заданы в последовательности 
    p = {a₀, a₁, a₂, ..., a_n}
    по убыванию степеней:
    
y = a₀*tⁿ + a₁*t^n-1 + ... + a_n
    
                                        
                                                            
                        
                                            
                            
Сколько в сумме операций сложения и умножения
будет выполнено при вычислении
значения многочлена степени 3, коэффициенты которого
заданы в последовательности по убыванию степеней,
при использовании схемы вычисления индуктивной функции?

                            
                                                                                                    
                                        (1) 
    6
                                        
                                                                    
                                        (2) 
    8
                                        
                                                                    
                                        (3) 
    9
                                        
                                                                    
                                        (4) 
    7
                                        
                                                            
                        
                                            
                            
Оценить сверху время работы (т.е. количество
выполнений тела цикла) алгоритма быстрого возведения в степень:

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;
}


                            
                                                                                                    
                                        (1) 
    Время работы не больше, чем
    C*n,
    где C - некоторая константа
    (т.е. время пропорционально числу n).
                                        
                                                                    
                                        (2) 
    Время работы не больше, чем
    C*log₂ n,
    где C - некоторая константа
    (т.е. время пропорционально количеству цифр в двоичной или
    десятичной записи числа n).
                                        
                                                                    
                                        (3) 
    Время работы не больше, чем
    C*r, где C - некоторая константа,
    r - квадратный корень из числа n
    (т.е. время пропорционально квадратному корню из n).
                                        
                                                            
                        
                                            
                            
Программа, использующая бинарный поиск, ищет
элемент в массиве длины миллион в среднем за
одну тысячную секунды. Сколько примерно времени
потребуется на поиск, если мы заменим алгоритм поиска
с бинарного на последовательный?

                            
                                                                                                    
                                        (1) 
    5 секунд
                                        
                                                                    
                                        (2) 
    20 секунд
                                        
                                                                    
                                        (3) 
    50 секунд
                                        
                                                                    
                                        (4) 
    10 секунд
                                        
                                                                    
                                        (5) 
    40 секунд
                                        
                                                            
                        
                                            
                            
Есть 4 монеты, известно, что все они имеют различные веса.
Веса двух монет можно сравнить, используя весы-коромысло.
Какое минимальное количество взвешиваний во всех случаях достаточно,
чтобы упорядочить монеты по возрастанию их веса?

                            
                                                                                                    
                                        (1) 
    4 взвешивания
                                        
                                                                    
                                        (2) 
    5 взвешиваний
                                        
                                                                    
                                        (3) 
    6 взвешиваний
                                        
                                                                    
                                        (4) 
    3 взвешивания
                                        
                                                                    
                                        (5) 
    2 взвешивания
                                        
                                                            
                        
                                            
                            
Алгоритм быстрой сортировки реализован с помощью комбинированной
схемы, использующей рекурсию и цикл while;
рекурсия применяется лишь к меньшему сегменту массива,
разделенного на части функцией partition.
Алгоритм применяется к массиву размером миллион. Может ли
глубина рекурсии равняться 30?

                            
                                                                                                    
                                        (1) 
    Может.
                                        
                                                                    
                                        (2) 
    Не может.
                                        
                                                            
                        
                                            
                            
К целочисленному массиву применяется алгоритм сортировки
кучей. На первом этапе из элементов массива строится
пирамида (бинарная куча) путем просеивания элементов
по бинарному дереву в порядке справа налево и снизу вверх.
Пусть вначале массив содержал элементы
4, 5, 6, 7, 1, 2, 3
в указанном порядке.
Каким будет содержимое массива
после построения пирамиды?

                            
                                                                                                    
                                        (1) 
    7, 6, 4, 5, 1, 2, 3.
                                        
                                                                    
                                        (2) 
    7, 6, 5, 4, 1, 2, 3.
                                        
                                                                    
                                        (3) 
    7, 5, 6, 4, 1, 2, 3.
                                        
                                                                    
                                        (4) 
    7, 6, 5, 4, 3, 2, 1.
                                        
                                                                    
                                        (5) 
    7, 5, 6, 4, 3, 2, 1.
                                        
                                                            
                        
                                                                                
                            
Чему равно значение целочисленной переменной x
в результате выполнения приведенного ниже фрагмента программы?

    int x = 64;
    while (x*x > 100) {
        x = -(x / 2);
    }


                            
                                                                                                    
                                        -8                                    
                                                            
                        
                                            
                            
В алгоритме сортировки слиянием "In Place Merge Sort",
не использующем дополнительной памяти, применяется
функция mergeBlocks
слияния двух упорядоченных блоков, т.е. подмассивов длины
m и n, реализованная рекурсивно.
Пусть сумма длин блоков m+n=1000. Какой может быть
максимальная суммарная длина блоков при рекурсивном вызове
функции mergeBlocks на первом шаге?

                            
                                                                                                    
                                        (1) 
    250
                                        
                                                                    
                                        (2) 
    500
                                        
                                                                    
                                        (3) 
    750
                                        
                                                                    
                                        (4) 
    1000
                                        
                                                                    
                                        (5) 
    1500
                                        
                                                            
                        
                                            
                            
В алгоритме сортировки слиянием "In Place Merge Sort",
не использующем дополнительной памяти, применяется
функция mergeBlocks
слияния двух упорядоченных блоков, т.е. подмассивов длины
m и n, реализованная рекурсивно.
Пусть сумма длин блоков m+n=512.
При реализации функции mergeBlocks
вызывается функция перестановки двух блоков
swapBlocks. Какой может быть
максимальная суммарная длина блоков переставляемых блоков?

                            
                                                                                                    
                                        (1) 
    192
                                        
                                                                    
                                        (2) 
    256
                                        
                                                                    
                                        (3) 
    384
                                        
                                                                    
                                        (4) 
    128
                                        
                                                                    
                                        (5) 
    512
                                        
                                                            
                        
                                            
                            
При вычислении (x+y)⁷
раскрываются скобки и приводятся подобные члены.
Чему будет равен коэффициент при
x³y⁴?

                            
                                                                                                    
                                        35                                    
                                                            
                        
                                            
                            
Какой двоичный код представляет
число -31 для типа short?
(Для удобства двоичная запись разбита запятыми на четверки.)

                            
                                                                                                    
                                        (1) 
    1111,1111,1100,0001.
                                        
                                                                    
                                        (2) 
    1111,1111,1101,1111.
                                        
                                                                    
                                        (3) 
    1111,1111,1110,0001.
                                        
                                                            
                        
                                            
                            
Двоичный код, представляющий число типа double,
хранит знак, смещенный порядок и дробную часть
двоичного представления мантиссы.
Сколько единичных битов в двоичном представлении
дробной части мантиссы для числа 0.125?

                            
                                                                                                    
                                        (1) 
    0.
                                        
                                                                    
                                        (2) 
    1.
                                        
                                                                    
                                        (3) 
    2.
                                        
                                                                    
                                        (4) 
    3.
                                        
                                                            
                        
                                            
                            
Сколько раз в алгоритме Гаусса будет выполнена операция
перестановки местами двух строк
(с изменением знака одной из них) при приведении к
ступенчатому виду следующей матрицы:

1  2  3  4
0  1  2  3
2  7 10 14


                            
                                                                                                    
                                        (1) 
    1 раз
                                        
                                                                    
                                        (2) 
    2 раза
                                        
                                                                    
                                        (3) 
    3 раза
                                        
                                                                    
                                        (4) 
    4 раза
                                        
                                                            
                        
                                            
                            
Какие переменные располагаются в языке C/C++ в стеке?

                            
                                                                                                    
                                        (1) 
    Локальные переменные функций, а также их аргументы.
                                        
                                                                    
                                        (2) 
    Глобальные и статические переменные.
                                        
                                                                    
                                        (3) 
    Объекты, которые создаются с помощью оператора new.
                                        
                                                                    
                                        (4) 
    Таких переменных нет.
                                        
                                                            
                        
                                            
                            
Пусть процессор имеет 32-разрядную архитектуру
и в некоторый момент его работы регистр SP содержит значение
1000. Укажите, какое значение будет содержаться в SP
после выполнения команды pop X.

                            
                                                                                                    
                                        (1) 
    1001
                                        
                                                                    
                                        (2) 
    1004
                                        
                                                                    
                                        (3) 
    999
                                        
                                                                    
                                        (4) 
    996
                                        
                                                            
                        
                                            
                            
Следующий фрагмент программы для последовательности
вещественных чисел вычисляет количество n элементов,
строго больших предыдущего, причем самый первый элемент не
учитывается (не считается больше предыдущего).
Например, для последовательности
{2, 1, 3, 5} ответ n=2
(элементы 3 и 5).

n = 0
x0 = ...

цикл пока в последовательности есть непрочитанные элементы
|выполнять
|  прочесть очередной элемент посл-ти в <вых: x>
|  если x > x0
|  | то n = n + 1
|  конец если
|  x0 = x
конец цикла

Каким значением надо инициализировать переменную
x0, чтобы программа работала правильно?

                            
                                                                                                    
                                        (1) 
    x0 = минус бесконечность
                                        
                                                                    
                                        (2) 
    x0 = плюс бесконечность
                                        
                                                                    
                                        (3) 
    x0 = 0
                                        
                                                                    
                                        (4) 
    x0 = 1
                                        
                                                            
                        
                                            
                            
Пусть w - последовательность
целых чисел, F(W) - максимальная из
сумм нескольких подряд идущих элементов
последовательности w.
Например, для последовательности
w={1, -2, 3, 4, -1, 5, -2, -3, 4}
максимальную сумму образуют элементы с третьего по шестой:
F(w)=3+4-1+5=11.
Какие из перечисленных ниже функций
являются индуктивным расширением функции F?
Укажите все правильные варианты.

                            
                                                                                                    
                                        (1) 
    Пара
    (максимальная из сумм непрерывных
    отрезков последовательности w;

    максимальная из сумм отрезков последовательности w,
    заканчивающихся в конце w).
                                        
                                                                    
                                        (2) 
    Пара
    (максимальная из сумм непрерывных
    отрезков последовательности w;

    сумма положительных элементов в конце последовательности w).
                                        
                                                                    
                                        (3) 
    Пара
    (минимальная из сумм непрерывных
    отрезков последовательности w;

    сумма положительных элементов в конце последовательности w).
                                        
                                                                    
                                        (4) 
    Пара
    (максимальная из сумм непрерывных
    отрезков последовательности w;

    сумма отрицательных элементов в конце последовательности w).
                                        
                                                            
                        
                                            
                            
Пусть 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]


                            
                                                                                                    
                                        (1) 
    Ошибки нет, фрагмент программы корректный.
                                        
                                                                    
                                        (2) 
    Фрагмент программы содержит ошибку.
                                        
                                                            
                        
                                            
                            
Оцените примерно, во сколько раз алгоритм бинарного поиска
работает быстрее алгоритма последовательного поиска
для массива из 64 миллионов элементов.

                            
                                                                                                    
                                        (1) 
    Примерно в 500 тысяч раз.
                                        
                                                                    
                                        (2) 
    Примерно в миллион раз.
                                        
                                                                    
                                        (3) 
    Примерно в 2.5 миллиона раз.
                                        
                                                                    
                                        (4) 
    Примерно в 3 миллиона раз.
                                        
                                                            
                        
                                            
                            
Алгоритм быстрой сортировки реализован с помощью комбинированной
схемы, использующей рекурсию и цикл while;
рекурсия применяется лишь к меньшему сегменту массива,
разделенного на части функцией partition.

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;
        }
    }
}

Алгоритм применяется к массиву размером 95. Какой может быть
максимальная глубина рекурсии?
(Под глубиной рекурсии мы подразумеваем количесто раз,
которое функция может вызвать сама себя в цепочке вызовов.
Если рекурсивный вызов отсутствует, то мы считаем глубину рекурсии
нулевой.)

                            
                                                                                                    
                                        5                                    
                                                            
                        
                                                                                
                            
Завершится ли когда-нибудь выполнение цикла
в приведенном ниже фрагменте программы?

    int x = 1;
    while (x != 120) {
        x = (x * 7) % 490;
    }


                            
                                                                                                    
                                        (1) 
    Завершится.
                                        
                                                                    
                                        (2) 
    Не завершится.
                                        
                                                            
                        
                                            
                            
Пусть n - переменная типа unsigned char.
Укажите значение n после выполнения оператора
n = ((127 >> 2) & (15 << 2));

                            
                                                                                                    
                                        (1) 
    12.
                                        
                                                                    
                                        (2) 
    24.
                                        
                                                                    
                                        (3) 
    28.
                                        
                                                                    
                                        (4) 
    48.
                                        
                                                                    
                                        (5) 
    60.
                                        
                                                            
                        
                                            
                            
Можно ли сохранить целое число

    123456789012345

в переменной типа double
без потери точности?

                            
                                                                                                    
                                        (1) 
    Можно.
                                        
                                                                    
                                        (2) 
    Нельзя.
                                        
                                                            
                        
                                            
                            
По логике задачи нам требуется использовать большой массив вещественных
чисел, размер которого не превышает миллион элементов. Какие из перечисленных
ниже решений являются корректными?

                            
                                                                                                    
                                        (1) 
    Используем описание

    double a[1000000];

в начале файла с программой, вне функций.
                                        
                                                                    
                                        (2) 
    Используем описание

    double a[1000000];

    в начале тела функции main.
                                        
                                                                    
                                        (3) 
    Используем описание

    double a[1000000];

    в начале тела той функции, которая работает с этим массивом.
                                        
                                                                    
                                        (4) 
    Создадим массив в динамической памяти
    с помощью строки 

    double* a = new double a[1000000];

    которая выполняется внутри тела фунции main.
                                        
                                                            
                        
                                            
                            
Пусть процессор имеет 32-разрядную архитектуру.
Рассмотрим функцию f(x, y) языка C/C++ со
следующим прототипом:

void f(int x, int y);

Чему равен адрес второго фактического аргумента
y функции f относительно регистра
FP (Frame Pointer - указатель кадра) во время выполнения
тела функции?

                            
                                                                                                    
                                        (1) 
    FP-4
                                        
                                                                    
                                        (2) 
    FP-8
                                        
                                                                    
                                        (3) 
    FP-12
                                        
                                                                    
                                        (4) 
    FP
                                        
                                                                    
                                        (5) 
    FP+4
                                        
                                                                    
                                        (6) 
    FP+8
                                        
                                                                    
                                        (7) 
    FP+12
                                        
                                                            
                        
                                            
                            
Последовательность вещественных чисел w
содержит коэффициенты многочлена по возрастанию степеней.
Функция F(w) равна значению второй производной
многочлена в фиксированной точке t=2. Среди
указанных ниже функций отметьте те, которые являются индуктивным
расширением функции F.

                            
                                                                                                    
                                        (1) 
    Тройка
    (значение многочлена в точке t;

    значение первой производной многочлена в точке t;

    значение второй производной многочлена в точке t).
                                        
                                                                    
                                        (2) 
    Пара
    (значение второй производной многочлена в точке t;

    степень многочлена).
                                        
                                                                    
                                        (3) 
    Тройка
    (значение многочлена в точке 0;

    значение первой производной многочлена в точке 0;

    значение второй производной многочлена в точке 0).
                                        
                                                                    
                                        (4) 
    Пара
    (значение второй производной многочлена в точке 0;

    степень многочлена).
                                        
                                                            
                        
                                                                                
                            
Рассмотрим следующий фрагмент программы на C/C++:

    double x = 1.0;
    double y = 1e-20;
    double z = x + y - x;
    double t = x - x + y;

Равны ли значения переменных
z и t после его выполнения?

                            
                                                                                                    
                                        (1) 
    Равны.
                                        
                                                                    
                                        (2) 
    Не равны.
                                        
                                                            
                        
                                            
                            
Пусть m=143. Существуют ли два различных целых числа
a, b такие, что 
a²b² (mod m), но 
a±b (mod m)?

                            
                                                                                                    
                                        (1) 
    Да, существуют.
                                        
                                                                    
                                        (2) 
    Нет, не существуют.
                                        
                                                            
                        
                                            
                            
Рассмотрим рекурсивную реализацию алгоритма Евклида:

int gcd1(int m, int n) {
    if (n == 0)
        return m;
    int r = m % n;
    return gcd1(n, r);
}

Укажите, какова будет глубина рекурсии (т.е. какое максимальное
количество кадров локальных переменных функции gcd1
будет размещено одновременно в аппаратном стеке) при следующем
вызове функции:

    int d = gcd1(7, 17);


                            
                                                                                                    
                                        (1) 
    2
                                        
                                                                    
                                        (2) 
    3
                                        
                                                                    
                                        (3) 
    4
                                        
                                                                    
                                        (4) 
    5
                                        
                                                            
                        
                                                
                        
                                                            
                            
Укажите корректные адреса машинных слов в 32-разрядной
архитектуре среди перечисленных ниже:

                            
                                                                                                    
                                        (1) 
    1000
                                        
                                                                    
                                        (2) 
    1022
                                        
                                                                    
                                        (3) 
    2147483644
                                        
                                                                    
                                        (4) 
    4000000000
                                        
                                                                    
                                        (5) 
    5000000000
                                        
                                                            
                        
                                            
                            
Алгоритм сортировки называется стабильным, если он
сохраняет относительный порядок равных элементов.
Среди перечисленных ниже алгоритмов сортировки
(имеются в виду их классические варианты) отметьте все стабильные.

                            
                                                                                                    
                                        (1) 
    Пузырьковая сортировка.
                                        
                                                                    
                                        (2) 
    Быстрая сортировка QuickSort.
                                        
                                                                    
                                        (3) 
    Сортировка кучей HeapSort.
                                        
                                                            
                        
                                            
                            
Сколько единиц в двоичной записи числа 11?

                            
                                                                                                    
                                        (1) 
    1.
                                        
                                                                    
                                        (2) 
    2.
                                        
                                                                    
                                        (3) 
    3.
                                        
                                                            
                        
                                            
                            
При представлении целых чисел в формате Big Endian
байты внутри слова нумеруются слева направо, в формате
Little Endian - справа налево. Пусть компьютер использует
архитектуру Big Endian. Укажите, чему будет равно значение
переменной n в результате выполнения
следующего фрагмента программы:

    int k = (-256); int n;
    signed char *p = (signed char *) &k;
    n = *p;


                            
                                                                                                    
                                        (1) 
    Значение n равно 0.
                                        
                                                                    
                                        (2) 
    Значение n равно -1.
                                        
                                                                    
                                        (3) 
    Значение n равно 255.
                                        
                                                                    
                                        (4) 
    Значение n равно -256.
                                        
                                                            
                        
                                            
                            
Рассмотрим следующую программу на C/C++:

#include <stdio.h>
#include <math.h>

int main() {
    double x = pow(2., 1022.)*2.;
    double y = pow(2., 1024.)/2.;
    if (x == y) {
        printf("x == y\n");
    } else {
        printf("x != y\n");
    }
    return 0;
}

(Функция pow(a, b) возводит
число a в степень b.)
Что будет напечатано в результате ее выполнения?

                            
                                                                                                    
                                        (1) 
    x == y.
                                        
                                                                    
                                        (2) 
    x != y.
                                        
                                                            
                        
                                            
                            
Какой самый первый объектно-ориентированный язык программирования?

                            
                                                                                                    
                                        (1) 
    Objective C
                                        
                                                                    
                                        (2) 
    Small Talk
                                        
                                                                    
                                        (3) 
    C++
                                        
                                                                    
                                        (4) 
    Java
                                        
                                                                    
                                        (5) 
    C#
                                        
                                                            
                        
                                            
                            
Рассмотрим следующий фрагмент программы на C++:

    int a[3][5];
    const int *p = &(a[1][1]);
    int n;
    for (int i = 0; i < 3; ++i) {
        for (int j = 0; j < 5; ++j) {
            a[i][j] = 10*i + j;
        }
    }
    n = p[6];

Чему равно значение n
после выполнения этого фрагмента?

                            
                                                                                                    
                                        (1) 
    n = 3
                                        
                                                                    
                                        (2) 
    n = 13
                                        
                                                                    
                                        (3) 
    n = 21
                                        
                                                                    
                                        (4) 
    n = 22
                                        
                                                            
                        
                                            
                            
Пусть 2 многочлена p(x) и q(x)
степени 4 принимают в четырех попарно различных узлах
x₀, x₁,
x₂, x₃ одни и те же
значения
y₀, y₁,
y₂, y₃. Следует ли из
этого, что многочлены p(x) и q(x)
равны?

                            
                                                                                                    
                                        (1) 
    Да, следует.
                                        
                                                                    
                                        (2) 
    Нет, не следует.
                                        
                                                            
                        
                                            
                            
Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел.
Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.
Программа должна содержать функцию, которая получает в качестве параметра имя файла  и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.
Задание: посчитать среднее гармоническое чисел из последовательности.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                            
                            
Постановка задачи: программа должна содержать функцию, которая получает в качестве параметров имя массива и его длину (или нескольких массивов, если этого требуют условия задачи) и выполняет необходимые действия.
При решении не разрешается создавать или резервировать в программе дополнительную память, соизмеримую по размерам с объемом исходных данных. То есть, нельзя создавать дополнительные массивы, если это явно не оговорено в задаче.
Функция main должна заполнить массив числами из файла. Для определения длины массива предусматривается два варианта: 1) по значению первого числа в файле, 2) непосредственным подсчетом количества чисел в файле. Результат также выводится в файл.
Задание: циклически сдвинуть элементы массива на одну позицию вправо.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                            
                            
Каков диапазон целочисленного типа short?

                            
                                                                                                    
                                        (1) 
    -128 ... 127
                                        
                                                                    
                                        (2) 
    0 ... 255
                                        
                                                                    
                                        (3) 
    0 ... 65535
                                        
                                                                    
                                        (4) 
    -32768 ... 32767
                                        
                                                            
                        
                                            
                            
Сколько раз будет выполнено тело цикла в алгоритме
Евклида

int gcd(int m, int n) {
    while (n != 0) {
        int r = m % n;
        m = n; n = r;
    }
    return m;
}

при следующих входных значениях аргументов:
m=17, n=22?

                            
                                                                                                    
                                        5                                    
                                                            
                        
                                            
                            
Пусть расположенный в статической памяти
целочисленный массив a описан как

static int a[] = {
    1, 1, 2, 2, 3, 3, 4, 4, 5, 5
};

Пусть в программе задана функция суммирования массива
с прототипом

int sum(const int *m, int n);

где m - константный указатель на начало
массива, n - число его элементов. Укажите,
чему будет равно значение переменной s в
результате выполнения следующего фрагмента программы:

    int s = sum(a+5, 3);


                            
                                                                                                    
                                        11                                    
                                                            
                        
                                            
                            
Какой объект описан в следующей строке программы
на C/C++?

    double a[20][30];


                            
                                                                                                    
                                        (1) 
    Массив из 20 элементов типа массив из 30 элементов
    типа double.
                                        
                                                                    
                                        (2) 
    Массив из 30 элементов типа массив из 20 элементов
    типа double.
                                        
                                                                    
                                        (3) 
    Указатель на первую переменную массива типа double.
                                        
                                                                    
                                        (4) 
    Указатель на массив из 20 элементов типа массив из 30 элементов
    типа double.
                                        
                                                            
                        
                                            
                            
Левым нейтральным элементом (левой единицей) для бинарной операции
 называется элемент e такой, что для всякого
другого элемента x "произведение" e на
x равно x:
e  x = x. Какие элементы будут нейтральными
для операций суммы и минимума чисел соответственно?

                            
                                                                                                    
                                        (1) 
    0, 0.
                                        
                                                                    
                                        (2) 
    0, +
                                        
                                                                    
                                        (3) 
    0, -
                                        
                                                                    
                                        (4) 
    -, +
                                        
                                                            
                        
                                            
                            
Укажите, в какие моменты работы программы выполняется
инвариант цикла.

                            
                                                                                                    
                                        (1) 
    Перед первым выполнением тела цикла и после
    последнего выполнения тела цикла.
                                        
                                                                    
                                        (2) 
    Перед каждым выполнением тела цикла.
                                        
                                                                    
                                        (3) 
    Перед каждым выполнением тела цикла и после
    каждого выполнения тела цикла.
                                        
                                                            
                        
                                            
                            
Массив a размера 4 содержит
элементы 4, 1, 3, 2 в указанном порядке.
К нему применяется алгоритм пузырьковой сортировки,
использующий сравнение элементов с помощью функции compare
и обмен элементов с помощью функции swap.
Сколько раз будет вызвана функция swap?

                            
                                                                                                    
                                        4                                    
                                                            
                        
                                            
                            
Пусть мы имеем набор из n элементов,
которые можно сравнивать
между собой. Их медианой называется такое
значение m, что число элементов набора,
меньших либо равных m,
равно числу элементов, больших либо равных m.
Существует ли алгоритм выбора медианы, который
работает за время O(n) (т.е. за время,
линейно зависящее от n)?

                            
                                                                                                    
                                        (1) 
    Да.
                                        
                                                                    
                                        (2) 
    Нет.
                                        
                                                            
                        
                                                                                
                            
В чем главный недостаток первоначальной версии языка Pascal?

                            
                                                                                                    
                                        (1) 
    Невозможность раздельной компиляции модулей.
                                        
                                                                    
                                        (2) 
    Неэффективность вызова процедур и функций из-за
    возможности их вложения друг в друга.
                                        
                                                            
                        
                                            
                            
К трехзначным десятичным числам (строкам длины 3 из десятичных
цифр) применяется алгоритм RADIX-сортировки сначала по младшей цифре,
затем по средней и в конце по старшей. Исходный массив содержит следующие
числа:

102, 232, 307, 901, 835, 215, 105, 301, 335, 811.

Каким будет содержимое массива после выполнения первых двух шагов
сортировки (т.е. после сортировки по младшей и средней цифрам)?

                            
                                                                                                    
                                        (1) 
    901, 301, 102, 105, 307, 811, 215, 232, 835, 335
                                        
                                                                    
                                        (2) 
    301, 901, 102, 105, 307, 811, 215, 232, 835, 335
                                        
                                                                    
                                        (3) 
    102, 301, 901, 105, 307, 811, 215, 232, 335, 835
                                        
                                                                    
                                        (4) 
    901, 301, 102, 105, 307, 811, 215, 232, 335, 835
                                        
                                                                    
                                        (5) 
    301, 901, 105, 102, 307, 811, 215, 232, 335, 835
                                        
                                                            
                        
                                            
                            
Для записи n-значных чисел в системе счисления с основанием
b требуется n разрядов,
каждый из которых может находиться
в b состояниях. Таким образом, суммарное число состояний
равно произведению n*b.
Рассмотрим восьмеричную (b=8), десятичную (b=10)
и шестнадцатеричную (b=16) системы счисления.
Какая из них наиболее экономна по суммарному числу состояний
для записи чисел в диапазоне 0..N,
где N - некоторое достаточно большое число?

                            
                                                                                                    
                                        (1) 
    Восьмеричная.
                                        
                                                                    
                                        (2) 
    Десятичная.
                                        
                                                                    
                                        (3) 
    Шестнадцатеричная.
                                        
                                                            
                        
                                            
                            
Пусть для представления вещественных чисел
мы используем десятичные целые числа с фиксированной позицией
десятичной точки, отделяющей ровно 3 знака дробной части.
Например, целое число 1414 представляет
вещественное число 1.414. Рассмотрим два числа
с фиксированной точкой, представленные целыми числами
100001 и 20050. Каким числом будет представлено их произведение?

                            
                                                                                                    
                                        (1) 
    20050.
                                        
                                                                    
                                        (2) 
    200502.
                                        
                                                                    
                                        (3) 
    2005020.
                                        
                                                                    
                                        (4) 
    200502005.
                                        
                                                            
                        
                                            
                            
Формула Бинома Ньютона дает следующее разложение в ряд
для функции "квадратный корень из z":

(1+x)^0.5 = sqrt(1+x) =
    1 + 0.5 x + 0.5(-0.5)/2! x² + 0.5(-0.5)(-1.5)/3! x³ + 0.5(-0.5)(-1.5)(-2.5)/4! x⁴ + ...

(мы обозначили z=1+x). 
Рассмотрим реализованную на C/C++ функцию mySqrt(z),
вычисляющую значение квадратного корня с точностью до одной миллионной:

static const double EPS = 1e-6;

double mySqrt(double z) {
    double x = z - 1.;
    double s = 1;
    double k = 0.5;
    double n = 1.;
    double a = k*x;
    while (fabs(a) > eps) {
        s += a;
        k -= 1.;
        n += 1.;
        a *= (k/n)*x;
    }
    return s;
}

Для каких значений z ее можно применять так,
чтобы функция завершала работу за разумное время и
ошибка вычисления результата была бы не более 0.0001?
Укажите все правильные ответы из числа перечисленных ниже.

                            
                                                                                                    
                                        (1) 
    Для небольших положительных значений z,
    например, 0<z<10.
                                        
                                                                    
                                        (2) 
    Для любых значений z в интервале
    0<z<2.
                                        
                                                                    
                                        (3) 
    Для z = 10^-10.
                                        
                                                                    
                                        (4) 
    Для z = 2.0001.
                                        
                                                                    
                                        (5) 
    Для z = 0.
                                        
                                                                    
                                        (6) 
    Для значений z в интервале
    0.1<z<1.9.
                                        
                                                            
                        
                                            
                            
Отметьте, в каких из трех конструкций цикла языка C
тело цикла может ни разу не выполняться.

                            
                                                                                                    
                                        (1) 
    Цикл while.
                                        
                                                                    
                                        (2) 
    Цикл for.
                                        
                                                                    
                                        (3) 
    Цикл do-while.
                                        
                                                            
                        
                                            
                            
Рассмотрим реализацию матрицы целых чисел,
размеры которой определяются
в процессе работы программы, через массив указателей на начало
строк, захватываемый в динамической памяти. Каждая строка
также представляет собой отдельный массив в
динамической памяти:

    typedef int* intptr;
    int m, n; // Размеры матрицы: число строк, столбцов
    . . .
    intptr* a = new intptr[m];
    for (int i = 0; i < m; ++i) {
        a[i] = new int[n];
    }
    // a[i][j] -- элемент i-й строки и j-го столбца

Сколько памяти требуется для хранения прямоугольной
матрицы размером в 10 строк и 20 столбцов
в 64-разрядной архитектуре
(без учета памяти, используемой под описатели фрагментов кучи;
предполагаем, что размер элемента типа int равен 4)?

                            
                                                                                                    
                                        (1) 
    800 байтов
                                        
                                                                    
                                        (2) 
    840 байтов
                                        
                                                                    
                                        (3) 
    880 байтов
                                        
                                                                    
                                        (4) 
    960 байтов
                                        
                                                            
                        
                                            
                            
Интерполяционный многочлен в форме Ньютона, построенный
по узлам
x₀, x₁, ..., x_n и
принимающий в этих узлах значения
y₀, y₁, ..., y_n,
представляется формулой

p_n(x) = a₀ + a₁(x-x₀) + a₁(x-x₀)(x-x₁) + ... + a_n(x-x₀)(x-x₁)...(x-x_n-1)

Пусть коэффициенты
a₀, a₁, ..., a_n
многочлена p_n(x)
уже вычислены. Мы добавляем новый узел x_n+1,
значение в котором должно быть равно y_n+1,
и строим новый многочлен Ньютона p_n+1(x)
на единицу большей степени по узлам
x₀, x₁, ..., x_n, x_n+1
и значениям
y₀, y₁, ..., y_n, y_n+1.
Сколько действий нужно выполнить, чтобы вычислить все
коэффициенты нового многочлена?

                            
                                                                                                    
                                        (1) 
    O(1).
                                        
                                                                    
                                        (2) 
    O(n).
                                        
                                                                    
                                        (3) 
    O(n²).
                                        
                                                                    
                                        (4) 
    O(n³).
                                        
                                                            
                        
                                            
                            
Отметьте, какие из перечисленных ниже целочисленных значений
помещаются в переменную типа unsigned short

                            
                                                                                                    
                                        (1) 
    10000
                                        
                                                                    
                                        (2) 
    30000
                                        
                                                                    
                                        (3) 
    50000
                                        
                                                                    
                                        (4) 
    100000
                                        
                                                                    
                                        (5) 
    1000000
                                        
                                                            
                        
                                            
                            
Укажите, чему будет равно значение переменной k
в результате выполнения следующего фрагмента программы:

    int n = (-5), k, *p;
    p = &n; --*p; k = 4-*p*5+n;


                            
                                                                                                    
                                        28                                    
                                                            
                        
                                            
                            
Пусть переменные a, p,
q, n описаны следующим образом:

    double a[10]; double *p;
    const double *q; int n;

Отметьте, какие из приведенных ниже операторов языка C/C++
корректны.

                            
                                                                                                    
                                        (1) 
    p = a + 10;
                                        
                                                                    
                                        (2) 
    p = &q[5] + 2;
                                        
                                                                    
                                        (3) 
    q = &p[5] + 5;
                                        
                                                                    
                                        (4) 
    n = q - &a[4];
                                        
                                                                    
                                        (5) 
    n = p - a;
                                        
                                                            
                        
                                            
                            
Чему будет равно значение переменной n
в результате выполнения следующего фрагмента программы?
Процессор имеет 32-разрядную архитектуру.

    double a[10][2]; int n, m;
    n = (int)(a+1); m = (int) a;
    n -= m;


                            
                                                                                                    
                                        16                                    
                                                            
                        
                                            
                            
Какие константы можно в практическом программировании использовать
в качестве воображаемого значения "минус бесконечность" при работе с
целыми числами типа int? Укажите все правильные
варианты.

                            
                                                                                                    
                                        (1) 
    Число -INT_MAX
    (константа INT_MAX описана в стандартном заголовочном файле
    limits.h).
                                        
                                                                    
                                        (2) 
    Константу INT_MIN,
    заданную в стандартном заголовочном файле
    limits.h.
                                        
                                                                    
                                        (3) 
    Константу -2147483648,
    равную -2³¹.
                                        
                                                            
                        
                                            
                            
Пусть целочисленная переменная n
содержит некоторое положительное целое число.
Указать, что вычисляет следующая функция f(n):

int f(int n) {
    int s = 10; int k = 0;
    while (s <= n) {
        // Invariant: s == 10*(k+1)
        s += 10; ++k;
    }
    return k;
}


                            
                                                                                                    
                                        (1) 
    Целую часть частного n/10.
                                        
                                                                    
                                        (2) 
    Произведение 10*n.
                                        
                                                                    
                                        (3) 
    Целую часть десятичного логарифма log₁₀ n.
                                        
                                                                    
                                        (4) 
    Целую часть кубического корня из n/10.
                                        
                                                                    
                                        (5) 
    Целую часть от 2^10*n.
                                        
                                                            
                        
                                            
                            
Алгоритм пузырьковой сортировки упорядочивает массив
из 100 тысяч элементов примерно за 1 минуту. За какое примерно
время тот же алгоритм упорядочит массив из 10 тысяч элементов?

                            
                                                                                                    
                                        (1) 
    За 0.6 секунды
                                        
                                                                    
                                        (2) 
    За 6 секунд
                                        
                                                                    
                                        (3) 
    За 30 секунд
                                        
                                                                    
                                        (4) 
    За 0.6 секунды
                                        
                                                            
                        
                                            
                            
Целочисленный массив содержит элементы
30, 25, 23, 15, 10, 20, 16, 7, 12, 5, 11, 9
в указанном порядке. Образуют ли они бинарную кучу (пирамиду)?

                            
                                                                                                    
                                        (1) 
    Да.
                                        
                                                                    
                                        (2) 
    Нет.
                                        
                                                            
                        
                                                                                
                            
Что можно сказать об условии, указанном в заголовке цикла "while",
в процессе выполнения тела цикла?

                            
                                                                                                    
                                        (1) 
    Условие истинно.
                                        
                                                                    
                                        (2) 
    Условие ложно.
                                        
                                                                    
                                        (3) 
    Условие может быть как истинным, так и ложным.
                                        
                                                            
                        
                                            
                            
Сортируемый массив содержит составные ключи из 10
десятичных цифр.
Массив имеет длину 1000000 (миллион). Надо выбрать один из двух алгоритмов
сортировки: сортировку кучей HeapSort или RADIX-сортировку.
Какой из двух алгоритмов будет в среднем работать быстрее
в данной ситуации?

                            
                                                                                                    
                                        (1) 
    RADIX-сортировка.
                                        
                                                                    
                                        (2) 
    Сортировка кучей HeapSort.
                                        
                                                            
                        
                                            
                            
В алгоритме получения записи числа n
в системе счисления с основанием b
мы вычисляем цифры числа справа налево,
начиная с последней цифры. На очередном шаге
мы делим n с остатком на b, получая
частное q и остаток r;
остаток представляет очередную цифру числа
в порядке справа налево.
Затем мы переменной n
присваиваем значение частного q,
и процесс повторяется, пока n не станет равным нулю.
Сколько раз будет выполнена операция деления
при переводе числа 1000 (тысяча)
в троичную систему счисления?

                            
                                                                                                    
                                        (1) 
    7 раз.
                                        
                                                                    
                                        (2) 
    8 раз.
                                        
                                                                    
                                        (3) 
    9 раз.
                                        
                                                                    
                                        (4) 
    10 раз.
                                        
                                                            
                        
                                            
                            
При представлении вещественных чисел в плавающей форме
мы выражаем вещественное число x в виде

    x = s 2^e m,

где s - знак числа, принимающий значение
плюс или минус единица,
e - порядок, представляющий собой
целое число (положительное, 0 или отрицательное),
m - мантисса, представляющая собой
вещественное число в диапазоне
1  m < 2.
Чему равны порядок и мантисса для числа 0.1?

                            
                                                                                                    
                                        (1) 
    e = -3, m = 1.0.
                                        
                                                                    
                                        (2) 
    e = -3, m = 1.125.
                                        
                                                                    
                                        (3) 
    e = -4, m = 1.6.
                                        
                                                            
                        
                                            
                            
Формула Бинома Ньютона дает следующее разложение в ряд
для функции "кубический корень из z" 
(обозначим ее croot(z)):

(1+x)^1/3 = croot(1+x) =
    1 + (1/3)x + (1/3)(-2/3)/2! x² + (1/3)(-2/3)(-5/3)/3! x³ + (1/3)(-2/3)(-5/3)(-8/3)/4! x⁴ + ...

(мы сделали замену z=1+x). 
Этот ряд сходится лишь для значений 
x, по абсолютной величине не превосходящих 1, а эффективно вычислять
его сумму можно только для еще более узкого интервала значений 
x. 
Каким свойством функции croot(z)=z^1/3
удобнее всего воспользоваться, чтобы свести ее вычисление 
для положительных значений z к суммированию ряда?

                            
                                                                                                    
                                        (1) 
    Свойством croot(z)=croot(n)*croot(z/n),
    где n - целая часть z.
                                        
                                                                    
                                        (2) 
    Свойствами 
    croot(z) = 2*croot(z/8) при z > 1.6 и
    croot(z) = 0.5*croot(z*8) при 0 < z < 0.2.
                                        
                                                                    
                                        (3) 
    Свойствами 
    croot(z) = croot(2)*croot(z/2)
    при z > 1.5 и
    croot(z) = croot(z*2)/croot(2)
    при 0 < z < 0.5.
                                        
                                                            
                        
                                            
                            
Где описан прототип функции printf,
используемой для печати различных значений по заданному формату?

                            
                                                                                                    
                                        (1) 
    В стандартном заголовочном файле stdio.h
                                        
                                                                    
                                        (2) 
    В стандартном заголовочном файле stdlib.h
                                        
                                                                    
                                        (3) 
    В стандартном заголовочном файле math.h
                                        
                                                            
                        
                                            
                            
Рассмотрим реализацию матрицы вещественных чисел
размера m строк на n столбцов
при помощи линейного массива,
в котором хранятся сначала элементы нулевой строки матрицы,
затем первой и т.д., в конце - элементы (m-1)-й строки:

    int m, n; // Размеры матрицы: число строк, столбцов
    . . .
    double* a = new double[m*n];
    // a[i*n + j] -- элемент i-й строки и j-го столбца

Пусть функция с прототипом

void transp(double* a, int m, int n);

реализует транспонирование
матрицы, при выполнении которого строки матрицы становятся
столбцами, столбцы - строками, а матрица размера
m на n
превращается в матрицу размера
n на m
Пусть эта функция применяется к прямоугольной матрице,
содержащей 3 строки и 5 столбцов, элементы которой хранятся
в линейном массиве a. Сколько элементов массива
a при этом останутся на своем месте?

                            
                                                                                                    
                                        (1) 
    2 элемента
                                        
                                                                    
                                        (2) 
    3 элемента
                                        
                                                                    
                                        (3) 
    4 элемента
                                        
                                                                    
                                        (4) 
    5 элементов
                                        
                                                            
                        
                                            
                            
Пусть неизвестная функция определена на отрезке [a, b],
причем на концах отрезка заданы ее значения
y₀=f(a),
y₁=f(b),
а также значения ее производной
y'₀=f'(a),
y'₁=f'(b).
Всегда ли существует многочлен степени 2 такой, что
на концах отрезка его значения и значения его производной
совпадают со значениями и производной функции?

                            
                                                                                                    
                                        (1) 
    Да, всегда.
                                        
                                                                    
                                        (2) 
    Нет, не всегда.
                                        
                                                            
                        
                                            
                            
Чему равно значение выражения (-17)%3*10
в языке C?

                            
                                                                                                    
                                        -20                                    
                                                            
                        
                                            
                            
Укажите, чему будет равно значение переменной n
в результате выполнения следующего фрагмента программы:

    double *p = 10000;
    p -= 1000;
    int n = (int) p;


                            
                                                                                                    
                                        2000                                    
                                                            
                        
                                            
                            
Мы хотим реализовать функцию length, которая находит
длину вектора в трехмерном пространстве. Вектор задается массивом
из трех его координат.
Отметьте, какие из возможных прототипов данной функции
корректны.

                            
                                                                                                    
                                        (1) 
    double length(double v[3]);
                                        
                                                                    
                                        (2) 
    double length(double *v);
                                        
                                                                    
                                        (3) 
    double length(const double v[]);
                                        
                                                                    
                                        (4) 
    double length(const double *v);
                                        
                                                            
                        
                                            
                            
Укажите, какие из приведенных ниже строк языка C/C++
корректно описывают объекты языка.

                            
                                                                                                    
                                        (1) 
    void (*a[10][20])(int x);
                                        
                                                                    
                                        (2) 
    int (*(*a)(int x))[256];
                                        
                                                                    
                                        (3) 
    void (*a)(double x)[10];
                                        
                                                                    
                                        (4) 
    double (*a(int x))[3];
                                        
                                                            
                        
                                            
                            
Является ли индуктивной функция, которая последовательности
коэффициентов многочлена по возрастанию степеней ставит
в соответствие пару чисел:
(степень многочлена, интеграл многочлена по отрезку [0, 1])?

                            
                                                                                                    
                                        (1) 
    Является.
                                        
                                                                    
                                        (2) 
    Не является.
                                        
                                                            
                        
                                            
                            
Рассмотрим следующий фрагмент программы, вычисляющей
частное q и остаток r от деления
целых чисел a, b:

    // дано: целые числа a >= 0, b > 0
    int a, b;
    . . .
    int q = 0, r = a;
    int e = 1, m = b;
    while (r >= b) {
        if (2*m <= r) {
            e *= 2; m *= 2;
        } else if (m > r) {
            e /= 2; m /= 2;
        } else {
            // утверждение: m <= r && r < 2*m
            q += e; r -= m;
        }
    }
    // q и r - частное и остаток от деления a на b

Какое условие является инвариантом цикла?

                            
                                                                                                    
                                        (1) 
    Число e является степенью двойки, а также
    выполняются равенства
    a - q*b == r и
    m == e*b.
                                        
                                                                    
                                        (2) 
    Число e является степенью двойки, а также
    выполняются равенства
    a - q*m == r и
    m == e*b.
                                        
                                                                    
                                        (3) 
    Число e является степенью двойки, а также
    выполняются равенства
    a + q*b == r и
    m == e*b.
                                        
                                                                    
                                        (4) 
    Число e является степенью двойки, а также
    выполняются равенства
    a - q*m == r и
    m == e+b.
                                        
                                                            
                        
                                            
                            
Массив длины 5 содержит элементы
2, 1, 5, 4, 3 в указанном порядке.
К нему применяется
алгоритм сортировки методом прямого выбора,
использующий сравнение элементов с помощью функции compare
и обмен элементов с помощью функции swap.
Сколько раз будет вызвана функция swap?

                            
                                                                                                    
                                        (1) 
    2 раза
                                        
                                                                    
                                        (2) 
    3 раза
                                        
                                                                    
                                        (3) 
    4 раза
                                        
                                                                    
                                        (4) 
    5 раз
                                        
                                                            
                        
                                            
                            
Пусть целочисленный массив содержит элементы
10, 16, 12, 8, 11, 7, 5
в указанном порядке. Услове пирамиды нарушается
только для элемента 10, стоящего в вершине пирамиды.
Для исправления пирамиды выполняется процедура просеивания,
при которой элемент 10 опускается на свое место.
Каким будет содержимое массива после окончания этой процедуры?

                            
                                                                                                    
                                        (1) 
    16, 10, 12, 8, 11, 7, 5.
                                        
                                                                    
                                        (2) 
    16, 11, 12, 8, 7, 10, 5.
                                        
                                                                    
                                        (3) 
    16, 11, 12, 8, 10, 7, 5.
                                        
                                                                    
                                        (4) 
    16, 12, 11, 8, 10, 7, 5.
                                        
                                                                    
                                        (5) 
    16, 11, 12, 8, 10, 5, 7.
                                        
                                                            
                        
                                                                                
                            
Сколько раз будет выполнено тело цикла в приведенной
ниже программе? Многоточием обозначен фрагмент,
не содержащий переменной x.

int x = 0;
while (x <= 100) {
    . . .
    x = x + 2;
}


                            
                                                                                                    
                                        51                                    
                                                            
                        
                                            
                            
Функция merge слияния двух упорядоченных массивов
применяется к двум массивам длины 100 и 1000. Какое минимальное
число сравнений может быть сделано при выполнении этой функции?

                            
                                                                                                    
                                        (1) 
    99
                                        
                                                                    
                                        (2) 
    100
                                        
                                                                    
                                        (3) 
    999
                                        
                                                                    
                                        (4) 
    1000
                                        
                                                            
                        
                                            
                            
Рассмотрим следующую запись числа
в троичной системе счисления
(для удобства запись разбита запятыми на четверки):
1201,1122,2111,2010.
Укажите запись этого числа
в системе счисления с основанием 9.

                            
                                                                                                    
                                        (1) 
    51487463.
                                        
                                                                    
                                        (2) 
    41387362.
                                        
                                                                    
                                        (3) 
    41376352.
                                        
                                                            
                        
                                            
                            
Можно ли сохранить целое число типа int
(4 байта) в переменной типа double без потери
точности? То есть, если мы имеем целочисленную
переменную n типа int,
то она не изменит своего значения в результе выполнения
следующего фрагмента программы:

    int n;
    . . .
    double x = (double) n;
    n = (int) x;


                            
                                                                                                    
                                        (1) 
    Можно.
                                        
                                                                    
                                        (2) 
    Нельзя.
                                        
                                                            
                        
                                            
                            
Функция arctg(x) (ее также обозначают 
arctan или atan)
представляется рядом Тейлора:

    arctg(x) = x - x³/3 + x⁵/5 - x⁷/7 + ...

Этот ряд сходится лишь для значений x, по модулю не превосходящих
единицы, а эффективно вычислять его можно лишь для x, по модулю
существенно меньших единицы - например, |x|<0.5.
(Для значений x, по модулю близких к единице и не превосходящих
единицу, ряд сходится, но очень медленно, а точность вычисления его суммы
невысока.)
Какие способы вычисления функции arctan(x) для "плохих"
значений x возможны? Укажите все разумные способы из
числа перечисленных ниже.
(Предполагается, что мы умеем быстро и точно вычислять квадратный корень
sqrt(z), а также знаем константу pi.)

                            
                                                                                                    
                                        (1) 
    Применив формулу

    arctg(x) = 2*arctg(y), где y = x/(1 + sqrt(1 + x*x))

    один или несколько раз, мы сведем вычисление 
    arctg(x) к вычислению arctg(y)
    для меньшего по модулю значения y.
                                        
                                                                    
                                        (2) 
    Применив формулу

    arctg(x) = arcsin(x / sqrt(1 + x*x)),

    мы сведем задачу к вычислению функции arcsin(y),
    где y=x/sqrt(1+x*x). Значение arcsin(y)
    можно вычислить как сумму ряда, когда |y|
    существенно меньше единицы (например, |y|<0.75):

    arcsin(x) = x +(1/2)x³/3 + (1/2)(3/4)x⁵/5 + (1/2)(3/4)(5/6)x⁷/7 + ...

    Для значений y, по модулю близких к единице, этот ряд
    сходится очень медленно, поэтому для них можно дополнительно
    воспользоваться формулой

    arcsin(y) = pi/2 - arcsin(sqrt(1 - y*y)),

    которая сводит задачу к вычислению ряда функции arcsin(z)
    для значения z=sqrt(1-y*y).
                                        
                                                                    
                                        (3) 
    Функция arctg(x) нечетная, поэтому
    достаточно уметь ее вычислять только для неотрицательных x.
    Для 0  x  1 вычисляется сумма указанного ряда.
    Для x>1 применим формулу

    arctg(x) = pi/2 - arctg(1/x),

    сведя задачу к суммированию ряда для функции arctg(y),
    где y=1/x и значение y
    меньше единицы.
                                        
                                                            
                        
                                            
                            
Прыгун в длину совершает прыжок на 7 метров, при этом
время полетной фазы составляет 0.7 сек, а высота траектории 60 см.
До какого примерно значения нужно увеличить высоту траектории
прыжка, чтобы при той же горизонтальной скорости достичь
результата 8 метров?

                            
                                                                                                    
                                        (1) 
    69 см
                                        
                                                                    
                                        (2) 
    79 см
                                        
                                                                    
                                        (3) 
    89 см
                                        
                                                                    
                                        (4) 
    99 см
                                        
                                                            
                        
                                            
                            
Чему равен ранг следующей матрицы:

0 1 1 1
1 1 1 1
1 1 1 0


                            
                                                                                                    
                                        (1) 
    ранг равен 1
                                        
                                                                    
                                        (2) 
    ранг равен 2
                                        
                                                                    
                                        (3) 
    ранг равен 3
                                        
                                                                    
                                        (4) 
    ранг равен 4
                                        
                                                            
                        
                                            
                            
Пусть f(x) - гладкая функция,
заданная на отрезке [a, b], третья производная которой
по абсолютной величине не превышает некоторой константы.
Для приближенного вычисления интеграла от этой функции мы
применяем формулу Симпсона (парабол), разбивая отрезок
[a, b] на 2*n равных частей.
Какова точность вычисления интеграла в зависимости от n?

                            
                                                                                                    
                                        (1) 
    O(1/n).
                                        
                                                                    
                                        (2) 
    O((1/n)²).
                                        
                                                                    
                                        (3) 
    O((1/n)³).
                                        
                                                                    
                                        (4) 
    O((1/n)⁴).
                                        
                                                            
                        
                                            
                            
Укажите минимальное значение x > 0
типа signed char, удовлетворяющее неравенству
x+x <= 0?

                            
                                                                                                    
                                        (1) 
    0
                                        
                                                                    
                                        (2) 
    32
                                        
                                                                    
                                        (3) 
    64
                                        
                                                                    
                                        (4) 
    128
                                        
                                                                    
                                        (5) 
    16
                                        
                                                            
                        
                                            
                            
Пусть переменные p, q, n
описаны следующим образом:

    double *p, q[100], *r; int n;

Отметьте, какие из перечисленных ниже строк программы на C/C++
являются корректными:

                            
                                                                                                    
                                        (1) 
    p = q+20;
                                        
                                                                    
                                        (2) 
    p = &q[10];
                                        
                                                                    
                                        (3) 
    n = p - q;
                                        
                                                                    
                                        (4) 
    r = p - n;
                                        
                                                                    
                                        (5) 
    p = q + r;
                                        
                                                            
                        
                                            
                            
Рассмотрим следующий фрагмент программы на С++:

    static double *a = new double[10];
    a[0] = 3.7;

Где хранится значение выражения "a[0]" (т.е.
число 3.7)?

                            
                                                                                                    
                                        (1) 
    В статической памяти.
                                        
                                                                    
                                        (2) 
    В динамической памяти.
                                        
                                                                    
                                        (3) 
    В стеке.
                                        
                                                            
                        
                                            
                            
Эквивалентны ли в языке C/C++ типы 
Callback и Action,
заданные в приведенном ниже фрагменте программы?

typedef void (*Callback)(char *);
typedef void (*Action)(void *);


                            
                                                                                                    
                                        (1) 
    Эквивалентны.
                                        
                                                                    
                                        (2) 
    Не эквивалентны.
                                        
                                                            
                        
                                            
                            
Функция F последовательности цифр в десятичной записи числа
n ставит в соответстие единицу, если n делится на 14,
и ноль в противном случае. Какая из приведенных
ниже функций на последовательности десятичных цифр числа n
является индуктивным расширением функции F?

                            
                                                                                                    
                                        (1) 
    Пара (остаток от деления числа n на 57,
    остаток от деления числа n на 35).
                                        
                                                                    
                                        (2) 
    Пара (остаток от деления числа n на 52,
    остаток от деления числа n на 21).
                                        
                                                                    
                                        (3) 
    Остаток от деления числа n на 165.
                                        
                                                                    
                                        (4) 
    Остаток от деления числа n на 57.
                                        
                                                            
                        
                                            
                            
Какое утверждение является инвариантом для следующего
фрагмента программы (т.е. из справедливости утверждения
до выполнения фрагмента программы вытекает справедливость утверждения
после выполнения)? Предполагается, что
n не меньше k.
Восклицательным знаком обозначается операция вычисления факториала.

    int n, k, c;
    . . .
    c *= (n+1);
    c /= (n+1-k);
    ++n;


                            
                                                                                                    
                                        (1) 
    Утверждение
    c = n! / (k! * (n-k)!).
                                        
                                                                    
                                        (2) 
    Утверждение
    c = (n+k)! / (n! * (n-k)!).
                                        
                                                                    
                                        (3) 
    Утверждение
    c = (n-k)! / (k! * (n+k)!).
                                        
                                                                    
                                        (4) 
    Утверждение
    c = (n+k)! / (k! * (n-k)!).
                                        
                                                            
                        
                                            
                            
Для конкретного массива длины 1000 применяются
алгоритмы пузырьковой сортировки и сортировки
методом прямого выбора.
Оба алгоритма используют сравнение элементов
с помощью функции compare
и обмен элементов с помощью функции swap.
Какой из этих алгоритмов вызывает функцию swap
большее число раз? (Имеется в виду нестрогое сравнение.)

                            
                                                                                                    
                                        (1) 
    Пузырьковая сортировка всегда вызывает функцию swap
    не меньшее число раз, чем сортировка
    прямым выбором.
                                        
                                                                    
                                        (2) 
    Сортировка прямым выбором
    всегда вызывает функцию swap
    не меньшее число раз, чем
    пузырьковая сортировка.
                                        
                                                                    
                                        (3) 
    Возможны оба варианта в зависимости от содержания массива
    (для каких-то массивов пузырьковая сортировка вызывает функцию swap
    большее число раз,
    для других массивов - сортировка прямым выбором).
                                        
                                                            
                        
                                            
                            
К целочисленному массиву применяется алгоритм сортировки
кучей. Пусть после первого этапа алгоритма пирамида
(бинарная куча) уже построена и массив содержит элементы
30, 20, 25, 10, 7, 19, 5
в указанном порядке. Затем выполняется второй этап сортировки.
На его первом шаге начальный и конечный элементы массива
меняются местами, от пирамиды отрезается правая нижняя ветка
(т.е. последний элемент массива), затем элемент в вершине
пирамиды просеивается, благодаря чему восстанавливается
условие пирамиды. Каким будет содержимое массива по
окончании этого шага?

                            
                                                                                                    
                                        (1) 
    25, 20, 19, 10, 7, 5, 30.
                                        
                                                                    
                                        (2) 
    25, 20, 19, 10, 5, 7, 30.
                                        
                                                                    
                                        (3) 
    25, 19, 20, 10, 7, 5, 30.
                                        
                                                                    
                                        (4) 
    25, 10, 19, 20, 5, 7, 30.
                                        
                                                                    
                                        (5) 
    25, 30, 19, 10, 5, 7, 20.
                                        
                                                            
                        
                                                                                
                            
Укажите, чему может быть равно значение переменной z
в результате выполнения следующего фрагмента программы:

z := 0;
while (x < y) {
    . . .
    if (z > 100) {
        z = 10; x = y;
    } else {
        z = 20; x = y - 1;
    }
}


                            
                                                                                                    
                                        (1) 
    Значение z равно 0 или 10.
                                        
                                                                    
                                        (2) 
    Значение z равно 0 или 20.
                                        
                                                                    
                                        (3) 
    Значение z равно 10 или 20.
                                        
                                                                    
                                        (4) 
    Значение z не равно 0.
                                        
                                                            
                        
                                            
                            
Рассмотрим алгоритм сортировки слиянием с использованием
дополнительной памяти. Используется нисходящая (рекурсивная)
схема реализации алгоритма. Алгоритм применяется к массиву
длины 1000. Какова максимально возможная
глубина рекурсии? Дайте наиболее точную оценку среди приведенных ниже.

                            
                                                                                                    
                                        (1) 
    Не больше 8.
                                        
                                                                    
                                        (2) 
    Не больше 10.
                                        
                                                                    
                                        (3) 
    Не больше 12.
                                        
                                                                    
                                        (4) 
    Не больше 20.
                                        
                                                            
                        
                                            
                            
Рассмотрим максимальное по абсолютной величине
целое число, которое в языке C/C++ представимо
типом short. Четное оно или нечетное?

                            
                                                                                                    
                                        (1) 
    Четное.
                                        
                                                                    
                                        (2) 
    Нечетное.
                                        
                                                            
                        
                                            
                            
Двоичный код, представляющий число типа double,
хранит знак, смещенный порядок и дробную часть
двоичного представления мантиссы.
Чему равен смещенный порядок в представлении числа 0.3?

                            
                                                                                                    
                                        (1) 
    1021.
                                        
                                                                    
                                        (2) 
    1022.
                                        
                                                                    
                                        (3) 
    1023.
                                        
                                                            
                        
                                            
                            
Функция с прототипом

double root(double a, double b, double eps);

находит корень фиксированной функции

double f(double x);

на отрезке [a, b] методом деления отрезка пополам
с точностью eps.
Пусть функция f(x) определена следующим
образом:

double f(double x) {
    double p = 1.;
    double r = 1.;
    while (r < 5.5) {
        p *= (x - r);
        r += 1.;
    }
    return p;
}

Каким будет приблизительное значение переменной x
в результате выполнения следующего фрагмента программы:

    double x = root(0., 5.9, 0.000001);


                            
                                                                                                    
                                        (1) 
    Значение x приблизительно равно 1.
                                        
                                                                    
                                        (2) 
    Значение x приблизительно равно 2.
                                        
                                                                    
                                        (3) 
    Значение x приблизительно равно 3.
                                        
                                                                    
                                        (4) 
    Значение x приблизительно равно 4.
                                        
                                                                    
                                        (5) 
    Значение x приблизительно равно 5.
                                        
                                                            
                        
                                            
                            
Какое максимальное число операций деления может
быть выполнено в алгоритме Гаусса в процессе приведения
к ступенчатому виду прямоугольной матрицы, содержащей
3 строки и 4 столбца?

                            
                                                                                                    
                                        (1) 
    3 операции деления
                                        
                                                                    
                                        (2) 
    4 операции деления
                                        
                                                                    
                                        (3) 
    5 операций деления
                                        
                                                                    
                                        (4) 
    6 операций деления
                                        
                                                            
                        
                                            
                            
Приближенное значение интеграла по отрезку [a, b]
от функции y = f(x) вычисляется по формуле

    1/6 * (y₀ + 4*y₁ + y₂) * (b - a).

где

    y₀ = f(a), y₁ = f((a+b)/2), y₂ = f(b).

Пусть f(x) - многочлен некоторой степени.
Какова максимальная степень многочленов, для которых эта формула
всегда дает точное значение интеграла?

                            
                                                                                                    
                                        (1) 
    Формула точна для многочленов степени не выше 1.
                                        
                                                                    
                                        (2) 
    Формула точна для многочленов степени не выше 2.
                                        
                                                                    
                                        (3) 
    Формула точна для многочленов степени не выше 3.
                                        
                                                            
                        
                                            
                            
Среди перечисленных ниже чисел отметьте простые.

                            
                                                                                                    
                                        (1) 
    91
                                        
                                                                    
                                        (2) 
    97
                                        
                                                                    
                                        (3) 
    101
                                        
                                                                    
                                        (4) 
    133
                                        
                                                                    
                                        (5) 
    139
                                        
                                                                    
                                        (6) 
    143

                                        
                                                            
                        
                                            
                            
Что содержит регистр PC (Program Counter - счетчик команд, в
процессоре Intel 80x86 он обозначается как IP - Instruction
Pointer) в момент выполнения процессором очередной команды?

                            
                                                                                                    
                                        (1) 
    Адрес выполняемой команды.
                                        
                                                                    
                                        (2) 
    Адрес команды, которая будет выполняться на следующем
    шаге.
                                        
                                                                    
                                        (3) 
    Адрес команды, которая выполнилась на предудущем
    шаге.
                                        
                                                                    
                                        (4) 
    Значение 1.
                                        
                                                                    
                                        (5) 
    Значение 0.
                                        
                                                            
                        
                                            
                            
Среди указанных ниже операторов языка C/C++
отметьте корректные.

                            
                                                                                                    
                                        (1) 
    int* x = new int(8);
                                        
                                                                    
                                        (2) 
    int* x = new int(1000);
                                        
                                                                    
                                        (3) 
    int x = new int[1000];
                                        
                                                                    
                                        (4) 
    int* x = (int *) malloc(8 * sizeof(int));
                                        
                                                            
                        
                                            
                            
Назовем функцию y = f(p) на последовательности p 
элементов некоторого типа индуктивной, если при добавлении в конец
последовательности p
еще одного элемента x новое значение функции
y1 = f(p&x) можно вычислить, зная только
старое значение y и добавленный элемент x.
Среди перечисленных ниже функций на последовательностях вещественных
чисел укажите индуктивные.

                            
                                                                                                    
                                        (1) 
    Произведение элементов последовательности.
                                        
                                                                    
                                        (2) 
    Среднее геометрическое значение элементов последовательности.
                                        
                                                                    
                                        (3) 
    Значение максимального элемента последовательности.
                                        
                                                                    
                                        (4) 
    Разность между максимальным и минимальным элементами последовательности.
                                        
                                                                    
                                        (5) 
    Значение многочлена в фиксированной точке t=2,
    коэффициенты многочлена заданы в последовательности 
    p = {a₀, a₁, a₂, ..., a_n}
    по убыванию степеней:
    
y = a₀*tⁿ + a₁*t^n-1 + ... + a_n
    
                                        
                                                            
                        
                                            
                            
Сколько умножений выполняется в схеме Горнера при
вычислении значения многочлена степени 3?

                            
                                                                                                    
                                        (1) 
    3
                                        
                                                                    
                                        (2) 
    4
                                        
                                                                    
                                        (3) 
    5
                                        
                                                                    
                                        (4) 
    6
                                        
                                                            
                        
                                            
                            
Оценить сверху время работы (т.е. количество
выполнений тела цикла) алгоритма
приблизительного вычисления логарифма:

double myLog(double x, double a, double eps) {
    // дано: x > 0, a > 1, eps > 0
    // надо: вычислить log_a x с точностью eps
    double y = 0.0, z = x, t = 1.0;

    while (
        fabs(t) > eps ||
        x <= 1.0/a ||
        z >= a
    ) {
        // Invariant: a^y * z^t == x
        if (z >= a) {
            z /= a; y += t;
        } else if (z <= 1.0/a) {
            z *= a; y -= t;
        } else {
            z *= z; t /= 2.0;
        }
    }
    return y;
}


                            
                                                                                                    
                                        (1) 
    Время работы не больше, чем
    C*log₂ [x+1],
    где C - некоторая константа,
    [x+1] - целая часть числа x+1
    (т.е. время пропорционально количеству цифр
    в двоичной или десятичной записи
    целой части числа x).
                                        
                                                                    
                                        (2) 
    Время работы не больше, чем
    C*log₂[x+1]*log₂(1/eps),
    где C - некоторая константа, а квадратные скобки
    обозначают целую часть.
    Иначе говоря, время пропорционально количеству цифр
    в двоичной или десятичной записи
    целой части x, умноженному на требуемое количество значащих
    цифр в дробной части результата.
                                        
                                                                    
                                        (3) 
    Время работы не больше, чем
    C*log₂[x+1] + log₂(1/eps),
    где C - некоторая константа, а квадратные скобки
    обозначают целую часть. Иначе говоря,
    время пропорционально сумме количества цифр
    в двоичной или десятичной записи
    целой части x и требуемого количества значащих
    цифр в дробной части результата.
                                        
                                                            
                        
                                            
                            
Есть 6 монет, известно, что все они имеют различные веса.
Веса двух монет можно сравнить, используя весы-коромысло.
Требуется упорядочить монеты по возрастанию их веса.
Можно ли придумать такой алгоритм сортировки монет по весу,
при котором в любом случае будет сделано не больше 9 взвешиваний?

                            
                                                                                                    
                                        (1) 
    Можно.
                                        
                                                                    
                                        (2) 
    Нельзя.
                                        
                                                            
                        
                                            
                            
К целочисленному массиву применяется алгоритм сортировки
кучей. На первом этапе из элементов массива строится
пирамида (бинарная куча) путем просеивания элементов
по бинарному дереву в порядке справа налево и снизу вверх.
Пусть вначале массив содержал элементы
1, 2, 3, 4, 7, 6, 5
в указанном порядке.
Каким будет содержимое массива
после построения пирамиды?

                            
                                                                                                    
                                        (1) 
    7, 4, 6, 1, 2, 3, 5.
                                        
                                                                    
                                        (2) 
    7, 4, 5, 1, 2, 6, 3.
                                        
                                                                    
                                        (3) 
    7, 6, 5, 4, 2, 3, 1.
                                        
                                                                    
                                        (4) 
    7, 4, 6, 5, 2, 3, 1.
                                        
                                                                    
                                        (5) 
    7, 6, 4, 5, 2, 3, 1.
                                        
                                                            
                        
                                                                                
                            
Чему равно значение целочисленной переменной x
в результате выполнения приведенного ниже фрагмента программы?

    int x = 1;
    while (x < 11) {
        x = -2*x + 11;
    }


                            
                                                                                                    
                                        25                                    
                                                            
                        
                                            
                            
Какой двоичный код представляет
число -14 для типа signed char?

                            
                                                                                                    
                                        (1) 
    11110010.
                                        
                                                                    
                                        (2) 
    11111010.
                                        
                                                                    
                                        (3) 
    11111110.
                                        
                                                            
                        
                                            
                            
Двоичный код, представляющий число типа double,
хранит знак, смещенный порядок и дробную часть
двоичного представления мантиссы.
Сколько единичных битов в двоичном представлении
дробной части мантиссы для числа 15.0?

                            
                                                                                                    
                                        (1) 
    1.
                                        
                                                                    
                                        (2) 
    2.
                                        
                                                                    
                                        (3) 
    3.
                                        
                                                                    
                                        (4) 
    4.
                                        
                                                            
                        
                                            
                            
Сколько раз в алгоритме Гаусса будет выполнена операция
перестановки местами двух строк
(с изменением знака одной из них) при приведении к
ступенчатому виду следующей матрицы:

0 1 2 3
4 5 6 7
1 2 3 4


                            
                                                                                                    
                                        (1) 
    1 раз
                                        
                                                                    
                                        (2) 
    2 раза
                                        
                                                                    
                                        (3) 
    3 раза
                                        
                                                                    
                                        (4) 
    4 раза
                                        
                                                            
                        
                                            
                            
Какие объекты языка C/C++ располагаются в
динамической памяти?

                            
                                                                                                    
                                        (1) 
    Локальные переменные функций, а также их аргументы.
                                        
                                                                    
                                        (2) 
    Глобальные и статические переменные.
                                        
                                                                    
                                        (3) 
    Объекты, которые создаются с помощью оператора new.
                                        
                                                                    
                                        (4) 
    Таких переменных нет.
                                        
                                                            
                        
                                            
                            
Пусть процессор имеет 32-разрядную архитектуру
и в некоторый момент его работы регистр SP содержит значение
1000. Укажите, какое значение будет содержаться в SP
после выполнения команды вызова функции call f.

                            
                                                                                                    
                                        (1) 
    1001
                                        
                                                                    
                                        (2) 
    1004
                                        
                                                                    
                                        (3) 
    999
                                        
                                                                    
                                        (4) 
    996
                                        
                                                            
                        
                                            
                            
Следующий фрагмент программы для последовательности
вещественных чисел вычисляет количество n элементов,
строго меньших предыдущего, причем самый первый элемент также
учитывается (считается меньше предыдущего).
Например, для последовательности
{2, 1, 3, 5, 4} ответ n=3
(элементы 2, 1 и 4).

n = 0
x0 = ...

цикл пока в последовательности есть непрочитанные элементы
|выполнять
|  прочесть очередной элемент посл-ти в <вых: x>
|  если x < x0
|  | то n = n + 1
|  конец если
|  x0 = x
конец цикла

Каким значением надо инициализировать переменную
x0, чтобы программа работала правильно?

                            
                                                                                                    
                                        (1) 
    x0 = минус бесконечность
                                        
                                                                    
                                        (2) 
    x0 = плюс бесконечность
                                        
                                                                    
                                        (3) 
    x0 = 0
                                        
                                                                    
                                        (4) 
    x0 = 1
                                        
                                                            
                        
                                            
                            
Пусть w - последовательность целых чисел,
F(w)=длина максимального постоянного участка в w.
Например, для последовательности
w={1, 1, 4, 4, 4, 0, 2} значение F
равно 3 (постоянный участок из четверок).
Какие из перечисленных ниже функций
являются индуктивным расширением функции F?
Укажите все правильные варианты.

                            
                                                                                                    
                                        (1) 
    Тройка
    (длина максимального постоянного участка в w;

    последний элемент последовательности w;

    1, если максимальный постоянный участок заканчивается
    в конце последовательности, и 0 в противном случае).
                                        
                                                                    
                                        (2) 
    Тройка
    (длина максимального постоянного участка в w;

    последний элемент последовательности w;

    длина постоянного участка в конце последовательности w).
                                        
                                                                    
                                        (3) 
    Тройка
    (длина максимального постоянного участка в w;

    предпоследний элемент последовательности w;

    1, если максимальный постоянный участок заканчивается
    в конце последовательности, и 0 в противном случае).
                                        
                                                                    
                                        (4) 
    Тройка
    (длина максимального постоянного участка в w;

    последний элемент последовательности w;

    0, если максимальный постоянный участок заканчивается
    в конце последовательности, и 1 в противном случае).
                                        
                                                            
                        
                                            
                            
Пусть f(x) - вещественная функция функция
от вещественного
аргумента. Определить,
содержит ли следующий фрагмент программы ошибку
(т.е. действительно ли тело цикла сохраняет инвариант):

// Программа корень функции
    double a, b, c;
    double eps = 0.000001;
    . . .
    // утверждение: a < b  && f(a)*f(b) <= 0.0
    // Значения функции на концах отрезка [a, b] разных знаков

    while (b - a > eps) {
        // Invariant: f(a)*f(b) <= 0.0
        // Делим отрезок [a, b] пополам
        c = (a + b)/2.0; // c - середина отрезка [a, b]
        if (f(a) * f(c) < 0.0) {
            b = c;     // выбираем левую половину отрезка
        } else {
            a = c;     // выбираем правую половину
        }
    }

    // утверждение: b - a <= eps  &&
    //              f(a)*f(b) <= 0.0


                            
                                                                                                    
                                        (1) 
    Ошибки нет, фрагмент программы корректный.
                                        
                                                                    
                                        (2) 
    Фрагмент программы содержит ошибку.
                                        
                                                            
                        
                                                                                
                            
Завершится ли когда-нибудь выполнение цикла
в приведенном ниже фрагменте программы?

    int x = 1;
    while (x != 144) {
        x = (x * 13) % 299;
    }


                            
                                                                                                    
                                        (1) 
    Завершится.
                                        
                                                                    
                                        (2) 
    Не завершится.
                                        
                                                            
                        
                                            
                            
Пусть n - переменная типа unsigned char.
Укажите значение n после выполнения оператора
n = ((16 << 3) | (1 << 4) | (3 << 2));

                            
                                                                                                    
                                        (1) 
    78.
                                        
                                                                    
                                        (2) 
    92.
                                        
                                                                    
                                        (3) 
    140.
                                        
                                                                    
                                        (4) 
    156.
                                        
                                                            
                        
                                            
                            
Можно ли сохранить целое число
    1,000,000,000 (миллиард)
в переменной типа float
без потери точности?

                            
                                                                                                    
                                        (1) 
    Можно.
                                        
                                                                    
                                        (2) 
    Нельзя.
                                        
                                                            
                        
                                            
                            
В функции с прототипом

int f(int x);

которая вызывается часто в различных контекстах
и должна работать быстро, нам требуется небольшой 
массив целых чисел размером в 16 элементов.
Какое из перечисленных ниже решений является
наиболее правильным?

                            
                                                                                                    
                                        (1) 
    Используем описание

    static int a[16];

непосредственно перед определением функции f,
вне тела функции.
                                        
                                                                    
                                        (2) 
    Используем описание

    int a[16];

    в начале тела функции f.
                                        
                                                                    
                                        (3) 
    В начале тела функции f
    cоздаем массив в динамической памяти с помощью строки 

    int* a = new int[16];

    а перед выходом из функции освобождаем память с помощью строки

    delete[] a;

                                        
                                                            
                        
                                            
                            
В каком порядке фактические аргументы функции помещаются в стек
при ее вызове в языке C/C++?

                            
                                                                                                    
                                        (1) 
    Сначала в стек помещается первый аргумент функции,
    затем второй и т.д., последний аргумент аргумент функции
    помещается в стек последним.
                                        
                                                                    
                                        (2) 
    Сначала в стек помещается последний аргумент функции,
    затем предпоследний и т.д., первый аргумент функции
    помещается в стек последним.
                                        
                                                                    
                                        (3) 
    В произвольном.
                                        
                                                            
                        
                                            
                            
Последовательность вещественных чисел w
содержит коэффициенты многочлена по возрастанию степеней.
Функция F(w) равна значению производной
многочлена в фиксированной точке t=2. Среди
указанных ниже функций отметьте те, которые являются индуктивным
расширением функции F.

                            
                                                                                                    
                                        (1) 
    Пара
    (значение многочлена в точке t;

    значение производной многочлена в точке t).
                                        
                                                                    
                                        (2) 
    Пара
    (значение производной многочлена в точке t;

    степень многочлена).
                                        
                                                                    
                                        (3) 
    Пара
    (значение многочлена в точке t;

    значение второй производной многочлена в точке t).
                                        
                                                                    
                                        (4) 
    Пара
    (значение производной многочлена в точке t;

    значение второй производной многочлена в точке t).
                                        
                                                            
                        
                                                                                
                            
Рассмотрим следующий фрагмент программы на C/C++:

    double x = 1.0;
    double y = 1e-20;
    double z = y - x + x;
    double t = x - x + y;

Равны ли значения переменных
z и t после его выполнения?

                            
                                                                                                    
                                        (1) 
    Равны.
                                        
                                                                    
                                        (2) 
    Не равны.
                                        
                                                            
                        
                                            
                            
Пусть m=101. Существуют ли два различных целых числа
a, b такие, что 
a²b² (mod m), но 
a±b (mod m)?

                            
                                                                                                    
                                        (1) 
    Да, существуют.
                                        
                                                                    
                                        (2) 
    Нет, не существуют.
                                        
                                                            
                        
                                            
                            
Рассмотрим рекурсивную реализацию алгоритма Евклида:

int gcd1(int m, int n) {
    if (n == 0)
        return m;
    int r = m % n;
    return gcd1(n, r);
}

Укажите, какова будет глубина рекурсии (т.е. какое максимальное
количество кадров локальных переменных функции gcd1
будет размещено одновременно в аппаратном стеке) при следующем
вызове функции:

    int d = gcd1(21, 56);


                            
                                                                                                    
                                        (1) 
    2
                                        
                                                                    
                                        (2) 
    3
                                        
                                                                    
                                        (3) 
    4
                                        
                                                                    
                                        (4) 
    5
                                        
                                                            
                        
                                                
                        
                                                            
                            
Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел.
Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.
Программа должна содержать функцию, которая получает в качестве параметра имя файла  и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.
Задание: посчитать количество чисел, больших предыдущего.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                            
                            
Постановка задачи: программа должна содержать функцию, которая получает в качестве параметров имя массива и его длину (или нескольких массивов, если этого требуют условия задачи) и выполняет необходимые действия.
При решении не разрешается создавать или резервировать в программе дополнительную память, соизмеримую по размерам с объемом исходных данных. То есть, нельзя создавать дополнительные массивы, если это явно не оговорено в задаче.
Функция main должна заполнить массив числами из файла. Для определения длины массива предусматривается два варианта: 1) по значению первого числа в файле, 2) непосредственным подсчетом количества чисел в файле. Результат также выводится в файл.
Задание: сравнить два неупорядоченных  целочисленных массива A и B как числовые множества без повторения  элементов: A = B и A входит B.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                                                                
                            
Сколько всего простых чисел в диапазоне от 100 до 110?

                            
                                                                                                    
                                        4                                    
                                                            
                        
                                                                                
                            
Пусть процессор имеет 32-разрядную архитектуру
и в некоторый момент его работы регистр SP содержит значение
1000. Укажите, какое значение будет содержаться в SP
после выполнения команды возврата из функции return.

                            
                                                                                                    
                                        (1) 
    1001
                                        
                                                                    
                                        (2) 
    1004
                                        
                                                                    
                                        (3) 
    999
                                        
                                                                    
                                        (4) 
    996
                                        
                                                            
                        
                                                                                
                            
Какие смещения относительно регистра FP
(Frame Pointer - указатель кадра)
имеют адреса локальных переменных, описанных внутри функции,
в языке C/C++?

                            
                                                                                                    
                                        (1) 
    Положительные, т.е. адрес любой локальной переменной
    равен FP+S, где константа S>0.
                                        
                                                                    
                                        (2) 
    Отрицательные, т.е. адрес любой локальной переменной
    равен FP-S, где константа S>0.
                                        
                                                                    
                                        (3) 
    Смещения равны нулю.
                                        
                                                            
                        
                                                
                        
                                                            
                            
Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел.
Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.
Программа должна содержать функцию, которая получает в качестве параметра имя файла  и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.
Задание: определить в последовательности действительных чисел количество равных некоторому число X с заданной точностью. Число X и точность ввдятся с клавиатуры.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                            
                            
Постановка задачи: программа должна содержать функцию, которая получает в качестве параметров имя массива и его длину (или нескольких массивов, если этого требуют условия задачи) и выполняет необходимые действия.
При решении не разрешается создавать или резервировать в программе дополнительную память, соизмеримую по размерам с объемом исходных данных. То есть, нельзя создавать дополнительные массивы, если это явно не оговорено в задаче.
Функция main должна заполнить массив числами из файла. Для определения длины массива предусматривается два варианта: 1) по значению первого числа в файле, 2) непосредственным подсчетом количества чисел в файле. Результат также выводится в файл.
Задание: для двух целочисленных массивов построить третий массив, являющийся их объединением как числовых множеств без повторения  элементов. Указать длину получившегося массива.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                                
                        
                                                            
                            
Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел.
Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.
Программа должна содержать функцию, которая получает в качестве параметра имя файла  и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.
Задание: определить номер последнего чмсла, равного заданному X с заданной точностью. Число X и точность ввдятся с клавиатуры.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                            
                            
Постановка задачи: программа должна содержать функцию, которая получает в качестве параметров имя массива и его длину (или нескольких массивов, если этого требуют условия задачи) и выполняет необходимые действия.
При решении не разрешается создавать или резервировать в программе дополнительную память, соизмеримую по размерам с объемом исходных данных. То есть, нельзя создавать дополнительные массивы, если это явно не оговорено в задаче.
Функция main должна заполнить массив числами из файла. Для определения длины массива предусматривается два варианта: 1) по значению первого числа в файле, 2) непосредственным подсчетом количества чисел в файле. Результат также выводится в файл.
Задание: для двух целочисленных массивов построить третий массив, являющийся их пересечением как числовых множеств без повторения  элементов. Указать длину получившегося массива.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                                
                        
                                                            
                            
Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел.
Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.
Программа должна содержать функцию, которая получает в качестве параметра имя файла  и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.
Задание: определить является ли последовательнсть возврастающей или убывающей.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                            
                            
Постановка задачи: программа должна содержать функцию, которая получает в качестве параметров имя массива и его длину (или нескольких массивов, если этого требуют условия задачи) и выполняет необходимые действия.
При решении не разрешается создавать или резервировать в программе дополнительную память, соизмеримую по размерам с объемом исходных данных. То есть, нельзя создавать дополнительные массивы, если это явно не оговорено в задаче.
Функция main должна заполнить массив числами из файла. Для определения длины массива предусматривается два варианта: 1) по значению первого числа в файле, 2) непосредственным подсчетом количества чисел в файле. Результат также выводится в файл.
Задание: определить какое число встречается в массиве целых чисел наибольшее количество раз.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                                
                        
                                                            
                            
Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел.
Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.
Программа должна содержать функцию, которая получает в качестве параметра имя файла  и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.
Задание: определить удовлетворяют ли элементы последовательности данному рекуррентному соотношению c₁*a_i-1+c₂*a_i+c₃*a_i+1=b с заданной точностью. Параметры c_i, b и точность задаются с клавиатуры.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                            
                            
Постановка задачи: программа должна содержать функцию, которая получает в качестве параметров имя массива и его длину (или нескольких массивов, если этого требуют условия задачи) и выполняет необходимые действия.
При решении не разрешается создавать или резервировать в программе дополнительную память, соизмеримую по размерам с объемом исходных данных. То есть, нельзя создавать дополнительные массивы, если это явно не оговорено в задаче.
Функция main должна заполнить массив числами из файла. Для определения длины массива предусматривается два варианта: 1) по значению первого числа в файле, 2) непосредственным подсчетом количества чисел в файле. Результат также выводится в файл.
Задание: удалить из целочисленного  массива одинаковые  значения, т.е. если какое-то  значение встречается  несколько раз (в разных местах массива), то оставить только первый такой элемент, а остальные удалить из массива. Оставшиеся элементы сдвинуть к началу массива, и указать их количество.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                                
                        
                                                            
                            
Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел.
Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.
Программа должна содержать функцию, которая получает в качестве параметра имя файла  и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.
Задание: определить количество различных элементов в неубывающнй последовательности целых чисел.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                            
                            
Постановка задачи: программа должна содержать функцию, которая получает в качестве параметров имя массива и его длину (или нескольких массивов, если этого требуют условия задачи) и выполняет необходимые действия.
При решении не разрешается создавать или резервировать в программе дополнительную память, соизмеримую по размерам с объемом исходных данных. То есть, нельзя создавать дополнительные массивы, если это явно не оговорено в задаче.
Функция main должна заполнить массив числами из файла. Для определения длины массива предусматривается два варианта: 1) по значению первого числа в файле, 2) непосредственным подсчетом количества чисел в файле. Результат также выводится в файл.
Задание: сократить подряд идущие одинаковые элементы целочисленного массива до одного элемента. То есть, если в массиве встречается несколько одинаковых элементов, стоящих рядом, то оставить только один из них, а остальные удалить из массива. Оставшиеся элементы сдвинуть к началу массива, и указать их количество.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                                
                        
                                                            
                            
Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел.
Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.
Программа должна содержать функцию, которая получает в качестве параметра имя файла  и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.
Задание: определить общее количество элементов в постоянных участках последовательности целых чисел.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                            
                            
Постановка задачи: программа должна содержать функцию, которая получает в качестве параметров имя массива и его длину (или нескольких массивов, если этого требуют условия задачи) и выполняет необходимые действия.
При решении не разрешается создавать или резервировать в программе дополнительную память, соизмеримую по размерам с объемом исходных данных. То есть, нельзя создавать дополнительные массивы, если это явно не оговорено в задаче.
Функция main должна заполнить массив числами из файла. Для определения длины массива предусматривается два варианта: 1) по значению первого числа в файле, 2) непосредственным подсчетом количества чисел в файле. Результат также выводится в файл.
Задание: удалить из массива все отрицательные значения, а оставшиеся уплотнить (сдвинуть) с сохранение исходного порядка к началу массива. Указать количество оставшихся значений.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                                
                        
                                                            
                            
Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел.
Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.
Программа должна содержать функцию, которая получает в качестве параметра имя файла  и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.
Задание: определить порядковый номер первого числа, равного максимуму по всей последовательности.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                            
                            
Постановка задачи: программа должна содержать функцию, которая получает в качестве параметров имя массива и его длину (или нескольких массивов, если этого требуют условия задачи) и выполняет необходимые действия.
При решении не разрешается создавать или резервировать в программе дополнительную память, соизмеримую по размерам с объемом исходных данных. То есть, нельзя создавать дополнительные массивы, если это явно не оговорено в задаче.
Функция main должна заполнить массив числами из файла. Для определения длины массива предусматривается два варианта: 1) по значению первого числа в файле, 2) непосредственным подсчетом количества чисел в файле. Результат также выводится в файл.
Задание: циклически сдвинуть элементы массива на K позиций вправо с затратой O(N) действий (N - длина массива).

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                                
                        
                                                            
                            
Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел.
Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.
Программа должна содержать функцию, которая получает в качестве параметра имя файла  и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.
Задание: определить порядковый номер последнего числа, равного минимуму по всей последовательности..

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                            
                            
Постановка задачи: программа должна содержать функцию, которая получает в качестве параметров имя массива и его длину (или нескольких массивов, если этого требуют условия задачи) и выполняет необходимые действия.
При решении не разрешается создавать или резервировать в программе дополнительную память, соизмеримую по размерам с объемом исходных данных. То есть, нельзя создавать дополнительные массивы, если это явно не оговорено в задаче.
Функция main должна заполнить массив числами из файла. Для определения длины массива предусматривается два варианта: 1) по значению первого числа в файле, 2) непосредственным подсчетом количества чисел в файле. Результат также выводится в файл.
Задание: каждый элемент a[i] массива заменить на сумму элементов исходного массива вплоть до него самого включительно, т.е. от 0 до i-го.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                                
                        
                                                            
                            
Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел.
Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.
Программа должна содержать функцию, которая получает в качестве параметра имя файла  и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.
Задание: определить количество чисел, равных минимальному из всей последовательности целых чисел.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                            
                            
Постановка задачи: программа должна содержать функцию, которая получает в качестве параметров имя массива и его длину (или нескольких массивов, если этого требуют условия задачи) и выполняет необходимые действия.
При решении не разрешается создавать или резервировать в программе дополнительную память, соизмеримую по размерам с объемом исходных данных. То есть, нельзя создавать дополнительные массивы, если это явно не оговорено в задаче.
Функция main должна заполнить массив числами из файла. Для определения длины массива предусматривается два варианта: 1) по значению первого числа в файле, 2) непосредственным подсчетом количества чисел в файле. Результат также выводится в файл.
Задание: каждый  элемент массива заменить на полусумму его соседних элементов (кроме первого и последнего).

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                                
                        
                                                            
                            
Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел.
Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.
Программа должна содержать функцию, которая получает в качестве параметра имя файла  и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.
Задание: найти среднее квадратичное отклонение от среднего арифметического в последовательности.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                            
                            
Постановка задачи: программа должна содержать функцию, которая получает в качестве параметров имя массива и его длину (или нескольких массивов, если этого требуют условия задачи) и выполняет необходимые действия.
При решении не разрешается создавать или резервировать в программе дополнительную память, соизмеримую по размерам с объемом исходных данных. То есть, нельзя создавать дополнительные массивы, если это явно не оговорено в задаче.
Функция main должна заполнить массив числами из файла. Для определения длины массива предусматривается два варианта: 1) по значению первого числа в файле, 2) непосредственным подсчетом количества чисел в файле. Результат также выводится в файл.
Задание: назовем x-отрезком группу подряд идущих элементов массива, каждый из которых равен x. Для заданного числа x заменить элементы каждого x-отрезка на полусумму элементов, прилегающих к этому отрезку справа и слева. Если x-отрезок расположен в начале или конце массива, считать второй крайний элемент равным нулю.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                                
                        
                                                            
                            
Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел.
Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.
Программа должна содержать функцию, которая получает в качестве параметра имя файла  и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.
Задание: найти величину максимального отклонения элементов последовательности от их среднего арифметического.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                            
                            
Постановка задачи: программа должна содержать функцию, которая получает в качестве параметров имя массива и его длину (или нескольких массивов, если этого требуют условия задачи) и выполняет необходимые действия.
При решении не разрешается создавать или резервировать в программе дополнительную память, соизмеримую по размерам с объемом исходных данных. То есть, нельзя создавать дополнительные массивы, если это явно не оговорено в задаче.
Функция main должна заполнить массив числами из файла. Для определения длины массива предусматривается два варианта: 1) по значению первого числа в файле, 2) непосредственным подсчетом количества чисел в файле. Результат также выводится в файл.
Задание: сгруппировать положительные элементы  массива в его начале, а отрицательные  - в конце  с сохранением их порядка.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                                
                        
                                                            
                            
Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел.
Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.
Программа должна содержать функцию, которая получает в качестве параметра имя файла  и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.
Задание: найти количество элементов последовательности больших среднего арифметическго.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                            
                            
Постановка задачи: программа должна содержать функцию, которая получает в качестве параметров имя массива и его длину (или нескольких массивов, если этого требуют условия задачи) и выполняет необходимые действия.
При решении не разрешается создавать или резервировать в программе дополнительную память, соизмеримую по размерам с объемом исходных данных. То есть, нельзя создавать дополнительные массивы, если это явно не оговорено в задаче.
Функция main должна заполнить массив числами из файла. Для определения длины массива предусматривается два варианта: 1) по значению первого числа в файле, 2) непосредственным подсчетом количества чисел в файле. Результат также выводится в файл.
Задание: Назовем массив из N целых чисел счастливым, если существует такое 0 < k < N , что сумма элементов с индексами от 0 до k-1 совпадает с суммой элементов с индексами от k до N-1. Определить является ли данный массив счастливым.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                                
                        
                                                            
                            
Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел.
Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.
Программа должна содержать функцию, которая получает в качестве параметра имя файла  и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.
Задание: найти количество возрастающих участков последовательности.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                            
                            
Постановка задачи: программа должна содержать функцию, которая получает в качестве параметров имя массива и его длину (или нескольких массивов, если этого требуют условия задачи) и выполняет необходимые действия.
При решении не разрешается создавать или резервировать в программе дополнительную память, соизмеримую по размерам с объемом исходных данных. То есть, нельзя создавать дополнительные массивы, если это явно не оговорено в задаче.
Функция main должна заполнить массив числами из файла. Для определения длины массива предусматривается два варианта: 1) по значению первого числа в файле, 2) непосредственным подсчетом количества чисел в файле. Результат также выводится в файл.
Задание: назовем массив из целых чисел плотным, если множество значений элементов массива полностью заполняет некоторый отрезок [a, b] (рассматривются  целые значения). Определить является ли данный массив плотным.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                                
                        
                                                            
                            
Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел.
Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.
Программа должна содержать функцию, которая получает в качестве параметра имя файла  и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.
Задание: найти сумму четных эдементов во всех возрастающих участках последовательности целых чисел.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                            
                            
Постановка задачи: программа должна содержать функцию, которая получает в качестве параметров имя массива и его длину (или нескольких массивов, если этого требуют условия задачи) и выполняет необходимые действия.
При решении не разрешается создавать или резервировать в программе дополнительную память, соизмеримую по размерам с объемом исходных данных. То есть, нельзя создавать дополнительные массивы, если это явно не оговорено в задаче.
Функция main должна заполнить массив числами из файла. Для определения длины массива предусматривается два варианта: 1) по значению первого числа в файле, 2) непосредственным подсчетом количества чисел в файле. Результат также выводится в файл.
Задание: получить массив биномиальных  коэффициентов для степени N, последовательно вычисляя строки треугольника Паскаля (можно использовать только один массив).

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                                
                        
                                                            
                            
Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел.
Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.
Программа должна содержать функцию, которая получает в качестве параметра имя файла  и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.
Задание: определить количество возрастающих и убывающих участков в последовательности.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                            
                            
Постановка задачи: программа должна содержать функцию, которая получает в качестве параметров имя массива и его длину (или нескольких массивов, если этого требуют условия задачи) и выполняет необходимые действия.
При решении не разрешается создавать или резервировать в программе дополнительную память, соизмеримую по размерам с объемом исходных данных. То есть, нельзя создавать дополнительные массивы, если это явно не оговорено в задаче.
Функция main должна заполнить массив числами из файла. Для определения длины массива предусматривается два варианта: 1) по значению первого числа в файле, 2) непосредственным подсчетом количества чисел в файле. Результат также выводится в файл.
Задание: элементы массива не убывают. Двоичным поиском определить позицию, где в этот массив можно вставить данное число x.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                                
                        
                                                            
                            
Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел.
Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.
Программа должна содержать функцию, которая получает в качестве параметра имя файла  и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.
Задание: найти количество элементов в наибольшем постоянном участке последовательности целых чисел.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                            
                            
Постановка задачи: программа должна содержать функцию, которая получает в качестве параметров имя массива и его длину (или нескольких массивов, если этого требуют условия задачи) и выполняет необходимые действия.
При решении не разрешается создавать или резервировать в программе дополнительную память, соизмеримую по размерам с объемом исходных данных. То есть, нельзя создавать дополнительные массивы, если это явно не оговорено в задаче.
Функция main должна заполнить массив числами из файла. Для определения длины массива предусматривается два варианта: 1) по значению первого числа в файле, 2) непосредственным подсчетом количества чисел в файле. Результат также выводится в файл.
Задание: даны два неубывающих массива. Построить третий неубывающий массив, который является объединением первых двух (элементы могут повторяться).

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                                
                        
                                                            
                            
Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел.
Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.
Программа должна содержать функцию, которая получает в качестве параметра имя файла  и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.
Задание: найти количество элементов в постоянном участке последовательности целых чисел с наибольшей суммой элементов этого участка.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                            
                            
Постановка задачи: программа должна содержать функцию, которая получает в качестве параметров имя массива и его длину (или нескольких массивов, если этого требуют условия задачи) и выполняет необходимые действия.
При решении не разрешается создавать или резервировать в программе дополнительную память, соизмеримую по размерам с объемом исходных данных. То есть, нельзя создавать дополнительные массивы, если это явно не оговорено в задаче.
Функция main должна заполнить массив числами из файла. Для определения длины массива предусматривается два варианта: 1) по значению первого числа в файле, 2) непосредственным подсчетом количества чисел в файле. Результат также выводится в файл.
Задание: выполнить следующее преобразование. Элементы с четными индексами сгруппировать в начале массива с сохранением их исходного порядка относительно друг друга, а элементы с нечетными индексами сгрупировать в конце массива также с сохранением их исходного порядка.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                                
                        
                                                            
                            
Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел.
Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.
Программа должна содержать функцию, которая получает в качестве параметра имя файла  и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.
Задание: найти длину возрастающего участка последовательности с наибольшим количеством элементов.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                            
                            
Постановка задачи: программа должна содержать функцию, которая получает в качестве параметров имя массива и его длину (или нескольких массивов, если этого требуют условия задачи) и выполняет необходимые действия.
При решении не разрешается создавать или резервировать в программе дополнительную память, соизмеримую по размерам с объемом исходных данных. То есть, нельзя создавать дополнительные массивы, если это явно не оговорено в задаче.
Функция main должна заполнить массив числами из файла. Для определения длины массива предусматривается два варианта: 1) по значению первого числа в файле, 2) непосредственным подсчетом количества чисел в файле. Результат также выводится в файл.
Задание: Выполнить следующее преобразование массива длины N . Элементы с индексами i <= [(N + 1)/2] переместить на позиции с четными индексами с сохранением их исходного порядка относительно друг друга, а оставшиеся элементы (i > [(N + 1)/2])  разместить на позициях с нечетными индексами также  с сохранением  их исходного порядка. Т.е. начальная и конечная половины массива "перемешиваются"  чередованием элементов.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                                
                        
                                                            
                            
Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел.
Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.
Программа должна содержать функцию, которая получает в качестве параметра имя файла  и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.
Задание: найти наибольшую сумму возрастающего участка последовательности (т.е. максимум из сумм элементов по каждому возрастающему участку).

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                            
                            
Постановка задачи: программа должна содержать функцию, которая получает в качестве параметров имя массива и его длину (или нескольких массивов, если этого требуют условия задачи) и выполняет необходимые действия.
При решении не разрешается создавать или резервировать в программе дополнительную память, соизмеримую по размерам с объемом исходных данных. То есть, нельзя создавать дополнительные массивы, если это явно не оговорено в задаче.
Функция main должна заполнить массив числами из файла. Для определения длины массива предусматривается два варианта: 1) по значению первого числа в файле, 2) непосредственным подсчетом количества чисел в файле. Результат также выводится в файл.
Задание: пусть в массиве последовательно записаны цифры некоторого длинного десятичного числа. Реализовать функции “прибавляющие единицу”  и “вычитающие единицу” из такого числа. (для реализации  переноса из “старшего разряда” можно заранее запасти 1 лишний элемент в массиве).

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                                
                        
                                                            
                            
Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел.
Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.
Программа должна содержать функцию, которая получает в качестве параметра имя файла  и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.
Задание: найти среднее арифметическое локальных максимумов последовательности (локальный максимум - элемент строго больший своих соседей).

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                                
                        
                                                            
                            
Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел.
Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.
Программа должна содержать функцию, которая получает в качестве параметра имя файла  и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.
Задание: найти максимальное количество элементов между двумя соседними локальными минимумами последовательности (локальный минимум - элемент строго меньший своих соседей).

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                                
                        
                                                            
                            
Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел.
Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.
Программа должна содержать функцию, которая получает в качестве параметра имя файла  и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.
Задание: найти среднее арифметическое значений элементов последовательности целых чисел, учитывая значения в постоянных участказ только один раз.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                                
                        
                                                            
                            
Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел.
Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.
Программа должна содержать функцию, которая получает в качестве параметра имя файла  и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.
Задание: найти среднее арифметическое, взяв только по одному значению из каждого постоянного участка последовательности.

                            
                                                                                                    
                                        Свой ответ                                    
                                                            
                        
                                                
                        
                                                            
                            
Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел.
Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности.
Программа должна содержать функцию, которая получает в качестве параметра имя файла  и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл.
Задание: найти максимальную сумму трех подряд идущих элементов последовательности.

                            
                                                                                                    
                                        Свой ответ