У каких операций с самоорганизующейся кучей амортизационная трудоемкость Ο(1)?

Какие операции с самоорганизующейся кучей выполняются с трудоемкостью в худшем случае Ο(1)?

Пусть n[x] - количество узлов в поддереве с корнем х, а h[x] - высота узла х. Какие из перечисленных ниже утверждений истинны после выполнения любой последовательности операций типа СОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИ для любого узла x?

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

Какова трудоемкость операции ВСПЛЫТИЕ в d-куче из n элементов?

Как можно оценить трудоемкость операции удаления минимального элемента из левосторонней кучи, состоящей из n элементов?

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

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

Пусть P, Q и S - одноместные и R - двухместный предикатные символы; a, b - константы. Какие из перечисленных ниже формул могут быть выведены с помощью правила резолюции из формул P(x) ∨ Q(y) ∨ R(b, x) и P(b) ∨ S(y) ∨ R(y, a)?

Пусть P - трехместный предикатный символ; f , g - одноместные функциональные символы; x, y, u - переменные; b - константа. Какие из подстановок являются унификаторами атомарных формул P(b, y, f (g(y))) и P(x, f (x), f (u))?

Каково будет содержимое ленты после выполнения программы [K2, L, K2], если на ее вход подать псевдослово *u2 * u1*^↓(считаем, что слова u1, u2 не содержат символа *, K2 - копирование второго слова, L - сдвиг головки до ближайшего слева символа *)?