Ответы к тесту/контрольной: Структуры данных и модели вычислений

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

Как можно оценить высоту d-кучи, состоящей из n элементов?

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

Какие из следующих соотношений истинны для регулярных выражений в алфавите {a, b, c}?

Каково максимальное число узлов в левостороннем дереве высота 3?

Какие поисковые деревья являются сбалансированными?

Какие из записей является результатом удвоения числа 3b8b45, заданного в избыточными b-арном представлении (b=10)?

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

Толстая куча построена из двух деревьев F3 и одного дерева F2. Каково в этой куче минимальное число неправильных узлов?

Сколько биномиальных деревьев в биномиальном лесе с общим количеством узлов равным 125?

Какие из следующих регулярных выражений в алфавите {a, b, c} являются решениями уравнения X = Xα + β, где α = b+с, β = ab*?

Каково минимальное число узлов в тонком дереве T3?

Какова высота 3-кучи, содержащей 17 элементов?

Какие из перечисленных функций принадлежат классу Ο(n2)?

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

Какие биномиальные деревья не присутствуют в биномиальном лесе с общим количеством узлов равным 60?

Пусть P и Q - одноместные предикатные символы. Какие из перечисленных формул являются тождественно истинными?

Сколько слов длины 3 содержится в регулярном множестве, заданном регулярным выражением (a+b+c)*?

Пусть p(n) - максимальная продуктивность Абак-программы, состоящей из n команд. Какие соотношения для функции p(n) истинны?

Какие из моделей вычислений работают с адресуемой памятью?

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

Каково максимальное число узлов в тонком дереве T5?

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

Какова максимальная высота АВЛ-дерева, состоящего из 7 узлов?

Какие из моделей вычислений являются словарными?

При каких способах представления разделенных множеств наиболее эффективно выполняется операция ОБЪЕДИНИТЬ?

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

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

Какие биномиальные деревья из перечисленных не присутствуют в биномиальном лесе с общим количеством узлов равным 50?

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

Толстая куча построена из одного дерева F3 и одного дерева F2. Сколько в ней узлов ранга 2?

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

Какова высота 2-кучи, содержащей 17 элементов?

Какие из записей являются избыточными b-арными (b=10) представлениями числа 1041045, представленного в обычной десятичной системе счисления?

Какой класс функций используется для оценки трудоемкости алгоритмов снизу?

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

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

Пусть P и Q - соответственно одноместный и двухместный предикатные символы. Какие из перечисленных формул являются сколемовской формой формулы ∀x ∃y [P(x)& Q(x,y)]?

Пусть P и Q - одноместные, а R - двухместный предикатные символы. Какие из перечисленных формул являются тождественно истинными?

Какие из следующих регулярных выражений в алфавите {a, b, c} являются решениями уравнения X =αX + β, где α = b+с, β = ab*?

Какая из таблиц задает функцию откатов для слова (aabaababaab) в алгоритме Кнута - Морриса - Пратта?

Какие из моделей вычислений являются числовыми?

Какова минимальная высота АВЛ-дерева, состоящего из 7 узлов?

Каково минимальное число узлов в АВЛ-дереве высоты 3?

Сколько толстых деревьев в толстом лесе, состоящем из 155 узлов?

Толстый лес состоит из двух деревьев F3 и одного дерева F2. Сколько в этом лесе узлов?

Какие из записей являются результатом инкрементации 2-го разряда в избыточными b-арном (b=10) представлении 3b8b45 ?

Сколько узлов в биномиальном лесе состоящем из деревьев B5, B2, B1?

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

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

Каково минимальное число узлов в левостороннем дереве высота 3?

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

Какова трудоемкость окучивания массива длины n?

Чему равно значение функции Аккермана A (i, j) при i = 2, j = 3?

При каком способе представления разделенных множеств известны рекордные амортизационные оценки трудоемкости?

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

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

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

Какие из перечисленных функций принадлежат классу Θ(n2)?

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

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

При каких способах представления разделенных множеств наиболее эффективно выполняется операция НАЙТИ?

Каково максимальное число узлов в АВЛ-дереве высоты 3?

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

Какие из записей являются регулярными избыточными b-арными (b=10) представлениями числа 1041045, представленного в обычной десятичной системе счисления?

Пусть P и Q - одноместные предикатные символы. Какие из перечисленных формул являются префиксной формой формулы [∀x P(x) ∨ ∀x Q(x)]?

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

Как изменится число биномиальных деревьев в биномиальном лесе с общим количеством узлов равным 60 при удалении из него одного элемента?

Пусть l - количество легких узлов в самоорганизующейся куче из 16 элементов. Какие соотношения заведомо ложны?

Какова максимальная длина правой ветви в левостороннем дереве высоты 4?

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

Какая из перечисленных ниже операций является наиболее трудоемкой?

Какие из перечисленных функций принадлежат классу Ω(n2)?

Чему равен log *n при n = 128?

Какие из следующих регулярных выражений в алфавите {a, b, c} являются решениями уравнения X = Xα , где α = ab+aс?

Какова трудоемкость поиска минимального элемента в АВЛ-дереве, состоящем из n узлов?

Сколько узлов в биномиальном дереве B5?

В какое слово переработает алгорифм Маркова11 →​ 12,2 →​ λ,1 →​ 1!последовательность, состоящую из 4 единиц?

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

Какие операции с левосторонней ленивой кучей выполняются ленивым образом?

Каково максимальное число элементов в 2-куче, высоты 4?

Каково минимальное число элементов в 2-куче, высоты 4?

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

Сколько может быть толстых деревьев в толстом лесе из 33 узлов?

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

Сколько слов длины 3 содержится в регулярном множестве, заданном регулярным выражением a*b*c*?

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

Какие соотношения истинны для любых регулярных выражений α, β, γ?

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

Какова минимальная длина правой ветви в левостороннем дереве высоты 4?