Вариант 1512835938.
Каково минимальное и максимальное количество узлов, которые может содержать в себе куча на минимум/максимум высотой ?
Предположим, что символы встречаются с частотами . Какие получатся коды Хаффмана для букв соответственно?
Пусть неориентированный граф, какие утверждения ниже являются верными?
I. Если является деревом, то между двумя любыми вершинами существует единственный уникальный путь.
II. Если является связным, и , тогда является деревом.
III. Удаление ребра из цикла не может сделать граф несвязным.
Рассмотрим следующие выражения:
I. Подсчет медианы из элементов занимает времени для любого алгоритма, основанного на сравнении элементов.
II. Пусть является минимальным остовным деревом для графа . Тогда для любой пары вершин и кратчайший путь между ними в является кратчайшим путем между ними в .
Какие утверждения верные, а какие нет?
Сколько существует различных бинарных деревьев с 8 узлами?
Какие из представленных ниже утверждений являются верными?
1)
2)
3), - константа
4)
Предположим, что - это связный неориентированный граф, ребра которого имеют положительные веса. Пусть - минимальное остовное дерево этого графа. Мы модифицируем граф, добавляя "6" к весу каждого ребра, какое из следующих утверждений верно?
Рассмотрим следующее AVL-дерево: [svg]
Если в данное дерево требуется вставить элемент со значением 12, сколько поворотов необходимо сделать для балансировки дерева?
Рассмотрим следующие утверждения об алгоритме обхода графа в глубину:
I. Предположим, мы запускаем DFS на неориентированном графе и находим ровно 15 обратных ребер. Тогда граф гарантированно будет иметь по крайней мере один цикл.
II. DFS на ориентированном графе с вершинами и, по крайней мере, ребрами гарантированно найдет хотя бы одно обратное ребро.
Какие из данных утверждений верны?
Какова временная сложность выполнения алгоритма Беллмана-Форда на K-регулярном графе ()?