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

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

Правильные ответы выделены зелёным цветом.
Все ответы: В курсе рассматриваются способы структурирования информации в моделях с адресуемой памятью и классические модели вычислений, которые сыграли основную роль в формировании математического понятия алгоритма.
Какие поисковые деревья являются сбалансированными?
(1) АВЛ-деревья
(2) Случайные
(3) Красно-черные
Какие из моделей вычислений являются числовыми?
(1) Машина Тюринга
(2) Абак
(3) РАМ-машина
Пусть P и Q - одноместные, а R - двухместный предикатные символы. Какие из перечисленных формул являются тождественно истинными?
(1) ∀x [P(x) ∨ Q(x)]→​∀x P(x) ∨ ∃x Q(x)
(2) [∀x P(x) ∨x Q(x)]→​∀x [P(x) ∨ Q(x)]
(3) [∀x ∃y R(x, y)→​ ∃x ∀y R(x, y)]
Какой класс функций используется для оценки трудоемкости алгоритмов сверху?
(1) Ο
(2) Θ
(3) Ω
При каких способах представления разделенных множеств наиболее эффективно выполняется операция ОБЪЕДИНИТЬ?
(1) массив
(2) дерево с использованием рангов.
(3) дерево без использования рангов
(4) дерево с использованием рангов и сжатия путей
Как можно оценить высоту d-кучи, состоящей из n элементов?
(1) Θ(n)
(2) Ο(logd n)
(3) Ω(n)
Как можно оценить высоту левостороннего дерева, состоящего из n узлов?
(1) Ο(n)
(2) Ο(log2 n)
(3) Ω(n)
Какие операции с левосторонней ленивой кучей выполняются ленивым образом?
(1) УДАЛИТЬ
(2) НАЙТИ ЭЛЕМЕНТ С МИНИМАЛЬНЫМ КЛЮЧОМ
(3) ВСТАВИТЬ
(4) УМЕНЬШИТЬ КЛЮЧ
Каково максимальное число узлов в тонком дереве T5?
(1) 31
(2) 32
(3) 64
Каково максимальное число узлов в АВЛ-дереве высоты 3?
(1) 15
(2) 16
(3) 17
Пусть p(n) - максимальная продуктивность Абак-программы, состоящей из n команд. Какие соотношения для функции p(n) истинны?
(1) p(100)> 100
(2) p(100)< 166
(3) p(100)≥ 166
Пусть 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)) унифицируемы?
(1) A и B
(2) A и С
(3) С и B
Какие из перечисленных функций принадлежат классу Ο(n2)?
(1) 2n
(2) 2n2+3n
(3) 2n3+3n
(4) n logn
(5) n2logn
Пусть n[x] - количество узлов в поддереве с корнем х, а h[x] - высота узла х. Какие из перечисленных ниже утверждений истинны после выполнения любой последовательности операций типа СОЗДАТЬ, ОБЪЕДИНИТЬ, НАЙТИ для любого узла x?
(1) n[x] = 5, h[x] = 3
(2) n[x] = 7, h[x] = 3
(3) n[x] = 8, h[x] = 3
(4) n[x] = 9, h[x] = 3
Какова высота 2-кучи, содержащей 17 элементов?
(1) 3
(2) 4
(3) 5
Каково минимальное число узлов в левостороннем дереве высота 3?
(1) 3
(2) 4
(3) 5
Пусть l - количество легких узлов в самоорганизующейся куче из 16 элементов. Какие соотношения заведомо ложны?
(1) l >2
(2) l >3
(3) l >4
Какие из записей являются избыточными b-арными (b=10) представлениями числа 1041045, представленного в обычной десятичной системе счисления?
(1) b3bb45
(2) b03bb45
(3) b40b45
Какие из следующих утверждений истинны?
(1) любая машина Тюринга остановится через конечное число шагов, если на ее вход подать пустую ленту
(2) существует машина Тюринга, которая при любом входе не останавливается
(3) любая машина Тьюринга будет работать без остановки, если на ее вход подать ее собственный код
Какие соотношения истинны для любых регулярных выражений α, β, γ?
(1) α*(β+γ) = α*β + α*γ,
(2) (β+γ)*α = β*α + γ*α
(3) α*β = β*α
Пусть P, Q и S - одноместные и R - двухместный предикатные символы; a, b - константы. Какие из перечисленных ниже формул могут быть выведены с помощью правила резолюции из формул P(x) ∨ Q(y) ∨ R(b, x) и P(b) ∨ S(y) ∨ R(y, a)?
(1) P(x) ∨ Q(b) ∨ P(b) ∨ S(y)
(2) P(a) ∨ Q(b) ∨ P(b) ∨ S(b)
(3) P(a) ∨ Q(y) ∨ P(b) ∨ S(b)
Какие из следующих операций выполняются за время Ο(1) при представлении списка массивом?
(1) нахождение позиции элемента в памяти по его номеру в кортеже
(2) нахождение позиции элемента, следующего в кортеже за элементом из заданной позиции
(3) нахождение позиции элемента, предшествующего в кортеже элементу из заданной позиции
(4) удаление элемента, находящегося в заданной позиции
(5) вставка в кортеж нового элемента перед элементом, расположенным в заданной позиции
(6) определение длины кортежа
Какие из утверждений истинны?
(1) log *127 < log *128
(2) log *127 > log *128
(3) log *127 = log *128
Каково максимальное число элементов в 2-куче, высоты 4?
(1) 32
(2) 31
(3) 30
Какова максимальная длина правой ветви в левостороннем дереве высоты 4?
(1) 3
(2) 4
(3) 2
Сколько биномиальных деревьев в биномиальном лесе с общим количеством узлов равным 125?
(1) 6
(2) 7
(3) 8
Какие из записей является результатом удвоения числа 3b8b45, заданного в избыточными b-арном представлении (b=10)?
(1) 818090
(2) 818b80
(3) 817b80
Каково будет содержимое ленты после выполнения программы [K2,K2], если на ее вход подать псевдослово *u2 * u1*↓(считаем, что слова u1, u2 не содержат символа *, K2 - копирование второго слова)?
(1) *u2 * u1*u2 *u1 *↓
(2) *u2 * u1*u2 u1 *↓
(3) *u2 * u1*u2 *u2 *↓
Какие из следующих регулярных выражений в алфавите {a, b, c} являются решениями уравнения X =αX + β, где α = b+с, β = ab*?
(1) (b+c)*+ab*
(2) a+(b+c)*a
(3) (b+c)*ab*
(4) (b+c)*a
Какова трудоемкость поиска заданного элемента в одностороннем динамическом списке, содержащем n элементов?
(1) Ο(1)
(2) Ο(n)
(3) Ο(log n)
Какие биномиальные деревья из перечисленных не присутствуют в биномиальном лесе с общим количеством узлов равным 50?
(1) B5
(2) B2
(3) B1
Толстая куча построена из одного дерева F3 и одного дерева F2. Сколько в ней узлов ранга 2?
(1) 3
(2) 4
(3) 2
Сколько слов длины 3 содержится в регулярном множестве, заданном регулярным выражением a*b*c*?
(1) 1
(2) 6
(3) 10
(4) 27
Какой может быть трудоемкость поиска заданного элемента в списке, представленном массивом из n элементов?
(1) Ο(1)
(2) Ο(n)
(3) Ο(log n)
(4) Ο(n2)
Как изменится число биномиальных деревьев в биномиальном лесе с общим количеством узлов равным 60 при удалении из него одного элемента?
(1) уменьшится
(2) увеличится
(3) сохранится прежним
Какова трудоемкость поиска минимального элемента в АВЛ-дереве, состоящем из n узлов?
(1) Ο(1)
(2) Ο(log n)
(3) Ω(n)
Какие из моделей вычислений являются словарными?
(1) Алгорифмы Маркова
(2) РАМ-машина
(3) Машина Тюринга
Пусть P и Q - одноместные предикатные символы. Какие из перечисленных формул являются тождественно истинными?
(1) ∃x [P(x) & Q(x)] →​ ∀xP(x) ∨ ∃x Q(x)
(2) [∀x P(x) ∨ ∃x Q(x)] →​ ∀x [P(x) ∨ Q(x)]
(3) ∃x ∀y R(x, y) →​ ∀x ∃y R(x, y)
Какой класс функций используется для оценки трудоемкости алгоритмов снизу?
(1) Ο
(2) Θ
(3) Ω
При каких способах представления разделенных множеств наиболее эффективно выполняется операция НАЙТИ?
(1) массив
(2) дерево с использованием рангов
(3) дерево без использования рангов
(4) дерево с использованием рангов и сжатия путей
Какова трудоемкость операции ВСПЛЫТИЕ в d-куче из n элементов?
(1) Θ(n)
(2) Θ(logd n)
(3) Ω(n)
Как можно оценить длину правой ветви левостороннего дерева, состоящего из n узлов?
(1) Ο(n)
(2) Ο(log2 n)
(3) Ω(n)
У каких операций с самоорганизующейся кучей амортизационная трудоемкость Ο(1)?
(1) УДАЛИТЬ
(2) НАЙТИ ЭЛЕМЕНТ С МИНИМАЛЬНЫМ КЛЮЧОМ +
(3) ВСТАВИТЬ
(4) УМЕНЬШИТЬ КЛЮЧ
Каково минимальное число узлов в тонком дереве T3?
(1) 5
(2) 4
(3) 6
Какова максимальная высота АВЛ-дерева, состоящего из 7 узлов?
(1) 2
(2) 3
(3) 4
В какое слово переработает алгорифм Маркова
  • 11 →​ 12,
  • 2 →​ λ,
  • 1 →​ 1!
    •  последовательность, состоящую из 4 единиц?
    (1) в последовательность, состоящую из 3 единиц
    (2) в последовательность, состоящую из 2 единиц
    (3) в последовательность, состоящую из 1 единицы
    (4) в пустую последовательность
    Пусть P и Q - одноместные предикатные символы. Какие из перечисленных формул являются префиксной формой формулы [∀x P(x) ∨ ∀x Q(x)]?
    (1) ∀x [P(x)∨ Q(x)]
    (2) ∀x ∀y [P(x) ∨ Q(y)]
    (3) ∀x ∀z [P(z) ∨ Q(x)]
    Какие из перечисленных функций принадлежат классу Ω(n2)?
    (1) 2n
    (2) 2n2+3n
    (3) 2n3+3n
    (4) n logn
    (5) n2logn
    Как можно оценить трудоемкость алгоритма Крускала для графов с n вершинами и m ребрами при реализации разделенных множеств с использованием рангов и сжатия путей?
    (1) Ο(log n)
    (2) Ο(m log n)
    (3) Ο(m)
    (4) Ο(n log m)
    Какова высота 3-кучи, содержащей 17 элементов?
    (1) 3
    (2) 4
    (3) 5
    Каково максимальное число узлов в левостороннем дереве высота 3?
    (1) 15
    (2) 16
    (3) 17
    Какие из записей являются регулярными избыточными b-арными (b=10) представлениями числа 1041045, представленного в обычной десятичной системе счисления?
    (1) b3bb45
    (2) 103bb45
    (3) b40b45
    Какие из следующих утверждений истинны?
    (1) если программа при некоторых входах из области определения вычисляемой функции останавливается через конечное число шагов и дает правильный ответ, то она частично корректна
    (2) если программа при всех входах из области определения вычисляемой функции, при которых она останавливается через конечное число шагов, дает правильный ответ, то она корректна
    (3) если программа при всех входах из области определения вычисляемой функции, при которых она останавливается через конечное число шагов, дает правильный ответ, то она частично корректна
    (4) если программа при всех входах из области определения вычисляемой функции останавливается через конечное число шагов и дает правильный ответ, то она корректна.
    (5) если программа при всех входах из области определения останавливается через конечное число шагов, то она частично корректна
    Какие из следующих соотношений истинны для регулярных выражений в алфавите {a, b, c}?
    (1) (ab)*c=a*(ab)*c
    (2) (abc)*=a*b*c*
    (3) (a+b)*c(b+a) =(a+b)*(cb+ca)
    Пусть P Q и S- одноместные и R - двухместный предикатные символы, a, b - константы. Какие из перечисленных ниже формул могут быть выведены с помощью правила резолюции из формул P(x) ∨ Q(y) ∨ R(b, x) и P(b) ∨ S(y) ∨ R(y, a)?
    (1) P(x) ∨ Q(b) ∨ P(b) ∨ S(y)
    (2) P(a) ∨ Q(b) ∨ P(b) ∨ S(b)
    (3) P(a) ∨ Q(y) ∨ P(b) ∨ S(y)
    Какие из следующих операций выполняются за время Ο(1) при динамическом представлении списка с односторонними связями?
    (1) нахождение позиции элемента в памяти по его номеру в кортеже
    (2) нахождение позиции элемента, следующего в кортеже за элементом из заданной позиции.
    (3) вставка в кортеж нового элемента перед элементом, расположенным в заданной позиции
    (4) определение длины кортежа
    Чему равно значение функции Аккермана A (i, j) при i = 2, j = 3?
    (1) 65536
    (2) 32768
    (3) 1024
    Какова трудоемкость окучивания массива длины n?
    (1) Ο(n)
    (2) Θ(n log n)
    (3) Ο(log n)
    Сколько узлов в биномиальном дереве B5?
    (1) 31
    (2) 32
    (3) 16
    Сколько может быть толстых деревьев в толстом лесе из 33 узлов?
    (1) 2
    (2) 3
    (3) 4
    Каково будет содержимое ленты после выполнения программы [K1, K2], если на ее вход подать псевдослово *u2 * u1*↓(считаем, что слова u1, u2 не содержат символа *, K1 - копирование первого слова, K2 - копирование второго слова)?
    (1) *u2 * u1*u2 *u1 *↓
    (2) *u2 * u1*u1* u1 *↓
    (3) *u2 * u1*u2 *u2 *↓
    Какие из следующих регулярных выражений в алфавите {a, b, c} являются решениями уравнения X = Xα + β, где α = b+с, β = ab*?
    (1) ab* + (b+c)*
    (2) a+(b+c)*a
    (3) ab*(b+c)*
    (4) a(b+c)*
    Какой может быть трудоемкость удаления элемента из заданной позиции одностороннего динамического списка, содержащего n элементов?
    (1) Ο(1)
    (2) Ο(n)
    (3) Ο(log n)
    (4) Ο(n2)
    Сколько узлов в биномиальном лесе состоящем из деревьев B5, B2, B1?
    (1) 16
    (2) 32
    (3) 38
    Толстая куча построена из двух деревьев F3 и одного дерева F2. Каково в этой куче минимальное число неправильных узлов?
    (1) 1
    (2) 5
    (3) 0
    Сколько слов длины 3 содержится в регулярном множестве, заданном регулярным выражением (a+b+c)*?
    (1) 1
    (2) 3
    (3) 10
    (4) 27
    Каково минимальное число узлов в АВЛ-дереве высоты 3?
    (1) 6
    (2) 7
    (3) 8
    Какие из моделей вычислений работают с адресуемой памятью?
    (1) Абак
    (2) Машина Тюринга
    (3) РАМ-машина
    Пусть P - трехместный предикатный символ; f , g - одноместные функциональные символы; x, y, u - переменные; b - константа. Какие из подстановок являются унификаторами атомарных формул P(b, y, f (g(y))) и P(x, f (x), f (u))?
    (1) (x/b, y/f (b), u/y)
    (2) (x/b, y/f (b), u/g(y))
    (3) (x/a, y/f (a), u/g(y))
    Какие классы функций используются для амортизационных оценок трудоемкости алгоритмов?
    (1) Ο
    (2) Θ
    (3) Ω
    При каком способе представления разделенных множеств известны рекордные амортизационные оценки трудоемкости?
    (1) массив
    (2) дерево с использованием рангов
    (3) дерево без использования рангов
    (4) дерево с использованием рангов и сжатия путей
    Как можно оценить сверху число элементов в нижнем ярусе d-кучи, состоящей из n элементов?
    (1) Ο(logd n)
    (2) n/d
    (3) Ο(n)
    Как можно оценить трудоемкость операции удаления минимального элемента из левосторонней кучи, состоящей из n элементов?
    (1) Ο(1)
    (2) Ο(log2 n)
    (3) Ω(n)
    Какие операции с самоорганизующейся кучей выполняются с трудоемкостью в худшем случае Ο(1)?
    (1) УДАЛИТЬ
    (2) НАЙТИ ЭЛЕМЕНТ С МИНИМАЛЬНЫМ КЛЮЧОМ
    (3) ВСТАВИТЬ
    (4) УМЕНЬШИТЬ КЛЮЧ
    Какая из перечисленных ниже операций является наиболее трудоемкой?
    (1) Delete
    (2) DecreaseKey
    (3) Insert
    Какова минимальная высота АВЛ-дерева, состоящего из 7 узлов?
    (1) 2
    (2) 3
    (3) 4
    Пусть P и Q - соответственно одноместный и двухместный предикатные символы. Какие из перечисленных формул являются сколемовской формой формулы ∀x ∃y [P(x)& Q(x,y)]?
    (1) ∀x [P(x) ∨ Q(x, f(x))]
    (2) ∀x [P(f(x)) ∨ Q(x, f(x))]
    (3) ∀z [P(z) ∨ Q(z, f(z))]
    Какие из перечисленных функций принадлежат классу Θ(n2)?
    (1) 2n
    (2) 2n2+3n
    (3) 2n3+3n
    (4) n logn
    (5) n2logn
    Чему равен log *n при n = 128?
    (1) 3
    (2) 4
    (3) 8
    (4) 10
    Каково минимальное число элементов в 2-куче, высоты 4?
    (1) 16
    (2) 17
    (3) 15
    Какова минимальная длина правой ветви в левостороннем дереве высоты 4?
    (1) 3
    (2) 4
    (3) 0
    Какие из записей являются результатом инкрементации 2-го разряда в избыточными b-арном (b=10) представлении 3b8b45 ?
    (1) 3b9045
    (2) 408b45
    (3) 3b9145
    Каково будет содержимое ленты после выполнения программы [K2, L, K2], если на ее вход подать псевдослово *u2 * u1*↓(считаем, что слова u1, u2 не содержат символа *, K2 - копирование второго слова, L - сдвиг головки до ближайшего слева символа *)?
    (1) *u2 * u1*u2 *u2 *↓
    (2) *u2 * u1*u2 u2 *↓
    (3) *u2 * u1*u2 *u1 *↓
    Какая из таблиц задает функцию откатов для слова (aabaababaab) в алгоритме Кнута - Морриса - Пратта?
    (1)
    i1234567891011
    f(i)01001230123
    (2)
    i1234567891011
    f(i)01202340123
    (3)
    i1234567891011
    f(i)01012340123
    Какие из следующих операций выполняются за время Ο(1) при динамическом представлении списка с двухсторонними связями?
    (1) нахождение позиции элемента, следующего в кортеже за элементом из заданной позиции
    (2) нахождение позиции элемента, предшествующего в кортеже элементу из заданной позиции.
    (3) удаление элемента, находящегося в заданной позиции
    (4) поиск заданного элемента
    Какова трудоемкость в худшем случае операции нахождения минимального элемента в приоритетной очереди реализованной с помощью биномиальных куч?
    (1) Ο(n)
    (2) Ο(log n)
    (3) Ο(1)
    Толстый лес состоит из двух деревьев F3 и одного дерева F2. Сколько в этом лесе узлов?
    (1) 32
    (2) 36
    (3) 38
    Каково будет содержимое ленты после выполнения программы [L, K1, K2], если на ее вход подать псевдослово *u2 * u1*↓(считаем, что слова u1, u2 не содержат символа *, L - сдвиг головки до ближайшего слева символа *, K1 - копирование первого слова, K2 - копирование второго слова)?
    (1) *u2 * u1*u2 *u1 *↓
    (2) *u2 * u1u2 *u2 *↓
    (3) *u2 * u1*u2 *u2 *↓
    Какие из следующих регулярных выражений в алфавите {a, b, c} являются решениями уравнения X = Xα , где α = ab+aс?
    (1) ab* + ac*
    (2) a(b+c)*a
    (3) (ab+aс)*
    (4) (ab)* + (ac)*
    Какова возможна трудоемкость удаления элемента из заданной позиции двустороннего динамического списка, содержащего n элементов?
    (1) Ο(1)
    (2) Ο(n)
    (3) Ο(log n)
    (4) Ο(n2)
    Какие биномиальные деревья не присутствуют в биномиальном лесе с общим количеством узлов равным 60?
    (1) B5
    (2) B2
    (3) B1
    Сколько толстых деревьев в толстом лесе, состоящем из 155 узлов?
    (1) 7
    (2) 5
    (3) 6
    Сколько слов длины 3 содержится в регулярном множестве, заданном регулярным выражением (ab+c)*?
    (1) 1
    (2) 3
    (3) 10
    (4) 27