- Тема 1. Элементарные структуры данных и рост функций
- Лабораторная работа по теме 1
- Тема 2. Алгоритмы сортировки
- Лабораторная работа 1 по теме 2
- Лабораторная работа 2 по теме 2
- Тема 3. Бинарные деревья поиска
- Лабораторная работа 1 по теме 3
- Лабораторная работа 2 по теме 3
- Тема 4. Динамическое программирование
- Лабораторная работа по теме 4
… используется для оценки оптимальности решения на каждом шаге в динамическом программировании.
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Функция состояния
- Функция оптимизации
- Функция Беллмана
- Функция воздействия
… к вычислению последовательности Фибоначчи требует меньше памяти.
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Верхний подход (сверху-вниз)
- Нижний подход (снизу-вверх)
- Подход с использованием рекурсии
- Подход с использованием цикла
… улучшает производительность вычисления n-го элемента последовательности Фибоначчи.
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Рекурсивный метод
- Метод наивной реализации
- Метод перебора
- Метод с использованием динамического программирования
… характеризует(ют) управление на каждом шаге задачи динамического программирования.
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Переменная состояния
- Переменная управления
- Переменные состояния и управления
- Переменные состояния и начального состояния
«Черная высота» узла в красно-черном дереве – это …
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- цвет узла
- количество дочерних узлов
- количество черных узлов на пути от узла до листа
- высота узла в дереве
АВЛ-деревья – это…
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- массивы данных
- бинарные деревья
- списки
- связные списки
Алгоритм быстрой сортировки включает в себя этапы …
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Разделение, Покорение, Комбинирование
- Разделение, Слияние, Обмен
- Разделение, Сортировка, Объединение
- Разделение, Покорение, Обмен
Асимптотическая сложность вставки узла в красно-черное дерево равна …
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
Асимптотическая сложность выполнения операций поворотов в красно-черных деревьях равна …
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
Асимптотическую сложность быстрой сортировки в худшем случае описывает выражение …
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
Бинарные деревья – это …
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- деревья, которые имеют только одну ветвь
- деревья, которые могут иметь не более двух потомков
- деревья, где каждый элемент имеет два указателя
- деревья, используемые только для хранения данных организационных диаграмм
В задачах динамического программирования влияние будущих воздействий управления учитывается …
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- путем проведения условной оптимизации с учетом всех возможных исходов предыдущего шага
- путем максимизации выигрыша на текущем шаге
- путем независимости решений на каждом шаге
- путем игнорирования будущих воздействий
В задачах сжатия информации бинарные деревья применяются для …
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- кодирования аудиофайлов
- уменьшения разрешения изображений
- сокращения объема хранимых данных
- создания видеокодеков
В лекции рассматриваются …
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Односвязные и двусвязные списки
- Односвязные списки
- Двусвязные списки
- Циклические списки
В рекуррентном соотношении для 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]
Время выполнения основных операций в пирамиде равно …
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
Высота невозрастающей пирамиды с 63 элементами равна …
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
Глубина разветвленного списка, представляющего выражение (a + b) * (c - (d / e)) + f равна…
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
Для "обычных" данных с небольшим количеством сортируемых элементов подходит …
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Поразрядная сортировка
- Рандомизированная сортировка
- Быстрая сортировка
- Сортировка списков
Для балансировки АВЛ-деревьев используются такие операции, как …
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- умножение и деление
- сортировка и фильтрация
- вращение
- сложение и вычитание
Для доступа к текущему объекту в C++ используется ключевое слово …
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
Для преобразования массива в невозрастающую пирамиду применяется операция …
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- 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]
- становятся равными пустым строкам
Управление в задачах динамического программирования характеризуют …
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- и переменные состояния, и переменные управления
- только переменные состояния
- только переменные управления
- только целевые переменные
Уровень дерева, который обычно не полностью заполнен в пирамиде – это …
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- Первый
- Второй
- Последний
- Никакой, все уровни заполняются одинаково
Условная оптимизация в задачах динамического программирования проводится …
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- от начала процесса к концу
- одновременно на всех шагах
- от конца процесса к началу
- случайным образом
Целевая функция в задачах динамического программирования …
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- всегда является максимальной
- является аддитивной и равна сумме целевых функций каждого шага
- зависит только от текущего состояния системы
- не влияет на принятие решений
Целью выполнения операций поворотов в красно-черных деревьях является …
Тип ответа: Одиночный выбор • с выбором одного правильного ответа из нескольких предложенных вариантов
- увеличение количества узлов в дереве
- восстановление красно-черных свойств дерева
- увеличение черной высоты узла
- уменьшение высоты дерева