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

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

Сколько раз происходит обращение ко всем вершинам в графе G(V, E) в процессе работы алгоритма поиска в глубину?

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

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

• I.

• II.

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

Рассмотрим следующее AVL-дерево:

Если в данное дерево требуется вставить элемент со значением 12, сколько поворотов необходимо сделать для балансировки дерева?

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

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

• I. Подсчет медианы из n элементов занимает времени для любого алгоритма, основанного на сравнении элементов.

• II. Пусть T является минимальным остовным деревом для графа G. Тогда для любой пары вершин a и b кратчайший путь между ними в G является кратчайшим путем между ними в T.

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

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

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

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

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

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