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

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

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

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

Дан неориентированный граф и положительное целое число , имеет ли m>G</m> m>K</m> вершин, которые образуют полный подграф, и если да, то каково минимальное значение ?

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

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

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

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

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

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

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

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

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

(В книге опечатка с ответами)

Пусть структура данных поддерживает операцию `foo`, таким образом, что последовательность из операций `foo` занимает времени в худшем случае. Каково амортизационное время операции `foo`?