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

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

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

Пусть и что из ниже перечисленного является верным?

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

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

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

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

Рассмотрим следующие утверждения (h(k) — хэш-функция):

• I. если даже .

• II. для любых .

• III. для любых .

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

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

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

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

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