Инструменты, алгоритмы и структуры данных

Упражнение 1:

Номер 1

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

Ответ:

(1) определение понятия является рекурсивным, если определение один или несколько раз ссылается на определяемое понятие

(2) рекурсивно определенное понятие называют рекурсивным понятием только для простоты, хотя это и не вполне корректно

(3) для любого понятия существует рекурсивное определение

(4) любое рекурсивно определенное понятие можно определить, не используя рекурсию

Номер 2

Что можно определить рекурсивно?

Ответ:

(1) любую структуру данных

(2) некоторую структуру данных

(3) любой алгоритм - метод класса (процедуру, функцию)

(4) некоторый алгоритм - метод класса (процедуру, функцию)

(5) любые понятия проблемной области - грамматики языков программирования, каталоги операционной системы и так далее

(6) некоторые понятия проблемной области - некоторые грамматики языков программирования, каталоги операционной системы, допускающие подкаталоги и другие понятия, имеющие вложенную структуру

Номер 3

Напомним, что идентификатором называется любая последовательность букв, цифр и символа подчеркивания, начинающаяся с буквы. Заметьте, это определение не рекурсивно. Какие из БНФ определений идентификатора являются корректными рекурсивными определениями?

Ответ:

(1)

(2)

(3)

(4)

(5)

Упражнение 2:

Номер 1

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

Ответ:

(1) понятие "Буква", где буквой может быть любой из символов алфавита кириллицы, воспринимаемый как терминальный, не определяемый символ

(2) понятие "Целое", понимаемое как последовательность цифр, воспринимаемых как терминальные, не определяемые символы

(3) понятие "Целое со знаком", понимаемое как последовательность цифр, воспринимаемых как терминальные, не определяемые символы. Цифрам может предшествовать знак плюс или минус

(4) понятие "ФИО", понимаемое как последовательность трех строк, задающих фамилию, имя и отчество и воспринимаемых в данном контексте как терминальные, не определяемые символы

Номер 2

Рассмотрим язык программирования с двумя операторами - присваивания и цикла. Присваивание рассматривается в классическом варианте variable := expression и считается терминальным, не определяемым далее понятием. Грамматика языка такова:
 
 Какие утверждения являются справедливыми относительно правил этой грамматики?

Ответ:

(1) определение понятия "Оператор" является явно рекурсивным определением

(2) определение понятия "Цикл" является явно рекурсивным определением

(3) определение понятия "Оператор" является определением с косвенной рекурсией

(4) определение понятия "Цикл" не является рекурсивным определением

Номер 3

Представим себе, что при определении ссылочного класса PERSON заданы два атрибута (поля класса) mother и father класса PERSON. Какие утверждения справедливы относительно порождения объектов этого класса?

Ответ:

(1) такое определение, являясь рекурсивным, всегда порождает бесконечную цепочку объектов, каждый из которых ссылается на свою пару объектов mother и father

(2) такое определение, являясь рекурсивным, позволяет порождать конечную цепочку объектов, задавая генеалогическое древо до определенного уровня

(3) такое определение, являясь рекурсивным, будет порождать конечную цепочку объектов, заканчивающуюся парой объектов "ЕВА" и "АДАМ" - праматерью и праотцом

(4) такое определение, являясь рекурсивным, может и не порождать цепочки объектов, поскольку родители могут быть неизвестны или не указаны по каким либо причинам.

(5) возможное для ссылки значение void является по умолчанию частью рекурсивного определения любой рекурсивной ссылочной структуры данных, что позволяет создавать конечную структуру связанных ссылками объектов

Упражнение 3:

Номер 1

Укажите некорректные варианты определения рекурсивной версии программы fibonacci:

Ответ:

(1) fibonacci(n: INTEGER): INTEGER require positive: n >=0 do if n = 0 then Result := 1 elseif n = 1 then Result := 1 else Result := fibonacci(n-1); n := n-1; Result := Result + fibonacci(n-1); end end

(2) fibonacci(n: INTEGER): INTEGER require positive: n >=0 do Result :=0 if n = 1 then Result := 1 else Result := fibonacci(n-1) + fibonacci(n-2); end end

(3) fibonacci(n: INTEGER): INTEGER require positive: n >=0 do if n = 0 then Result := 1 elseif n = 1 then Result := 1 else Result := fibonacci(n-2) + fibonacci(n-1); end end

(4) fibonacci(n: INTEGER): INTEGER require positive: n >=1 do if n = 1 then Result := 1 elseif n = 2 then Result := 1 else Result := fibonacci(n-1) + fibonacci(n-2); end end

Номер 2

Какие утверждения справедливы относительно сравнения циклического и рекурсивного варианта вычисления чисел Фибоначчи?

Ответ:

(1) циклический вариант имеет временную сложность O(n)

(2) при эффективной реализации рекурсии сложность рекурсивного варианта O(n)

(3) циклический вариант, как правило, работает быстрее

(4) рекурсивный вариант, как правило, работает быстрее

Номер 3

Преобразование рекурсивного определения в циклическое может быть не простой задачей. Зная рекурсивное решение задачи о Ханойской башне, укажите, какой первый ход следует сделать для произвольного значения n:

Ответ:

(1) перенос с А на В

(2) перенос с А на С

(3) не имеет значения, куда переносить на А или на С

(4) если n - нечетно, то перенос на В, иначе перенос на С

Упражнение 4:

Номер 1

Рекурсивное определение напоминает фокус. Рассмотрим рекурсивное определение известной в математике функции:
 
 Совершенно очевидно, какие значения принимает эта функция при . А каковы ее значения при ? Оказывается, для таких  функция имеет одно и то же значение. Какое?

Ответ:

(1) 1

(2) 11

(3) 33

(4) 77

(5) 91

(6) 99

Номер 2

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

Ответ:

(1) корректно определенное рекурсивное определение всегда включает выбор, по крайней мере, одна ветвь которого содержит нерекурсивную часть определения

(2) рекурсия, подобно стратегии цикла, в большинстве случаев задает последовательное приближение к решению задачи

(3) в отличие от цикла until (while), который может не иметь варианта и описывать не завершающийся процесс (зацикливаться), рекурсивное определение всегда гарантирует завершаемость

(4) рекурсия использует стратегию вызова процедуры с тем отличием, что вызывает саму себя, но при других значениях аргументов, приближающих, как правило, к цели

Номер 3

Какие утверждения справедливы для бинарного дерева?

Ответ:

(1) бинарное дерево можно определить как рекурсивную структуру данных

(2) бинарное дерево всегда имеет узел, называемый корнем дерева

(3) бинарное дерево может быть пустым, не иметь корня, не иметь ни одного узла

(4) бинарное дерево всегда имеет два бинарных поддерева - левое и правое

(5) бинарное дерево может иметь два поддерева, одно поддерево или ни одного поддерева

Упражнение 5:

Номер 1

Какие утверждения справедливы для узла бинарного дерева?

Ответ:

(1) только один узел бинарного дерева является его корнем

(2) у бинарного дерева может быть несколько узлов, являющихся корнями этого дерева

(3) каждый узел бинарного дерева является корнем самого дерева или корнем одного из поддеревьев бинарного дерева

(4) каждый узел math

бинарного дерева math

определяет бинарное дерево math

Номер 2

Какие утверждения справедливы для задачи "Ханойская башня"?

Ответ:

(1) для ее решения существует только рекурсивный алгоритм

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

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

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

Номер 3

Сколько времени понадобится вашему персональному компьютеру для решения задачи о "ханойской башне" в ее оригинальном варианте с 64 дисками (для корректности постановки будем полагать, что ваш ПК хотя и не является суперкомпьютером, но способен выполнить за секунду 1 миллиард переносов дисков)?

Ответ:

(1) менее наносекунды

(2) менее секунды

(3) менее часа

(4) менее суток

(5) более 100 лет

Упражнение 6:

Номер 1

Пусть  - полное бинарное дерево (каждый узел не являющийся листом дерева имеет двух потомков) число листьев в котором равно . Для обхода дерева применяется инфиксная процедура обхода (обойти левое дерево, обойти корень, обойти правое дерево). Каким по счету будет посещен корень дерева, если счет узлов начинается с 1)?

Ответ:

(1) 1

(2)

(3)

(4)

Номер 2

В соответствии с определением бинарного дерева поиска для него справедливо?

Ответ:

(1) все элементы, хранимые в узлах дерева, различны

(2) для любых двух элементов, хранимых в узлах дерева, один из них "больше другого"

(3) максимальный элемент хранится в корне дерева

(4) максимальный элемент левого дерева меньше минимального элемента правого дерева

Номер 3

Какие утверждения справедливы о сложности операции вставки элемента в дерево поиска с n элементами?

Ответ:

(1) для любого дерева поиска средняя сложность равна math

(2) для любого дерева поиска средняя сложность равна math

(3) для полного дерева поиска средняя сложность равна math

(4) для полного дерева поиска средняя сложность равна math

(5) для произвольного дерева поиска максимальная сложность равна math

Упражнение 7:

Номер 1

Пусть разыскивается путь в графе. Содержательно можно рассматривать города, соединенные сетью дорог. Задача состоит в том, чтобы найти путь из города А в город В. Для поиска пути применяется алгоритм перебора с возвратами, реализованный в виде процедуры поиска find(path), где path - это построенный путь, начинающийся в городе А и заканчивающийся приходом в некоторый ранее не встречавшийся на построенном пути город N. Из города N дороги ведут в n городов - , не вошедшие в путь path. Какие утверждения справедливы для процедуры поиска?

Ответ:

(1) поиск может завершиться успехом в городе N только в том случае, если N - это и есть искомая цель - город В

(2) поиск всегда завершается в городе N успехом или неуспехом

(3) поиск обязательно завершится в одном из городов math

успехом или неуспехом

(4) поиск может завершиться успехом в одном из городов math

Номер 2

Пусть разыскивается путь в графе. Содержательно можно рассматривать города, соединенные сетью дорог. Задача состоит в том, чтобы найти путь из города А в город В. Для поиска пути применяется алгоритм перебора с возвратами, реализованный в виде процедуры поиска find(path), где path - это построенный путь, начинающийся в городе А и заканчивающийся приходом в некоторый ранее не встречавшийся на построенном пути город N. Из города N дороги ведут в n городов - , не входящие в путь path. Какие утверждения справедливы относительно вызовов процедуры поиска?

Ответ:

(1) если после вызова find(path), в процессе ее работы, достигнут город N, то больше эта процедура вызываться не будет

(2) если город N не является искомой целью - городом В, то процедура find как рекурсивная процедура будет вызвана как минимум один раз

(3) если город N не является искомой целью - городом В, то процедура find как рекурсивная процедура будет вызвана не менее n раз

(4) если город N не является искомой целью - городом В, то процедура find как рекурсивная процедура будет вызвана не более n раз

(5) если город N не является искомой целью - городом В, то процедура find как рекурсивная процедура будет вызвана m раз, где m может быть как больше, так и равно или меньше n

Номер 3

Пусть разыскивается путь в графе. Содержательно можно рассматривать города, соединенные сетью дорог. Задача состоит в том, чтобы найти путь из города А в город В. Для поиска пути применяется алгоритм перебора с возвратами, реализованный в виде процедуры поиска find(path), где path - это построенный путь, начинающийся в городе А и заканчивающийся приходом в некоторый ранее не встречавшийся на построенном пути  город N. Из города N дороги ведут в n городов - , не входящие в путь path. Какие утверждения справедливы относительно возвратов в процессе поиска?

Ответ:

(1) если в процессе поиска путь поведет в следующий город, то возврата в город N никогда не будет

(2) в процессе поиска всегда будет происходить возврат в город N

(3) если путь math

ведет к успеху, то возврата в город N не будет

(4) в процессе поиска может произойти возврат из города N в город, путь из которого привел в N

(5) в процессе поиска с возвратами можно вернуться к исходной точке - городу А

Упражнение 8:

Номер 1

Алгоритм перебора с возвратами, реализованный рекурсивной процедурой find(path) исключает зацикливание (каждый город на пути встречается только один раз), что позволяет исходный граф рассматривать как дерево. Какие утверждения справедливы для графов, перебора с возвратом, и связанных с ними деревьев вариантов?

Ответ:

(1) граф без циклов является деревом

(2) для всякого графа можно построить остовное дерево, удалив часть узлов графа.

(3) для всякого графа можно построить остовное дерево, удалив часть дуг графа

(4) алгоритм перебора с возвратами сводится к префиксному обходу дерева вариантов

(5) алгоритм перебора с возвратами сводится к инфиксному обходу дерева вариантов

(6) алгоритм перебора с возвратами сводится к постфиксному обходу дерева вариантов

(7) единственное отличие алгоритма перебора от обхода дерева состоит в том, что алгоритм перебора останавливается в узле, где выполняется условие поиска

Номер 2

Рассмотрим игру, в которой применяется минимаксная стратегия. Напомним, это означает, что в игре участвуют два противника, поочередно выполняющие ходы. Существует оценочная функция, которая выдает оценку (число) для каждой позиции после очередного хода. Положительное значение этой оценки рассматривается как выигрыш для одного игрока и как проигрыш для другого (игра с нулевой суммой). Рассмотрим дерево конкретной игры, в узлах которого записываются оценки позиций. Дерево зададим скобочной записью:
 (((5, 3) (6, -1, 8))((10, 6, 2) (-2, -4, -7)) )
 Здесь цифры, заключенные в скобки - это оценки в листьях, принадлежащих одному родителю. Игрок на нижнем уровне выбирает минимальную оценку. Каково значение цены игры для этого дерева?

Ответ:

(1) 5

(2) 3

(3) -1

(4) 2

(5) -7

(6) 10

Номер 3

Рассмотрим игру, в которой применяется минимаксная стратегия. Напомним, это означает, что в игре участвуют два противника, поочередно выполняющие ходы. Существует оценочная функция, которая выдает оценку (число) для каждой позиции после очередного хода. Положительное значение этой оценки рассматривается как выигрыш для одного игрока и как проигрыш для другого (игра с нулевой суммой). Зададим дерево конкретной игры, в узлах которого записаны оценки позиций. Дерево зададим скобочной записью:
( ((5, 3) (6, -1, 8)) ((10, 6, 2) (-2, -4, -7)) )
Здесь цифры, заключенные в скобки - это оценки в листьях, принадлежащих одному родителю. Игрок на нижнем уровне выбирает минимальную оценку. При вычислении цены игры применяется альфа-бета стратегия отсечения вариантов. Сколько вариантов (в данном случае листьев дерева) будет отсечено при применении этой стратегии?

Ответ:

(1) 1

(2) 2

(3) 3

(4) 4

(5) 5

(6) 6

Инструменты, алгоритмы и структуры данных - тест 8