Структуры данных и модели вычислений - ответы

Количество вопросов - 93

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    Пусть 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, z - переменные; b - константа. Какие из формул A= P(b, y, f (g(y))), B= P(x, f (z), f (z)) и C= P(x, f (x), f (z)) унифицируемы?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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