uzluga.ru
добавить свой файл

Ответы на экзаменационные вопросы интернет-курсов ИНТУИТ (INTUIT) : Структуры данных и модели вычислений


  1. В какое слово переработает алгорифм Маркова

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  71. Пусть 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)) унифицируемы?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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



Актуальная информация по учебным программам ИНТУИТ расположена по адресу: http://www.intuit.ru/.

Повышение квалификации

(программ: 450)

Профессиональная переподготовка

(программ: 14)

Лицензия на образовательную деятельность и приложение











Developer Project предлагает поддержку при сдаче экзаменов учебных курсов Интернет-университета информационных технологий INTUIT (ИНТУИТ). Мы ответили на экзаменационные вопросы 380 курсов INTUIT (ИНТУИТ), всего 110 300 вопросов, 154 221 ответов (некоторые вопросы курсов INTUIT имеют несколько правильных ответов). Текущий каталог ответов на экзаменационные вопросы курсов ИНТУИТ опубликован на сайте объединения Developer Project по адресу: http://www.dp5.su/

Подтверждения правильности ответов можно найти в разделе «ГАЛЕРЕЯ», верхнее меню, там опубликованы результаты сдачи экзаменов по 100 курсам (удостоверения, сертификаты и приложения с оценками).

Более 21 000 вопросов по 70 курсам и ответы на них, опубликованы на сайте http://www.dp5.su/, и доступны зарегистрированным пользователям. По остальным экзаменационным вопросам курсов ИНТУИТ мы оказываем платные услуги (см. вкладку верхнего меню «ЗАКАЗАТЬ УСЛУГУ». Условия поддержки и помощи при сдаче экзаменов по учебным программам ИНТУИТ опубликованы по адресу: http://www.dp5.su/

Примечания:

- ошибки в текстах вопросов являются оригинальными (ошибки ИНТУИТ) и не исправляются нами по следующей причине - ответы легче подбирать на вопросы со специфическими ошибками в текстах;

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