💯 Алгоритмы обработки данных.ти_ФРК — ответы на тест Синергия / МОИ / МТИ / МосАП

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

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

Алгоритмы обработки данных.ти_ФРК

1. Тема 1. Элементарные структуры данных и рост функций
2. Лабораторная работа по теме 1
3. Тема 2. Алгоритмы сортировки
4. Лабораторная работа 1 по теме 2
5. Лабораторная работа 2 по теме 2
6. Тема 3. Бинарные деревья поиска
7. Лабораторная работа 1 по теме 3
8. Лабораторная работа 2 по теме 3
9. Тема 4. Динамическое программирование
10. Лабораторная работа по теме 4

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

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

• Функция состояния
• Функция оптимизации
• Функция Беллмана
• Функция воздействия

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

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

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

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

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

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

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

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

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

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

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

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

АВЛ-деревья – это…

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

• массивы данных
• бинарные деревья
• списки
• связные списки

Алгоритм быстрой сортировки включает в себя этапы …

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

• Разделение, Покорение, Комбинирование
• Разделение, Слияние, Обмен
• Разделение, Сортировка, Объединение
• Разделение, Покорение, Обмен

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

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

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

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

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

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

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

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

• 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

Глубина разветвленного списка, представляющего выражение (a + b) * (c - (d / e)) + f равна…

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

• 2
• 3
• 4
• 5

Для "обычных" данных с небольшим количеством сортируемых элементов подходит …

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

• Поразрядная сортировка
• Рандомизированная сортировка
• Быстрая сортировка
• Сортировка списков

Для балансировки АВЛ-деревьев используются такие операции, как …

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

• умножение и деление
• сортировка и фильтрация
• вращение
• сложение и вычитание

Для доступа к текущему объекту в C++ используется ключевое слово …

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

• self
• current
• this
• object

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

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

• 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)

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

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

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

Если элементы x_i и y_j равны в рекуррентном соотношении для LCS, мы …

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

• вычитаем 1 из lcs[i][j]
• пропускаем этот шаг
• увеличиваем длину LCS на 1 и переходим к x_(i-1) и y_(j-1)
• завершаем выполнение алгоритма

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

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

• PARENT(i)
• LEFT(i)
• RIGHT(i)
• SIBLING(i)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Красно-черное дерево – это …

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

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

Лес в контексте структур данных – это …

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

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

Массив в программировании представляет собой …

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

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

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

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

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

На высоту поддеревьев в АВЛ-деревьях накладывается ограничение, устанавливающее, что …

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

• высота поддеревьев не регулируется
• высота поддеревьев может отличаться на 2
• высота поддеревьев не отличается более чем на 1
• высота поддеревьев всегда равна 1

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

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

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

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

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

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

Основная идея динамических структур данных, таких как списки – это …

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

• Структуры данных всегда имеют фиксированное количество элементов
• Структуры данных хранят элементы в физически упорядоченном порядке
• Динамические структуры данных могут изменять свое количество элементов и связи между ними в процессе выполнения программы
• Динамические структуры данных не используют указатели

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

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

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

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

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

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

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

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

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

Отличительной чертой невозрастающих пирамид (max-heap) является …

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

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

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

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

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

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

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

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

Принцип "First In First Out" (FIFO) использует структура данных …

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

• Стек (stack)
• Очередь (queue)
• Дек (deque)
• Массив (array)

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

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

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

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

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

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

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

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

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

Сложность алгоритма для нахождения LCS двух последовательностей длиной m и n равна …

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

• O(mn)
• O(m + n)
• O(log(mn))
• O(m^n)

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

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

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

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

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

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

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

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

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

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

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

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

Уровень дерева, который обычно не полностью заполнен в пирамиде – это …

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

• Первый
• Второй
• Последний
• Никакой, все уровни заполняются одинаково

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

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

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

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

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

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

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

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

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