🌞Алгоритмы обработки данных Темы 1-4

 Алгоритмы обработки данных.ти_ФРК Тема 1. Элементарные структуры данных и рост функций Лабораторная работа по теме 1 Тема 2. Алгоритмы сортировки Лабораторная работа 1 по теме 2 Лабораторная работа 2 по теме 2 Тема 3. Бинарные деревья поиска Лабораторная работа 1 по теме 3 Лабораторная работа 2 по теме 3 Тема 4. Динамическое программирование Лабораторная работа по теме 4 Односвязный список представляет собой… Список с двумя указателями на следующий и предыдущий элементы Список, где каждый элемент имеет указатель только на следующий элемент Список с циклическими связями Список, где элементы отсортированы в обратном порядке Пирамида (binary heap) представляет собой … Односвязный связный список Двоичное дерево Множество сортированных элементов Многомерный массив Оптимальное управление в методе динамического программирования имеет такую характеристику … оно имеет только максимальный выигрыш на текущем шаге оно выбирается так, чтобы обеспечить оптимальный результат на всех оставшихся шагах оно не зависит от состояния системы оно зависит только от предыдущего шага Массив в программировании представляет собой … Список всех целых чисел от 2 до n Однотипные элементы, доступные по единому имени и различающиеся индексами Совокупность всех доступных типов данных Алгоритм, который находит все простые числа в интервале от 2 до n При выборе шагового управления в задачах динамического программирования необходимо учитывать … возможные исходы предыдущего шага и влияние управления на все оставшиеся шаги влияние управления на предшествующие шаги оптимальное управление на данном шаге все управляющие переменные на текущем шаге Кодовая таблица в методе Хаффмана строится … с использованием таблицы соответствия символов и кодов с использованием бинарного дерева с использованием матрицы кодов с использованием алфавита символов Уровень дерева, который обычно не полностью заполнен в пирамиде – это … Первый Второй Последний Никакой, все уровни заполняются одинаково Принцип "First In First Out" (FIFO) использует структура данных … Стек (stack) Очередь (queue) Дек (deque) Массив (array) Алгоритм быстрой сортировки включает в себя этапы … Разделение, Покорение, Комбинирование Разделение, Слияние, Обмен Разделение, Сортировка, Объединение Разделение, Покорение, Обмен Сложность алгоритма для нахождения LCS двух последовательностей длиной m и n равна … O(mn) O(m + n) O(log(mn)) O(m^n) Алгоритм сортировки, который использует метод "разделяй и властвуй" называется … Пузырьковая сортировка Сортировка вставками Быстрая сортировка Сортировка выбором Установите соответствие между названием операции и действием, которое она выполняет: A.

empty B. popFront C. pushBack D. pushFront E. popBack F. Проверка на наличие элементов G. Операция удаления начального элемента H. Операция вставки нового элемента в конец I. Операция вставки нового элемента в начало J. Операция удаления конечного элемента Бинарные деревья – это … деревья, которые имеют только одну ветвь деревья, которые могут иметь не более двух потомков деревья, где каждый элемент имеет два указателя деревья, используемые только для хранения данных организационных диаграмм В задачах динамического программирования влияние будущих воздействий управления учитывается … путем проведения условной оптимизации с учетом всех возможных исходов предыдущего шага путем максимизации выигрыша на текущем шаге путем независимости решений на каждом шаге путем игнорирования будущих воздействий В лекции рассматриваются … Односвязные и двусвязные списки Односвязные списки Двусвязные списки Циклические списки «Черная высота» узла в красно-черном дереве – это … цвет узла количество дочерних узлов количество черных узлов на пути от узла до листа высота узла в дереве В рекуррентном соотношении для LCS, когда x_i и y_j не совпадают, используются значения … lcs[i-1][j] и lcs[j-1] lcs[j] и lcs[i-1][j-1] lcs[j] и lcs[i-2][j-1] lcs[i-1][j-1] и lcs[i-1][j+1] Высота у n-элементной пирамиды равна … n lg(n) 2n lg(n) + 1 Для "обычных" данных с небольшим количеством сортируемых элементов подходит … Поразрядная сортировка Рандомизированная сортировка Быстрая сортировка Сортировка списков АВЛ-деревья – это… массивы данных бинарные деревья списки связные списки Для преобразования массива в невозрастающую пирамиду применяется операция … Build_Min_Heap Build_Max_Heap Maxify_Array Organize_Heap Асимптотическая сложность выполнения операций поворотов в красно-черных деревьях равна … O(n) O(lg(n)) O(1) O(n^2) Если элементы x_i и y_j равны в рекуррентном соотношении для LCS, мы … вычитаем 1 из lcs[j] пропускаем этот шаг увеличиваем длину LCS на 1 и переходим к x_(i-1) и y_(j-1) завершаем выполнение алгоритма В задачах сжатия информации бинарные деревья применяются для … кодирования аудиофайлов уменьшения разрешения изображений сокращения объема хранимых данных создания видеокодеков Из перечисленного ниже списка примером контейнера является… Алгоритм Переменная Массив Функция Асимптотическую сложность быстрой сортировки в худшем случае описывает выражение … O(N) O(N log N) O(N^2) O(1) Индекс левого дочернего узла в структуре данных "пирамида" по индексу родительского узла позволяет найти метод … PARENT(i) LEFT(i) RIGHT(i) SIBLING(i) К особенностям структуры данных "дек" (deque) относится то, что она … Может хранить только целые числа Поддерживает только операции добавления и удаления из начала Поддерживает как операции добавления, так и удаления с обоих концов Не поддерживает операции вставки и удаления Свойство, которое обязательно выполняется для корня красно-черного дерева, подразумевает, что он должен … быть черным быть красным иметь два дочерних узла иметь наименьшее значение ключа Количество элементов пирамиды, содержащихся в массиве показывает атрибут … height[A] length[A] heap_size[A] parent Время выполнения основных операций в пирамиде равно … O(n) O(lg(n)) O(n^2) O(1) Корню пирамиды соответствует индекс в массиве … 0 1 2 heap_size[A] Лес в контексте структур данных – это … место, где растут деревья коллекция деревьев, связанных друг с другом отдельное дерево в генеалогическом древе структура данных, используемая только для хранения информации о корнях деревьев Мемоизация в контексте вычисления последовательности Фибоначчи – это … простой алгоритм вычисления сохранение уже вычисленных значений для повторного использования рекурсивное вычисление без сохранения результатов использование внешних данных для вычислений На высоту поддеревьев в АВЛ-деревьях накладывается ограничение, устанавливающее, что … высота поддеревьев не регулируется высота поддеревьев может отличаться на 2 высота поддеревьев не отличается более чем на 1 высота поддеревьев всегда равна 1 Асимптотическая сложность удаления узла из красно-черного дерева равна … O(n) O(1) O(n^2) O(lg(n)) Обычно операции над стеком, реализованным с использованием массива характеризуются асимптотической сложностью … O(n) O(log(n)) O(1) O(n^2) Основная идея динамических структур данных, таких как списки – это … Структуры данных всегда имеют фиксированное количество элементов Структуры данных хранят элементы в физически упорядоченном порядке Динамические структуры данных могут изменять свое количество элементов и связи между ними в процессе выполнения программы Динамические структуры данных не используют указатели Отличительной чертой невозрастающих пирамид (max-heap) является … Свойство организации корневого элемента Свойство того, что значение родительского узла не превышает значения потомка Свойство, что значение корневого элемента наименьшее в дереве Свойство, что уровни дерева заполнены слева направо Причина, по которой в многошаговых процессах управление на каждом шаге должно учитывать будущие воздействия … решения на каждом шаге независимы друг от друга максимизация результата на текущем шаге решения на каждом шаге могут влиять на будущие шаги и результат в целом упрощение процесса принятия решений Свойство, которое имеют все листья (NIL) в красно-черных деревьях, подразумевает, что … каждый лист является красным каждый лист имеет случайный цвет каждый лист имеет ключ каждый лист является черным Соотнесите термины с их определениями: A.

Деревья B. Бинарные деревья C. Лес D. АВЛ-дерево E. Красно-черное дерево F. Иерархическая структура, которая организует элементы в виде ветвей и узлов G. Структура данных, где каждая вершина может иметь не более двух потомков H. Коллекция деревьев I. Двоичное дерево, в котором высота поддеревьев-потомков одной вершины отличается не более чем на 1 J. Бинарное дерево поиска с одним дополнительным битом цвета в каждом узле Указатели на 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) Характеристики, которые используются для классификации структур данных включают … Цвет и форму элементов Внутреннее и внешнее распределение данных Содержимое данных Размер структуры данных Цель задачи наибольшей общей подпоследовательности (LCS) … найти наибольшую общую последовательность элементов найти самую длинную подстроку в последовательности найти наибольшую общую подпоследовательность в двух последовательностях найти наибольшую подпоследовательность чисел Элементарные структуры данных – это … структуры, состоящие из элементов с одинаковыми значениями структуры, которые нельзя разбить на боле....