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

    Тема 1. Элементарные структуры данных и рост функций
    Лабораторная работа по теме 1
    Тема 2. Алгоритмы сортировки
    Лабораторная работа 1 по теме 2
    Лабораторная работа 2 по теме 2
    Тема 3. Бинарные деревья поиска
    Лабораторная работа 1 по теме 3
    Лабораторная работа 2 по теме 3
    Тема 4. Динамическое программирование
    Лабораторная работа по теме 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) …

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

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

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

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

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