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

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

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

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

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

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

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

Какие из следующих алгоритмов используют подход Разделяй и Властвуй?

Запустим алгоритм Дейкстры, начиная с вершины S, чтобы найти кратчайший путь T, и рассмотрим следующие утверждения:

• I. Алгоритм Дейкстры возвращает кратчайший путь с минимальным общим весом.

• II. Алгоритм Дейкстры возвращает кратчайший путь с минимальным количеством ребер.

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

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

Хэш функция с линейным зондированием используется для вставки ключей 37, 38, 72, 68, 98, 11, 74 в хэш-таблицу с индексом (0-6). Какой индекс соответствует ключу 74?

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

Алгоритм Беллмана-Форда решает задачу кратчайшего пути из вершины в случае, когда веса ребер могут быть отрицательными, какова временная сложность выполнения алгоритма Беллмана-Форда?

Пусть M является целым числом, которое больше единицы. Какая асимптотика роста функции является верной?