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

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

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

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

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

Предположим, что символы a,b,c,d,e встречаются с частотами . Какие получатся коды Хаффмана для букв a,b,c соответственно?

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

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

Какова временная сложность выполнения алгоритма Беллмана-Форда на K-регулярном графе ()?

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

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

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

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

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

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

Сколько вершин имеет дерево с 57 ребрами?