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

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

Правильные ответы выделены зелёным цветом.
Все ответы: В курсе рассказывается о "продвинутых" (advanced) алгоритмах для школьников. Этот курс читался на летней компьютерной школе для участников олимпиад по информатике.
Смотрите также:
Программирование
Образование
К методам сортировки массивов по неубыванию следует отнести
(1) сортировку по модулю
(2) сортировку подсчетом
(3) сортировку с возвратом
Выпуклая оболочка для точек - это
(1) набор всех элементов множества точек
(2) наименьший многоугольник, содержащий все точки
(3) матрица смежности точек
Какие данные можно записывать в вершины корневого дерева?
(1) числа
(2) идентификаторы
(3) массивы
Вершины, находящиеся от первой на расстоянии 1, носят название
(1) близкие
(2) соседние
(3) смежные
Связный граф, не содержащий циклов, носит название
(1) контейнер
(2) дерево
(3) матрица
Для чего предназначен алгоритм Дейкстры?
(1) для формирования минимального остовного дерева
(2) для нахождения кратчайшего расстояния от одной из вершин графа до всех остальных
(3) для поиска смежных вершин взвешенного графа
Совокупность объектов со связями между ними носит название
(1) контейнер
(2) граф
(3) класс
Задача о вершинном покрытии является
(1) NP-полной
(2) модификативной
(3) терминальной
Метод решения задач с оптимальной подструктурой и перекрывающимися подзадачами носит название
(1) модульное программирование
(2) динамическое программирование
(3) комплексное программирование
Простейшим геометрическим объектом является
(1) точка
(2) прямая
(3) вектор
Что такое строка?
(1) набор символов
(2) матрица идентификаторов
(3) непрерывная последовательность
Какая функция в Паскале применяется для задания случайных чисел?
(1) result
(2) random
(3) detect
Максимальное расстояние от корня до листа в дереве носит название
(1) высота
(2) ширина
(3) длина
Что представляет собой очередь?
(1) структуру данных
(2) тип данных
(3) размер массива
Тип организации, в котором каждый объект связан с хотя бы одним другим, носит название
(1) циклическая структура
(2) древовидная структура
(3) матричная структура
Работа алгоритма Дейкстры завершается тогда, когда
(1) не осталось взвешенных поддеревьев
(2) найдено минимальное остовное дерево
(3) когда посещены все вершины
Что такое орграф?
(1) организованный граф
(2) ортодоксальный граф
(3) ориентированный граф
Число вершин, входящих в вершинное покрытие, является
(1) размером
(2) порядком
(3) модулем
Идея о том, что оптимальное решение подзадач меньшего размера может быть использовано для решения исходной задачи, лежит в основе концепции
(1) оптимальной подструктуры
(2) модульного программирования
(3) поиска вершинного покрытия
Сколько чисел необходимо для задания вектора?
(1) 1
(2) 2
(3) 3
Является ли запись fdlks строкой?
(1) да, является
(2) нет, не является
(3) только для языков программирования
Возможно ли определение положения элемента массива с помощью метода быстрой сортировки?
(1) нет, невозможно
(2) такой метод не используется, так как занимает большое число итераций
(3) да, возможно
За какое минимальное время можно найти старший бит числа?
(1) O(1)
(2) O(n)
(3) O(logn)
Операция поиска в двоичном дереве работает за время, которое зависит
(1) от веса ребер
(2) от матрицы смежности
(3) от высоты
Кратчайший путь к вершине можно найти с помощью
(1) поиска в высоту
(2) поиска в ширину
(3) поиска со сдвигом
Количество поддеревьев узла носит название
(1) степень узла
(2) модуль узла
(3) маркер узла
Обозначим через n количество вершин, а через m - количество ребер в графе G. Время работы алгоритма Дейкстры выражается значением
(1) O(n + m2)
(2) O(n*log(n) + m)
(3) O(n+ m)
Число ребер графа определяет
(1) размер графа
(2) порядок графа
(3) модуль графа
Задача о вершинном покрытии сходна с задачей
(1) о независимом наборе
(2) о контекстных связях
(3) об остовных деревьях
Подзадачи, которые используются для решения некоторого количества задач большего размера, носят название
(1) динамические подзадачи
(2) перекрывающиеся подзадачи
(3) контекстные подзадачи
Что такое нормаль к прямой?
(1) параллельная прямая
(2) перпендикуляр
(3) направление
Что такое префикс строки?
(1) несколько первых символов
(2) длина строки
(3) тип данных строки
В основе метода сортировки слиянием лежит
(1) выставление идентификаторов
(2) разделение массива пополам
(3) вызов рекурсивной процедуры модульного подсчета
Что представляет собой дерево отрезков?
(1) структуру данных
(2) метод доступа к элементам
(3) тип связи
Каким образом можно хранить дерево поиска в памяти?
(1) в матрице смежности
(2) в массиве
(3) в контейнере идентификации
Граф, возле ребер которого стоят цифры, носит название
(1) цифровой
(2) взвешенный
(3) модульный
Узел с нулевой степенью носит название
(1) замкнутый узел
(2) матричный узел
(3) концевой узел
Матрица, элементами которой являются только 0 и 1, носит название
(1) простая
(2) бинарная
(3) вариативная
Если множества концевых вершин ребер совпадают, то такие ребра называются
(1) модульными
(2) парными
(3) кратными
Существуют ли алгоритмы решения задачи о вершинном покрытии за полиномиальное время?
(1) алгоритм Эйлера
(2) алгоритм Варда
(3) нет, не существуют
Для чего в динамическом программировании используется кэширование?
(1) для вычисления рекурсивных зависимостей
(2) для сохранения решений подзадач
(3) для вычисления по рекуррентным формулам
Геометрическое скалярное произведение векторов использует
(1) длины векторов
(2) угол между векторами
(3) направление векторов
Может ли строка быть префиксом самой себя?
(1) нет, это исключено
(2) да, может
(3) нет, всегда как минимум на один символ меньше
Эффективность метода сортировки слиянием выражается зависимостью
(1) O(NlogN)
(2) O(N)
(3) O(logN)
Увеличение в методе RSQ может быть
(1) только положительным
(2) только отрицательным
(3) как положительным, так и отрицательным
Может ли дерево поиска быть случайным?
(1) да, может
(2) нет, не может
(3) только ассоциативное дерево
Как называется числовое значение возле ребра взвешенного графа?
(1) модуль
(2) вес
(3) маркер
Дерево с отмеченной вершиной называется
(1) конечным деревом
(2) корневым деревом
(3) модульным деревом
Если в бинарной матрице на пересечении i-ой строки и j-го столбца стоит 1, и вершины i,j соединены ребром, и 0 в противном случае, то такая матрица называется
(1) матрицей смежности
(2) матрицей зависимости
(3) матрицей непрерывности
Упорядоченная пара вершин с началом и концом носит название
(1) петля
(2) дуга
(3) маркер
Размер паросочетания определяется
(1) числом ребер
(2) количеством вершин
(3) числом остовных поддеревьев
Из приведенных ниже записей выделите типы динамического программирования:
(1) нисходящее программирование
(2) циклическое программирование
(3) модульное программирование
От чего зависит длина проекции вектора на другой вектор?
(1) от длины проецируемого вектора
(2) от угла между векторами
(3) от направления векторов
Префикс какого-либо суффикса строки называется
(1) метастрокой
(2) подстрокой
(3) гиперстрокой
Что обозначает принцип устойчивости при сортировке?
(1) отсутствие перемещения упорядоченных элементов
(2) одинаковое количество вызовов при разных размерах массивов
(3) использование стандартных процедур ввода-вывода
Деревья отрезков, способные вычислять сумму и максимум, можно реализовать
(1) с хранением двух массивов одинаковой длины
(2) с матрицей вероятности
(3) с рекурсивной реализацией операции изменения
Пусть N - количество вершин в случайном двоичном дереве поиска. Тогда вероятность того, что вершина может быть корнем, составляет
(1) 1/N
(2) N-2
(3) logN
Может ли ребро быть нулевого веса?
(1) да, может
(2) нет, не может
(3) только в направленном графе
Сколько ребер входит в корень ориентированного дерева?
(1) 1
(2) множество
(3) ни одного
Какие операции применяются при вычислении булевой степени матрицы достижимости?
(1) конъюнкция
(2) дизъюнкция
(3) инъекция
Минимальная длина пути, соединяющего вершины, носит название
(1) путь
(2) расстояние
(3) модуль
Полное паросочетание возможно в графах
(1) только с четным количеством вершин
(2) только с нечетным количеством вершин
(3) с любым количеством вершин
Граф взаимосвязей переменных в динамическом программировании представляет собой
(1) путь
(2) контейнер
(3) матрицу
Вектор, умноженный на положительное число, в результате будет
(1) матрицей
(2) вектором
(3) числом
Подстрокой любой строки является
(1) бесконечная строка
(2) пустая строка
(3) гиперстрока
Количество инверсий для массива [9 5 7 3 6] составляет
(1) 7
(2) 5
(3) 6
Что такое RMQ?
(1) дерево отрезков для максимума
(2) дерево отрезков для суммы
(3) дерево отрезков для произведения
Что нужно сделать, чтобы добавить вершину в корень?
(1) разбить дерево на два поддерева и подвесить их к вершине
(2) использовать вызов ассоциативных массивов
(3) применить алгоритм Флойда-Уоршелла
Структура данных с методом доступа к элементам LIFO носит название
(1) модуль
(2) стек
(3) контейнер
Исходящие степени вершин двоичного дерева не превосходят
(1) 2
(2) 3
(3) 1
В языке C++ логическое "или" обозначается символом
(1) ||
(2) &&
(3) @
Если для любых вершин графа есть путь из одной во вторую, то такой граф называется
(1) связным
(2) модальным
(3) конструктивным
Если граф можно разбить на два множества, в которых не будет ребер, соединяющих его вершины, то такой граф будет называться
(1) полным
(2) двудольным
(3) бинарным
Из приведенных ниже записей выделите классические задачи динамического программирования:
(1) задача о наибольшей общей последовательности
(2) задача о перекрывающихся стеках
(3) задача о редакционном расстоянии
Сколько точек пересечения может быть у двух прямых?
(1) одна
(2) две
(3) множество
Что такое образец в строке?
(1) подстрока
(2) суффикс
(3) префикс
При сортировке подсчетом происходит хранение
(1) элементов массива
(2) количества элементов массива
(3) типа элементов массива
Препроцессинг для RMQ выполняется
(1) за O(n)
(2) за O(logn)
(3) за O(nlogn)
Сколько ключей хранится в вершине декартового дерева?
(1) 1
(2) 2
(3) множество
Добавление элемента в стек носит название
(1) калибровка
(2) инкремент
(3) проталкивание
В языке C++ логическое "и" обозначается символом
(1) &&
(2) @
(3) %
Если в графе каждая вершина одного подмножества соединена ребром с каждой вершиной другого подмножества, такое граф называется
(1) полным контекстным
(2) полным маркированным
(3) полным двудольным
Если в графе нет циклов нечетной длины, то он является
(1) двудольным
(2) орграфом
(3) контейнером
Для каких из приведенных ниже задач применимы методы динамического программирования?
(1) алгоритм Флойда-Уоршелла
(2) поиск максимального независимого множества вершин в дереве
(3) вычисление чисел Фибоначчи
Каким образом можно доказать, что два вектора параллельны?
(1) показать, что их нормали параллельны
(2) вычислить коэффициенты матрицы содержимого
(3) доказать, что они имеют одно направление
Для чего предназначен алгоритм Кнута-Морриса-Прата?
(1) для поиска ассоциативных деревьев
(2) для поиска подстроки в строке
(3) для поиска остовного дерева
Эффективность цифровой сортировки выражается зависимостью
(1) O(N)
(2) O(logN)
(3) O(N2)
Найти все точки пересечений прямолинейных отрезков на плоскости позволяет алгоритм
(1) пересечения отрезков
(2) большинства покрытия
(3) матричной совместимости
В хипе вершина
(1) больше своих детей
(2) меньше своих детей
(3) равна своим детям
Если исходный граф связный, то поиск в ширину пометит
(1) главные вершины
(2) вершины-потомки
(3) все вершины
Любое дерево, содержащее счётное количество вершин, является
(1) унимодальным графом
(2) планарным графом
(3) комбинированным графом
К отношениям транзитивности следует отнести
(1) отношение порядка
(2) импликацию
(3) эквивалентность
Если каждому ребру графа поставлено в соответствие некоторое число, называемое весом ребра, такой граф называется
(1) оцененным
(2) взвешенным
(3) статическим
Минимальное вершинное покрытие больше или равно размеру
(1) матрицы смежности
(2) максимального паросочетания
(3) поддерева связности
Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным
(1) среднему арифметическому индексов
(2) наибольшему общему делителю индексов
(3) сумме индексов
Если две прямые совпадают, то они
(1) ассоциативны
(2) параллельны
(3) равны
Каким образом можно увеличить размер сдвига образца?
(1) выводом в ассоциативный массив
(2) запомнив части текста, совпадающие с образцом
(3) сформировав матрицу инцидентности
Набор элементов, которые связаны между собой, носит название
(1) список
(2) файл
(3) идентификатор
Движущаяся прямая, сканирующая лини в алгоритме пересечения отрезков, носит название
(1) динамическая прямая
(2) выметающая прямая
(3) конструктивная прямая
Вершины декартового дерева можно
(1) добавлять
(2) имплицировать
(3) удалять
Структура данных с дисциплиной доступа к FIFO, носит название
(1) контейнер
(2) приоритет
(3) очередь
Из приведенных ниже записей выделите структуры данных, построенные на двоичном дереве:
(1) АВЛ-дерево
(2) суффиксное дерево
(3) маркерное дерево
Сумма весов рёбер, входящих в путь в графе, носит название
(1) длина пути
(2) модуль пути
(3) вес пути
Граф с кратными рёбрами, имеющими своими концами одну и ту же пару вершин, носит название
(1) псевдограф
(2) мультиграф
(3) комбограф
Паросочетание является максимальным тогда и только тогда, когда
(1) нет удлиняющей цепи
(2) оно входит в остовное дерево
(3) отсутствуют петли графа
Отношения чисел Фибоначчи Fn+1/Fn являются
(1) дробями золотого сечения
(2) индексами характеристического многочлена
(3) наибольшими индексами матрицы совместимости
Что такое определитель матрицы 2x2?
(1) разность произведений элементов главной и побочной диагоналей
(2) сумма элементов главной диагонали
(3) произведение разностей элементов строк и столбцов
Длина наиболее длинного префикса, являющегося одновременно суффиксом - это
(1) суффикс-функция
(2) префикс-функция
(3) постфикс-функция
Ссылки на элементы списка в массиве называются
(1) модулями
(2) конструкциями
(3) указателями
Выметающая прямая может быть
(1) только горизонтальной
(2) только вертикальной
(3) как горизонтальной, так и вертикальной
Граф взаимосвязей переменных в динамическом программировании представляет собой
(1) путь
(2) контейнер
(3) матрицу
К элементам пары очереди с приоритетом следует отнести
(1) ключ
(2) маркер
(3) значение
Каким является граф в алгоритме Прима?
(1) взвешенным
(2) связным
(3) комплексным
Для чего применяется алгоритм Флойда-Уоршелла?
(1) для нахождения остовных поддеревьев
(2) для нахождения кратчайших расстояний между всеми вершинами
(3) для формирования матрицы достижимости
Из приведенных ниже записей выделите методы обхода графа:
(1) поиск в глубину
(2) контекстный поиск
(3) маркированный поиск
Каким выражением оценивается время работы алгоритма поиска вершинного покрытия?
(1) O(V3)
(2) O(V2)
(3) O(V)
Последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом
(1) 10
(2) 40
(3) 60
Имеется прямая ax+by+c=0. Какая прямая будет ей перпендикулярна?
(1) -ax+by=0
(2) -bx-ay=0
(3) -bx+ay=0
Дерево, в котором хранятся несколько строк, носит название
(1) лес
(2) бор
(3) массив
К методам хранения графов следует отнести
(1) матрицу смежности
(2) матрицу терминалов
(3) матрицу идентификации
В алгоритме пересечения отрезков используется динамические структура данных без повторений с логарифмическим временем
(1) поиска точек событий
(2) вставки точек событий
(3) удаления точек событий
Дерево с отмеченной вершиной называется
(1) конечным деревом
(2) корневым деревом
(3) модульным деревом
Может ли очередь с приоритетом быть пустой?
(1) да, может
(2) нет, не может
(3) может, но это приведет к сбою в работе программы
От чего зависит асимптотика алгоритма Прима?
(1) от способа хранения графа
(2) от способа хранения вершин, не входящих в дерево
(3) от способа модификации узлов графа
На каждом шаге алгоритм Флойда-Уоршелла генерирует двухмерную матрицу, которая содержит
(1) псевдовершины графа
(2) длины кратчайших путей между всеми вершинами графа
(3) маркированные остовные поддеревья графа
Путь, проходящий по всем рёбрам графа и притом только по одному разу, носит название
(1) путь Флойда
(2) эйлеров путь
(3) унимодальный путь
Каким выражением оценивается время работы алгоритма Куна?
(1) O(V3)
(2) O(logV)
(3) O(V-E)
Если никакие две вершины множества вершин графа не соединены ребром, то такое множество носит название
(1) независимое
(2) висячее
(3) свободное
Имеются две прямые: 2x-y+3=0 и -3x+y+3=0. Перпендикулярны ли они?
(1) да, перпендикулярны
(2) нет, не перпендикулярны
(3) они совпадают
Корнем бора является
(1) гиперстрока
(2) пустая строка
(3) симплекс-строка
Метод сортировки подсчетом применяется для сортировки
(1) по неубыванию
(2) по модулю
(3) по типу данных
Что представляет собой выпуклая оболочка?
(1) многоугольник
(2) окружность
(3) матрицу
В каком случае двоичное дерево будет деревом поиска?
(1) если в одной части дерева хранятся значения, больше вершины, а в другой - меньше
(2) если матрица достижимости для него будет бинарной
(3) если орграф такого дерева будет циклическим
Расстояние между вершинами в графе выражается
(1) числом ребер
(2) модулем вершин
(3) количеством связей
Дерево - это
(1) ориентированный полновесный граф
(2) связный граф, не содержащий циклов
(3) граф с возвратом
Алгоритм Дейкстры работает только для графов без рёбер
(1) с положительными вершинами
(2) отрицательного веса
(3) с тремя вершинами
Объекты в графе представляются в виде
(1) ребер
(2) вершин
(3) маркеров
Для доказательства NP-полноты в теории сложности может использоваться
(1) задача об эйлеровом пути
(2) задача о гиппократовых луночках
(3) задача о вершинном покрытии
Какие принципы включаются в динамическое программирование?
(1) оптимальная подструктура
(2) перекрывающиеся подзадачи
(3) контекстные модули
Сколько координат имеет точка на плоскости?
(1) 1
(2) 2
(3) 3
Что представляет собой строка?
(1) абстрактный тип данных
(2) набор символов
(3) способ записи одномерного массива
Для чего в Паскале применяется функция random?
(1) для сортировки массива
(2) для задания случайных чисел
(3) для вычисления остатка от деления
Сортировка векторов по углу производится с помощью
(1) векторной суммы
(2) векторной разности
(3) векторного произведения
Высота дерева - это
(1) количество его вершин
(2) сумма весов его ребер
(3) максимальное расстояние от корня до листа
Данные очереди можно
(1) добавлять
(2) интерпретировать
(3) детерминировать
Древовидная структура - тип организации, в котором каждый объект связан
(1) с минимум двумя объектами
(2) с хотя бы одним другим объектом
(3) со всеми остальными объектами
Сложность алгоритма Дейкстры зависит
(1) от способа нахождения вершины
(2) от способа хранения множества непосещенных вершин
(3) от способа обновления меток
К элементам графа следует отнести
(1) узлы
(2) ребра
(3) метки
Размером вершинного покрытия называется
(1) модуль максимального веса ребра
(2) число вершин, входящих в вершинное покрытие
(3) наименьшее остовное поддерево
К составным частям оптимальной подструктуры следует отнести
(1) разбиение задачи на подзадачи меньшего размера
(2) нахождение оптимального решения подзадачи рекурсивно
(3) использование полученного решения подзадач для конструирования решения исходной задачи
Каким образом можно задать прямую на плоскости?
(1) двумя точками
(2) точкой и направлением
(3) уравнением
Какие символы может содержать строка?
(1) только буквы латинского алфавита
(2) только цифры
(3) как буквы, так и цифры
Количество вызовов при быстрой сортировке выражается зависимостью
(1) O(NlogN)
(2) O(N2)
(3) O(2N)
Структура данных, позволяющая быстро изменять значения в массиве, носит название
(1) дерево отрезков
(2) матрица инцидентности
(3) граф определений
От чего зависит время работы алгоритма поиска в двоичном дереве?
(1) от высоты
(2) от длины ребер
(3) от значений матрицы инцидентности
С помощью поиска в ширину можно найти
(1) количество составных ребер
(2) кратчайший путь к вершине
(3) тип вершин
Степень узла - это
(1) количество поддеревьев узла
(2) количество вершин узла
(3) количество связей вершины
Обозначим через n количество вершин, а через m - количество ребер в графе G. Если m много меньше n2, то граф G носит название
(1) маркированный
(2) разреженный
(3) вариативный
Какие вершины соединяет ребро графа?
(1) итерационные
(2) концевые
(3) маркированные
Множество вершин S является вершинным покрытием тогда и только тогда, когда его дополнение является
(1) остовным поддеревом
(2) ориентированным графом
(3) независимым набором
Из приведенных ниже записей выделите варианты применения перекрывающихся задач:
(1) симплекс-метод
(2) NP-модулирование
(3) вычисление чисел Фибоначчи
Сколько нормалей можно построить из одной точки?
(1) одну
(2) две
(3) множество
Несколько первых символов строки представляют собой
(1) суффикс
(2) префикс
(3) постфикс
Каким образом можно произвести слияние двух отсортированных массивов?
(1) с помощью меток и указателей
(2) с помощью еще одного массива
(3) с помощью принципа унимодальности массивов
Что такое RSQ?
(1) дерево отрезков для суммы
(2) дерево отрезков для разности
(3) дерево отрезков для произведения
Можно ли хранить дерево поиска в массиве?
(1) да, можно
(2) нет, нельзя
(3) только ассоциативное дерево
В каком случае граф считается взвешенным?
(1) когда имеет симметричную структуру
(2) когда возле его ребер стоят числа
(3) когда пути к последней вершине имеют одинаковую длину
Что представляет собой лист?
(1) концевой узел
(2) матрицу смежности
(3) модуль вершины
Бинарная матрица - это
(1) матрица с нулями на побочной диагонали
(2) матрица только с 0 и 1
(3) квадратная матрица
Если концы ребра совпадают, то такое ребро является
(1) дугой
(2) петлей
(3) меткой
Набор ребер, в котором все вершины различны, носит название
(1) маркер
(2) контейнер
(3) паросочетание
Граф подзадач для вычисления чисел Фибоначчи является
(1) модификативным
(2) ациклическим
(3) когнитивным
Пусть длина одного вектора a, второго - b, угол между ними - x. Тогда их скалярное произведение будет равно
(1) s=a*b*sin(x)
(2) s=a*b*cos(x)
(3) s=a*b*tg(x)
Что такое суффикс строки?
(1) несколько первых символов строки
(2) несколько последних символов строки
(3) несколько произвольных символов строки
Эффективность метода сортировки слиянием
(1) выше эффективности быстрой сортировки
(2) ниже эффективности быстрой сортировки
(3) равна эффективности быстрой сортировки
Какие определения используются при изменении в RSQ?
(1) отрезки, на которых производится изменение
(2) матрица инцидентности
(3) номера ячеек, в которых хранится информация
Корнем дерева может быть
(1) только главная вершина
(2) только ассоциативная вершина
(3) любая вершина
Вес во взвешенном графе - это
(1) значение в вершине
(2) количество свободных путей
(3) число возле ребра
Подграф данного графа, содержащий все его вершины и являющийся деревом, носит название
(1) терминальное дерево
(2) остовное дерево
(3) комплексное дерево
Матрица достижимости орграфа является
(1) матрицей сдвига
(2) бинарной матрицей
(3) модульной матрицей
Конечная последовательность вершин, в которой каждая вершина соединена со следующей в последовательности вершин ребром, носит название
(1) контейнер
(2) трасса
(3) цепь
Число ребер в паросочетании определяет
(1) размер
(2) порядок
(3) модуль
К типам динамического программирования следует отнести
(1) ациклическое программирование
(2) контейнерное программирование
(3) восходящее программирование
Если векторы перпендикулярны, то их скалярное произведение равно
(1) 1
(2) 0
(3) бесконечности
Подстрока - это
(1) элемент матрицы надежности строки
(2) префикс суффикса строки
(3) несколько произвольных символов строки
Степень неупорядоченности массива определяется понятием
(1) модульности
(2) инверсности
(3) контекстности
Какая реализация операции изменения используется при реализации дерева отрезков, способного вычислять сумму и максимум?
(1) рекурсивная
(2) матричная
(3) комплексная
Функция, которая возвращает случайное число, носит название
(1) mode
(2) random
(3) rect
Очередь, в которой при переходе в последний элемент осуществляется переход в начало, носит название
(1) рекурсивная
(2) кольцевая
(3) динамическая
Множество, не содержащее ни одного непересекающегося дерева, носит название
(1) лес
(2) контейнер
(3) вариант
Матрица сильной связности является
(1) симметричной
(2) модификативной
(3) транзитивной
Всякий максимальный связный подграф графа G называется
(1) аддитивной компонентой
(2) связной компонентой
(3) модификативной компонентой
Если взять совокупность всех вершин графа, будет ли она являться вершинным покрытием?
(1) да, будет
(2) нет, не будет
(3) только для связных графов
Несериальное динамическое программирование рассматривает целевую функцию
(1) как статическую функцию
(2) как рекурсивно вычислимую функцию
(3) как модификативную константную функцию
Вектор, умноженный на отрицательное число
(1) не изменяет размер
(2) меняет направление
(3) становится числом
Если длина одной строки N, а второй - M, то поиск вхождений строки M в строку N займет времени
(1) O(NM)
(2) O(logM)
(3) O(logN)
К устойчивым сортировкам следует отнести
(1) сортировку со сдвигом
(2) сортировку подсчетом
(3) сортировку детерминированием
Нахождение максимума на отрезке выполняется
(1) за O(1)
(2) за O(n)
(3) за O(2n)
Чем декартово дерево отличается от двоичного дерева поиска?
(1) числом ключей в вершине
(2) методом формирования матрицы смежности
(3) остовным деревом
Добавление элемента в стек возможно
(1) только в вершину стека
(2) только в корень стека
(3) как в вершину, так и корень стека
Любое дерево с n вершинами содержит
(1) n-1 ребро
(2) 2n ребер
(3) 2n-1 ребро
В языке C++ побитовое "и" обозначается символом
(1) &
(2) %%
(3) &&
Если граф можно изобразить диаграммой на плоскости без пересечений рёбер, такой граф называется
(1) комплексным
(2) планарным
(3) геометрическим
Дополнением вершинного покрытия является
(1) остовное дерево
(2) матрица инцидентности
(3) независимое множество
Какое рекуррентное соотношение задает последовательность чисел Фибоначчи?
(1) Fn+1=Fn+Fn-1
(2) Fn=Fn-1+Fn+1
(3) Fn-1=Fn+1+Fn
Имеются два вектора: (x1,y1), (x2,y2). Каков критерий их параллельности?
(1) x1y2=x2y1
(2) x1-y2=x2-y1
(3) x1+y2=x2+y1
Для каких из приведенных ниже операций применяется алгоритм Кнута-Морриса-Прата?
(1) поиск подстроки в строке
(2) формирование матрицы достижимости
(3) вывод из ассоциативного массива
Деление по модулю в Паскале обозначается оператором
(1) div
(2) mod
(3) srt
Для чего применяется алгоритм пересечения отрезков?
(1) для нахождения всех точек пересечения отрезков
(2) для заполнения матрицы инцидентности
(3) для формирования остовного дерева
Если во второй ключ вершин декартового дерева записать случайное число, то получится
(1) сбалансированное дерево
(2) дерево перебора
(3) ассоциативное дерево
Остовное ордерево бесконтурного орграфа носит название
(1) поисковое дерево
(2) матричное дерево
(3) комплексное дерево
Число различных деревьев, которые можно построить на n нумерованных вершинах, равно
(1) n2
(2) nn - 1
(3) nn - 2
Алгоритм Беллмана-Форда применяется для поиска
(1) минимального остовного поддерева
(2) порядка смежности вершин
(3) кратчайшего пути во взвешенном графе
Таблица, где как столбцы, так и строки соответствуют вершинам графа, носит название
(1) матрица смежности
(2) матрица достижимости
(3) матрица контекстности
Граф, в котором степень всех вершин не больше двух, является
(1) несвязным
(2) двудольным
(3) маркированным
Последовательность чисел Фибоначчи является частным случаем
(1) контекстной последовательности
(2) возвратной последовательности
(3) модульной последовательности
Как найти точку пересечения двух прямых?
(1) координатным спуском
(2) методом общих величин
(3) решить их общую систему уравнений
Список, в котором есть ссылка на предыдущий и на следующий элемент, носит название
(1) двусвязный
(2) маркированный
(3) контекстный
К точкам событий алгоритма пересечения отрезков следует отнести
(1) концы отрезков
(2) точки пересечения отрезков
(3) точки статических максимумов
Какую задачу могут решать деревья Фейнвика?
(1) посчитать функцию на отрезке
(2) составить остовное дерево
(3) найти матрицу смежности
К преимуществам использования очереди в динамическом программировании следует отнести
(1) неограниченность размера очереди
(2) ограничение очереди только по памяти
(3) модульность данных очереди
Алгоритм Прима посвящен построению
(1) поддерева совместимости
(2) минимального остовного дерева
(3) графа смежности
Цикл, сумма весов рёбер которого отрицательна, называется
(1) аддитивным циклом
(2) отрицательным циклом
(3) унимодальным циклом
Мультиграф, допускающий наличие петель, носит название
(1) логограф
(2) псевдограф
(3) циклограф
Каким образом можно найти удлиняющую цепь?
(1) маркировкой вершин
(2) поиском в глубину
(3) остовным деревом
Суммы биномиальных коэффициентов на диагоналях треугольника Паскаля являются
(1) числами матрицы инцидентности
(2) числами Фибоначчи
(3) числами модулей графа корректности
Чему равен определитель единичной матрицы 2x2?
(1) 0
(2) 1
(3) 2
Префикс-функция зависит
(1) от длины наиболее длинного префикса, являющегося суффиксом
(2) от длины наименее длинного префикса, не являющегося суффиксом
(3) от длины наиболее длинного префикса, е являющегося суффиксом
Какие действия можно совершать со списками?
(1) удалять элементы
(2) добавлять элементы
(3) обрабатывать элементы
Сколько будет точек пересечений, которые надо будет хранить, когда все отрезки, пересекаясь между собой, образуют прямоугольную сетку?
(1) O(n2)
(2) O(n)
(3) O(logn)
Несериальное динамическое программирование рассматривает целевую функцию
(1) как статическую функцию
(2) как рекурсивно вычислимую функцию
(3) как модификативную константную функцию
Может ли очередь с приоритетом хранить несколько пар с одинаковыми ключами?
(1) нет, это невозможно
(2) да, может
(3) только для комплексных чисел
Алгоритм Прима применяется
(1) для ориентированных графов
(2) для неориентированных графов
(3) для детерминированных графов
Какой граф рассматривается в алгоритме Флойда-Уоршелла?
(1) взвешенный
(2) маркированный
(3) терминальный
В алгоритмах поиска одно- и двусвязных компонент в качестве подпрограммы можно использовать
(1) курсирующий поиск
(2) поиск в глубину
(3) модульный поиск
Время работы алгоритма поиска вершинного покрытия
(1) меньше времени работы поиска в глубину
(2) больше времени работы поиска в глубину
(3) равно времени работы поиска в глубину
Последняя пара цифр чисел Фибоначчи образует последовательность с периодом
(1) 120
(2) 270
(3) 300
Проходит ли прямая ax+by+c=0 через начало координат?
(1) да, всегда проходит
(2) нет, не проходит
(3) только при c=0
Что представляет собой бор?
(1) дерево со строками
(2) контейнер
(3) массив инцидентности
Из приведенных ниже записей выделите методы хранения графов:
(1) список возврата
(2) список корреляции
(3) список смежных вершин
Какие из приведенных ниже множеств используются в алгоритме пересечения отрезков?
(1) множество отрезков с точкой события в левом конце
(2) множество отрезков с точкой события в правом конце
(3) множество отрезков, пересекающихся в точке события
Подграф данного графа, содержащий все его вершины и являющийся деревом, носит название
(1) терминальное дерево
(2) остовное дерево
(3) комплексное дерево
К реализациям очереди с приоритетом следует отнести
(1) двоичную кучу
(2) биномиальную кучу
(3) комплексную кучу
Асимптотика бинарной пирамиды в алгоритме Прима оценивается величиной
(1) O(Elog(V2))
(2) O(Elog(V))
(3) O(log(V))
Какую сложность имеет алгоритм Флойда-Уоршелла?
(1) квадратичную
(2) кубическую
(3) экспоненциальную
Граф, содержащий эйлеров путь, носит название
(1) полуэйлеров граф
(2) эйлеров граф
(3) полный граф
Время работы алгоритма Куна
(1) меньше времени работы алгоритма поиска вершинного покрытия
(2) больше времени работы алгоритма поиска вершинного покрытия
(3) равно времени работы алгоритма поиска вершинного покрытия
Задача о независимом множестве эффективно решается методом динамического программирования, если рассматриваемый граф является
(1) деревом
(2) контейнером
(3) гиперграфом
Имеются две прямые: x-y+3=0 и 3x+4y+3=0. Параллельны ли они?
(1) да, параллельны
(2) нет, не параллельны
(3) они перпендикулярны
Из приведенных ниже записей выделите элементы ассоциативного массива:
(1) ключ
(2) ссылка
(3) значение
Дерево отрезков для максимума носит название
(1) RSQ
(2) RMQ
(3) MRQ
Какова вероятность подвесить дерево с одной вершиной?
(1) 0,5
(2) 0
(3) 1
Стек представляет собой
(1) метод идентификации
(2) структуру данных
(3) тип объекта
Может ли степень вершин двоичного дерева быть равной 4?
(1) да, может
(2) нет, не может
(3) только для связного графа
В языке C++ побитовое "или" обозначается символом
(1) |
(2) #
(3) $
Если граф является связным и не содержит простых циклов, он называется
(1) мостом
(2) контейнером
(3) деревом
В двудольных графах нет циклов
(1) четной длины
(2) нечетной длины
(3) как четной, так и нечетной длины
Какие из приведенных ниже записей следует отнести к классическим задачам динамического программирования?
(1) задача о порядке перемножения матриц
(2) задача последовательного принятия решения
(3) задача о выборе траектории
Имеются две прямые: x=1 и -x=-1. Какими они являются?
(1) синхронными
(2) нормированными
(3) дублирующими
Подстрока строки носит название
(1) образец
(2) контейнер
(3) маркер
Возможна ли сортировка массива по неубыванию с помощью сортировки подсчетом?
(1) да, возможна
(2) нет, невозможна
(3) только для комплексных чисел
Наименьший многоугольник, содержащий все данные точки, носит название
(1) матрица вариантности
(2) выпуклая оболочка
(3) поле точек
Может ли двоичное дерево быть деревом поиска?
(1) да, может
(2) нет, не может
(3) только матричное дерево
Если от одной вершины до другой необходимо пройти два ребра, то расстояние между ними составляет
(1) 1
(2) 2
(3) 3
Каким из приведенных ниже типов графов может быть дерево?
(1) ориентированным
(2) модификативным
(3) контекстным
Какие требования к графу выдвигаются алгоритмом Дейкстры?
(1) граф должен быть взвешенным
(2) граф не должен иметь дуг отрицательного веса
(3) граф должен быть терминальным
Связи в графе представляются в виде
(1) дуг
(2) петель
(3) модулей
Множество вершин S графа, такое что, у каждого ребра графа хотя бы один из концов входит в S, носит название
(1) полином вершин
(2) матрица вершин
(3) вершинное покрытие
Центральным результатом теории динамического программирования следует считать
(1) уравнение Беллмана
(2) алгоритм Флойда
(3) теорему Кронекера-Капелли
Что такое вектор?
(1) направленный отрезок
(2) множество точек плоскости
(3) часть луча
Из каких элементов состоит строка?
(1) из символов
(2) из идентификаторов
(3) из обобщений
Задание случайных чисел в Паскале осуществляется с помощью функции
(1) std
(2) random
(3) markup
Каким образом можно произвести сортировку векторов по углу?
(1) с помощью матрицы смежности
(2) с помощью векторного произведения
(3) с помощью вектора инцидентности
Максимальное расстояние от корня до листа в дереве составляет 5. Какова высота дерева?
(1) 4
(2) 5
(3) 6
Очередь без элементов называется
(1) нулевая
(2) нестрогая
(3) пустая
Сколько корней должно иметь дерево?
(1) один
(2) два
(3) множество
Обновление меток носит название
(1) унификация
(2) релаксация
(3) конкатенация
Порядок графа задает
(1) максимальный вес ребра
(2) количество вершин
(3) число меток
От чего зависит размер вершинного покрытия?
(1) от числа вершин
(2) от связности графа
(3) от количества ребер
Если нужно найти n!, то тривиальной задачей может быть
(1) 1! = 1
(2) 0!=1
(3) (n-1)!
Из приведенных ниже записей выделите способы задания прямой на плоскости?
(1) точка и нормаль
(2) матрица смежности
(3) две точки
Можно ли считать запись e38ff строкой?
(1) нет, нельзя
(2) да, можно
(3) использование цифр делает строку числом
Может ли количество вызовов при быстрой сортировке достигнуть 4logN?
(1) нет, предел составляет 2logN
(2) да, может
(3) только для комплексных чисел
Дерево отрезков - это
(1) массив вершин графа
(2) структура данных, позволяющая быстро изменять значение в массиве
(3) взвешенный орграф динамических определений
Верно ли то, что время работы алгоритма поиска в двоичном дереве не зависит от высоты дерева?
(1) да, это верно
(2) нет, это неверно
(3) только для ориентированных графов
Каким из приведенных ниже способов можно реализовать поиск кратчайшего пути к вершине?
(1) поиск по фазе
(2) поиск в контексте
(3) поиск в ширину
Количество поддеревьев узла составляет 2. Какова степень данного узла?
(1) 2
(2) 4
(3) 3
Обозначим через n количество вершин, а через m - количество ребер в графе G. Если для хранения непосещенных вершин использовать фибоначчиеву кучу, то время работы алгоритма Дейкстры составит
(1) O(logn + m)
(2) O(n + m)
(3) O(nlogn + m)
Если два ребра графа имеют общую концевую вершину, они называются
(1) соседними
(2) слитными
(3) смежными
Граф с n вершинами имеет вершинное покрытие размера k тогда и только тогда, когда данный граф имеет незавимимый набор размера
(1) n
(2) k
(3) n-k
Сохранение решений перекрывающихся подзадач носит название
(1) стаффинг
(2) кэширование
(3) импликация
Каким образом выглядит уравнение прямой в декартовых координатах?
(1) ax+by+c=0
(2) ax=ky
(3) O(x,y)=F
Может ли префикс строки быть равен 0?
(1) да, может
(2) нет, не может
(3) только для обобщенных строк
Какой из приведенных ниже методов сортировки занимает наименьшее количество памяти?
(1) быстрая сортировка
(2) сортировка слиянием
(3) сортировка подбором
Дерево отрезков для суммы носит название
(1) SNQ
(2) RSQ
(3) QRS
К деревьям поиска следует отнести
(1) красно-черное дерево
(2) AVL-дерево
(3) 2-3-дерево
Как называется граф, возле ребер которого стоят цифры?
(1) унарный
(2) бинарный
(3) взвешенный
Неконцевой узел носит название
(1) узел соответствия
(2) узел ветвления
(3) узел достижимости
Бинарная матрица, в каждом столбце и строке которой лишь одна единица, а все остальные элементы - 0, носит название
(1) матрица связности
(2) матрица перестановки
(3) матрица возврата
Если вершина является концом одного ребра, то она называется
(1) отделенной
(2) висячей
(3) изолированной
Из каких элементов состоит паросочетание?
(1) из вершин
(2) из ребер
(3) из меток
Из приведенных ниже записей выделите тип графа подзадач для вычисления чисел Фибоначчи:
(1) комплексный
(2) ациклический
(3) приоритетный
Отношение прилежащего катета к гипотенузе, носит название
(1) синус
(2) косинус
(3) тангенс
Несколько последних символов строки представляют собой
(1) суффикс
(2) корень
(3) дополнение
Какие из приведенных ниже методов сортировки обладают устойчивостью?
(1) метод быстрой сортировки
(2) метод сортировки слиянием
(3) метод контекстной сортировки
Сложность изменения в методе RSQ составляет
(1) O(n)
(2) O(nlogn)
(3) O(logn)
Двоичное дерево поиска, у которого каждая вершина является корнем с равной вероятностью, носит название
(1) случайное
(2) модифицированное
(3) контекстное
Что собой представляет вес во взвешенном графе?
(1) максимальную вершину
(2) число возле ребра
(3) число корней графа
Ориентированный граф без циклов, в котором в каждую вершину, кроме одной, входит одно ребро, носит название
(1) конечное дерево
(2) ориентированное дерево
(3) структурное дерево
Информация о существовании путей между вершинами орграфа хранится
(1) в матрице смежности
(2) в матрице достижимости
(3) в матрице вариативности
Путь графа, в котором первая и последняя вершины совпадают, носит название
(1) цикл
(2) инкремент
(3) декремент
Если каждая вершина входит только в одно ребро, то паросочетание называется
(1) конечным
(2) контекстным
(3) полным
Какие из приведенных ниже записей следует отнести к подходам к динамическому программированию?
(1) циклическое и ациклическое программирование
(2) восходящее и нисходящее программирование
(3) модульное и потоковое программирование
Каким образом можно сложить два вектора?
(1) по правилу параллелограмма
(2) по методу координатного сдвига
(3) матричным способом
Несколько символов строки, идущих подряд, представляют собой
(1) подстроку
(2) маркированный суффикс
(3) контейнер
Имеется массив: [7 3 6 4 8]. Каково количество инверсий в данном массиве?
(1) 3
(2) 4
(3) 5
Каким образом можно реализовать хранение деревьев отрезков, способных вычислять сумму и максимум?
(1) в двух массивах одинаковой длины
(2) в матрице инцидентности
(3) в стеке
Для чего в Паскале применяется функция random?
(1) для возврата случайного числа
(2) для округления переменных
(3) для целочисленного деления
К типам очередей следует отнести
(1) кольцевую
(2) матричную
(3) идентификационную
Степени вершин в двоичном дереве не превосходят
(1) 2
(2) 3
(3) 4
Если удаление ребра увеличивает число компонент, такое ребро называется
(1) маркером
(2) мостом
(3) контейнером
Множество вершин является независимым, если
(1) нет ребер, соединяющих вершины этого множества
(2) они входят в остовное поддерево
(3) все вершины связаны ребрами одинакового веса
Эффективность несериального динамического программирования зависит
(1) от метода поиска остовного дерева графа соответствия
(2) от структуры графа взаимосвязей переменных
(3) от типа данных и количества вершин графа смежности
Каким образом выглядит каноническое уравнение прямой, проходящей через точки (x1,y1) и (x2,y2)?
(1) (x-x1)/(x2-x1)= (y-y1)/(y2-y1)
(2) x2/(x2-x1)=y2/(y2-y1)
(3) x1/(x2-x1)= y1/(y2-y1)
За какое время в строке длины N можно найти наибольший префикс, являющийся суффиксом?
(1) O(N)
(2) O(logN)
(3) O(N2)
Имеются два массива: A[7 3 5 6 8] и B[23 4 12 17 8]. В каком из массивов большее количество инверсий?
(1) в массиве A
(2) в массиве B
(3) одинаково
Что представляет собой RMQ?
(1) матрицу
(2) дерево отрезков
(3) контейнер
Имеются два дерева: A и B. C какой вероятностью корень будет лежать в дереве A?
(1) A/(A+B)
(2) A/B
(3) A-B
Метод доступа к объектам в стеке носит название
(1) LIFO
(2) FILO
(3) FIFO
Могут ли исходящие степени вершин двоичного дерева быть равными 3?
(1) да, могут
(2) нет, не могут
(3) только в комплексном графе
Дизъюнкция является
(1) бинарной операцией
(2) инфиксной операцией
(3) когнитивной операцией
Если любые две вершины графа соединены ребром, такой граф называется
(1) комплексным
(2) полным
(3) конечным
К классическим задачам динамического программирования следует отнести
(1) задачу об использовании рабочей силы
(2) задачу о ранце
(3) задачу поиска кратчайшего пути в сети
Если нормаль прямой имеет длину 1, то такая прямая называется
(1) нормальной
(2) нормированной
(3) нормативной
Является ли rt образцом строки dkrtp?
(1) да, является
(2) нет, не является
(3) это контейнер строки
Цифровая сортировка является
(1) линейной
(2) квадратичной
(3) экспоненциальной
За какое время выполняется нахождение минимума на отрезке?
(1) O(logn)
(2) O(1)
(3) O(n)
По первому ключу вершины декартово дерево является
(1) деревом поиска
(2) ассоциативным деревом
(3) матричным деревом
Добавленный в стек элемент становится
(1) первым сверху
(2) вторым сверху
(3) первым снизу
Любое дерево является
(1) комплексным графом
(2) модульным графом
(3) двудольным графом
Если a=01100101, b=00101001, то конъюнкция a и b будет равна
(1) 01001101
(2) 00100001
(3) 00101001
Как называется граф, который можно изобразить диаграммой на плоскости без пересечений рёбер?
(1) маркированный
(2) модификационный
(3) планарный
Дополнением независимого множества является
(1) вершинное покрытие
(2) матрица смежности
(3) контейнер связей
Каким образом можно выразить числа Фибоначчи через многочлены Чебышева?
(1) Fn+1=(-i)nTn(-i)
(2) Fn+1=Tn
(3) Fn+1=(-i)nTn
Имеются две прямые: a1x+b1y+c1=0, a2x+b2y+с2=0. Каков критерий их параллельности?
(1) a1b2=a2b1
(2) a1-b2=a2-b1
(3) a1+b2=a2+b1
Для поиска подстроки в строке можно использовать алгоритм
(1) Флойда-Уоршелла
(2) Кронекера-Капелли
(3) Кнута-Морриса-Прата
Для чего в Паскале используется оператор mod?
(1) для деления по модулю
(2) целевой адрес
(3) контрольная сумма
Какой метод применяется в алгоритме пересечения отрезков?
(1) метод выметающей прямой
(2) метод обобщающих прямых
(3) метод конструктивной матрицы
Какое дерево получится, если во второй ключ вершин декартового дерева записать случайное число?
(1) модульное дерево
(2) пустое дерево
(3) сбалансированное дерево
При поиске в ширину дуги вида (i, i+1), где i - это индекс вершины, порождают
(1) остовный бесконтурный орграф
(2) поисковый орграф
(3) модульный орграф
Каждый узел в дереве задаёт
(1) маркер
(2) контекст
(3) поддерево
В чем основное отличие алгоритма Беллмана-Форда от алгоритма Дейкстры?
(1) возможность использования отрицательных ребер
(2) использование дизъюнкции
(3) модификация бинарной матрицы
Таблица, в которой каждая строка соответствует определённой вершине графа, а столбцы соответствуют связям графа, носит название
(1) матрица модульности
(2) матрица инцидентности
(3) матрица определений
Если в графе есть удлиняющая цепь, то размер паросочетания можно увеличить
(1) на 1
(2) на квадрат числа вершин
(3) на бесконечное число
Характеристический многочлен возвратной последовательности чисел Фибоначчи имеет вид
(1) x2-x-1
(2) x2-1
(3) 2x-x2
Сколько координат имеет точка пересечения двух прямых в двухмерном пространстве?
(1) 1
(2) 2
(3) 3
(4) 4
Увеличение размера сдвига образца
(1) увеличивает скорость алгоритма КМП
(2) уменьшает скорость алгоритма КМП
(3) не изменяет скорость алгоритма КМП
Ссылки на элементы списка в динамической памяти носят название
(1) указатели
(2) модификаторы
(3) мосты
Самый верхний из пересекающихся отрезков в алгоритме пересечения отрезков после точки пересечения становится
(1) вторым верхним
(2) вторым нижним
(3) самым нижним
Для того, чтобы посчитать функцию на отрезке можно использовать
(1) ассоциативные деревья
(2) модульные деревья
(3) деревья Фейнвика
Из приведенных ниже записей выделите недостатки применения очередей в динамическом программировании:
(1) фрагментация памяти
(2) использование контейнеров данных
(3) ограничение очереди по памяти
Из приведенных ниже записей выделите алгоритмы построения минимального остовного дерева:
(1) алгоритм Коши
(2) алгоритм Прима
(3) алгоритм возвратных вершин
Каким образом в алгоритме Беллмана-Форда можно определить, существует ли в графе G отрицательный цикл?
(1) модифицировать вершины графа
(2) произвести дополнительную внешнюю итерацию цикла
(3) пересмотреть кратчайшие пути остовных поддеревьев
Если ребро графа может соединять более двух вершин, то такой граф называется
(1) гиперграф
(2) псевдограф
(3) ультраграф
Время работы поиска в глубину оценивается выражением
(1) O(V2)
(2) O(logE)
(3) O(ElogE)
Произведение и частное двух любых различных чисел Фибоначчи, отличных от единицы
(1) всегда является числом Фибоначчи
(2) никогда не является числом Фибоначчи
(3) может являться числом Фибоначчи
Для чего используется формула Крамера?
(1) для поиска значений с помощью определителя
(2) для формирования матрицы смежности
(3) для поиска точек пересечения прямы
Каким образом определяется префикс-функция?
(1) с помощью префикса
(2) с помощью матрицы инцидентности
(3) с помощью алгоритма Флойда-Уоршелла
Что представляет собой список?
(1) тип данных
(2) структуру данных
(3) упорядоченный массив
Удаление точки пересечения отрезков, которые временно перестают быть соседними при данном положении выметающей прямой, применяется для избегания использования
(1) квадрата памяти
(2) матрицы совместимости
(3) графа полярности
Эффективность несериального динамического программирования зависит
(1) от метода поиска остовного дерева графа соответствия
(2) от структуры графа взаимосвязей переменных
(3) от типа данных и количества вершин графа смежности
Какие из приведенных ниже операций поддерживает очередь с приоритетом?
(1) добавление пары
(2) поиск пары с минимальным ключом
(3) извлечение пары с минимальным ключом
Выходом алгоритма Прима является
(1) множество рёбер минимального остовного дерева
(2) множество узлов минимального остовного дерева
(3) множество вершин минимального остовного дерева
Алгоритм Флойда-Уоршелла используется
(1) для неориентированного графа
(2) для ориентированного графа
(3) для детерминированного графа
Что такое процедура DFS?
(1) поиск по меткам
(2) поиск в глубину
(3) поиск по связям
Для чего используется алгоритм Куна?
(1) для поиска вершинного покрытия
(2) для поиска остовного дерева
(3) для поиска минимальных путей
Последняя тройка цифр чисел Фибоначчи образует последовательность с периодом
(1) 1500
(2) 2000
(3) 3500
От чего зависят координаты точки пересечения перпендикулярных прямых?
(1) от коэффициентов прямых
(2) от направления прямых
(3) от определителей смежности
Дерево в бору является
(1) подвешенным
(2) маркированным
(3) комплексным
Для чего может применяться список смежных вершин?
(1) для возврата данных
(2) для расстановки метод
(3) для хранения графа
Если не удалять точки пересечения отрезков, которые перестали быть соседними, алгоритм пересечения отрезков занимает времени
(1) O(n)
(2) O(n+n2)
(3) O(nlogn)
Ориентированный граф без циклов, в котором в каждую вершину, кроме одной, входит одно ребро, носит название
(1) конечное дерево
(2) ориентированное дерево
(3) структурное дерево
Очередь с приоритетом является
(1) методом реализации данных
(2) абстрактным типом данных
(3) идентификатором последовательности данных
Асимптотика Фибоначчиевой пирамиды в алгоритме Прима оценивается величиной
(1) O(logV2)
(2) O(E + Vlog(V))
(3) O(V2-1)
О чего зависит сложность алгоритма Флойда-Уоршелла?
(1) от количества вершин
(2) от связности графа
(3) от модуля весов ребер
Связный ориентированный граф содержит эйлеров цикл тогда и только тогда, когда для каждой вершины графа её полустепень захода равна
(1) 1
(2) 2
(3) полустепени исхода
Верно ли то, что алгоритм Куна работает быстрее, чем поиск в глубину?
(1) да, это верно
(2) нет, это неверно
(3) только для маркированных графов
Задача о независимом множестве является
(1) циклической
(2) симплексной
(3) NP-полной
Какие данные необходимы для задания окружности на плоскости?
(1) радиус
(2) координаты центра
(3) матрица достижимости точек
Верно ли, что ассоциативный массив не может хранить две пары с одинаковыми ключами?
(1) да, это верно
(2) нет, это неверно
(3) только для маркированных массивов