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

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

• # Укажите, чему может быть равно значение переменной 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; }
• # Для записи n-значных чисел в системе счисления с основанием b требуется n разрядов, каждый из которых может находиться в b состояниях. Таким образом, суммарное число состояний равно произведению n*b. Рассмотрим двоичную (b=2), троичную (b=3) и десятичную (b=10) системы счисления. Какая из них наиболее экономна по суммарному числу состояний для записи чисел в диапазоне 0..N, где N - некоторое достаточно большое число?
• # Какой самый первый объектно-ориентированный язык программирования?
• # Какие из перечисленных ниже алгоритмов сортировки работают в среднем за время O(n log2 n)? Отметьте все правильные ответы.