Функциональное программирование

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

Номер 1

 Как связаны двоичные деревья и деревья общего вида?

Ответ:

(1) дерево общего вида является частным случаем двоичного дерева

(2) двоичное дерево является частным случаем дерева общего вида

(3) любое дерево общего вида однозначно представимо в виде двоичного дерева

Номер 2

 Как правильно описать дерево общего вида на F#?

Ответ:

(1) type 'T tree = Leaf of 'T | Node of 'T*('T tree list)

(2) type 'T tree = Leaf of 'T | Node of 'T*T'

(3) type 'T tree = Nil | Leaf of 'T | Node of 'T -> ('T tree list)

(4) type 'T tree = Nil | Leaf of 'T | Node of 'T*T’*(’T tree)

Номер 3

 Как правильно описать двоичное дерево на F#?

Ответ:

(1) type 'T btree = Leaf of 'T | Node of 'T*('T btree list)

(2) type 't btree = Node of 't * 't btree * 't btree | Nil

(3) type 't btree = Node of 't * 't btree * 't btree

(4) type 't btree = Leaf of 't | Node of 't btree

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

Номер 1

 В каком порядка обходятся поддеревья в инфиксном порядке обхода?

Ответ:

(1) корень, левое поддерево, правое поддерево

(2) левое поддерево, корень, правое поддерево

(3) левое поддерево, правое поддерево, корень

(4) корень, правое поддерево, левое поддерево

Номер 2

 В каком порядка обходятся поддеревья в префиксном порядке обхода?

Ответ:

(1) корень, левое поддерево, правое поддерево

(2) левое поддерево, корень, правое поддерево

(3) левое поддерево, правое поддерево, корень

(4) корень, правое поддерево, левое поддерево

Номер 3

 В каком порядка обходятся поддеревья в постфиксном порядке обхода?

Ответ:

(1) корень, левое поддерево, правое поддерево

(2) левое поддерево, корень, правое поддерево

(3) левое поддерево, правое поддерево, корень

(4) корень, правое поддерево, левое поддерево

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

Номер 1

 Что такое дерево поиска?

Ответ:

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

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

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

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

Номер 2

 Какова сложность поиска в дереве поиска?

Ответ:

(1) O(log n)

(2) O(n)

(3) между O(log n) и O(n), в зависимости от сбалансированности дерева

(4) между O(n) и O(n2), в зависимости от количества элементов дерева

Номер 3

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

Ответ:

(1) деревом общего вида, в котором число поддеревьев соответствует количеству аргументов операции

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

(3) двоичным деревом

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

Номер 1

 Что такое продолжение (continuation)?

Ответ:

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

(2) оператор, помогающий компилятору распознать хвостовую рекурсию

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

Номер 2

 Как можно свести нелинейно-рекурсивную функцию к хвостовой рекурсии?

Ответ:

(1) используя стек для хранения оставшихся заданий на обработку

(2) используя дерево для представления цепочки вычислений

(3) используя продолжения для разворачивания рекурсии в цепочку функций

Функциональное программирование - тест 13