💯 Алгоритмы обработки данных [Тема 1-4] — ответы на тест Синергия / МОИ / МТИ / МосАП

Алгоритмы обработки данных > Итоговый тест

• правильные ответы на вопросы из теста по данной дисциплине
• вопросы отсортированы в лексикографическом порядке

Алгоритмы обработки данных

• Тема 1. Элементарные структуры данных и рост функций
• Тема 2. Алгоритмы сортировки
• Тема 3. Бинарные деревья поиска
• Тема 4. Динамическое программирование
• Практические занятия
• Итоговая аттестация

… к вычислению последовательности Фибоначчи требует меньше памяти.

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• Верхний подход (сверху-вниз)
• Нижний подход (снизу-вверх)
• Подход с использованием рекурсии
• Подход с использованием цикла

… улучшает производительность вычисления n-го элемента последовательности Фибоначчи.

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• Рекурсивный метод
• Метод наивной реализации
• Метод перебора
• Метод с использованием динамического программирования

… характеризует(ют) управление на каждом шаге задачи динамического программирования.

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• Переменная состояния
• Переменная управления
• Переменные состояния и управления
• Переменные состояния и начального состояния

«Черная высота» узла в красно-черном дереве – это …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• цвет узла
• количество дочерних узлов
• количество черных узлов на пути от узла до листа
• высота узла в дереве

Асимптотическая сложность вставки узла в красно-черное дерево равна …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• O(n)
• O(lg(n))
• O(1)
• O(n^2)

Асимптотическая сложность удаления узла из красно-черного дерева равна …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• O(n)
• O(1)
• O(n^2)
• O(lg(n))

Асимптотическую сложность быстрой сортировки в худшем случае описывает выражение …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• O(N)
• O(N log N)
• O(N^2)
• O(1)

В задачах динамического программирования влияние будущих воздействий управления учитывается …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• путем проведения условной оптимизации с учетом всех возможных исходов предыдущего шага
• путем максимизации выигрыша на текущем шаге
• путем независимости решений на каждом шаге
• путем игнорирования будущих воздействий

В задачах сжатия информации бинарные деревья применяются для …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• кодирования аудиофайлов
• уменьшения разрешения изображений
• сокращения объема хранимых данных
• создания видеокодеков

Две процедуры, которые используются для вычисления индексов дочерних узлов и родительского узла в пирамиде – это …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• LEFT(i) и RIGHT(i)
• PARENT(i) и RIGHT(i)
• LEFT(i) и PARENT(i)
• PARENT(i) и PARENT(PARENT(i))

Для преобразования массива в невозрастающую пирамиду применяется операция …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• Build_Min_Heap
• Build_Max_Heap
• Maxify_Array
• Organize_Heap

Для работы структуры данных "стек" (stack) характерен принцип …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• First In First Out (FIFO)
• Last In First Out (LIFO)
• First In Last Out (FILO)
• Last In Last Out (LILO)

Из перечисленного ниже списка примером контейнера является…

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• Алгоритм
• Переменная
• Массив
• Функция

К базовым типам данных относятся …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• Целые числа, числа с плавающей точкой, символы
• Массивы, структуры, пользовательские типы данных
• Цвета и формы
• Операции над данными

К преимуществам, которые предоставляют методы сортировки можно отнести …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• Ускорение работы процессора
• Упорядочивание данных для более эффективной обработки и доступа к ним
• Уменьшение размера хранимых данных
• Повышение безопасности информации

Мемоизация решает такую задачу, как …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• увеличение сложности программ
• ускорение выполнения программ
• оптимизация аппаратного обеспечения
• оптимизация сетевого взаимодействия

Нелинейный разветвленный список – это …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

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

Односвязный список представляет собой…

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

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

Оптимальное управление в методе динамического программирования имеет такую характеристику …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• оно имеет только максимальный выигрыш на текущем шаге
• оно выбирается так, чтобы обеспечить оптимальный результат на всех оставшихся шагах
• оно не зависит от состояния системы
• оно зависит только от предыдущего шага

Основные методы обхода бинарных деревьев …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• слева-направо и справа-налево
• нисходящий и восходящий
• прямой и обратный
• смешанный

Пирамида (binary heap) представляет собой …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• Односвязный связный список
• Двоичное дерево
• Множество сортированных элементов
• Многомерный массив

При выборе шагового управления в задачах динамического программирования необходимо учитывать …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• возможные исходы предыдущего шага и влияние управления на все оставшиеся шаги
• влияние управления на предшествующие шаги
• оптимальное управление на данном шаге
• все управляющие переменные на текущем шаге

Размерность массива – это …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

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

С сортировкой сложных структур, таких как строки связана рекомендация …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• Использовать обмен элементов
• Использовать указатели для перестановок
• Использовать поразрядную сортировку
• Использовать случайный выбор опорного элемента

Свойство, которое обязательно выполняется для корня красно-черного дерева, подразумевает, что он должен …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• быть черным
• быть красным
• иметь два дочерних узла
• иметь наименьшее значение ключа

Соотнесите термины с их определениями:

Тип ответа: Сопоставление

• A. Деревья
• B. Бинарные деревья
• C. Лес
• D. АВЛ-дерево
• E. Красно-черное дерево
• F. Иерархическая структура, которая организует элементы в виде ветвей и узлов
• G. Структура данных, где каждая вершина может иметь не более двух потомков
• H. Коллекция деревьев
• I. Двоичное дерево, в котором высота поддеревьев-потомков одной вершины отличается не более чем на 1
• J. Бинарное дерево поиска с одним дополнительным битом цвета в каждом узле

Управление в задачах динамического программирования характеризуют …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• и переменные состояния, и переменные управления
• только переменные состояния
• только переменные управления
• только целевые переменные

Установите соответствие между сложностью и ее обозначениями в Big O нотации:

Тип ответа: Сопоставление

• A. Константная сложность
• B. Линейная сложность
• C. Линеарифметическая сложность
• D. Квадратичная сложность
• E. Логарифмическая сложность
• F. O(1)
• G. O(n)
• H. O(n * log n)
• I. O(n^2)
• J. O(log n)

Целью выполнения операций поворотов в красно-черных деревьях является …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• увеличение количества узлов в дереве
• восстановление красно-черных свойств дерева
• увеличение черной высоты узла
• уменьшение высоты дерева

Экспоненциальное время выполнения алгоритма подразумевает, что …

Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов

• вычисление происходит быстро
• вычисление требует экспоненциально большой объем памяти
• вычисление занимает экспоненциально долгое время
• вычисление не зависит от входных данных