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

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

В курсе рассматриваются способы структурирования информации в моделях с адресуемой памятью и классические модели вычислений, которые сыграли основную роль в формировании математического понятия алгоритма.

Список вопросов:

# Какие поисковые деревья являются сбалансированными?
# Какова трудоемкость поиска минимального элемента в АВЛ-дереве, состоящем из n узлов?
# Каково минимальное число узлов в АВЛ-дереве высоты 3?
# Каково максимальное число узлов в АВЛ-дереве высоты 3?
# Какова максимальная высота АВЛ-дерева, состоящего из 7 узлов?
# Какова минимальная высота АВЛ-дерева, состоящего из 7 узлов?
# Какие из следующих утверждений истинны?
# Какие из следующих утверждений истинны?
# Каково будет содержимое ленты после выполнения программы [K2, L, K2], если на ее вход подать псевдослово *u2 * u1*↓(считаем, что слова u1, u2 не содержат символа *, K2 - копирование второго слова, L - сдвиг головки до ближайшего слева символа *)?
# Каково будет содержимое ленты после выполнения программы [K2,K2], если на ее вход подать псевдослово *u2 * u1*↓(считаем, что слова u1, u2 не содержат символа *, K2 - копирование второго слова)?
# Каково будет содержимое ленты после выполнения программы [K1, K2], если на ее вход подать псевдослово *u2 * u1*↓(считаем, что слова u1, u2 не содержат символа *, K1 - копирование первого слова, K2 - копирование второго слова)?
# Каково будет содержимое ленты после выполнения программы [L, K1, K2], если на ее вход подать псевдослово *u2 * u1*↓(считаем, что слова u1, u2 не содержат символа *, L - сдвиг головки до ближайшего слева символа *, K1 - копирование первого слова, K2 - копирование второго слова)?
# Какие из моделей вычислений являются числовыми?
# Какие из моделей вычислений являются словарными?
# Какие из моделей вычислений работают с адресуемой памятью?
# Пусть p(n) - максимальная продуктивность Абак-программы, состоящей из n команд. Какие соотношения для функции p(n) истинны?
# В какое слово переработает алгорифм Маркова 11 → 12,2 → λ,1 → 1! последовательность, состоящую из 4 единиц?
# Какие соотношения истинны для любых регулярных выражений α, β, γ?
# Какие из следующих соотношений истинны для регулярных выражений в алфавите {a, b, c}?
# Какая из таблиц задает функцию откатов для слова (aabaababaab) в алгоритме Кнута - Морриса - Пратта?
# Какие из следующих регулярных выражений в алфавите {a, b, c} являются решениями уравнения X =αX + β, где α = b+с, β = ab*?
# Какие из следующих регулярных выражений в алфавите {a, b, c} являются решениями уравнения X = Xα + β, где α = b+с, β = ab*?
# Какие из следующих регулярных выражений в алфавите {a, b, c} являются решениями уравнения X = Xα , где α = ab+aс?
# Сколько слов длины 3 содержится в регулярном множестве, заданном регулярным выражением a*b*c*?
# Сколько слов длины 3 содержится в регулярном множестве, заданном регулярным выражением (a+b+c)*?
# Сколько слов длины 3 содержится в регулярном множестве, заданном регулярным выражением (ab+c)*?
# Пусть P и Q - одноместные, а R - двухместный предикатные символы. Какие из перечисленных формул являются тождественно истинными?
# Пусть P и Q - одноместные предикатные символы. Какие из перечисленных формул являются тождественно истинными?
# Пусть P - трехместный предикатный символ; f , g - одноместные функциональные символы; x, y, u - переменные; b - константа. Какие из подстановок являются унификаторами атомарных формул P(b, y, f (g(y))) и P(x, f (x), f (u))?
# Пусть 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 - одноместные предикатные символы. Какие из перечисленных формул являются префиксной формой формулы [∀x P(x) ∨ ∀x Q(x)]?
# Пусть 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 Q и S- одноместные и R - двухместный предикатные символы, a, b - константы. Какие из перечисленных ниже формул могут быть выведены с помощью правила резолюции из формул P(x) ∨ Q(y) ∨ R(b, x) и P(b) ∨ S(y) ∨ R(y, a)?
# Какой класс функций используется для оценки трудоемкости алгоритмов сверху?
# Какой класс функций используется для оценки трудоемкости алгоритмов снизу?
# Какие классы функций используются для амортизационных оценок трудоемкости алгоритмов?
# Какие из перечисленных функций принадлежат классу Ο(n2)?
# Какие из перечисленных функций принадлежат классу Ω(n2)?
# Какие из перечисленных функций принадлежат классу Θ(n2)?
# Какие из следующих операций выполняются за время Ο(1) при представлении списка массивом?
# Какие из следующих операций выполняются за время Ο(1) при динамическом представлении списка с односторонними связями?
# Какие из следующих операций выполняются за время Ο(1) при динамическом представлении списка с двухсторонними связями?
# Какова трудоемкость поиска заданного элемента в одностороннем динамическом списке, содержащем n элементов?
# Какой может быть трудоемкость удаления элемента из заданной позиции одностороннего динамического списка, содержащего n элементов?
# Какова возможна трудоемкость удаления элемента из заданной позиции двустороннего динамического списка, содержащего n элементов?
# Какой может быть трудоемкость поиска заданного элемента в списке, представленном массивом из n элементов?
# При каких способах представления разделенных множеств наиболее эффективно выполняется операция ОБЪЕДИНИТЬ?
# При каких способах представления разделенных множеств наиболее эффективно выполняется операция НАЙТИ?
# При каком способе представления разделенных множеств известны рекордные амортизационные оценки трудоемкости?
# Пусть n[x] - количество узлов в поддереве с корнем х, а h[x] - высота узла х. Какие из перечисленных ниже утверждений истинны после выполнения любой последовательности операций типа СОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИ для любого узла x?
# Как можно оценить трудоемкость алгоритма Крускала для графов с n вершинами и m ребрами при реализации разделенных множеств с использованием рангов и сжатия путей?
# Чему равен log *n при n = 128?
# Какие из утверждений истинны?
# Чему равно значение функции Аккермана A (i, j) при i = 2, j = 3?
# Как можно оценить высоту d-кучи, состоящей из n элементов?
# Какова трудоемкость операции ВСПЛЫТИЕ в d-куче из n элементов?
# Как можно оценить сверху число элементов в нижнем ярусе d-кучи, состоящей из n элементов?
# Какова высота 2-кучи, содержащей 17 элементов?
# Какова высота 3-кучи, содержащей 17 элементов?
# Каково минимальное число элементов в 2-куче, высоты 4?
# Каково максимальное число элементов в 2-куче, высоты 4?
# Какова трудоемкость окучивания массива длины n?
# Как можно оценить высоту левостороннего дерева, состоящего из n узлов?
# Как можно оценить длину правой ветви левостороннего дерева, состоящего из n узлов?
# Как можно оценить трудоемкость операции удаления минимального элемента из левосторонней кучи, состоящей из n элементов?
# Каково минимальное число узлов в левостороннем дереве высота 3?
# Каково максимальное число узлов в левостороннем дереве высота 3?
# Какова минимальная длина правой ветви в левостороннем дереве высоты 4?
# Какова максимальная длина правой ветви в левостороннем дереве высоты 4?
# Какие операции с левосторонней ленивой кучей выполняются ленивым образом?
# У каких операций с самоорганизующейся кучей амортизационная трудоемкость Ο(1)?
# Какие операции с самоорганизующейся кучей выполняются с трудоемкостью в худшем случае Ο(1)?
# Пусть l - количество легких узлов в самоорганизующейся куче из 16 элементов. Какие соотношения заведомо ложны?
# Сколько биномиальных деревьев в биномиальном лесе с общим количеством узлов равным 125?
# Сколько узлов в биномиальном дереве B5?
# Какова трудоемкость в худшем случае операции нахождения минимального элемента в приоритетной очереди реализованной с помощью биномиальных куч?
# Какие биномиальные деревья из перечисленных не присутствуют в биномиальном лесе с общим количеством узлов равным 50?
# Сколько узлов в биномиальном лесе состоящем из деревьев B5, B2, B1?
# Какие биномиальные деревья не присутствуют в биномиальном лесе с общим количеством узлов равным 60?
# Как изменится число биномиальных деревьев в биномиальном лесе с общим количеством узлов равным 60 при удалении из него одного элемента?
# Каково максимальное число узлов в тонком дереве T5?
# Каково минимальное число узлов в тонком дереве T3?
# Какая из перечисленных ниже операций является наиболее трудоемкой?
# Какие из записей являются избыточными b-арными (b=10) представлениями числа 1041045, представленного в обычной десятичной системе счисления?
# Какие из записей являются регулярными избыточными b-арными (b=10) представлениями числа 1041045, представленного в обычной десятичной системе счисления?
# Какие из записей являются результатом инкрементации 2-го разряда в избыточными b-арном (b=10) представлении 3b8b45 ?
# Какие из записей является результатом удвоения числа 3b8b45, заданного в избыточными b-арном представлении (b=10)?
# Сколько может быть толстых деревьев в толстом лесе из 33 узлов?
# Толстый лес состоит из двух деревьев F3 и одного дерева F2. Сколько в этом лесе узлов?
# Толстая куча построена из одного дерева F3 и одного дерева F2. Сколько в ней узлов ранга 2?
# Толстая куча построена из двух деревьев F3 и одного дерева F2. Каково в этой куче минимальное число неправильных узлов?
# Сколько толстых деревьев в толстом лесе, состоящем из 155 узлов?