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

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

Какие из представленных ниже утверждений являются верными?

• 1)

• 2)

• 3),  — константа

• 4)

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

Чтобы выполнить поиск элемента в dynamic set, какой из следующих методов является асимптотически наиболее эффективным по времени в наихудшем случае для операции поиска?

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

Рассмотрим следующий код:

y = y + z
for i in range(1, n + 1):
    k = k + 2;
for i in range(1, n + 1):
    for j in range(1, n + 1):
        x = x + 1;

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

Дан неориентированный граф G = (V, E) и положительное целое число K, имеет ли G K вершин, которые образуют полный подграф, и если да, то каково минимальное значение K?

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

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

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

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

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

• Пусть n — это число элементов в массиве
• В процессе сортировки массива происходит порядка уровней
• На каждом уровне происходит порядка действий

Для какого алгоритма сортировки все утверждения являются верными?

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