Главная / "Продвинутые" алгоритмы для школьников

"Продвинутые" алгоритмы для школьников - ответы на тесты Интуит

В курсе рассказывается о "продвинутых" (advanced) алгоритмах для школьников. Этот курс читался на летней компьютерной школе для участников олимпиад по информатике.

Список вопросов:

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