Тест по Computer Science — вопросы

Сколько существует различных бинарных деревьев с 8 узлами?

Рассмотрим массив из n элементов. Какую временную сложность имеет алгоритм поиска максимальной суммы трех элементов в массиве?

Какой будет временная сложность печати всех ключей дерева бинарного поиска в отсортированном порядке?

Какое из представленных ниже регулярных выражений задает строки вида , где m, p, n больше либо равно 2.

Пусть G = (V, E) неориентированный граф, какие утверждения ниже являются верными?

• I. Если G является деревом, то между двумя любыми вершинами G существует единственный уникальный путь.

• II. Если G = (V, E) является связным, и E = V - 1, тогда G является деревом.

• III. Удаление ребра из цикла не может сделать граф несвязным.

Сколько остовных деревьев имеет данный граф (все ребра имеют одинаковый вес)?

Рассмотрим следующие выражения:

• I.

• II.

Какие утверждения верные, а какие нет?

Рассмотрим следующие утверждения об алгоритме обхода графа в глубину:

• I. Предположим, мы запускаем DFS на неориентированном графе и находим ровно 15 обратных ребер. Тогда граф гарантированно будет иметь по крайней мере один цикл.

• II. DFS на ориентированном графе с n вершинами и, по крайней мере, n ребрами гарантированно найдет хотя бы одно обратное ребро.

Какие из данных утверждений верны?

Пусть дана последовательность n случайных чисел. Какая будет временная сложность для нахождения элемента, который встречается больше, чем n/2 раз (если такой элемент существует)?

Каково число подстрок любой длины, за исключением пустой строки, может быть получено из заданной строки длиной n?