Главная / Образование / Базовые и "продвинутые" алгоритмы для школьников

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

Правильные ответы выделены зелёным цветом.
Все ответы: В курсе рассказывается о базовых и "продвинутых" (advanced) алгоритмах для школьников. Этот курс читался на летней компьютерной школе для участников олимпиад по информатике.
Смотрите также:
Программирование
Алгоритмы и дискретные структуры
Какое время занимает алгоритм быстрой сортировки?
(1) O(nlogn)
(2) O(logn)
(3) O(n)
Точка отсчёта полярной системы координат носит название
(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) FIND
(2) DEPEND
(3) ADDICT
К основным проблемам в машинном представлении строкового типа следует отнести
(1) существенный размер строк
(2) изменение размера строк со временем
(3) невозможность осуществлять выборку из строк
К методам обхода и разметки вершин графа следует отнести
(1) контейнер
(2) список
(3) маркер
Сколько памяти занимает хранение матрицы смежности?
(1) квадрат количества вершин
(2) логарифм количества вершин
(3) количество вершин
Число вершин в графе носит название
(1) порядок
(2) глубина
(3) высота
Куча использует память, выделенную
(1) контекстно
(2) статически
(3) модульно
Для связных графов остовный лес называется
(1) остовное дерево
(2) остовный комплекс
(3) остовный контейнер
Входом алгоритма Прима является
(1) терминальный ориентированный граф
(2) связный неориентированный граф
(3) комплексный сильно связный граф
Количество разбиений числа 2 составляет
(1) 1
(2) 2
(3) 3
Сколько в дереве существует способов добраться от одной вершины к другой?
(1) 1
(2) 2
(3) зависит от глубины дерева
Количество сравнений в худшем случае при быстрой сортировке составляет
(1) CN = 2CN/2+N
(2) CN = NlogN
(3) CN = 2C2N
Длину соответствующего вектору направленного отрезка называют
(1) величиной
(2) модулем
(3) итератором
К операциям обхода узлов дерева следует отнести
(1) INFIX_ATTACH
(2) INFIX_DEPEND
(3) INFIX_TRAVERSE
К недостаткам хранения строки в виде массива символов следует отнести
(1) проблемы с хранением и обработкой символов произвольной длины
(2) содержание в строке любых данных
(3) ограничение максимального размера строки
Количество элементов в списке, исключая последний элемент, носит название
(1) размер списка
(2) порядок списка
(3) глубина списка
Какие значения могут содержаться в матрице инцидентности?
(1) 1
(2) 0
(3) end
Если множества концевых вершин графа совпадают, то такие графы называются
(1) четными
(2) кратными
(3) битовыми
Функция выделения динамической памяти библиотеки С носит название
(1) new
(2) create
(3) malloc
В системе непересекающихся множеств каждому подмножеству назначается
(1) итератор
(2) представитель
(3) модификатор
Если приоритетная очередь вершин графа реализована как обычный массив, то операция извлечения минимальных вершин выполняется
(1) за O(logn)
(2) за O(n2)
(3) за O(n)
Количество разбиений числа 6 составляет
(1) 10
(2) 11
(3) 12
Тип организации, в котором каждый объект связан с хотя бы одним другим, носит название
(1) древовидная структура
(2) матрица смежности
(3) массив векторов
При выборе опорного элемента из данного диапазона случайным образом ожидаемое время выполнения алгоритма быстрой сортировки составляет
(1) O(nlogn)
(2) O(logn)
(3) O(n2)
Сложение двух свободных векторов можно осуществлять по правилу
(1) прямоугольника
(2) параллелограмма
(3) треугольника
Можно ли использовать бинарное дерево поиска использовать для сортировки?
(1) нет, нельзя
(2) да, можно
(3) только в комплексной плоскости
К алфавитам с переменным размером символа следует отнести
(1) UTF-8
(2) Unisef-11
(3) ASCII-257
К основным операциям над списками следует отнести
(1) проход по списку
(2) составление дерева списка
(3) конкретизацию ключей списка
Для чего используется алгоритм Форда-Беллмана?
(1) для формирования матрицы смежности
(2) для поиска кратчайшего пути во взвешенном графе
(3) для вывода списка ребер
Если ребра в пути не повторяются, такой путь является
(1) циклическим
(2) простым
(3) массивным
Функция стандартной библиотеки языка С, предназначенная для освобождения ранее выделенной динамической памяти, носит название
(1) erase
(2) delete
(3) free
Система непересекающихся множеств очень удобна для хранения
(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) приложение
Глубина каждого поддерева T при использовании Union-By-Size на СНМ не может превысить величину
(1) log|T|
(2) 2T
(3) 2T-1
Положение о том, что оптимальное решение подзадач меньшего размера может быть использовано для решения исходной задачи, является принципом
(1) оптимальной подструктуры
(2) модульного контекста
(3) терминального программирования
Представление числа в упорядоченную сумму натуральных слагаемых носит название
(1) терминация
(2) композиция
(3) сегрегация
Уровень корня дерева равен
(1) 0
(2) 1
(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) только в орграфах
Чтобы ускорить операцию Find(x) на СНМ используется
(1) сжатие путей
(2) трассировка компонент связности
(3) стек вершин
Сохранение в памяти подзадач для их использования носит название
(1) терминация
(2) кэширование
(3) модулирование
Разрешаются ли нулевые слагаемые в композициях?
(1) да, разрешаются
(2) нет, не разрешаются
(3) только в комплексной плоскости
Множество, не содержащее ни одного непересекающегося дерева или содержащее несколько непересекающихся деревьев, носит название
(1) бор
(2) лес
(3) роща
Время работы алгоритма сортировки слиянием составляет
(1) O(nlogn)
(2) O(logn)
(3) O(n)
Все координаты нулевого вектора в любой аффинной системе координат равны
(1) -1
(2) 0
(3) 1
Последовательность элементов множества образующих выпуклую оболочку для этого множества определяется
(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) возвести это число в квадрат
Неориентированное дерево, в котором степени вершин не превосходят 3, называется
(1) тернарным
(2) бинарным
(3) унарным
При сортировке подсчетом используется
(1) диапазон чисел
(2) маркировка данных
(3) проверка числа вхождений в массив
Вектор, задающий положения точки в пространстве относительно некоторой заранее фиксированной точки, носит название
(1) тензор-вектор
(2) нуль-вектор
(3) радиус-вектор
В худшем случае алгоритм Джарвиса работает за время
(1) O(n2)
(2) O(n)
(3) O(logn)
Сколько сравнений обрабатывает алгоритм грубой силы?
(1) 2h
(2) logh
(3) h
Для чего протокол OSPF использует алгоритм Дейкстры?
(1) для вывода данных
(2) для устранения кольцевых маршрутов
(3) для формирования массивов индексов вершин
Кратчайшие пути между всеми парами вершин взвешенного ориентированного графа можно найти с помощью
(1) алгоритма Брайана
(2) алгоритма Джонсона
(3) алгоритма Стеффсона
Для топологической сортировки граф должен быть
(1) последовательным
(2) комплексным
(3) без циклов
Граф, содержащий эйлеров цикл, носит название
(1) коммутативный граф
(2) детерминальный граф
(3) эйлеров граф
Сколько времени потребует сортировка ребер графа по весу?
(1) O(Elog(E))
(2) O(log(E))
(3) O(E)
К методам решения задачи нахождения наибольшей общей подпоследовательности следует отнести
(1) полный перебор
(2) массив вершин
(3) динамическое программирование
Коэффициенты в разложении (1 + x)n по степеням x носят название
(1) биномиальные коэффициенты
(2) транзитивные коэффициенты
(3) модальные коэффициенты
Любое дерево является
(1) декрементным графом
(2) двудольным графом
(3) сильно связным графом
К типам алгоритма сортировки подсчетом следует отнести
(1) алгоритм со списком
(2) массивный алгоритм
(3) контекстный алгоритм
Базис, в качестве которого выбран единичный вектор, называется
(1) нормированным
(2) матричным
(3) комплексным>
В алгоритме Грэхема задача о выпуклой оболочке решается с помощью
(1) матрицы
(2) стека
(3) кучи
Алгоритмы поиска подстроки могут быть основаны
(1) на массивном сравнении
(2) на сравнении сначала
(3) на модальном сравнении
От чего зависит сложность алгоритма Дейкстры?
(1) от типа данных
(2) от способа нахождения вершины
(3) от метода формирования меток
Время работы алгоритма Джонсона равно
(1) O(V2lgV + VE)
(2) O(ElogV)
(3) O(EV2)
При топологической сортировке номер начала дуги
(1) меньше номера конца дуги
(2) больше номера конца дуги
(3) равен номеру конца дуги
Если каждая вершина связного графа имеет четную степень, такой граф является
(1) эйлеровым
(2) комплексным
(3) терминальным
Алгоритм Краскала является частным случаем алгоритма
(1) Коши
(2) Радо-Эдмондса
(3) Гамильтона
В задаче поиска наибольшей увеличивающейся подпоследовательности такая подпоследовательность
(1) всегда будет подстрокой
(2) никогда не будет подстрокой
(3) может не являться подстрокой
Что обозначает запись n!?
(1) факториал
(2) разбиение
(3) биекцию
Геометрическая фигура, являющаяся n-мерным обобщением треугольника, носит название
(1) симплекс
(2) икосаэдр
(3) триангулятор
Является ли алгоритм со списком устойчивым?
(1) не всегда
(2) да, является
(3) нет, не является
Все собственные значения самосопряжённого оператора являются
(1) действительными
(2) вещественными
(3) коммутативными
Каким образом в стеке по завершении работы алгоритма Грэхема хранятся точки?
(1) в порядке обхода по часовой стрелке
(2) в порядке обхода против часовой стрелки
(3) в произвольном порядке
Снижение сложности алгоритма Рабина-Карпа достигается за счет
(1) хеширования
(2) импликации
(3) терминации
Для разреженных графов сложность алгоритма Дейкстры составляет
(1) O(nlogn + mlogn)
(2) O(mlogn)
(3) O(nlogm)
При поиске в глубину всегда развертывается
(1) самый глубокий узел
(2) самый доступный узел
(3) самый первый узел
В каком случае орграф называется сильно связным?
(1) если любые две его вершины сильно связаны
(2) если все его вершины сильно связаны
(3) если из каждой вершины существует не меньше двух путей в остальные
Связный ориентированный граф содержит эйлеров цикл тогда и только тогда, когда для каждой вершины графа её полустепень захода равна
(1) 0
(2) 1
(3) её полустепени исхода
Верно ли то, что линии разреза графа могут пересекать произвольное число ребер и хорд?
(1) да, верно
(2) нет, неверно
(3) только в циклическом графе
К операциям редактирования строки следует отнести
(1) добавление символа в произвольную позицию
(2) удаление символа
(3) замену одного символа другим
Каждое число треугольника Паскаля равно
(1) произведению двух предыдущих
(2) сумме двух предыдущих
(3) разности двух предыдущих
2-симплекс - это
(1) вектор
(2) треугольник
(3) луч
Линейная вычислительная сложность цифровой сортировки составляет
(1) O(logn)
(2) O(3n)
(3) O(n)
Простейшим примером аксиального вектора в трёхмерном пространстве является
(1) матричное произведение
(2) скалярное произведение
(3) векторное произведение
Выпуклой оболочкой множества X называется
(1) наибольшее выпуклое множество, содержащее X
(2) наименьшее выпуклое множество, содержащее X
(3) полиномиальное выпуклое множество, содержащее X
Алгоритм Бойера-Мура, оптимизированный под короткие алфавиты, носит название
(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) итератор
Выпуклая оболочка множества X обычно обозначается
(1) ConvX
(2) DetX
(3) LespX
Эмпирический алгоритм поиска подстроки, оптимизированный под английские тексты, носит название
(1) алгоритм Максвелла
(2) алгоритм Корнера
(3) алгоритм Райты
Перед применением поразрядной сортировки следует знать
(1) максимальное количество разрядов в сортируемых величинах
(2) количество возможных значений одного разряда
(3) глубину рекурсии
Для пространства состояний с коэффициентом ветвления 4 и максимальной глубиной 5 поиск в глубину требует хранения
(1) 15 узлов
(2) 21 узел
(3) 24 узла
Множество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, носит название
(1) массив соответствия графа
(2) компонента связности графа
(3) список зацикленных ребер
Гамильтонов цикл является
(1) терминальным циклом
(2) простым остовным циклом
(3) модульным циклом
О чем говорит теорема Форда-Фалкерсона?
(1) о максимальном потоке в графе
(2) о минимальном потоке в графе
(3) об оптимальном потоке в графе
Суммы биномиальных коэффициентов на диагоналях треугольника Паскаля являются
(1) числами Эйлера
(2) числами Фибоначчи
(3) числами Коши
Представление группы в пространстве которого есть собственное инвариантное подпространство называется
(1) контекстным
(2) заменяемым
(3) приводимым
Разбиение топологического пространства на симплексы носит название
(1) триангуляция
(2) маркировка
(3) детерминация
Время работы алгоритма быстрой сортировки составляет
(1) O(n2)
(2) O(n)
(3) O(nlogn)
Луч, начинающийся в полюсе полярной системы координат, называется
(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) INSERT
(2) ADJUST
(3) INVOKE
Каким образом можно хранить строки в памяти компьютера?
(1) в виде симплекса
(2) в виде массива символов
(3) с помощью метода завершающего байта
Операция для доступа к элементам внутри списка носит название
(1) модификатор
(2) селектор
(3) контейнер
В матрице инцидентности строки соответствуют
(1) вершинам графа
(2) ребрам графа
(3) итераторам графа
Число ребер в графе определяет
(1) ширину графа
(2) размер графа
(3) степень графа
В любой момент времени существования кучи вся память, на которой работает куча, разделена
(1) на занятую и свободную
(2) на системную и прикладную
(3) на строгую и нестрогую
Скелет графа - это
(1) остовное дерево
(2) компонента связности
(3) минимальный эйлеров путь
Выходом алгоритма Прима является
(1) матрица смежности
(2) множество рёбер минимального остовного дерева
(3) комплексный граф соответствия
Каково количество разбиений числа 4?
(1) 5
(2) 8
(3) 12
Верно ли то, что для любой вершины дерева есть один и только один способ добраться до любой другой вершины?
(1) нет, это неверно
(2) таких путей может и не быть
(3) да, это верно
Сколько сравнений происходит в худшем случае при использовании быстрой сортировки?
(1) O(n2)
(2) O(nlogn)
(3) O(logn)
К типам векторов следует отнести
(1) свободные вектора
(2) массивные вектора
(3) терминальные вектора
Из приведенных ниже записей выделите операции обхода узлов дерева:
(1) PREFIX_UNION
(2) PREFIX_TRAVERSE
(3) PREFIX_VERSION
К методам завершающего байта следует отнести
(1) ASCIIZ
(2) C-strings
(3) метод нуль-терминированных строк
Из приведенных ниже записей выберите характерные особенности списков:
(1) тип элементов
(2) отсортированность
(3) возможность доступа
Если связь является петлей, в матрицу инцидентности записывается
(1) 0
(2) 1
(3) любое число, кроме 0, 1, -1
Если концы ребра совпадают, то ребро называется
(1) дугой
(2) петлей
(3) маркером
Функция malloc принимает в качестве аргумента
(1) количество распределяемых элементов
(2) размер выделяемой области
(3) время исполнения
Какими из приведенных ниже операциями определяется абстрактная структура данных в системе непересекающихся множеств?
(1) Union
(2) Find
(3) Define
Если приоритетная очередь вершин графа реализована как бинарная пирамида, то операция извлечения минимальных вершин выполняется
(1) за O(logn)
(2) за O(nlogn)
(3) за O(1)
Каково количество разбиений числа 8?
(1) 22
(2) 24
(3) 32
Древовидная структура - это
(1) тип организации, в котором каждый объект связан с хотя бы одним другим
(2) метод формирования матрицы совместимости
(3) компонента связного взвешенного графа, предназначенная для прохода вершин по алгоритму Прима
Самым быстродействующим из всех существующих алгоритмов обменной сортировки является
(1) алгоритм Шелла
(2) алгоритм быстрой сортировки
(3) алгоритм массивной сортировки
Сложение двух скользящих векторов определено лишь в случае, когда прямые, на которых они расположены
(1) не пересекаются
(2) пересекаются
(3) перпендикулярны
Если элементы массива различны и расположены в случайном порядке, а длина массива N, алгоритм сортировки с помощью бинарного дерева поиска требует в среднем
(1) O(NlogN)
(2) O(logN)
(3) O(N)
К недостаткам использования метода завершающего байта следует отнести
(1) долгое выполнение операций получения длины и конкатенации строк
(2) отсутствие средств контроля за выходом за пределы строки
(3) использование символа завершающего байта в качестве элемента строки
Из приведенных ниже записей выделите основные операции над списками:
(1) модуляция списка
(2) форматирование списка
(3) включение в список
Граф в алгоритме Форда-Беллмана должен быть
(1) статическим
(2) динамическим
(3) взвешенным
Тип представления графа в памяти, подразумевающий, что каждое ребро представляется номерами вершин этого ребра, носит название
(1) массив ребер
(2) список ребер
(3) компонента ребер
Функция free может принимать на вход
(1) NULL
(2) указатель на область, подлежащую освобождению
(3) количество освобождаемых элементов
Для чего в СНМ используется операция MakeSet?
(1) для создания элемента
(2) для вывода данных
(3) для формирования остовного дерево
Задачи динамического программирования характеризуются
(1) оптимальной подструктурой
(2) перекрывающимися подзадачами
(3) динамическими модульными массивами
Для чего применяется диаграмма Юнга?
(1) для представления разбиения числа
(2) для вывода матрицы смежности
(3) для связывания компонент графа
Узел дерева со степенью нуль носит название
(1) ветвь
(2) лист
(3) вершина
К достоинствам алгоритма быстрой сортировки следует отнести
(1) простоту реализации
(2) хорошее сочетание с алгоритмом подкачки памяти
(3) быстродействие
Скалярное произведение перпендикулярных векторов равно
(1) 0
(2) 1
(3) -1
Двоичное дерево может
(1) быть связным матричным деревом
(2) являться пустым
(3) состоять из данных и двух поддеревьев
К операциям при трактовке строк как списков относят
(1) свертку
(2) отображение одного списка на другой
(3) фильтрацию списка по критерию
Поиск в ширину пометит все вершины графа, если этот граф
(1) контекстный
(2) связный
(3) модификативный
Длина пути в графе - это
(1) количество пройденных ребер
(2) сумма весов ребер пути
(3) сумма по столбцу матрицы достижимости
Вершина, степень которой равна 1, носит название
(1) стойкая
(2) висячая
(3) аддитивная
Какие из приведенных ниже операций поддерживает очередь с приоритетом?
(1) добавление в очередь элемента с назначенным приоритетом
(2) извлечение из очереди и возврат элемента с наивысшим приоритетом
(3) просмотр элемента с наивысшим приоритетом без извлечения
При использовании эвристики Union-By-Size worst-case-время операции Find составляет
(1) O(logn)
(2) O(n)
(3) O(1)
Подзадачи, которые используются для решения некоторого количества задач большего размера, носят название
(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(1)
(2) O(n)
(3) O(logn)
Функция Аккермана возвращает
(1) натуральное число
(2) комплексное число
(3) массив вершин
К типам динамического программирования следует отнести
(1) восходящее динамическое программирование
(2) модульное динамическое программирование
(3) контекстное динамическое программирование
Сколько существует композиций числа 5?
(1) 7
(2) 13
(3) 16
Ориентированный граф без циклов, в котором в каждую вершину, кроме одной, входит одно ребро, носит название
(1) статическое дерево
(2) ориентированное дерево
(3) динамическое дерево
Расход памяти для сортировки слиянием
(1) ниже, чем для быстрой сортировки
(2) выше, чем для быстрой сортировки
(3) равен быстрой сортировке
Сумма любых двух противоположных векторов является
(1) нулевым вектором
(2) маркером
(3) скаляром
Для чего используется алгоритм Джарвиса?
(1) для поиска выпуклой оболочки
(2) для формирования матрицы достижимости
(3) для составления компоненты смежности
Массив Z, каждый элемент которого Z[i] равен наидлиннейшему префиксу подстроки, начинающейся с позиции i в строке S, который одновременно является и префиксом всей строки S, носит название
(1) Z-функция
(2) Z-индекс
(3) Z-модуль
Каких ребер не должно быть в графе для применения алгоритма Дейкстры?
(1) положительного веса
(2) отрицательного веса
(3) нулевого веса
Сложность алгоритма Флойда выражается временем
(1) O(n3)
(2) O(n2)
(3) O(n)
Граф при топологической сортировке должен быть
(1) ориентированным
(2) сильно связанным
(3) априорным
Эйлеров путь - это
(1) кратчайший путь в компоненте связности
(2) путь, проходящий по всем рёбрам графа и притом только по одному разу
(3) путь в графе, который проходит ребра с максимальным весом
Для нахождения остовного леса минимального веса в данном графе используется
(1) алгоритм Краскала
(2) алгоритм Коши
(3) алгоритм Эйлера
Несериальное динамическое программирование рассматривает множество ограничений и целевую функцию
(1) как статическую функцию
(2) как рекурсивно вычислимую функцию
(3) как комплексную функцию
Общее количество композиций числа с нулевыми слагаемыми составляет
(1) экспоненту числа
(2) квадрат числа
(3) бесконечность
Ориентированное дерево, в котором исходящие степени вершин не превосходят 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) O(1)
(2) O(Elog(E))
(3) O(E2)
Время работы полного перебора при решении задачи задачи нахождения наибольшей общей подпоследовательности будет равно
(1) экспоненте длины строки
(2) логарифму длины строки
(3) квадрату длины строки
Для биномиальных коэффициентов производящей функцией является
(1) (1 + x)n-1
(2) (1 + x)2n
(3) (1 + x)n
Любое дерево, содержащее счётное количество вершин, является
(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(n)
(3) O(n2)
Биномиальные коэффициенты используются
(1) в комбинаторных задачах
(2) в теории вероятностей
(3) в машинных словах
Выпуклая оболочка n+1 точек, не лежащих в одной n-мерной гиперплоскости, называется
(1) комплексом
(2) аффикцией
(3) симплексом
Алгоритм со списком занимает времени
(1) O(n)
(2) O(logn)
(3) O(n2)
Все собственные значения антиэрмитового оператора являютсять
(1) действительными
(2) мнимыми
(3) целыми
Время работы алгоритма Грэхема равно
(1) O(n2)
(2) O(nlgn)
(3) O(n)
К алгоритмам поиска подстроки, основанным на сравнении с начала, следует отнести
(1) автоматный алгоритм
(2) алгоритм Апостолико-Крошмора
(3) алгоритм Санди
Удаление для фибоначчиевой кучи происходит в среднем за время
(1) O(logn)
(2) O(n)
(3) O(n2)
Очередь LIFO носит название
(1) стек
(2) контейнер
(3) массив
Если существуют ориентированные пути из одной вершины в другую и обратно, то такие вершины являются
(1) модульными
(2) сильно связными
(3) комплексными
Если в вершину входит столько же ребер, сколько из нее и выходит, то её полустепень захода
(1) больше ее полустепени исхода
(2) меньше ее полустепени исхода
(3) равна ее полустепени исхода
Для получения главного сечения графа нужно линию сечения графа провести таким образом, чтобы она при произвольном пересечении хорд пересекала
(1) только одну ветвь графа
(2) не менее двух ветвей графа
(3) все верви графа
Мера разницы двух последовательностей символов (строк) относительно минимального количества операций вставки, удаления и замены, необходимых для перевода одной строки в другую, носит название
(1) динамическое расстояние
(2) редакционное расстояние
(3) комплексное расстояние
Если рассмотреть ряды в треугольнике Паскаля, состоящие из биномиальных коэффициентов, то в пределе получится
(1) распределение Коши
(2) распределение Гаусса
(3) распределение Майера
3-симплекс - это
(1) треугольник
(2) тетраэдр
(3) додекаэдр
Когда несколько различных элементов попадает в одну ячейку эффективность алгоритма цифровой сортировки
(1) возрастает
(2) падает
(3) остается неизменной
Комплексный вектор, имеющий нулевую длину, носит название
(1) априорный
(2) аксиальный
(3) изотропный
Наименьшее выпуклое множество, содержащее X, носит название
(1) пространство вариантов множества X
(2) выпуклая оболочка множества X
(3) матрица вариативности множества X
Какой алгоритм эффективен только в случае, когда искомая подстрока меньше машинного слова?
(1) алгоритм комплексного поиска
(2) алгоритм Бойера-Мура
(3) алгоритм Shift-Or
Каждый ключ при поразрядной сортировке представляется
(1) в линейном виде
(2) в двоичном виде
(3) в матричном виде
После того как при поиске в глубину был развернут некоторый узел
(1) он может быть удален из памяти
(2) он хранится в матрице смежности
(3) он записывается в конец стека вершин
Каким образом можно проверить достижимость вершин?
(1) транзитивным замыканием
(2) методом Хаффмана
(3) с помощью массива тождеств графа
В каком случае можно не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине?
(1) если все вершины нечетные
(2) если все вершины четные
(3) это невозможно
В условии допустимости для потока в графе используется
(1) количество вершин
(2) пропускная способность дуги
(3) массив итераторов рекурсии
Если строки равны, дистанция Левенштейна равна
(1) 0
(2) 1
(3) -1
Гомоморфизм заданной группы в группу невырожденных линейных преобразований векторного пространства носит название
(1) линейное представление группы
(2) квадратичное представление группы
(3) модульное представление группы
Объём симплекса вычисляется с помощью
(1) определителя Герона
(2) определителя Кэли-Менгера
(3) определителя Эйлера
К вариантам сортировки подсчетом следует отнести
(1) модульную сортировку
(2) комплексную сортировку
(3) блочную сортировку
К примерам скаляров следует отнести
(1) длину
(2) площадь
(3) время
Что обозначает запись ConvX?
(1) матрицу совместимости X
(2) выпуклую оболочку X
(3) дерево поиска X
Какой алгоритм позволяет за один проход по исследуемым строкам найти одну строку из нескольких?
(1) алгоритм Санди
(2) алгоритм конечных автоматов
(3) алгоритм Ахо-Корасик
Количество проходов при поразрядной сортировке равно
(1) количеству возможных значений одного разряда
(2) максимальному количеству разрядов в сортируемых величинах
(3) глубине дерева поиска
Для пространства состояний с коэффициентом ветвления 3 и максимальной глубиной 4 поиск в глубину требует хранения
(1) 10 узлов
(2) 11 узлов
(3) 13 узлов
Теория, описывающая возникновение бесконечных связных структур, состоящих из отдельных элементов, носит название
(1) теория протекания
(2) теория аддитивности
(3) теория коммутативности
Гамильтонов путь, начальная и конечная вершины которого совпадают, называется
(1) полуэйлеровым циклом
(2) гамильтоновым циклом
(3) терминальным циклом
Согласно теореме Форда-Фалкерсона величина максимального потока равна величине
(1) минимального разреза
(2) компоненты связности
(3) терминальной матрицы ребер
К задачам комбинаторной оптимизации следует отнести
(1) задачу о перекрывающихся додекаэдрах
(2) задачу о мостах Кенигсберга
(3) задачу о ранце
Гомоморфизм группы в группу всех обратимых преобразований некоторого множества является
(1) представлением группы
(2) биекцией группы
(3) проекцией группы
Триангуляция Делоне осуществляется для точек, именуемых
(1) маркерами
(2) итераторами
(3) сайтами
Сколько элементов входит в базу рекурсии алгоритма быстрой сортировки?
(1) 1-2 элемента
(2) 5-6 элементов
(3) все элементы
От скольких координат зависит точка в полярной системе координат?
(1) 1
(2) 2
(3) 3
BST - это
(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) ESCAPE
(2) REMOVE
(3) RETRY
Из приведенных ниже записей выделите преимущества хранения строки в виде массива символов:
(1) строка может содержать любые данные
(2) возможно на программном уровне следить за выходом за границы строки при её обработке
(3) программа в каждый момент времени знает о размере строки
Функция для списка, возвращающая булевское значение в зависимости от некоторых условий, носит название
(1) объект
(2) предикат
(3) маркер
В матрице инцидентности столбцы соответствуют
(1) вершинам графа
(2) связям графа
(3) модификаторам графа
Если два ребра имеют общую концевую вершину, то они являются
(1) соседними
(2) побочными
(3) смежными
Перед началом работы программы выполняется
(1) модификация кучи
(2) инициализация кучи
(3) комплектация кучи
Сколько вершин графа содержит остовный лес?
(1) половину
(2) одну
(3) все
От чего зависит асимптотика алгоритма Прима?
(1) от способа хранения графа
(2) от способа хранения вершин, не входящих в дерево
(3) от способа хранения матрицы смежности
Сколько разбиений содержит число 7?
(1) 13
(2) 15
(3) 18
Может ли дерево содержать циклы?
(1) да, может
(2) нет, не может
(3) только коммутативное дерево
При большом количестве элементов быстрая сортировка приведет
(1) к исчерпанию памяти
(2) к вызову дополнительной ветви рекурсии
(3) к зацикливанию процедуры
Из приведенных ниже записей выделите типы векторов:
(1) априорные вектора
(2) скользящие вектора
(3) фиксированные вектора
Какие из приведенных ниже операций относятся к операциям обхода узлов дерева?
(1) POSTFIX_ADDICT
(2) POSTFIX_TRAVERSE
(3) POSTFIX_TREND
Из приведенных ниже записей выделите преимущества использования метода завершающего байта:
(1) отсутствие дополнительной служебной информации о строке
(2) возможность представления строки без создания отдельного типа данных
(3) отсутствие ограничения на максимальный размер строки
Данные, хранимые в списках должны быть
(1) однотипными
(2) массивными
(3) комплексными
Каждое ребро графа в списке ребер представляется
(1) номерами вершин ребра
(2) маркерами ребра
(3) весом ребра
Конечная последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром, носит название
(1) контейнер
(2) путь
(3) трасса
К аргументам функции calloc следует отнести
(1) время вызова
(2) количество распределяемых элементов
(3) размер каждого распределяемого элемента
Из приведенных ниже записей выделите операции, которыми определяется абстрактная структура данных в системе непересекающихся множеств:
(1) Rewrite
(2) Find
(3) MakeSet
Если приоритетная очередь вершин графа реализована как фибоначчиевая пирамида, то операция извлечения минимальных вершин выполняется
(1) за O(2n)
(2) за O(1)
(3) за O(logn)
Сколько разбиений содержит число 10?
(1) 11
(2) 34
(3) 42
Формально дерево определяется как конечное множество
(1) матриц
(2) узлов
(3) симплексов
Деградация алгоритма быстрой сортировки по скорости составляет
(1) O(n2)
(2) O(logn)
(3) O(2n)
Сложение двух фиксированных векторов определено лишь в случае, когда они
(1) пересекаются
(2) имеют общее начало
(3) параллельны
Чтобы сбалансировать дерево, следует использовать
(1) алгоритм пирамиды
(2) красно-чeрное дерево
(3) матричное дерево
Соединение строк называется
(1) импликацией
(2) конкатенацией
(3) модуляцией
Объект, предназначенный для перебора элементов внутри списка, носит название
(1) итератор
(2) селектор
(3) модификатор
В чем отличие алгоритма Форда-Беллмана от алгоритма Дейкстры?
(1) порядок массивной сложности
(2) использование отрицательных ребер
(3) отличий нет
Каким образом представляется ребро в списке ребер графа?
(1) весом
(2) номерами вершин
(3) компонентой соответствия
Область памяти, освобождённая после вызова free()
(1) блокируется
(2) не вызывается ни в одной подпрограмме
(3) может быть выделена снова
Для чего корень более низкого дерева вешается под корень более высокого дерева во время операции Union на СНМ?
(1) для балансировки дерева
(2) для составления остовного дерева
(3) для формирования матрицы смежности
Формулировка оптимизационной задачи в рекурсивной форме осуществляется
(1) теоремой Кронекера
(2) уравнением Беллмана
(3) леммой Эйлера
Какие из приведенных ниже понятий применяются в теории представлений симметрической группы?
(1) матрица совместимости
(2) разбиение числа
(3) классификационная компонента
Любой неконцевой узел называется
(1) узлом аддитивности
(2) узлом модульности
(3) узлом ветвления
Алгоритм быстрой сортировки для строк носит название
(1) алгоритм Брайана
(2) алгоритм Шелла
(3) алгоритм Седжвика
Если векторное произведение двух векторов равно 0, то такие вектора называются
(1) линейными
(2) матричными
(3) коллинеарными
Если у некоторого узла оба поддерева пустые, то он называется
(1) контекстным узлом
(2) листовым узлом
(3) маркерным узлом
Какие методы используются для решения проблемы с хранением символов разных алфавитов?
(1) переключение языка управляющими кодами
(2) использование двух или более байт для представления каждого символа
(3) использование кодировки с переменным размером символа
Поиск в ширину реализуется с помощью структуры
(1) стек
(2) список
(3) очередь
Цикл, сумма весов рёбер которого отрицательна, называется
(1) маркированным циклом
(2) деградационным циклом
(3) отрицательным циклом
Вершина, степень которой равна 0, носит название
(1) модульная
(2) контекстная
(3) изолированная
К элементам объекта очереди с приоритетом следует отнести
(1) ключ
(2) значение
(3) маркер
Для эффективной имплементации при использовании эвристики Union-By-Size предлагается сохранять в корне
(1) компоненту связности
(2) количество узлов в дереве
(3) ключ доступа к вершинам дерева
Из приведенных ниже записей выделите задачи с перекрывающимися подзадачами:
(1) определение смежных ребер графа
(2) вычисление чисел Фибоначчи
(3) сложение натуральных чисел
Количество разбиений чисел, более 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) комплексное динамическое программирование
Сколько существует композиций числа n?
(1) 2n-1
(2) 2n
(3) n-1
Входящая степень корня ориентированного дерева равна
(1) 0
(2) 1
(3) не более 2
Какого размера массив по умолчанию считается упорядоченным?
(1) не более 3
(2) 2
(3) 1
Произведение любого числа на нулевой вектор даст в результате
(1) нулевой вектор
(2) само число
(3) число 0
Пусть n - общее число точек на плоскости, h - число точек в выпуклой оболочке. Какое время занимает алгоритм Джарвиса?
(1) O(nh)
(2) O(nlogh)
(3) O(hlogn)
Значение Z-функции в позиции 0 обычно считается
(1) постоянным
(2) неопределенным
(3) скалярным
Применим ли алгоритм Дейкстры для графов с ребрами отрицательного веса?
(1) да, применим
(2) нет, не применим
(3) только для орграфов
Какова сложность алгоритма Флойда?
(1) O(n3)
(2) O(nlogn)
(3) O(logn)
В качестве подпрограммы при топологической сортировке используется алгоритм
(1) CHM
(2) DFS
(3) AMT
Эйлеров путь, являющийся циклом, носит название
(1) эйлеров цикл
(2) модульный цикл
(3) терминальный цикл
Результатом работы алгоритма Краскала является
(1) остовный лес
(2) матрица достижимости
(3) набор вершин
Одним из основных свойств задач, решаемых с помощью динамического программирования, является
(1) модальность
(2) аддитивность
(3) контекстность
Для каких чисел количество композиций и разбиений совпадает?
(1) 2
(2) 4
(3) 5
Какие структуры данных основаны на двоичном дереве?
(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(n2)
(2) O(logn)
(3) O(n)
(1 + x)n для биномиальных коэффициентов является
(1) гиперфункцией
(2) производящей функцией
(3) комплексной функцией
Число различных деревьев которые можно построить на n нумерованных вершинах, равно
(1) n2
(2) nn ? 2
(3) 2n
Когда массив данных нужно отсортировать по ключам используется
(1) алгоритм со списком
(2) модульный алгоритм
(3) устойчивый алгоритм
Все корневые векторы нормального оператора являются
(1) импликативными
(2) детализированными
(3) собственными
В стеке в алгоритме Джарвиса содержатся
(1) маркеры
(2) точки-кандидаты
(3) итераторы
Из приведенных ниже записей выделите алгоритмы поиска подстроки, основанные на сравнении как в "черном ящике":
(1) алгоритм грубой силы
(2) алгоритм Бойера-Мура-Хорспула
(3) алгоритм Рабина-Карпа
В простейшем случае сложность алгоритма Дейкстры составляет
(1) O(n2 + m)
(2) O(logn)
(3) O(n)
DFS - это
(1) поиск в глубину
(2) метод сжатия
(3) матрица достижимости
Нестрогий порядок называется
(1) аддитивным
(2) модификативным
(3) рефлексивным
Эйлеров путь существует тогда и только тогда, когда число вершин нечётной степени
(1) равно 3
(2) не превосходит 2
(3) менее 4
Множество рёбер, удаление которых делит граф на два изолированных подграфа, носит название
(1) модуляция графа
(2) разрез графа
(3) компонента графа
Если строка является перестановкой, решение задачи поиска наибольшей увеличивающейся подпоследовательности занимает времени
(1) O(nloglogn)
(2) O(logn)
(3) O(n)
Обобщением биномиальных коэффициентов являются
(1) полиномиальные коэффициенты
(2) мультиномиальные коэффициенты
(3) гиперномиальные коэффициенты
Что представляет собой 0-симплекс?
(1) точку
(2) вектор
(3) скаляр
Сколько времени занимает устойчивый алгоритм?
(1) O(2n)
(2) O(logn)
(3) O(n)
Величина, преобразующаяся как вектор при операциях поворота, носит название
(1) аксиальный вектор
(2) матричный вектор
(3) терминальный вектор
Каково время работы алгоритма Грэхема?
(1) O(1)
(2) O(2n)
(3) O(nlogn)
Предварительная обработка при использовании алгоритма Кнута-Морриса-Пратта занимает времени
(1) O(1)
(2) O(n)
(3) O(logn)
Уменьшение значения для фибоначчиевой кучи составляет
(1) O(1)
(2) O(n)
(3) O(logn)
Стек имеет реализацию доступа
(1) LIFO
(2) FILO
(3) FIFO
Сильно связными компонентами орграфа называются
(1) ребра графа
(2) вершины графа
(3) максимально сильно связные подграфы
Граф, в котором существует пара вершин, которая соединена более чем одним ребром (ненаправленным), либо более чем двумя дугами противоположных направлений, называется
(1) гиперграф
(2) мультиграф
(3) метаграф
Может ли изолированный подграф, получившийся после разреза графа быть отдельным узлом?
(1) нет, это исключено
(2) да, может
(3) только в комплексном графе
Расстояние Левенштейна применяется
(1) в поисковых системах для нахождения объектов или записей по имени
(2) в базах данных при поиске с неполно-заданным или неточно-заданным именем
(3) для исправления ошибок при вводе текста
В ряду биномиальных коэффициентов количество нечётных чисел равно
(1) разности членов
(2) степени двойки
(3) количеству четных
Что представляют собой 0-грани симплекса?
(1) вершины
(2) грани
(3) ребра
Является ли цифровая сортировка устойчивой?
(1) да, является
(2) нет, не является
(3) только для целых чисел
Если фундаментальная форма вектора эвклидова n-мерного пространства равна нулю, такой вектор является
(1) скалярным
(2) коллинеарным
(3) изотропным
Обычно выпуклая оболочка определяется для подмножеств
(1) матричного пространства
(2) векторного пространства
(3) модульного пространства
К алгоритмам поиска подстроки, основанным на сравнении с конца, следует отнести
(1) алгоритм Бойера-Мура
(2) алгоритм Чжу-Такаоки
(3) алгоритм Апостолико-Джанкарло
Последовательность при поразрядной сортировке сортируется
(1) по младшему значимому двоичному разряду
(2) по старшему значимому двоичному разряду
(3) по нулевому двоичному разряду
Для пространства состояний с коэффициентом ветвления b и максимальной глубиной m поиск в глубину требует хранения
(1) b+m узлов
(2) bm+1 узлов
(3) blogm узлов
Основное время работы алгоритма при поиске компонент сильной связности идет на реализацию
(1) маркировки вершин
(2) взвешивания ребер
(3) транзитивного замыкания
Сколько нечетных вершин имел граф из задачи о мостах Кенигсберга?
(1) 3
(2) 4
(3) 5
Поток в графе зависит
(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. Чему равно количество проходов алгоритма?
(1) 6
(2) 7
(3) 8
Для пространства состояний с коэффициентом ветвления 6 и максимальной глубиной 3 поиск в глубину требует хранения
(1) 19 узлов
(2) 18 узлов
(3) 17 узлов
Что представляет собой компонента связности графа?
(1) множество ребер
(2) множество вершин
(3) множество подграфов
Граф Дирака является
(1) эйлеровым
(2) гамильтоновым
(3) исходным
Любой поток между вершинами
(1) больше любого сечения
(2) равен любому сечению
(3) меньше или равен любому сечению
Для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа используется
(1) алгоритм Флойда-Уоршелла
(2) алгоритм Эйлера
(3) алгоритм Гамильтона
Гомоморфизм группы в группу проективных преобразований проективного пространства носит название
(1) модульное представление группы
(2) комплексное представление группы
(3) проективное представление группы
Триангуляция - это
(1) подсчет объема симплекса
(2) разбиение топологического пространства на симплексы
(3) выборка минимальных углов симплекса