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

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

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

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

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(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

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

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

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

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

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

• self
• current
• this
• object

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

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

• Build_Min_Heap
• Build_Max_Heap
• Maxify_Array
• Organize_Heap

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

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

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

Если элементы 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) относится то, что она …

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

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

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

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

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

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

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

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

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

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

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

Корню пирамиды соответствует индекс в массиве …

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

• 0
• 1
• 2
• heap_size[A]

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

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

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

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

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

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

Мемоизация в контексте вычисления последовательности Фибоначчи – это …

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Свойство, которое имеют все листья (NIL) в красно-черных деревьях, подразумевает, что …

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

• каждый лист является красным
• каждый лист имеет случайный цвет
• каждый лист имеет ключ
• каждый лист является черным

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Установите соответствие между названием операции и действием, которое она выполняет:

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

• A. empty
• B. popFront
• C. pushBack
• D. pushFront
• E. popBack
• F. Проверка на наличие элементов
• G. Операция удаления начального элемента
• H. Операция вставки нового элемента в конец
• I. Операция вставки нового элемента в начало
• 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)

Характеристики, которые используются для классификации структур данных включают …

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

• Цвет и форму элементов
• Внутреннее и внешнее распределение данных
• Содержимое данных
• Размер структуры данных

Цель задачи наибольшей общей подпоследовательности (LCS) …

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

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

Элементарные структуры данных – это …

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

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