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

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

• # Функция merge слияния двух упорядоченных массивов применяется к двум массивам длины 10 и 20. Может ли в процессе ее выполнения быть сделано ровно 28 сравнений?
• # Рассмотрим следующий фрагмент программы на 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 после выполнения этого фрагмента?
• # Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел. Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности. Программа должна содержать функцию, которая получает в качестве параметра имя файла и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл. Задание: посчитать количество чисел, больших предыдущего.
• # Алгоритм пузырьковой сортировки упорядочивает массив из 10 тысяч элементов примерно за 1 секунду. За какое примерно время тот же алгоритм упорядочит массив из 100 тысяч элементов?
• # Есть 6 монет, известно, что все они имеют различные веса. Веса двух монет можно сравнить, используя весы-коромысло. Требуется упорядочить монеты по возрастанию их веса. Можно ли придумать такой алгоритм сортировки монет по весу, при котором в любом случае будет сделано не больше 9 взвешиваний?