💯 Алгоритмы обработки данных [Тема 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)

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

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

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

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

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

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

В основе построения дерева Фано лежит …

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

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

В рекуррентном соотношении для LCS, когда x_i и y_j не совпадают, используются значения …

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

• lcs[i-1][j] и lcs[i][j-1]
• lcs[i][j] и lcs[i-1][j-1]
• lcs[i][j] и lcs[i-2][j-1]
• lcs[i-1][j-1] и lcs[i-1][j+1]

Время выполнения основных операций в пирамиде равно …

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

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

Высота невозрастающей пирамиды с 63 элементами равна …

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

• 7
• 6
• 5
• 63

Высота у n-элементной пирамиды равна …

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

• n
• lg(n)
• 2n
• lg(n) + 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)

Для сортировки числовых последовательностей используется …

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

• Сортировка пузырьком
• Жадный алгоритм
• Алгоритм Дейкстры
• Алгоритм нахождения кратчайшего пути

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

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

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

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

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

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

К особенностям структуры данных "дек" (deque) относится то, что она …

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

• Может хранить только целые числа
• Поддерживает только операции добавления и удаления из начала
• Поддерживает как операции добавления, так и удаления с обоих концов
• Не поддерживает операции вставки и удаления

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

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

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

Кодирование символов в методе Хаффмана происходит …

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

• с использованием шифра Цезаря
• по численному значению символа в алфавите
• с помощью пути от корня дерева до листового узла
• с использованием XOR-операции

Кодовая таблица в методе Хаффмана строится …

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

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

Количество элементов пирамиды, содержащихся в массиве показывает атрибут …

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

• height[A]
• length[A]
• heap_size[A]
• parent[i]

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

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

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

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

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

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

Обычно операции над стеком, реализованным с использованием массива характеризуются асимптотической сложностью …

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

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

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

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

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

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

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

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

Основная разница между верхним и нижним подходами к вычислению последовательности Фибоначчи заключается в том, что …

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

• верхний подход использует рекурсию, а нижний – циклы
• верхний подход разбивает задачу на подзадачи, а нижний – строит значения снизу-вверх
• верхний подход требует больше времени, но меньше памяти
• верхний подход более эффективен для малых значений n, а нижний – для больших

Основное изменение в рандомизированной версии быстрой сортировки заключается в том, что …

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

• Опорный элемент всегда равен 0
• Опорный элемент выбирается случайным образом из подмассива A[p..r]
• Опорный элемент всегда равен A[r]
• Опорный элемент выбирается в зависимости от его индекса

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Структура данных – это …

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

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

Структура данных "стек" поддерживает основные операции …

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

• add и remove
• push и pop
• enqueue и dequeue
• insert и delete

Указатели на NIL при выполнении операции вставки в красно-черное дерево …

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

• остаются без изменений
• устанавливаются в NULL
• заменяются на nil[T]
• становятся равными пустым строкам

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

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

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

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

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

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

Установите соответствие между сложностью и ее обозначениями в 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)

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

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

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

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

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

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