"Продвинутые" алгоритмы для школьников - ответы
Количество вопросов - 390
Структура данных, позволяющая быстро изменять значения в массиве, носит название
Данные очереди можно
Набор ребер, в котором все вершины различны, носит название
Эффективность метода сортировки слиянием
Сколько координат имеет точка пересечения двух прямых в двухмерном пространстве?
Объекты в графе представляются в виде
Расстояние между вершинами в графе выражается
Деление по модулю в Паскале обозначается оператором
Граф с кратными рёбрами, имеющими своими концами одну и ту же пару вершин, носит название
Эффективность несериального динамического программирования зависит
Из приведенных ниже записей выделите методы хранения графов:
Последняя тройка цифр чисел Фибоначчи образует последовательность с периодом
Для чего используется алгоритм Куна?
Что представляет собой список?
Какие вершины соединяет ребро графа?
Суммы биномиальных коэффициентов на диагоналях треугольника Паскаля являются
Какой из приведенных ниже методов сортировки занимает наименьшее количество памяти?
Вектор, умноженный на отрицательное число
В языке C++ логическое "и" обозначается символом
Что представляет собой выпуклая оболочка?
Что такое нормаль к прямой?
Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным
Может ли дерево поиска быть случайным?
Если концы ребра совпадают, то такое ребро является
В каком случае двоичное дерево будет деревом поиска?
Если исходный граф связный, то поиск в ширину пометит
Можно ли хранить дерево поиска в массиве?
Для чего используется формула Крамера?
Высота дерева - это
Каким является граф в алгоритме Прима?
Возможна ли сортировка массива по неубыванию с помощью сортировки подсчетом?
Какая функция в Паскале применяется для задания случайных чисел?
Может ли количество вызовов при быстрой сортировке достигнуть 4logN?
Какие из приведенных ниже методов сортировки обладают устойчивостью?
Что обозначает принцип устойчивости при сортировке?
Имеются два массива: A[7 3 5 6 8] и B[23 4 12 17 8]. В каком из массивов большее количество инверсий?
Цифровая сортировка является
Список, в котором есть ссылка на предыдущий и на следующий элемент, носит название
Вершины, находящиеся от первой на расстоянии 1, носят название
Каким из приведенных ниже способов можно реализовать поиск кратчайшего пути к вершине?
Как называется граф, возле ребер которого стоят цифры?
Что собой представляет вес во взвешенном графе?
Очередь, в которой при переходе в последний элемент осуществляется переход в начало, носит название
Структура данных с методом доступа к элементам LIFO носит название
Добавление элемента в стек возможно
При поиске в ширину дуги вида (i, i+1), где i - это индекс вершины, порождают
К преимуществам использования очереди в динамическом программировании следует отнести
К элементам пары очереди с приоритетом следует отнести
Очередь с приоритетом является
Дерево - это
Сколько корней должно иметь дерево?
Количество поддеревьев узла составляет 2. Какова степень данного узла?
Что представляет собой лист?
Подграф данного графа, содержащий все его вершины и являющийся деревом, носит название
Сколько ребер входит в корень ориентированного дерева?
Может ли степень вершин двоичного дерева быть равной 4?
Любое дерево является
Любое дерево, содержащее счётное количество вершин, является
Алгоритм Прима посвящен построению
Алгоритм Прима применяется
Асимптотика бинарной пирамиды в алгоритме Прима оценивается величиной
Для чего предназначен алгоритм Дейкстры?
Обновление меток носит название
Обозначим через n количество вершин, а через m - количество ребер в графе G. Если для хранения непосещенных вершин использовать фибоначчиеву кучу, то время работы алгоритма Дейкстры составит
Бинарная матрица - это
Информация о существовании путей между вершинами орграфа хранится
Какие операции применяются при вычислении булевой степени матрицы достижимости?
В языке C++ логическое "или" обозначается символом
В языке C++ побитовое "и" обозначается символом
В чем основное отличие алгоритма Беллмана-Форда от алгоритма Дейкстры?
Цикл, сумма весов рёбер которого отрицательна, называется
Алгоритм Флойда-Уоршелла используется
Какую сложность имеет алгоритм Флойда-Уоршелла?
Связи в графе представляются в виде
К элементам графа следует отнести
Число ребер графа определяет
Если вершина является концом одного ребра, то она называется
Конечная последовательность вершин, в которой каждая вершина соединена со следующей в последовательности вершин ребром, носит название
Минимальная длина пути, соединяющего вершины, носит название
Если любые две вершины графа соединены ребром, такой граф называется
Если в графе каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества, такое граф называется
Таблица, где как столбцы, так и строки соответствуют вершинам графа, носит название
Мультиграф, допускающий наличие петель, носит название
Из приведенных ниже записей выделите методы обхода графа:
Граф, содержащий эйлеров путь, носит название
Задача о вершинном покрытии является
Число вершин, входящих в вершинное покрытие, является
Задача о вершинном покрытии сходна с задачей
Число ребер в паросочетании определяет
Множество вершин является независимым, если
В двудольных графах нет циклов
Дополнением вершинного покрытия является
Если в графе есть удлиняющая цепь, то размер паросочетания можно увеличить
Каким образом можно найти удлиняющую цепь?
Каким выражением оценивается время работы алгоритма поиска вершинного покрытия?
Верно ли то, что алгоритм Куна работает быстрее, чем поиск в глубину?
Метод решения задач с оптимальной подструктурой и перекрывающимися подзадачами носит название
Идея о том, что оптимальное решение подзадач меньшего размера может быть использовано для решения исходной задачи, лежит в основе концепции
Из приведенных ниже записей выделите варианты применения перекрывающихся задач:
Для чего в динамическом программировании используется кэширование?
К типам динамического программирования следует отнести
Эффективность несериального динамического программирования зависит
К классическим задачам динамического программирования следует отнести
Для каких из приведенных ниже задач применимы методы динамического программирования?
Отношения чисел Фибоначчи Fn+1/Fn являются
Последняя пара цифр чисел Фибоначчи образует последовательность с периодом
Если никакие две вершины множества вершин графа не соединены ребром, то такое множество носит название
Что такое вектор?
Сколько чисел необходимо для задания вектора?
Отношение прилежащего катета к гипотенузе, носит название
Если векторы перпендикулярны, то их скалярное произведение равно
Имеются две прямые: x=1 и -x=-1. Какими они являются?
Каким образом можно доказать, что два вектора параллельны?
Если две прямые совпадают, то они
Что такое определитель матрицы 2x2?
Проходит ли прямая ax+by+c=0 через начало координат?
Имеются две прямые: x-y+3=0 и 3x+4y+3=0. Параллельны ли они?
Что представляет собой строка?
Какие символы может содержать строка?
Что такое префикс строки?
Может ли строка быть префиксом самой себя?
Префикс какого-либо суффикса строки называется
Если длина одной строки N, а второй - M, то поиск вхождений строки M в строку N займет времени
Что такое образец в строке?
Для поиска подстроки в строке можно использовать алгоритм
Каким образом можно увеличить размер сдвига образца?
Префикс-функция зависит
Что представляет собой бор?
Корнем бора является
Сортировка векторов по углу производится с помощью
За какое минимальное время можно найти старший бит числа?
Дерево отрезков для суммы носит название
Сложность изменения в методе RSQ составляет
Какая реализация операции изменения используется при реализации дерева отрезков, способного вычислять сумму и максимум?
Что представляет собой RMQ?
Нахождение максимума на отрезке выполняется
Для чего применяется алгоритм пересечения отрезков?
Самый верхний из пересекающихся отрезков в алгоритме пересечения отрезков после точки пересечения становится
Сколько будет точек пересечений, которые надо будет хранить, когда все отрезки, пересекаясь между собой, образуют прямоугольную сетку?
Если не удалять точки пересечения отрезков, которые перестали быть соседними, алгоритм пересечения отрезков занимает времени
Какие данные можно записывать в вершины корневого дерева?
Максимальное расстояние от корня до листа в дереве носит название
От чего зависит время работы алгоритма поиска в двоичном дереве?
К деревьям поиска следует отнести
Двоичное дерево поиска, у которого каждая вершина является корнем с равной вероятностью, носит название
Функция, которая возвращает случайное число, носит название
Имеются два дерева: A и B. C какой вероятностью корень будет лежать в дереве A?
По первому ключу вершины декартово дерево является
В хипе вершина
Какую задачу могут решать деревья Фейнвика?
Ориентированный граф без циклов, в котором в каждую вершину, кроме одной, входит одно ребро, носит название
К реализациям очереди с приоритетом следует отнести
Существуют ли алгоритмы решения задачи о вершинном покрытии за полиномиальное время?
Движущаяся прямая, сканирующая лини в алгоритме пересечения отрезков, носит название
Центральным результатом теории динамического программирования следует считать
Матрица, элементами которой являются только 0 и 1, носит название
Из приведенных ниже записей выделите тип графа подзадач для вычисления чисел Фибоначчи:
Если взять совокупность всех вершин графа, будет ли она являться вершинным покрытием?
Каким образом можно реализовать хранение деревьев отрезков, способных вычислять сумму и максимум?
Имеются две прямые: 2x-y+3=0 и -3x+y+3=0. Перпендикулярны ли они?
Добавление элемента в стек носит название
Множество вершин S является вершинным покрытием тогда и только тогда, когда его дополнение является
Верно ли то, что время работы алгоритма поиска в двоичном дереве не зависит от высоты дерева?
Ссылки на элементы списка в массиве называются
Что такое суффикс строки?
Любое дерево с n вершинами содержит
Какова вероятность подвесить дерево с одной вершиной?
Из приведенных ниже записей выделите элементы ассоциативного массива:
Какие из приведенных ниже записей следует отнести к классическим задачам динамического программирования?
Несколько последних символов строки представляют собой
Для чего в Паскале используется оператор mod?
Очередь без элементов называется
От чего зависят координаты точки пересечения перпендикулярных прямых?
Дерево с отмеченной вершиной называется
При сортировке подсчетом происходит хранение
Остовное ордерево бесконтурного орграфа носит название
В языке C++ побитовое "или" обозначается символом
Размер паросочетания определяется
Какой граф рассматривается в алгоритме Флойда-Уоршелла?
Метод сортировки подсчетом применяется для сортировки
Задание случайных чисел в Паскале осуществляется с помощью функции
Количество вызовов при быстрой сортировке выражается зависимостью
Эффективность цифровой сортировки выражается зависимостью
Набор элементов, которые связаны между собой, носит название
К методам хранения графов следует отнести
Если от одной вершины до другой необходимо пройти два ребра, то расстояние между ними составляет
Кратчайший путь к вершине можно найти с помощью
Граф, возле ребер которого стоят цифры, носит название
Может ли ребро быть нулевого веса?
Стек представляет собой
Может ли очередь с приоритетом хранить несколько пар с одинаковыми ключами?
Каким из приведенных ниже типов графов может быть дерево?
Тип организации, в котором каждый объект связан с хотя бы одним другим, носит название
Степень узла - это
Степени вершин в двоичном дереве не превосходят
Исходящие степени вершин двоичного дерева не превосходят
Число различных деревьев, которые можно построить на n нумерованных вершинах, равно
Из приведенных ниже записей выделите алгоритмы построения минимального остовного дерева:
Сложность алгоритма Дейкстры зависит
Обозначим через n количество вершин, а через m - количество ребер в графе G. Время работы алгоритма Дейкстры выражается значением
Матрица достижимости орграфа является
Каким образом в алгоритме Беллмана-Форда можно определить, существует ли в графе G отрицательный цикл?
О чего зависит сложность алгоритма Флойда-Уоршелла?
Совокупность объектов со связями между ними носит название
Порядок графа задает
Если множества концевых вершин ребер совпадают, то такие ребра называются
Всякий максимальный связный подграф графа G называется
Если граф является связным и не содержит простых циклов, он называется
Как называется граф, который можно изобразить диаграммой на плоскости без пересечений рёбер?
Если каждому ребру графа поставлено в соответствие некоторое число, называемое весом ребра, такой граф называется
Что такое процедура DFS?
Связный ориентированный граф содержит эйлеров цикл тогда и только тогда, когда для каждой вершины графа её полустепень захода равна
От чего зависит размер вершинного покрытия?
Если каждая вершина входит только в одно ребро, то паросочетание называется
Если граф можно разбить на два множества, в которых не будет ребер, соединяющих его вершины, то такой граф будет называться
Паросочетание является максимальным тогда и только тогда, когда
Время работы алгоритма Куна
К составным частям оптимальной подструктуры следует отнести
Из приведенных ниже записей выделите типы динамического программирования:
Несериальное динамическое программирование рассматривает целевую функцию
Произведение и частное двух любых различных чисел Фибоначчи, отличных от единицы
Из приведенных ниже записей выделите способы задания прямой на плоскости?
Сколько нормалей можно построить из одной точки?
Геометрическое скалярное произведение векторов использует
Каким образом выглядит каноническое уравнение прямой, проходящей через точки (x1,y1) и (x2,y2)?
Если нормаль прямой имеет длину 1, то такая прямая называется
Чему равен определитель единичной матрицы 2x2?
Какие данные необходимы для задания окружности на плоскости?
Из каких элементов состоит строка?
Является ли запись fdlks строкой?
Несколько первых символов строки представляют собой
Подстрока строки носит название
Увеличение размера сдвига образца
Каким образом определяется префикс-функция?
Дерево, в котором хранятся несколько строк, носит название
Что такое RSQ?
Какие определения используются при изменении в RSQ?
Деревья отрезков, способные вычислять сумму и максимум, можно реализовать
Что такое RMQ?
Найти все точки пересечений прямолинейных отрезков на плоскости позволяет алгоритм
К точкам событий алгоритма пересечения отрезков следует отнести
Для чего в Паскале применяется функция random?
Чем декартово дерево отличается от двоичного дерева поиска?
Для того, чтобы посчитать функцию на отрезке можно использовать
Если граф можно изобразить диаграммой на плоскости без пересечений рёбер, такой граф называется
Время работы поиска в глубину оценивается выражением
Количество поддеревьев узла носит название
Алгоритм Дейкстры работает только для графов без рёбер
Что представляет собой дерево отрезков?
Каким образом можно произвести сортировку векторов по углу?
Какое дерево получится, если во второй ключ вершин декартового дерева записать случайное число?
В алгоритмах поиска одно- и двусвязных компонент в качестве подпрограммы можно использовать
Пусть длина одного вектора a, второго - b, угол между ними - x. Тогда их скалярное произведение будет равно
Имеется прямая ax+by+c=0. Какая прямая будет ей перпендикулярна?
Множество, не содержащее ни одного непересекающегося дерева, носит название
Сколько координат имеет точка на плоскости?
Метод доступа к объектам в стеке носит название
Могут ли исходящие степени вершин двоичного дерева быть равными 3?
С помощью поиска в ширину можно найти
Древовидная структура - тип организации, в котором каждый объект связан
Связный граф, не содержащий циклов, носит название
Для чего в Паскале применяется функция random?
Граф подзадач для вычисления чисел Фибоначчи является
Каким выражением оценивается время работы алгоритма Куна?
Какие принципы включаются в динамическое программирование?
Работа алгоритма Дейкстры завершается тогда, когда
Сколько точек пересечения может быть у двух прямых?
В основе метода сортировки слиянием лежит
Степень неупорядоченности массива определяется понятием
За какое время выполняется нахождение минимума на отрезке?
Количество инверсий для массива [9 5 7 3 6] составляет
Возможно ли определение положения элемента массива с помощью метода быстрой сортировки?
Эффективность метода сортировки слиянием выражается зависимостью
К устойчивым сортировкам следует отнести
Для чего может применяться список смежных вершин?
К типам очередей следует отнести
Из приведенных ниже записей выделите недостатки применения очередей в динамическом программировании:
Какие из приведенных ниже операций поддерживает очередь с приоритетом?
Узел с нулевой степенью носит название
Дерево с отмеченной вершиной называется
Каждый узел в дереве задаёт
Из приведенных ниже записей выделите структуры данных, построенные на двоичном дереве:
Асимптотика Фибоначчиевой пирамиды в алгоритме Прима оценивается величиной
Если a=01100101, b=00101001, то конъюнкция a и b будет равна
К отношениям транзитивности следует отнести
Если удаление ребра увеличивает число компонент, такое ребро называется
Если для любых вершин графа есть путь из одной во вторую, то такой граф называется
Для доказательства NP-полноты в теории сложности может использоваться
Из каких элементов состоит паросочетание?
Дополнением независимого множества является
Минимальное вершинное покрытие больше или равно размеру
Если нужно найти n!, то тривиальной задачей может быть
Подзадачи, которые используются для решения некоторого количества задач большего размера, носят название
Какие из приведенных ниже записей следует отнести к подходам к динамическому программированию?
Каким образом можно выразить числа Фибоначчи через многочлены Чебышева?
Последовательность чисел Фибоначчи является частным случаем
Простейшим геометрическим объектом является
Каким образом можно сложить два вектора?
Вектор, умноженный на положительное число, в результате будет
Что такое строка?
Можно ли считать запись e38ff строкой?
Может ли префикс строки быть равен 0?
Подстрока - это
Является ли rt образцом строки dkrtp?
Верно ли, что ассоциативный массив не может хранить две пары с одинаковыми ключами?
Выпуклая оболочка для точек - это
Какой метод применяется в алгоритме пересечения отрезков?
Удаление точки пересечения отрезков, которые временно перестают быть соседними при данном положении выметающей прямой, применяется для избегания использования
В алгоритме пересечения отрезков используется динамические структура данных без повторений с логарифмическим временем
Операция поиска в двоичном дереве работает за время, которое зависит
Если во второй ключ вершин декартового дерева записать случайное число, то получится
Граф взаимосвязей переменных в динамическом программировании представляет собой
Обозначим через n количество вершин, а через m - количество ребер в графе G. Если m много меньше n2, то граф G носит название
Как называется числовое значение возле ребра взвешенного графа?
Длина наиболее длинного префикса, являющегося одновременно суффиксом - это
Последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом
Имеется массив: [7 3 6 4 8]. Каково количество инверсий в данном массиве?
Для чего предназначен алгоритм Кнута-Морриса-Прата?
К методам сортировки массивов по неубыванию следует отнести
Какие действия можно совершать со списками?
В каком случае граф считается взвешенным?
Вес во взвешенном графе - это
Добавленный в стек элемент становится
Структура данных с дисциплиной доступа к FIFO, носит название
Ориентированный граф без циклов, в котором в каждую вершину, кроме одной, входит одно ребро, носит название
Выходом алгоритма Прима является
Матрица сильной связности является
Путь графа, в котором первая и последняя вершины совпадают, носит название
Если ребро графа может соединять более двух вершин, то такой граф называется
Множество вершин S графа, такое что, у каждого ребра графа хотя бы один из концов входит в S, носит название
Полное паросочетание возможно в графах
Время работы алгоритма поиска вершинного покрытия
Характеристический многочлен возвратной последовательности чисел Фибоначчи имеет вид
Задача о независимом множестве эффективно решается методом динамического программирования, если рассматриваемый граф является
От чего зависит длина проекции вектора на другой вектор?
Как найти точку пересечения двух прямых?
Дерево в бору является
Дерево отрезков для максимума носит название
Какие из приведенных ниже множеств используются в алгоритме пересечения отрезков?
Может ли двоичное дерево быть деревом поиска?
Пусть N - количество вершин в случайном двоичном дереве поиска. Тогда вероятность того, что вершина может быть корнем, составляет
Что нужно сделать, чтобы добавить вершину в корень?
Вершины декартового дерева можно
Подграф данного графа, содержащий все его вершины и являющийся деревом, носит название
Увеличение в методе RSQ может быть
На каждом шаге алгоритм Флойда-Уоршелла генерирует двухмерную матрицу, которая содержит
Имеются два вектора: (x1,y1), (x2,y2). Каков критерий их параллельности?
Может ли очередь с приоритетом быть пустой?
Подстрокой любой строки является
Сохранение решений перекрывающихся подзадач носит название
Каким образом можно произвести слияние двух отсортированных массивов?
Ссылки на элементы списка в динамической памяти носят название
От чего зависит асимптотика алгоритма Прима?
Бинарная матрица, в каждом столбце и строке которой лишь одна единица, а все остальные элементы - 0, носит название
Таблица, в которой каждая строка соответствует определённой вершине графа, а столбцы соответствуют связям графа, носит название
Если в графе нет циклов нечетной длины, то он является
Какое рекуррентное соотношение задает последовательность чисел Фибоначчи?
Каким образом можно задать прямую на плоскости?
Имеются две прямые: a1x+b1y+c1=0, a2x+b2y+с2=0. Каков критерий их параллельности?
За какое время в строке длины N можно найти наибольший префикс, являющийся суффиксом?
Дерево отрезков - это
Выметающая прямая может быть
Максимальное расстояние от корня до листа в дереве составляет 5. Какова высота дерева?
Несериальное динамическое программирование рассматривает целевую функцию
Какие требования к графу выдвигаются алгоритмом Дейкстры?
Что такое орграф?
Упорядоченная пара вершин с началом и концом носит название
Размером вершинного покрытия называется
Из приведенных ниже записей выделите классические задачи динамического программирования:
Каким образом выглядит уравнение прямой в декартовых координатах?
Каким образом можно хранить дерево поиска в памяти?
Сколько ключей хранится в вершине декартового дерева?
Для чего применяется алгоритм Флойда-Уоршелла?
Алгоритм Беллмана-Форда применяется для поиска
Граф взаимосвязей переменных в динамическом программировании представляет собой
Если в бинарной матрице на пересечении i-ой строки и j-го столбца стоит 1, и вершины i,j соединены ребром, и 0 в противном случае, то такая матрица называется
Сумма весов рёбер, входящих в путь в графе, носит название
Граф, в котором степень всех вершин не больше двух, является
Задача о независимом множестве является
Препроцессинг для RMQ выполняется
Корнем дерева может быть
Если два ребра графа имеют общую концевую вершину, они называются
Граф с n вершинами имеет вершинное покрытие размера k тогда и только тогда, когда данный граф имеет незавимимый набор размера
Неконцевой узел носит название
Что представляет собой очередь?
Дизъюнкция является
Путь, проходящий по всем рёбрам графа и притом только по одному разу, носит название
Для каких из приведенных ниже операций применяется алгоритм Кнута-Морриса-Прата?
Наименьший многоугольник, содержащий все данные точки, носит название
Несколько символов строки, идущих подряд, представляют собой