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

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

• # В алгоритме получения записи числа n в системе счисления с основанием b мы вычисляем цифры числа справа налево, начиная с последней цифры. На очередном шаге мы делим n с остатком на b, получая частное q и остаток r; остаток представляет очередную цифру числа в порядке справа налево. Затем мы переменной n присваиваем значение частного q, и процесс повторяется, пока n не станет равным нулю. Сколько раз будет выполнена операция деления при переводе числа 1000 (тысяча) в троичную систему счисления?
• # Какова степень интерполяционного многочлена, построенного по четырем узлам x0, x1, x2, x3, принимающего в этих узлах значения y0, y1, y2, y3?
• # Постановка задачи: в файле записана последовательность чисел неизвестной длины (возможно пустая). Между числами стоит разделитель - пробел. Требуется за один просмотр файла и без запомнинания последовательности чисел в массиве определить требуюмую характеристику последовательности. Программа должна содержать функцию, которая получает в качестве параметра имя файла и возвращает требуемое значение в файл (output.txt). Функция main открывает необходимые файлы, проверяет успешность открытия, обращается к функции для вычисления результата и выводит результат в соответствующий файл. Задание: определить количество возрастающих и убывающих участков в последовательности.
• # Какая из приведенных ниже строк языка С/С++ описывает массив указателей на тип char?
• # Массив длины 5 содержит элементы 5, 4, 1, 2, 3 в указанном порядке. К нему применяется алгоритм сортировки методом прямого выбора, использующий сравнение элементов с помощью функции compare и обмен элементов с помощью функции swap. Сколько раз будет вызвана функция swap?