Программирование - ответы
Количество вопросов - 342
Назовем элемент xiчисловой последовательностиw={x1, x2, ..., xn}локальным максимумом,если он строго больше соседних элементов (для крайнихэлементов рассматривается только 1 сосед, элемент последовательностидлины 1 считается локальным максимумом).Пусть F(w)=числу локальных максимумов в w.Какие из перечисленных ниже функцийявляются индуктивным расширением функции F?Укажите все правильные варианты.
Двоичный код, представляющий число типа double,хранит знак, смещенный порядок и дробную частьдвоичного представления мантиссы.Чему равен смещенный порядок в представлении числа 6.0?
К трехзначным десятичным числам (строкам длины 3 из десятичныхцифр) применяется алгоритм RADIX-сортировки сначала по младшей цифре,затем по средней и в конце по старшей. Исходный массив содержит следующиечисла:232, 102, 307, 901, 835, 215, 105, 301, 323, 811.
Каким будет содержимое массива после выполнения первых двух шаговсортировки (т.е. после сортировки по младшей и средней цифрам)?
Алгоритм быстрой сортировки реализован с помощью комбинированнойсхемы, использующей рекурсию и цикл while;рекурсия применяется лишь к меньшему сегменту массива,разделенного на части функцией partition.Алгоритм применяется к массиву размером миллион. Может лиглубина рекурсии равняться 30?
Какова степень интерполяционного многочлена,построенного по трем узламx0, x1, x2,принимающего в этих узлах значенияy0, y1, y2?
В массиве, содержащем 1000 элементов,выполняется последовательный поиск элемента x.При этом x содержитсяв массиве с вероятностью 0.75. Сколько в среднем операций сравнениябудет выполнено?
По логике задачи нам требуется использовать большой массив вещественныхчисел, размер которого не превышает миллион элементов. Какие из перечисленныхниже решений являются корректными?
Какой максимальный адрес байта в 32-разряднойархитектуре?
Какие переменные располагаются в языке C/C++ в стеке?
При представлении целых чисел в формате Big Endianбайты внутри слова нумеруются слева направо, в форматеLittle Endian - справа налево. Пусть компьютер используетархитектуру Big Endian. Укажите, чему будет равно значениепеременной n в результате выполненияследующего фрагмента программы: int k = (-2); int n; signed char *p = (signed char *) &k; n = *p;
Рассмотрим следующий фрагмент программы на C/C++: double x = 1.0; double y = 1e-20; double z = x + y - x; double t = x - x + y;
Равны ли значения переменныхz и t после его выполнения?
Какая из конструкций цикла потенциально безопаснее?
К массиву a длины 28 применяетсявосходящая схема двунаправленного алгоритма сортировкислиянием с использованием дополнительной памяти — массива bтакого же размера. В каком из этих массивов мы получим результат послеокончательного шага слияния, т.е. будет ли вызванафункция copyArray, чтобыскопировать результат из вспомогательного массиваb в массив a?
Массив a размера 4 содержитэлементы 4, 3, 2, 1 в указанном порядке.К нему применяется алгоритм пузырьковой сортировки,использующий сравнение элементов с помощью функции compareи обмен элементов с помощью функции swap.Сколько раз будет вызвана функция swap?
Пусть переменные p, q, nописаны следующим образом: double *p, *q; int n;
Отметьте, какие из перечисленных ниже выражений языка C/C++являются корректными:
Алгоритм быстрой сортировки реализован с помощью комбинированнойсхемы, использующей рекурсию и цикл 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. Какой может бытьмаксимальная глубина рекурсии?(Под глубиной рекурсии мы подразумеваем количесто раз,которое функция может вызвать сама себя в цепочке вызовов.Если рекурсивный вызов отсутствует, то мы считаем глубину рекурсиинулевой.)
Есть 4 монеты, известно, что все они имеют различные веса.Веса двух монет можно сравнить, используя весы-коромысло.Какое минимальное количество взвешиваний во всех случаях достаточно,чтобы упорядочить монеты по возрастанию их веса?
Является ли индуктивной функция, которая последовательностикоэффициентов многочлена по убыванию степеней ставитв соответствие пару чисел:(степень многочлена, интеграл многочлена по отрезку [0, 1])?
В алгоритме сортировки слиянием "In Place Merge Sort",не использующем дополнительной памяти,применяется функция mergeBlocksслияния двух упорядоченных блоков, т.е. подмассивов длиныm и n, реализованная рекурсивно.За какое время работает эта функция?
Дан массив длины 21, требуется циклическисдвинуть его элементы вправо на 6 позиций.Существует ли алгоритм, который решает эту задачу,выполняя 22 операции копирования?Имеются в виду операции копированияодного элемента массива в другой, элемента массива в простуюпеременную, одной простой переменной в другую.
Укажите, какие из приведенных ниже строк языка C/C++корректно описывают объекты языка.
Пусть m=101. Существуют ли два различных целых числаa, b такие, что a2b2 (mod m), но a±b (mod m)?
Рассмотрим рекурсивную реализацию алгоритма Евклида: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);
Пусть дан массив 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?
Чему будет равно значение переменной nв результате выполнения следующего фрагмента программы?Процессор имеет 32-разрядную архитектуру. double a[4][3]; int n, m; n = (int)(a+1); m = (int) a; n -= m;
Пусть процессор имеет 32-разрядную архитектуру.Рассмотрим функцию f(x, y) языка C/C++ соследующим прототипом:void f(int x, int y);
Чему равен адрес второго фактического аргументаy функции f относительно регистраFP (Frame Pointer - указатель кадра) во время выполнениятела функции?
Функция F последовательности цифр в десятичной записи числаn ставит в соответстие единицу, если n делится на 15,и ноль в противном случае. Какая из перечисленныхниже функций на последовательности десятичных цифр числа nявляется индуктивным расширением функции F?
Мы хотим реализовать функцию, которая находитиндекс максимального элемента вещественного массива.Отметьте, какие из возможных прототипов данной функциикорректны.
Алгоритм быстрой сортировки реализован с помощью комбинированнойсхемы, использующей рекурсию и цикл while, а такжевспомогательную функцию partition,которая разделяет текущий отрезок массива на 3 части(элементы, меньшие либо равные медиане, медиана,элементы, большие либо равные медиане):void quickSort(double* a, int n) { if (n <= 1) { return; } else if (n == 2) { if (a[0] > a[1]) swap(&(a[0]), &(a[1])); return; } int beg = 0; int k = n; while (k > 1) { int m = k / 2; partition(a+beg, k, &m); int left = m; int right = k - left - 1; if (left <= right) { // Рекурсивно применяем алг. к левой части quickSort(a+beg, left); beg += left + 1; k -= left + 1; } else { // Рекурсивно применяем алг. к правой части quickSort(a+beg+m+1, right); k -= right + 1; } }}Сколько раз будет вызвана функция partition при выполненииалгоритма быстрой сортировки для массива размера 95?Дайте наиболее точную оценку снизу этого числа.
Пусть расположенный в статической памятицелочисленный массив 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);
Какой из перечисленных языков высокого уровня являетсянаиболее современным?
В каком случае выполняется тело цикла "while"?
Сколько раз будет выполнено тело цикла в приведеннойниже программе? Многоточием обозначен фрагмент,не содержащий переменной x.int x = 100;while (x >= 0) { . . . x = x-1;}
Пусть - некоторое условие, не зависящееот значения переменной x.Укажите, чему может быть равно значение xв результате выполнения следующего фрагмента программы(многоточием обозначен текст, не содержащийпеременной x):int x = 1;while () { . . . if () { x = 2; } else { x = 3; }}
Чему равно значение целочисленной переменной xв результате выполнения приведенного ниже фрагмента программы? int x = 1; while (x < 11) { x = -2*x + 11; }
Завершится ли когда-нибудь выполнение циклав приведенном ниже фрагменте программы? int x = 1; while (x != 56) { x = (x * 11) % 253; }
Какой самый первый объектно-ориентированный язык программирования?
Где следует описывать прототипы функций?
Камень, отпущенный с высоты 6-го этажа, падает на землюпримерно за 2 сек. За какое примерно время упадет камень с высоты12-го этажа (в 2 раза большей)? Сопротивлением воздуха пренебречь.
Функция с прототипом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);
Каков диапазон целочисленного типа unsigned char?
Отметьте, какие из перечисленных ниже целочисленных значенийпомещаются в переменную типа unsigned int(для удобства триады цифр разделяются запятыми).
Чему равно значение выражения (-23)%6*10в языке C?
Укажите минимальное значение x > 0типа signed char, удовлетворяющее неравенствуx+x <= 0?
Среди перечисленных ниже чисел отметьте простые.
Отметьте, что из перечисленного ниже является дурным стилемпрограммирования на C/C++ (т.е. чего никогда не следует делать).
Пусть m=143. Существуют ли два различных целых числаa, b такие, что a2b2 (mod m), но a±b (mod m)?
Сколько раз будет выполнено тело цикла в алгоритмеЕвклидаint gcd(int m, int n) { while (n != 0) { int r = m % n; m = n; n = r; } return m;}при следующих входных значениях аргументов:m=13, n=17?
Укажите, чему будет равно значение переменной kв результате выполнения следующего фрагмента программы: int n=11, k, *p; p = &n; ++*p; k = 4-*p*2+n;
Укажите, чему будет равно значение переменной nв результате выполнения следующего фрагмента программы: double *p = 1000; double *q = 2000; int n = q - p;
Пусть переменные p, q описаны следующим образом: double *p, q[100];
Отметьте, какие из перечисленных ниже выражений языка C/C++являются корректными:
Какой из перечисленных ниже регистров процессора содержитадрес команды, которая будет выполнятся на очередномшаге работы процессора?
Пусть процессор имеет 32-разрядную архитектуруи в некоторый момент его работы регистр SP содержит значение1000. Укажите, какое значение будет содержаться в SPпосле выполнения команды вызова функции call 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);
Пусть расположенный в статической памятицелочисленный массив 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);
Пусть переменные a, p,q, n описаны следующим образом: double a[16]; double *p; const double *q; int n;
Отметьте, какие из приведенных ниже операторов языка C/C++корректны.
Мы хотим реализовать функцию product, которая находитпроизведение элементов вещественного массива aдлины n.Отметьте, какие из возможных прототипов данной функциикорректны.
Рассмотрим следующий фрагмент программы на С++: static double *a = new double[10]; a[0] = 3.7;
Где хранится значение выражения "a[0]" (т.е.число 3.7)?
Среди указанных ниже операторов языка C/C++отметьте корректные.
Какой объект описан в следующей строке программына C/C++? double a[20][30];
Чему будет равно значение переменной nв результате выполнения следующего фрагмента программы?Процессор имеет 32-разрядную архитектуру. double (*a)[4]; int n, m; n = (int)(a+1); m = (int) a; n -= m;
Укажите, какие из приведенных ниже строк языка C/C++корректно описывают объекты языка.
Эквивалентны ли в языке C/C++ типы Callback и Action,заданные в приведенном ниже фрагменте программы?typedef void (*Callback)(char *);typedef void (*Action)(void *);
Назовем функцию y = f(p) на последовательности p элементов некоторого типа индуктивной, если при добавлении в конецпоследовательности pеще одного элемента x новое значение функцииy1 = f(p&x) можно вычислить, зная толькостарое значение y и добавленный элемент x.Среди перечисленных ниже функций на последовательностях вещественныхчисел укажите индуктивные.
Следующий фрагмент программы вычисляет разность dмежду максимальным и минимальным элементами непустой числовой последовательности.xmin = ...xmax = ...цикл пока в последовательности есть непрочитанные элементы|выполнять| прочесть очередной элемент посл-ти в <вых: x>| если x < xmin| | то xmin = x| конец если|| если x > xmax| | то xmax = x| конец есликонец циклаd = xmax - xmin
Какими значениями надо инициализировать переменныеxmin и xmax, чтобы программаработала правильно?
Левым нейтральным элементом (левой единицей) для бинарной операции называется элемент e такой, что для всякогодругого элемента x "произведение" e наx равно x:e x = x. Какие элементы будут нейтральнымидля операций произведения и минимума чисел соответственно?
Какие константы можно в практическом программировании использоватьв качестве воображаемого значения "минус бесконечность" при работе свещественными числами типа double? Укажите все правильныеварианты.
Является ли индуктивной функция, которая последовательностивещественных чисел ставит в соответствие сумму ее первогои последнего элементов?
Функция F последовательности цифр в десятичной записи числаn ставит в соответстие единицу, если n делится на 7,и ноль в противном случае. Какая из приведенныхниже функций на последовательности десятичных цифр числа nявляется индуктивным расширением функции F?
Сколько умножений будет выполнено при вычислениизначения многочлена степени 3, коэффициенты которогозаданы в последовательности по убыванию степеней,при использовании схемы вычисления индуктивной функции?
Пусть w - последовательностьцелых чисел, F(W) - максимальная изсумм нескольких подряд идущих элементовпоследовательности w.Например, для последовательностиw={1, -2, 3, 4, -1, 5, -2, -3, 4}максимальную сумму образуют элементы с третьего по шестой:F(w)=3+4-1+5=11.Какие из перечисленных ниже функцийявляются индуктивным расширением функции F?Укажите все правильные варианты.
Последовательность вещественных чисел wсодержит коэффициенты многочлена по возрастанию степеней.Функция F(w) равна значению производноймногочлена в фиксированной точке t=2. Средиуказанных ниже функций отметьте те, которые являются индуктивнымрасширением функции F.
Укажите, в какие моменты работы программы выполняетсяинвариант цикла.
Пусть целочисленная переменная 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;}
Рассмотрим следующую функцию, аргументами которойявляются два целых неотрицательных числа: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;}Какое условие является инвариантом цикла?
Какое утверждение является инвариантом для следующегофрагмента программы (т.е. из справедливости утверждениядо выполнения фрагмента программы вытекает справедливость утвержденияпосле выполнения)? Предполагается, что n > 0. double r, x; int n; . . . r *= -x; r *= n/(n+1); ++n;
Оценить сверху время работы (т.е. количествовыполнений тела цикла) алгоритма Евклидавычисления наибольшего общего делителя двух целых чисел: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}
Пусть 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]
В массиве, содержащем 1000 элементов,выполняется последовательный поиск элемента x.При x содержитсяв массиве с вероятностью равна 0.1.Сколько в среднем операций сравнениябудет выполнено?
Пусть дан массив 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?
Пусть элементы массива aнестрого возрастают (соседние элементы могут быть равными).Дано произвольное значение x, требуетсянайти максимальный индекс i такой, чтоa[i] <= x. Используется идея алгоритмабинарного поиска. Каким должен быть инвариант цикла,в котором рассматривается основной случай после отбрасыванияисключительных ситуаций?(Условие завершения циклаend == beg+1.)
Программа, использующая бинарный поиск, ищетэлемент в массиве длины миллион в среднем заодну тысячную секунды. Сколько примерно временипотребуется на поиск, если мы заменим алгоритм поискас бинарного на последовательный?
Программа, использующая последовательный поиск, ищетэлемент в массиве длины миллион в среднем заодну секунду. Сколько примерно временипотребуется на поиск, если мы заменим алгоритм поискас последовательного на бинарный?
Массив a размера 4 содержитэлементы 4, 1, 3, 2 в указанном порядке.К нему применяется алгоритм пузырьковой сортировки,использующий сравнение элементов с помощью функции compareи обмен элементов с помощью функции swap.Сколько раз будет вызвана функция swap?
Алгоритм пузырьковой сортировки упорядочивает массивиз 10 тысяч элементов примерно за 1 секунду. За какое примерновремя тот же алгоритм упорядочит массив из 100 тысяч элементов?
Массив длины 5 содержит элементы2, 1, 5, 4, 3 в указанном порядке.К нему применяетсяалгоритм сортировки методом прямого выбора,использующий сравнение элементов с помощью функции compareи обмен элементов с помощью функции swap.Сколько раз будет вызвана функция swap?
Для разных массивов фиксированной длины 1000 применяютсяалгоритмы пузырьковой сортировки и сортировкиметодом прямого выбора. Какой из этих двухалгоритмов работает в среднем быстрее?
В турнире участвуют 4 баскетбольные команды,все матчи проводятся последовательнов одном зале. По результатам турнира команды должны быть упорядочены всоответствии с их силой. В зависимости от исхода матчей турнир можетзавершиться раньше или позже; для всякого расписания турнираможно определить максимально возможное количество матчей.Приведите оценку снизу максимального количества матчейдля всех возможных расписаний турниров 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;}Правильна ли подобная реализация, или она может привестик катастрофическому замедлению алгоритма быстройсортировки в некоторых случаях?
Алгоритм быстрой сортировки использует вспомогательную функцию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;}Правильна ли подобная реализация, или она может привестик катастрофическому замедлению алгоритма быстройсортировки в некоторых случаях?
Алгоритм быстрой сортировки реализован с помощью комбинированнойсхемы, использующей рекурсию и цикл 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?Дайте наиболее точную оценку снизу этого числа.
Алгоритм быстрой сортировки упорядочивает случайный массивиз тысячи элементов в среднем за 0.01 секунду. За какое примерновремя тот же алгоритм упорядочит случайный массивиз миллиона элементов?
Алгоритм быстрой сортировки упорядочивает случайный массивиз миллиона элементов в среднем за 40 секунд. За какое примерновремя тот же алгоритм упорядочит случайный массивиз тысячи элементов?
Алгоритм быстрой сортировки реализован с помощью комбинированнойсхемы, использующей рекурсию и цикл 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. Какой может бытьмаксимальная глубина рекурсии?(Под глубиной рекурсии мы подразумеваем количесто раз,которое функция может вызвать сама себя в цепочке вызовов.Если рекурсивный вызов отсутствует, то мы считаем глубину рекурсиинулевой.)
Назовем алгоритм сортировки оптимальным, если онработает за время O(n log2 n) даже присамом плохом входе. Среди перечисленных ниже алгоритмовсортировки отметьте оптимальные.
Целочисленный массив содержит элементы30, 25, 23, 15, 10, 20, 16, 7, 12, 5, 11, 9в указанном порядке. Образуют ли они бинарную кучу (пирамиду)?
Пусть целочисленный массив содержит элементы11, 18, 10, 7, 15, 9, 8в указанном порядке. Услове пирамиды нарушаетсятолько для элемента 11, стоящего в вершине пирамиды.Для исправления пирамиды выполняется процедура просеивания,при которой элемент 11 опускается на свое место.Каким будет содержимое массива после окончания этой процедуры?
К целочисленному массиву применяется алгоритм сортировкикучей. Пусть после первого этапа алгоритма пирамида(бинарная куча) уже построена и массив содержит элементы20, 17, 12, 2, 10, 4, 8в указанном порядке. Затем выполняется второй этап сортировки.На его первом шаге начальный и конечный элементы массиваменяются местами, от пирамиды отрезается правая нижняя ветка(т.е. последний элемент массива), затем элемент в вершинепирамиды просеивается, благодаря чему восстанавливаетсяусловие пирамиды. Каким будет содержимое массива поокончании этого шага?
К целочисленному массиву применяется алгоритм сортировкикучей. На первом этапе из элементов массива строитсяпирамида (бинарная куча) путем просеивания элементовпо бинарному дереву в порядке справа налево и снизу вверх.Пусть вначале массив содержал элементы4, 5, 6, 7, 1, 2, 3в указанном порядке.Каким будет содержимое массивапосле построения пирамиды?
Алгоритм сортировки называется стабильным, если онсохраняет относительный порядок равных элементов.Среди перечисленных ниже алгоритмов сортировки(имеются в виду их классические варианты) отметьте все стабильные.
К трехзначным десятичным числам (строкам длины 3 из десятичныхцифр) применяется алгоритм RADIX-сортировки сначала по младшей цифре,затем по средней и в конце по старшей. Исходный массив содержит следующиечисла:122, 232, 171, 198, 401, 035, 077, 201, 199, 400.
Каким будет содержимое массива после выполнения первых двух шаговсортировки (т.е. после сортировки по младшей и средней цифрам)?
Сортируемый массив содержит составные ключи из 20десятичных цифр (например, идентификаторы банковских счетов).Массив имеет длину 1000. Надо выбрать один из двух алгоритмовсортировки: сортировку кучей HeapSort или RADIX-сортировку.Какой из двух алгоритмов будет в среднем работать быстреев данной ситуации?
Функция merge слияния двух упорядоченных массивовприменяется к двум массивам длины 100 и 1000. Какое максимальноечисло сравнений может быть сделано при выполнении этой функции?
Рассмотрим алгоритм сортировки слиянием с использованиемдополнительной памяти. Используется нисходящая (рекурсивная)схема реализации алгоритма. Алгоритм применяется к массивудлины 1000000 (миллион). Какова максимально возможнаяглубина рекурсии? Дайте наиболее точную оценку.
К массиву a длины 50 применяетсявосходящая схема двунаправленного алгоритма сортировкислиянием с использованием дополнительной памяти — массива bтакого же размера. В каком из этих массивов мы получим результат послеокончательного шага слияния, т.е. будет ли вызванафункция copyArray, чтобыскопировать результат из вспомогательного массиваb в массив a?
К массиву a длины 20 применяетсявосходящая схема двунаправленного алгоритма сортировкислиянием с использованием дополнительной памяти.В процессе выполнения алгоритма многократновызывается функция merge слияния двух упорядоченныхмассивов длины n и m. Каковыдлины массивов, которые сливаются при самом последнем вызовефункции merge?
К массиву a длины 12 применяется восходящая схемадвунаправленного алгоритма сортировкислиянием с использованием дополнительной памятитакого же размера. Сколько раз будет вызванафункция слияния двух упорядоченных массивов merge?
К массиву a длины 11 применяется восходящая схемадвунаправленного алгоритма сортировкислиянием с использованием дополнительной памятитакого же размера. Сколько раз будет вызванафункция слияния двух упорядоченных массивов merge?
В алгоритме сортировки слиянием "In Place Merge Sort",не использующем дополнительной памяти, применяетсяфункция mergeBlocksслияния двух упорядоченных блоков, т.е. подмассивов длиныm и n, реализованная рекурсивно.Пусть сумма длин блоков m+n=1000. Какой может бытьмаксимальная суммарная длина блоков при рекурсивном вызовефункции mergeBlocks на первом шаге?
Дан массив длины 11, требуется циклическисдвинуть его элементы вправо на 3 позиции. Какое минимальноечисло операций копирования выполняется в любом алгоритме,решающем данную задачу? Имеются в виду операции копированияодного элемента массива в другой, элемента массива в простуюпеременную, одной простой переменной в другую.
Дан массив длины 12, требуется циклическисдвинуть его элементы влево на 5 позиций. Какое минимальноечисло операций копирования выполняется в любом алгоритме,решающем данную задачу? Имеются в виду операции копированияодного элемента массива в другой, элемента массива в простуюпеременную, одной простой переменной в другую.
Дан массив длины 26, требуется циклическисдвинуть его элементы вправо на 6 позиций.Существует ли алгоритм, который решает эту задачу,выполняя 28 операций копирования?Имеются в виду операции копированияодного элемента массива в другой, элемента массива в простуюпеременную, одной простой переменной в другую.
Дан массив длины n, содержащийэлементы некоторого упорядоченного типа (их можносравнивать между собой, определяя,какой из них больше или их равенство).Требуется удалить из массива повторяющиеся элементы так,чтобы каждый элемент содержался в массиве ровно 1 раз(при этом n может уменьшиться).Приведите асимптотическуюоценку времени работы наилучшего алгоритма, решающего даннуюзадачу.
На 3 вакансии имеется 10 претендентов.Сколько способов выбора возможно?
Из восьми человек надо выбрать четверых.Сколько способов выбора возможно?
Сколько единиц в двоичной записи числа 10?
Для записи n-значных чисел в системе счисления с основаниемb требуется n разрядов,каждый из которых может находитьсяв b состояниях. Таким образом, суммарное число состоянийравно произведению n*b.Рассмотрим двоичную (b=2), троичную(b=3) и десятичную (b=10) системы счисления.Какая из нихнаиболее экономна по суммарному числу состояний для записичисел в диапазоне 0..N,где N - некоторое достаточно большое число?
В алгоритме получения записи числа nв системе счисления с основанием bмы вычисляем цифры числа справа налево,начиная с последней цифры. На очередном шагемы делим n с остатком на b, получаячастное q и остаток r;остаток представляет очередную цифру числа в порядке справа налево.Затем мы переменной nприсваиваем значение частного q,и процесс повторяется,пока n не станет равным нулю.Сколько раз будет выполнена операция деленияпри переводе числа 1000000 (миллион)в шестнадцатеричную систему счисления?
Рассмотрим следующую запись числа в двоичной системе счисления(для удобства запись разбита запятыми на триады):100,001,010,110,111,101,011.
Укажите восьмеричную запись этого числа.
Рассмотрим максимальное по абсолютной величинецелое число, которое в языке C/C++ представимотипом short. Четное оно или нечетное?
Какой двоичный код представляетчисло -10 для типа signed char?
Пусть n - переменная типа unsigned char.Укажите значение n после выполнения оператораn = ((16 << 3) | (1 << 4) | (3 << 2));
При представлении целых чисел в формате Big Endianбайты внутри слова нумеруются слева направо, в форматеLittle Endian - справа налево. Укажите, в каких случаяхиз перечисленных ниже используется формат Big Endian.
Пусть для представления вещественных чиселмы используем десятичные целые числа с фиксированной позициейдесятичной точки, отделяющей ровно 3 знака дробной части.Например, целое число 1414 представляетвещественное число 1.414. Рассмотрим два числас фиксированной точкой, представленные целыми числами100001 и 20050. Каким числом будет представлено их произведение?
При представлении вещественных чисел в плавающей формемы выражаем вещественное число x в виде x = s 2e m,
где s - знак числа, принимающий значениеплюс или минус единица,e - порядок, представляющий собойцелое число (положительное, 0 или отрицательное),m - мантисса, представляющая собойвещественное число в диапазоне1 m < 2.Чему равны порядок и мантисса для числа 0.1?
Двоичный код, представляющий число типа float,хранит знак, смещенный порядок и дробную частьдвоичного представления мантиссы. Сколько битовотводится под каждый элемент представления?
Двоичный код, представляющий число типа double,хранит знак, смещенный порядок и дробную частьдвоичного представления мантиссы.Чему равен смещенный порядок в представлении числа 0.3?
Двоичный код, представляющий число типа double,хранит знак, смещенный порядок и дробную частьдвоичного представления мантиссы.Сколько единичных битов в двоичном представлениидробной части мантиссы для числа 15.0?
Можно ли сохранить целое число 1,000,000,000 (миллиард)в переменной типа floatбез потери точности?
Рассмотрим следующий фрагмент программы на C/C++: double x = 1.0; double y = 1e-20; double z = -x + x + y; double t = x + y - x;
Равны ли значения переменныхz и t после его выполнения?
Рассмотрим следующую программу на 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.)Что будет напечатано в результате ее выполнения?
Функция ln(z) (натуральный логарифм z) представляетсяв виде степенного ряда следующим образом: ln(1+x) = x - x2/2 + x3/3 - x4/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?Укажите все правильные ответы из числа перечисленных ниже.
Формула Бинома Ньютона дает следующее разложение в ряддля функции "квадратный корень из z":(1+x)0.5 = sqrt(1+x) = 1 + 0.5 x + 0.5(-0.5)/2! x2 + 0.5(-0.5)(-1.5)/3! x3 + 0.5(-0.5)(-1.5)(-2.5)/4! x4 + ...
(мы обозначили z=1+x). Этот ряд сходится лишь для значений x, по абсолютной величине не превосходящих 1, а эффективно вычислятьего сумму можно только для еще более узкого интервала значений x. Каким свойством функции sqrt(z)удобнее всего воспользоваться, чтобы свести ее вычисление к суммированию ряда?
Функция arctg(x) (ее также обозначают arctg или atan)представляется рядом Тейлора: arctg(x) = x - x3/3 + x5/5 - x7/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?
Рассмотрим следующий фрагмент программы на C++: double a[5][3]; const double *p = &(a[0][0]); const double *q = &(a[2][2]); int n = q - p;
Чему равно значение nпосле выполнения этого фрагмента?
Рассмотрим реализацию матрицы целых чисел,размеры которой определяютсяв процессе работы программы, через массив указателей на началострок, захватываемый в динамической памяти. Каждая строкатакже представляет собой отдельный массив вдинамической памяти: 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)?
Рассмотрим реализацию матрицы вещественных чиселразмера 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; } } }}
Чему равен ранг следующей матрицы:0 1 1 11 1 1 11 1 1 0
Какое максимальное число операций деления можетбыть выполнено в алгоритме Гаусса в процессе приведенияк ступенчатому виду прямоугольной матрицы, содержащей3 строки и 4 столбца?
Сколько раз в алгоритме Гаусса будет выполнена операцияперестановки местами двух строк(с изменением знака одной из них) при приведении кступенчатому виду следующей матрицы:1 2 3 40 1 2 32 5 8 11
Пусть 2 многочлена p(x) и q(x)степени 4 принимают в четырех попарно различных узлахx0, x1,x2, x3 одни и те жезначенияy0, y1,y2, y3. Следует ли изэтого, что многочлены p(x) и q(x)равны?
Интерполяционный многочлен в форме Ньютона, построенныйпо узламx0, x1, ..., xn ипринимающий в этих узлах значенияy0, y1, ..., yn,представляется формулойpn(x) = a0 + a1(x-x0) + a1(x-x0)(x-x1) + ... + an(x-x0)(x-x1)...(x-xn-1)
Сколько действий нужно выполнить, чтобы вычислить все его коэффициентыa0, a1, ..., an?
Пусть неизвестная функция определена на отрезке [a, b],причем на концах отрезка заданы ее значенияy0=f(a),y1=f(b),а также значения ее производнойy'0=f'(a),y'1=f'(b).Всегда ли существует многочлен степени 2 такой, чтона концах отрезка его значения и значения его производнойсовпадают со значениями и производной функции?
Пусть f(x) - гладкая функция,заданная на отрезке [a, b], третья производная которойпо абсолютной величине не превышает некоторой константы.Для приближенного вычисления интеграла от этой функции мыприменяем формулу Симпсона (парабол), разбивая отрезок[a, b] на 2*n равных частей.Какова точность вычисления интеграла в зависимости от n?
Пусть функцияf(x) = p*x2 + q*x + r(многочлен степени 2), заданная на отрезке [a, b],принимает значенияy0, y1, y2в точках a, (a+b)/2, b(на концах и в середине отрезка). Чему равен интеграл от этойфункции по отрезку [a, b]?
Двоичный код, представляющий число типа double,хранит знак, смещенный порядок и дробную частьдвоичного представления мантиссы.Сколько единичных битов в двоичном представлениидробной части мантиссы для числа 10.0?
Алгоритм быстрой сортировки упорядочивает случайный массивиз 128 элементов в среднем за 0.0001 секунду. За какое примерновремя тот же алгоритм упорядочит случайный массивиз 1024 элементов?
Пусть n - переменная типа unsigned char.Укажите значение n после выполнения оператораn = (((3 << 4) | 3) & 0xF2);
Чему равно значение целочисленной переменной xв результате выполнения приведенного ниже фрагмента программы? int x = 64; while (x*x > 100) { x = -(x / 2); }
Какой максимальный адрес машинного слова в 32-разряднойархитектуре?
Укажите, какие из приведенных ниже строк языка C/C++корректно описывают объекты языка.
Сколько всего простых чисел в диапазоне от 100 до 110?
Какие константы можно в практическом программировании использоватьв качестве воображаемого значения "минус бесконечность" при работе сцелыми числами типа int? Укажите все правильныеварианты.
Последовательность вещественных чисел wсодержит коэффициенты многочлена по убыванию степеней.Функция F(w) равна значению второй производноймногочлена в фиксированной точке t=2. Средиуказанных ниже функций отметьте те, которые являются индуктивнымрасширением функции F.
Сколько раз будет выполнено тело цикла в алгоритмеЕвклидаint gcd(int m, int n) { while (n != 0) { int r = m % n; m = n; n = r; } return m;}при следующих входных значениях аргументов:m=24, n=30?
Оценить сверху время работы (т.е. количествовыполнений тела цикла) алгоритма быстрого возведения в степень: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;}
Чему равно значение выражения (-12)%5*10в языке C?
Дан массив длины n, требуется циклическисдвинуть его элементы вправо на одну позицию. Какое минимальноечисло операций копирования выполняется в любом алгоритме,решающем данную задачу? Имеются в виду операции копированияодного элемента массива в другой, элемента массива в простуюпеременную, одной простой переменной в другую.
Где описан прототип функции printf,используемой для печати различных значений по заданному формату?
Назовем функцию y = f(p) на последовательности p элементов некоторого типа индуктивной, если при добавлении в конецпоследовательности pеще одного элемента x новое значение функцииy1 = f(p&x) можно вычислить, зная толькостарое значение y и добавленный элемент x.Среди перечисленных ниже функций на последовательностях вещественныхчисел укажите индуктивные.
Пусть переменные a, p,q, n описаны следующим образом: double a[10]; double *p; const double *q; int n;
Отметьте, какие из приведенных ниже операторов языка C/C++корректны.
Двоичный код, представляющий число типа double,хранит знак, смещенный порядок и дробную частьдвоичного представления мантиссы. Сколько битовотводится под каждый элемент представления?
Пусть элементы массива 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Какое утверждение являетсяинвариантом этого цикла?
Алгоритм быстрой сортировки использует вспомогательную функцию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;}Правильна ли подобная реализация, или она может привестик катастрофическому замедлению алгоритма быстройсортировки в некоторых случаях?
Левым нейтральным элементом (левой единицей) для бинарной операции называется элемент e такой, что для всякогодругого элемента x "произведение" e наx равно x:e x = x. Какие элементы будут нейтральнымидля операций суммы и максимума чисел соответственно?
В алгоритме сортировки слиянием "In Place Merge Sort",не использующем дополнительной памяти, применяетсяфункция mergeBlocksслияния двух упорядоченных блоков, т.е. подмассивов длиныm и n, реализованная рекурсивно.Пусть сумма длин блоков m+n=512.При реализации функции mergeBlocksвызывается функция перестановки двух блоковswapBlocks. Какой может бытьмаксимальная суммарная длина блоков переставляемых блоков?
Рассмотрим следующий фрагмент программы на С++: static double *p = 0; . . . p = new double[100]; *p = 1.5;
Где хранится значение выражения "*p" (т.е.число 1.5)?
К целочисленному массиву применяется алгоритм сортировкикучей. Пусть после первого этапа алгоритма пирамида(бинарная куча) уже построена и массив содержит элементы30, 20, 25, 10, 7, 19, 5в указанном порядке. Затем выполняется второй этап сортировки.На его первом шаге начальный и конечный элементы массиваменяются местами, от пирамиды отрезается правая нижняя ветка(т.е. последний элемент массива), затем элемент в вершинепирамиды просеивается, благодаря чему восстанавливаетсяусловие пирамиды. Каким будет содержимое массива поокончании этого шага?
Рассмотрим алгоритм сортировки слиянием с использованиемдополнительной памяти. Используется восходящаясхема реализации алгоритма. Алгоритм применяется к массивудлины 100. На каждом шаге сливаются парысоседних упорядоченных подмассивов длиныне больше k и получаются упорядоченные подмассивыдлины не больше 2k; первый шаг выполняется приk=1.Сколько всего шагов будет выполнено?
Рассмотрим реализацию матрицы вещественных чиселразмера 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 при этом останутся на своем месте?
К массиву a длины 30 применяетсявосходящая схема двунаправленного алгоритма сортировкислиянием с использованием дополнительной памяти.В процессе выполнения алгоритма многократновызывается функция merge слияния двух упорядоченныхмассивов длины n и m. Каковыдлины массивов, которые сливаются при самом последнем вызовефункции merge?
При вычислении (x+y)7раскрываются скобки и приводятся подобные члены.Чему будет равен коэффициент приx3y4?
Для записи n-значных чисел в системе счисления с основаниемb требуется n разрядов,каждый из которых может находитьсяв b состояниях. Таким образом, суммарное число состоянийравно произведению n*b.Рассмотрим восьмеричную (b=8), десятичную (b=10)и шестнадцатеричную (b=16) системы счисления.Какая из них наиболее экономна по суммарному числу состоянийдля записи чисел в диапазоне 0..N,где N - некоторое достаточно большое число?
Какие из перечисленных ниже объектно-ориентированныхязыков программирования поддерживаются фирмой Microsoft?
Пусть дан массив 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?
Что можно сказать об условии, указанном в заголовке цикла "while",в процессе выполнения тела цикла?
Сколько раз будет выполнено тело цикла в приведеннойниже программе? Многоточием обозначен фрагмент,не содержащий переменной x.int x = 0;while (x < 1000) { . . . x = x+1;}
Укажите, чему может быть равно значение переменной zв результате выполнения следующего фрагмента программы:z := 0;while (x < y) { . . . if (z > 100) { z = 10; x = y; } else { z = 20; x = y - 1; }}
Завершится ли когда-нибудь выполнение циклав приведенном ниже фрагменте программы? int x = 1; while (x != 144) { x = (x * 13) % 299; }
Какие из из перечисленных ниже объектно-ориентированныхязыков программирования продолжают линию языка С,используя близкий синтаксис?
Отметьте, в каких из трех конструкций цикла языка Cтело цикла может ни разу не выполняться.
Цель - реализовать функцию fallTime,вычисляющую время падения камня с высотыh. Какой из приведенных ниже фрагментов кодаправильно решает задачу?
Функция с прототипомdouble root(double a, double b, double eps);
находит корень фиксированной функцииdouble f(double x);
на отрезке [a, b] методом деления отрезка пополамс точностью eps. Сколько примерно раз будет выполненотело цикла при поиске корня, когда используется следующий вызов: double x = root(1., 2., 0.001);
Каков диапазон целочисленного типа short?
Отметьте, какие из перечисленных ниже целочисленных значенийпомещаются в переменную типа unsigned short
Сколько всего простых чисел, меньших 30?
Какие объекты языка C/C++ располагаются вдинамической памяти?
В функции с прототипомint f(int x);
которая вызывается часто в различных контекстахи должна работать быстро, нам требуется небольшой массив целых чисел размером в 16 элементов.Какое из перечисленных ниже решений являетсянаиболее правильным?
Числами Ферма Fk называются числа вида22k+1. Например,F1=5, F2=17, F3=257,F4=65537. Отметьте, какие изприведенных ниже утверждений являются верными.
Укажите, чему будет равно значение переменной kв результате выполнения следующего фрагмента программы: int n = (-5), k, *p; p = &n; --*p; k = 4-*p*5+n;
Что содержит регистр PC (Program Counter - счетчик команд, впроцессоре Intel 80x86 он обозначается как IP - InstructionPointer) в момент выполнения процессором очередной команды?
В каком порядке фактические аргументы функции помещаются в стекпри ее вызове в языке C/C++?
Рассмотрим рекурсивную реализацию алгоритма Евклида: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);
Пусть расположенный в статической памятицелочисленный массив 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);
Рассмотрим следующий фрагмент программы на С/С++: static int *p = NULL; . . . p = (int *) malloc(sizeof(int)); *p = 123;
Где хранится значение выражения "*p" (т.е.число 123)?
Среди указанных ниже операторов языка C/C++отметьте корректные.
Назовем функцию y = f(p) на последовательности p элементов некоторого типа индуктивной, если при добавлении в конецпоследовательности pеще одного элемента x новое значение функцииy1 = f(p&x) можно вычислить, зная толькостарое значение y и добавленный элемент x.Среди перечисленных ниже функций на последовательностях вещественныхчисел укажите индуктивные.
Следующий фрагмент программы для последовательностивещественных чисел вычисляет количество n элементов,строго меньших предыдущего, причем самый первый элемент такжеучитывается (считается меньше предыдущего).Например, для последовательности{2, 1, 3, 5, 4} ответ n=3(элементы 2, 1 и 4).n = 0x0 = ...цикл пока в последовательности есть непрочитанные элементы|выполнять| прочесть очередной элемент посл-ти в <вых: x>| если x < x0| | то n = n + 1| конец если| x0 = xконец цикла
Каким значением надо инициализировать переменнуюx0, чтобы программа работала правильно?
Сколько умножений выполняется в схеме Горнера привычислении значения многочлена степени 3?
Последовательность вещественных чисел wсодержит коэффициенты многочлена по возрастанию степеней.Функция F(w) равна значению второй производноймногочлена в фиксированной точке t=2. Средиуказанных ниже функций отметьте те, которые являются индуктивнымрасширением функции F.
Выполняется ли инвариант цикла в процессе выполнениятела цикла?
Пусть целочисленная переменная 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;}
Рассмотрим следующую функцию, аргументами которойявляются два целых неотрицательных числа: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);}Какое условие является инвариантом цикла?(Через НОД и НОК обозначены наибольший общий делитель инаименьшее общее кратное.)
Оцените примерно, во сколько раз алгоритм бинарного поискаработает быстрее алгоритма последовательного поискадля массива из 64 миллионов элементов.
Массив a размера 4 содержитэлементы 4, 2, 1, 3 в указанном порядке.К нему применяется алгоритм пузырьковой сортировки,использующий сравнение элементов с помощью функции compareи обмен элементов с помощью функции swap.Сколько раз будет вызвана функция swap?
Алгоритм пузырьковой сортировки упорядочивает массивиз 10 тысяч элементов примерно за 1 секунду. За какое примерновремя тот же алгоритм упорядочит массив из миллиона элементов?
Массив длины 5 содержит элементы5, 4, 1, 2, 3 в указанном порядке.К нему применяетсяалгоритм сортировки методом прямого выбора,использующий сравнение элементов с помощью функции compareи обмен элементов с помощью функции swap.Сколько раз будет вызвана функция swap?
Пусть целочисленный массив содержит элементы10, 16, 12, 8, 11, 7, 5в указанном порядке. Услове пирамиды нарушаетсятолько для элемента 10, стоящего в вершине пирамиды.Для исправления пирамиды выполняется процедура просеивания,при которой элемент 10 опускается на свое место.Каким будет содержимое массива после окончания этой процедуры?
К целочисленному массиву применяется алгоритм сортировкикучей. Пусть после первого этапа алгоритма пирамида(бинарная куча) уже построена и массив содержит элементы16, 12, 11, 8, 7, 10, 6в указанном порядке. Затем выполняется второй этап сортировки.На его первом шаге начальный и конечный элементы массиваменяются местами, от пирамиды отрезается правая нижняя ветка(т.е. последний элемент массива), затем элемент в вершинепирамиды просеивается, благодаря чему восстанавливаетсяусловие пирамиды. Каким будет содержимое массива поокончании этого шага?
Алгоритм сортировки называется стабильным, если онсохраняет относительный порядок равных элементов.Среди перечисленных ниже алгоритмов сортировки(имеются в виду их классические варианты) отметьте все стабильные.
Функция merge слияния двух упорядоченных массивовприменяется к двум массивам длины 100 и 1000. Какое минимальноечисло сравнений может быть сделано при выполнении этой функции?
К массиву a длины 64 применяетсявосходящая схема двунаправленного алгоритма сортировкислиянием с использованием дополнительной памяти — массива bтакого же размера. В каком из этих массивов мы получим результат послеокончательного шага слияния, т.е. будет ли вызванафункция copyArray, чтобыскопировать результат из вспомогательного массиваb в массив a?
К массиву a длины 12 применяетсявосходящая схема двунаправленного алгоритма сортировкислиянием с использованием дополнительной памяти.В процессе выполнения алгоритма многократновызывается функция merge слияния двух упорядоченныхмассивов длины n и m. Каковыдлины массивов, которые сливаются при самом последнем вызовефункции merge?
Дан массив длины n, содержащийэлементы некоторого упорядоченного типа (их можносравнивать между собой, определяя,какой из них больше или их равенство).Рассмотрим задачу нахождения множества различныхэлементов, содержащихся в массиве. Приведите асимптотическуюоценку времени работы наилучшего алгоритма, решающего даннуюзадачу.
В алгоритме получения записи числа nв системе счисления с основанием bмы вычисляем цифры числа справа налево,начиная с последней цифры. На очередном шагемы делим n с остатком на b, получаячастное q и остаток r;остаток представляет очередную цифру числав порядке справа налево.Затем мы переменной nприсваиваем значение частного q,и процесс повторяется, пока n не станет равным нулю.Сколько раз будет выполнена операция деленияпри переводе числа 2000000 (два миллиона)в восьмеричную систему счисления?
Рассмотрим следующую запись числав двоичной системе счисления(для удобства запись разбита запятыми на четверки):1000,1010,0010,0110,1111,0101,0011.
Укажите шестнадцатеричную запись этого числа.
Какой двоичный код представляетчисло -31 для типа short?(Для удобства двоичная запись разбита запятыми на четверки.)
Пусть для представления вещественных чиселмы используем десятичные целые числа с фиксированной позициейдесятичной точки, отделяющей ровно 2 знака дробной части.Например, целое число 314 представляетвещественное число 3.14. Рассмотрим два числас фиксированной точкой, представленные целыми числами240 и 20001. Каким числом будет представлено их произведение?
При представлении вещественных чисел в плавающей формемы выражаем вещественное число x в виде x = s 2e m,
где s - знак числа, принимающий значениеплюс или минус единица,e - порядок, представляющий собойцелое число (положительное, 0 или отрицательное),m - мантисса, представляющая собойвещественное число в диапазоне1 m < 2.Чему равны порядок и мантисса для числа 12?
Рассмотрим 8 байтов, в которых записан некоторыйдвочный код. Всегда ли он представляетвещественное число, записанное в плавающей форме,т.е. значение типа double?
Функция arcsin(x) представляется рядом Тейлора: arcsin(x) = x +(1/2)x3/3 + (1/2)(3/4)x5/5 + (1/2)(3/4)(5/6)x7/7 + ...
Этот ряд сходится лишь для значений x, по модулю меньшихединицы, причем вблизи единицы сходится очень медленно и точность его вычисления низка. Поэтому эффективно вычислять сумму ряда можно лишь для x, по модулюсущественно меньших единицы - например, |x|<0.75. Каким свойством функции arcsin можно воспользоваться,чтобы свести ее вычисление к суммированию ряда для значеийx в интервале |x|<0.75? Укажите всевозможные правильные решения из числа перечисленных ниже.(Предполагается, что мы умеем быстро и точно вычислять квадратный кореньsqrt(z), а также знаем константу pi.)
Рассмотрим следующий фрагмент программы на 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после выполнения этого фрагмента?
Рассмотрим реализацию матрицы вещественных чисел,размеры которой определяютсяв процессе работы программы, через массив указателей на началастрок, захватываемый в динамической памяти. Каждая строкатакже представляет собой отдельный массив вдинамической памяти: 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 1 1 11 -1 1 -11 1 -1 -1
Сколько раз в алгоритме Гаусса будет выполнена операцияперестановки местами двух строк(с изменением знака одной из них) при приведении кступенчатому виду следующей матрицы:0 1 2 34 5 6 71 2 3 4
Пусть неизвестная функция определена на отрезке [a, b],причем на концах отрезка заданы ее значенияy0=f(a),y1=f(b),а также значения ее производнойy'0=f'(a),y'1=f'(b).Нужно приблизить функцию многочленом так, чтобы на концах отрезкаего значения, а также значения его производной совпадали созначениями и производной функции. Какой должна бытьстепень такого многочлена? (Укажите минимальнуюстепень, достаточную для решения этой задачи.)
Пусть f(x) - гладкая функция,заданная на отрезке [a, b], производная которойпо абсолютной величине не превышает некоторой константы.Для приближенного вычисления интеграла от этой функции мыприменяем формулу прямоугольников, разбивая отрезок[a, b] на n равных частей.Какова точность вычисления интеграла в зависимости от n?
Приближенное значение интеграла по отрезку [a, b]от функции y = f(x) вычисляется по формуле 1/6 * (y0 + 4*y1 + y2) * (b - a).где y0 = f(a), y1 = f((a+b)/2), y2 = f(b).Пусть f(x) - многочлен некоторой степени.Какова максимальная степень многочленов, для которых эта формулавсегда дает точное значение интеграла?
Интерполяционный многочлен в форме Ньютона, построенныйпо узламx0, x1, ..., xn,представляется формулойpn(x) = a0 + a1(x-x0) + a1(x-x0)(x-x1) + ... + an(x-x0)(x-x1)...(x-xn-1)
Сколько действий необходимо выполнить, чтобы вычислить его значениев некоторой точке x=t?
Рассмотрим алгоритм сортировки слиянием с использованиемдополнительной памяти. Используется нисходящая (рекурсивная)схема реализации алгоритма. Алгоритм применяется к массивудлины 1000. Какова максимально возможнаяглубина рекурсии? Дайте наиболее точную оценку среди приведенных ниже.
Какие переменные располагаются в языке C/C++ в статической памяти?
Пусть для представления вещественных чиселмы используем десятичные целые числа с фиксированной позициейдесятичной точки, отделяющей ровно 3 знака дробной части.Например, целое число 2718 представляетвещественное число 2.718. Рассмотрим два числас фиксированной точкой, представленные целыми числами10500 и 1010. Каким числом будет представлено их произведение?
Прыгун в длину совершает прыжок на 7 метров, при этомвремя полетной фазы составляет 0.7 сек, а высота траектории 60 см.До какого примерно значения нужно увеличить высоту траекториипрыжка, чтобы при той же горизонтальной скорости достичьрезультата 8 метров?
Рассмотрим следующий фрагмент программы на 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после выполнения этого фрагмента?
Сколько различных значений xтипа unsigned char удовлетворяют равенствуx+x+x+x == 0?
Функция с прототипом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);
Чему будет равно значение переменной nв результате выполнения следующего фрагмента программы?Процессор имеет 32-разрядную архитектуру. double a[10][2]; int n, m; n = (int)(a+1); m = (int) a; n -= m;
Пусть 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
Формула Бинома Ньютона дает следующее разложение в ряддля функции "кубический корень из z" (обозначим ее croot(z)):(1+x)1/3 = croot(1+x) = 1 + (1/3)x + (1/3)(-2/3)/2! x2 + (1/3)(-2/3)(-5/3)/3! x3 + (1/3)(-2/3)(-5/3)(-8/3)/4! x4 + ...
(мы сделали замену z=1+x). Этот ряд сходится лишь для значений x, по абсолютной величине не превосходящих 1, а эффективно вычислятьего сумму можно только для еще более узкого интервала значений x. Каким свойством функции croot(z)=z1/3удобнее всего воспользоваться, чтобы свести ее вычисление для положительных значений z к суммированию ряда?
В массиве, содержащем 1000 элементов,выполняется последовательный поиск элемента x.При этом x содержитсяв массиве с вероятностью 0.25. Сколько в среднем операций сравнениябудет выполнено?
Сколько раз будет выполнено тело цикла в алгоритмеЕвклидаint gcd(int m, int n) { while (n != 0) { int r = m % n; m = n; n = r; } return m;}при следующих входных значениях аргументов:m=17, n=22?
Алгоритм сортировки называется стабильным,если он сохраняет взаимный порядок равных элементов.(Такое определение имеет смысл при сортировке массива записей,состоящих из нескольких полей, которые сравниваются лишьпо значению одного конкретного поля - например, записи о людяхсортируются по их именам, при этом могут быть однофамильцы.)Является ли алгоритм быстрой сортировки стабильным?
Укажите корректные адреса машинных слов в 32-разряднойархитектуре среди перечисленных ниже:
В чем главный недостаток первоначальной версии языка Pascal?
Пусть 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; }}
Чему равно значение целочисленной переменной xв результате выполнения приведенного ниже фрагмента программы? int x = 1; while (x < 100) x = -(x * 2); }
Завершится ли когда-нибудь выполнение циклав приведенном ниже фрагменте программы? int x = 1; while (x != 120) { x = (x * 7) % 490; }
Где описан прототип функции sqrt(x), вычисляющийквадратный корень вещественного числа x?
Отметьте, какие из перечисленных ниже целочисленных значенийпомещаются в переменную типа int (для удобстватриады цифр разделяются запятыми).
Сколько различных значений xтипа int удовлетворяют равенствуx+x == 0?
Среди перечисленных ниже чисел отметьте простые.
Пусть переменные p, q, nописаны следующим образом: double *p, q[100], *r; int n;
Отметьте, какие из перечисленных ниже строк программы на C/C++являются корректными:
Пусть процессор имеет 32-разрядную архитектуруи в некоторый момент его работы регистр SP содержит значение1000. Укажите, какое значение будет содержаться в SPпосле выполнения команды pop X.
Пусть переменные a, p,q, n описаны следующим образом: double a[10]; double *p; const double *q; int n;
Отметьте, какие из приведенных ниже операторов языка C/C++корректны.
Среди указанных ниже операторов языка C/C++отметьте корректные.
Какая из приведенных ниже строк языка С/С++ описываетмассив указателей на тип char?
Является ли индуктивной функция, которая последовательностикоэффициентов многочлена по возрастанию степеней ставитв соответствие пару чисел:(степень многочлена, интеграл многочлена по отрезку [0, 1])?
Рассмотрим следующий фрагмент программы:утверждение: A(x)цикл пока B(x)| инвариант: A(x)| x := T(x)конец цикла
Здесь через A(x) и B(x)обозначены условия, зависящие от переменной x.Какое условие выполняется по окончании цикла?
Какое утверждение является инвариантом для следующегофрагмента программы (т.е. из справедливости утверждениядо выполнения фрагмента программы вытекает справедливость утвержденияпосле выполнения)? Предполагается, чтоn не меньше k.Восклицательным знаком обозначается операция вычисления факториала. int n, k, c; . . . c *= (n+1); c /= (n+1-k); ++n;
Оценить сверху время работы (т.е. количествовыполнений тела цикла) алгоритмаприблизительного вычисления логарифма: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;}
Пусть элементы массива aнестрого возрастают (соседние элементы могут быть равными).Дано произвольное значение x, требуетсянайти минимальный индекс i такой, чтоa[i] >= x. Используется идея алгоритмабинарного поиска. Каким должен быть инвариант цикла,в котором рассматривается основной случай после отбрасыванияисключительных ситуаций?(Условие завершения циклаend == beg+1.)
Для конкретного массива длины 1000 применяютсяалгоритмы пузырьковой сортировки и сортировкиметодом прямого выбора. Какой из этих двухалгоритмов работает быстрее?
Целочисленный массив содержит элементы20, 18, 10, 15, 7, 7, 9, 8, 10, 6, 4, 5в указанном порядке. Образуют ли они бинарную кучу (пирамиду)?
К целочисленному массиву применяется алгоритм сортировкикучей. На первом этапе из элементов массива строитсяпирамида (бинарная куча) путем просеивания элементовпо бинарному дереву в порядке справа налево и снизу вверх.Пусть вначале массив содержал элементы1, 2, 3, 4, 5, 6, 7в указанном порядке.Каким будет содержимое массивапосле построения пирамиды?
Алгоритм сортировки называется стабильным, если онсохраняет относительный порядок равных элементов.Среди перечисленных ниже алгоритмов сортировки(имеются в виду их классические варианты) отметьте все стабильные.
RADIX-сортировка применяется к составным ключам длины k,длина сортируемого массива равна n. Какова асимптотическаяоценка времени работы алгоритма?
К массиву a длины 10 применяется восходящая схемадвунаправленного алгоритма сортировкислиянием с использованием дополнительной памятитакого же размера. Сколько раз будет вызванафункция слияния двух упорядоченных массивов merge?
Дан массив длины 15, требуется циклическисдвинуть его элементы вправо на 6 позиций.Существует ли алгоритм, который решает эту задачу,выполняя 18 операций копирования?Имеются в виду операции копированияодного элемента массива в другой, элемента массива в простуюпеременную, одной простой переменной в другую.
Дан массив длины n, содержащийэлементы некоторого упорядоченного типа (их можносравнивать между собой, определяя,какой из них больше или их равенство).Требуется определить, сколько различныхэлементов содержится в массиве.Приведите асимптотическуюоценку времени работы наилучшего алгоритма, решающего даннуюзадачу.
Сколько единиц в двоичной записи числа 11?
Рассмотрим следующую запись числав троичной системе счисления(для удобства запись разбита запятыми на четверки):1201,1122,2111,2010.
Укажите запись этого числав системе счисления с основанием 9.
Рассмотрим максимальное по абсолютной величинецелое число, которое в языке C/C++ представимо типом int.Положительное оно или отрицательное?
Пусть n - переменная типа unsigned char.Укажите значение n после выполнения оператораn = ((127 >> 2) & (15 << 2));
Можно ли сохранить целое число типа int(4 байта) в переменной типа double без потериточности? То есть, если мы имеем целочисленнуюпеременную n типа int,то она не изменит своего значения в результе выполненияследующего фрагмента программы: int n; . . . double x = (double) n; n = (int) x;
Двоичный код, представляющий число типа double,хранит знак, смещенный порядок и дробную частьдвоичного представления мантиссы.Сколько единичных битов в двоичном представлениидробной части мантиссы для числа 0.125?
Можно ли сохранить целое число123456789012345678
в переменной типа doubleбез потери точности?
Рассмотрим следующий фрагмент программы на C/C++: double x = 1.0; double y = 1e-20; double z = y - x + x; double t = x - x + y;
Равны ли значения переменныхz и t после его выполнения?
Рассмотрим следующую программу на 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.)Что будет напечатано в результате ее выполнения?
Функция arctg(x) раскладываетсяв ряд Тейлора следующим образом: arctg(x) = x - x3/3 + x5/5 - x7/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 ее можно применять?Укажите все правильные ответы из числа перечисленных ниже.
Функция arctg(x) (ее также обозначают arctan или atan)представляется рядом Тейлора: arctg(x) = x - x3/3 + x5/5 - x7/7 + ...
Этот ряд сходится лишь для значений x, по модулю не превосходящихединицы, а эффективно вычислять его можно лишь для x, по модулюсущественно меньших единицы - например, |x|<0.5.(Для значений x, по модулю близких к единице и не превосходящихединицу, ряд сходится, но очень медленно, а точность вычисления его суммыневысока.)Какие способы вычисления функции arctan(x) для "плохих"значений x возможны? Укажите все разумные способы изчисла перечисленных ниже.(Предполагается, что мы умеем быстро и точно вычислять квадратный кореньsqrt(z), а также знаем константу pi.)
Сколько раз в алгоритме Гаусса будет выполнена операцияперестановки местами двух строк(с изменением знака одной из них) при приведении кступенчатому виду следующей матрицы:1 2 3 40 1 2 32 7 10 14
Какова степень интерполяционного многочлена,построенного по четырем узламx0, x1,x2, x3,принимающего в этих узлах значенияy0, y1,y2, y3?
Интерполяционный многочлен в форме Ньютона, построенныйпо узламx0, x1, ..., xn ипринимающий в этих узлах значенияy0, y1, ..., yn,представляется формулойpn(x) = a0 + a1(x-x0) + a1(x-x0)(x-x1) + ... + an(x-x0)(x-x1)...(x-xn-1)
Пусть коэффициентыa0, a1, ..., anмногочлена pn(x)уже вычислены. Мы добавляем новый узел xn+1,значение в котором должно быть равно yn+1,и строим новый многочлен Ньютона pn+1(x)на единицу большей степени по узламx0, x1, ..., xn, xn+1и значениямy0, y1, ..., yn, yn+1.Сколько действий нужно выполнить, чтобы вычислить всекоэффициенты нового многочлена?
Пусть f(x) - гладкая функция,заданная на отрезке [a, b], вторая производная которойпо абсолютной величине не превышает некоторой константы.Для приближенного вычисления интеграла от этой функции мыприменяем формулу трапеций, разбивая отрезок[a, b] на n равных частей.Какова точность вычисления интеграла в зависимости от n?
Пусть функцияf(x) = p*x2 + q*x + r(многочлен степени 2) задана на отрезке [a, b].Пусть отрезок [a, b] разделен на 4 равных части;обозначим концы этих отрезков черезx0, x1,x2, x3, x4: h = (b-a)/4, xi = a+i*h, i = 0,1,2,3,4.Обозначим yi = f(xi).Чему равен интеграл функции f(x)по отрезку [a, b]? Отметьте все правильные ответы.
Рассмотрим максимальное по абсолютной величинецелое число, которое в языке C/C++ представимотипом signed char.Чему оно равно?
Формула Бинома Ньютона дает следующее разложение в ряддля функции "квадратный корень из z":(1+x)0.5 = sqrt(1+x) = 1 + 0.5 x + 0.5(-0.5)/2! x2 + 0.5(-0.5)(-1.5)/3! x3 + 0.5(-0.5)(-1.5)(-2.5)/4! x4 + ...
(мы обозначили 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?Укажите все правильные ответы из числа перечисленных ниже.
Есть 6 монет, известно, что все они имеют различные веса.Веса двух монет можно сравнить, используя весы-коромысло.Требуется упорядочить монеты по возрастанию их веса.Можно ли придумать такой алгоритм сортировки монет по весу,при котором в любом случае будет сделано не больше 9 взвешиваний?
Пусть процессор имеет 32-разрядную архитектуруи в некоторый момент его работы регистр SP содержит значение1000. Укажите, какое значение будет содержаться в SPпосле выполнения команды push X.
В алгоритме получения записи числа nв системе счисления с основанием bмы вычисляем цифры числа справа налево,начиная с последней цифры. На очередном шагемы делим n с остатком на b, получаячастное q и остаток r;остаток представляет очередную цифру числав порядке справа налево.Затем мы переменной nприсваиваем значение частного q,и процесс повторяется, пока n не станет равным нулю.Сколько раз будет выполнена операция деленияпри переводе числа 1000 (тысяча)в троичную систему счисления?
Чему равно значение выражения (-17)%3*10в языке C?
Какую из конструкций цикла в языке C удобнее всего использоватьдля реализации арифметического цикла, в котором тело циклапоследовательно выполняется для всех значений переменной цикла,представляющих арифметическую прогрессию?
Укажите, чему будет равно значение переменной kв результате выполнения следующего фрагмента программы: int n = (-7), k, *p; p = &n; ++*p; k = 3-*p*3+n;
Укажите, чему будет равно значение переменной nв результате выполнения следующего фрагмента программы: double *p = 1000; p += 1000; int n = (int) p;
Пусть процессор имеет 32-разрядную архитектуруи в некоторый момент его работы регистр SP содержит значение1000. Укажите, какое значение будет содержаться в SPпосле выполнения команды возврата из функции return.
Мы хотим реализовать функцию length, которая находитдлину вектора в трехмерном пространстве. Вектор задается массивомиз трех его координат.Отметьте, какие из возможных прототипов данной функциикорректны.
Эквивалентны ли в языке C/C++ типы Matrix и Transform,заданные в приведенном ниже фрагменте программы?typedef double Matrix[3][3];typedef double Transform[3][3];
Следующий фрагмент программы для последовательностивещественных чисел вычисляет количество n элементов,строго больших предыдущего, причем самый первый элемент неучитывается (не считается больше предыдущего).Например, для последовательности{2, 1, 3, 5} ответ n=2(элементы 3 и 5).n = 0x0 = ...цикл пока в последовательности есть непрочитанные элементы|выполнять| прочесть очередной элемент посл-ти в <вых: x>| если x > x0| | то n = n + 1| конец если| x0 = xконец цикла
Каким значением надо инициализировать переменнуюx0, чтобы программа работала правильно?
Пусть целочисленная переменная 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;}
Рассмотрим следующий фрагмент программы, вычисляющейчастное 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Какое условие является инвариантом цикла?
Какое утверждение является инвариантом для следующегофрагмента программы (т.е. из справедливости утверждениядо выполнения фрагмента программы вытекает справедливость утвержденияпосле выполнения)? Предполагается, что значение переменнойn неотрицательно. double r, x; int n; . . . r *= x*x; r /= ((n+1)*(n+2)); n += 2;
Алгоритм пузырьковой сортировки упорядочивает массивиз 100 тысяч элементов примерно за 1 минуту. За какое примерновремя тот же алгоритм упорядочит массив из 10 тысяч элементов?
Какие из перечисленных ниже алгоритмов сортировкиработают в среднемза время O(n log2 n)?Отметьте все правильные ответы.
При представлении целых чисел в формате Big Endianбайты внутри слова нумеруются слева направо, в форматеLittle Endian - справа налево. Пусть компьютер используетархитектуру Big Endian. Укажите, чему будет равно значениепеременной n в результате выполненияследующего фрагмента программы: int k = (-256); int n; signed char *p = (signed char *) &k; n = *p;
Двоичный код, представляющий число типа float,хранит знак, смещенный порядок и дробную частьдвоичного представления мантиссы.Чему равен смещенный порядок в представлении числа 9.0?
Функция ln(z) (натуральный логарифм z) представляетсяв виде степенного ряда следующим образом: ln(1+x) = x - x2/2 + x3/3 - x4/4 + ...
(мы обозначили z=1+x). Этот ряд сходится лишь для значений x, по абсолютной величине не превосходящих 1, а эффективно вычислятьего сумму можно только для еще более узкого интервала значений x. Какими свойствами функции ln(z)удобнее всего воспользоваться, чтобы свести ее вычисление к суммированию ряда?
Какое максимальное число операций деления можетбыть выполнено в алгоритме Гаусса в процессе приведенияк ступенчатому виду квадратной матрицы размера4?
Сколько раз будет выполнено тело цикла в приведеннойниже программе? Многоточием обозначен фрагмент,не содержащий переменной x.int x = 0;while (x <= 100) { . . . x = x + 2;}
Для конкретного массива длины 1000 применяютсяалгоритмы пузырьковой сортировки и сортировкиметодом прямого выбора.Оба алгоритма используют сравнение элементовс помощью функции compareи обмен элементов с помощью функции swap.Какой из этих алгоритмов вызывает функцию swapбольшее число раз? (Имеется в виду нестрогое сравнение.)
Пусть мы имеем набор из n элементов,которые можно сравниватьмежду собой. Их медианой называется такоезначение m, что число элементов набора,меньших либо равных m,равно числу элементов, больших либо равных m.Существует ли алгоритм выбора медианы, которыйработает за время O(n) (т.е. за время,линейно зависящее от n)?
Что можно сказать об условии, указанном в заголовке цикла "while",после завершения цикла?
Отметьте, для каких из перечисленных ниже целей используетсяаппаратный стек в языке C/C++.
Левым нейтральным элементом (левой единицей) для бинарной операции называется элемент e такой, что для всякогодругого элемента x "произведение" e наx равно x:e x = x. Какие элементы будут нейтральнымидля операций суммы и минимума чисел соответственно?
Пусть w - последовательность целых чисел,F(w)=длина максимального постоянного участка в w.Например, для последовательностиw={1, 1, 4, 4, 4, 0, 2} значение Fравно 3 (постоянный участок из четверок).Какие из перечисленных ниже функцийявляются индуктивным расширением функции F?Укажите все правильные варианты.
Пусть 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
Функция merge слияния двух упорядоченных массивовприменяется к двум массивам длины 10 и 20.Может ли в процессе ее выполнения быть сделано ровно 28 сравнений?
Для записи n-значных чисел в системе счисленияс основанием b требуется n разрядов,каждый из которых может находиться в b состояниях.Таким образом, суммарное число состояний равно произведению n*b.Рассмотрим двоичную (b=2), восьмеричную (b=8)и шестнадцатеричную (b=16) системы счисления.Какая из них наиболее экономна по суммарному числу состоянийдля записи чисел в диапазоне 0..N,где N - некоторое достаточно большое число?
Чему равен ранг следующей матрицы:1 2 3 45 6 7 89 10 11 12
Укажите, чему будет равно значение переменной nв результате выполнения следующего фрагмента программы: double *p = 10000; p -= 1000; int n = (int) p;
К трехзначным десятичным числам (строкам длины 3 из десятичныхцифр) применяется алгоритм RADIX-сортировки сначала по младшей цифре,затем по средней и в конце по старшей. Исходный массив содержит следующиечисла:102, 232, 307, 901, 835, 215, 105, 301, 335, 811.
Каким будет содержимое массива после выполнения первых двух шаговсортировки (т.е. после сортировки по младшей и средней цифрам)?
Каков диапазон целочисленного типа signed char?
В чем главный недостаток языка Ассемблер?
Можно ли сохранить целое число 123456789012345
в переменной типа doubleбез потери точности?
Рассмотрим реализацию матрицы вещественных чисел,размеры которой определяютсяв процессе работы программы, через массив указателей на началастрок, захватываемый в динамической памяти. Каждая строкатакже представляет собой отдельный массив вдинамической памяти: 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-разрядной архитектуре(без учета памяти, используемой под описатели фрагментов кучи)?
Сколько единиц в двоичной записи числа 13?
Какой объект описан в следующей строке программына C/C++? double (*a)[20];
К массиву длины 5 применяетсяалгоритм сортировки методом прямого выбора,использующий сравнение элементов с помощью функции compareи обмен элементов с помощью функции swap.Какое максимальное количество раз может быть вызванафункция swap?
При представлении вещественных чисел в плавающей формемы выражаем вещественное число x в виде x = s 2e m,
где s - знак числа, принимающий значениеплюс или минус единица,e - порядок, представляющий собойцелое число (положительное, 0 или отрицательное),m - мантисса, представляющая собойвещественное число в диапазоне1 m < 2.Чему равны порядок и мантисса для числа 20?
К целочисленному массиву применяется алгоритм сортировкикучей. На первом этапе из элементов массива строитсяпирамида (бинарная куча) путем просеивания элементовпо бинарному дереву в порядке справа налево и снизу вверх.Пусть вначале массив содержал элементы1, 2, 3, 4, 7, 6, 5в указанном порядке.Каким будет содержимое массивапосле построения пирамиды?
Сколько в сумме операций сложения и умножениябудет выполнено при вычислениизначения многочлена степени 3, коэффициенты которогозаданы в последовательности по убыванию степеней,при использовании схемы вычисления индуктивной функции?
Как подключаются внешние устройства к общей шине компьютера?
Эквивалентны ли в языке C/C++ типы PntActи VectAct,заданные в приведенном ниже фрагменте программы?typedef double R3Point[3];typedef double R3Vector[3];typedef void (*PntAct)(R3Point);typedef void (*VectAct)(R3Vector);
Функция F последовательности цифр в десятичной записи числаn ставит в соответстие единицу, если n делится на 14,и ноль в противном случае. Какая из приведенныхниже функций на последовательности десятичных цифр числа nявляется индуктивным расширением функции F?
Целочисленный массив содержит элементы25, 10, 20, 5, 9, 15, 19, 1, 3, 8, 7, 12в указанном порядке. Образуют ли они бинарную кучу (пирамиду)?
Сортируемый массив содержит составные ключи из 10десятичных цифр.Массив имеет длину 1000000 (миллион). Надо выбрать один из двух алгоритмовсортировки: сортировку кучей HeapSort или RADIX-сортировку.Какой из двух алгоритмов будет в среднем работать быстреев данной ситуации?
Рассмотрим реализацию матрицы вещественных чиселразмера 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 при этом останутся на своем месте?
Какова асимптотическая оценка времени работыалгоритма Гаусса приведения матрицык ступенчатому видудля случая квадратной матрицы размера n?
Какие константы можно в практическом программировании использоватьв качестве воображаемого значения "минус бесконечность" при работе свещественными числами типа float? Укажите все правильныеварианты.
Для приближения функции, заданной на отрезке [a, b],применяется сплайн-интерполяция. Для этого отрезок разбиваетсяна n частей точкамиx0, x1, x2, ..., xn,в которых заданы значения функцииy0, y1, y2, ..., yn,На каждом из этих маленьких отрезков[xi, xi+1] функция приближаетсямногочленом степени d, который на концах отрезка принимаетзаданные значения. Пусть, помимо значений функции в узлах интерполяцииyi,заданы также и значения ее производнойy'i в узлах; производная каждого интерполяционногомногочлена также должна принимать заданные значенияна концах отрезка [xi, xi+1].Чему должна быть равнастепень d интерполяционных многочленов, из которыхсоставляется искомый сплайн?
Какой двоичный код представляетчисло -14 для типа signed char?
Какие смещения относительно регистра FP(Frame Pointer - указатель кадра)имеют адреса локальных переменных, описанных внутри функции,в языке C/C++?
Пусть целочисленный массив содержит элементы14, 20, 25, 15, 12, 22, 18в указанном порядке. Услове пирамиды нарушаетсятолько для элемента 14, стоящего в вершине пирамиды.Для исправления пирамиды выполняется процедура просеивания,при которой элемент 14 опускается на свое место.Каким будет содержимое массива после окончания этой процедуры?