База ответов ИНТУИТ

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

<<- Назад к вопросам

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

(Отметьте один правильный вариант ответа.)
Варианты ответа
2^m(Верный ответ)
m
1
2^{m +1} - 1
Похожие вопросы
Пусть аргументом функции h является множество пар целых чисел. Пусть также функция h:
  • добавляет в множество пару [0,0];
  • если в множестве есть пара [i, S] и i<n, то в множество добавляется пара [i+1, S+ i +1]
    •  Для какой рекурсивно определенной функции F(n), где n>=0, функция h является решением уравнения неподвижной точки F = h(F)?
    Пусть функция h является решением уравнения неподвижной точки F = h(F). Это позволяет дать не рекурсивное определение функции F, аналогично тому, как определяется предел последовательности. Рассмотрим последовательность графов и связанных с ними функций F_0, F_1, … , F_n. Какие утверждения не являются справедливыми относительно такого определения F?
    Рекурсивное определение напоминает фокус. Рассмотрим рекурсивное определение известной в математике функции:
    F(n) = n – 10,\text{ если }n > 100\\ F(n) = F(F(n + 11),\text{ если }n <= 100
    Совершенно очевидно, какие значения принимает эта функция при n> 100. А каковы ее значения при n< 101? Оказывается, для таких n функция имеет одно и то же значение. Какое?
    Рекурсивное определение можно рассматривать как уравнение неподвижной точки F = h(F). Пусть функция h является решением этого уравнения. Какие утверждения справедливы для этой функции?
    Рассмотрим игру, в которой применяется минимаксная стратегия. Напомним, это означает, что в игре участвуют два противника, поочередно выполняющие ходы. Существует оценочная функция, которая выдает оценку (число) для каждой позиции после очередного хода. Положительное значение этой оценки рассматривается как выигрыш для одного игрока и как проигрыш для другого (игра с нулевой суммой). Зададим дерево конкретной игры, в узлах которого записаны оценки позиций. Дерево зададим скобочной записью: 
    ( ((5, 3) (6, -1, 8)) ((10, 6, 2) (-2, -4, -7)) )
    Здесь цифры, заключенные в скобки - это оценки в листьях, принадлежащих одному родителю. Игрок на нижнем уровне выбирает минимальную оценку. При вычислении цены игры применяется альфа-бета стратегия отсечения вариантов. Сколько вариантов (в данном случае листьев дерева) будет отсечено при применении этой стратегии?
    Рекурсивное определение функции F можно рассматривать как уравнение неподвижной точки F = h(F). Какие утверждения справедливы для этого уравнения?
    Пусть для конечного множества элементов A ={a_1, a_2,… a_n} задано ациклическое отношение r множеством пар [a_k, a_j], принадлежащих отношению. На множестве А можно построить n! различных последовательностей этих элементов - перечислений элементов. Какие утверждения справедливы относительно этих перечислений и их топологической отсортированности?
    Рассмотрим игру, в которой применяется минимаксная стратегия. Напомним, это означает, что в игре участвуют два противника, поочередно выполняющие ходы. Существует оценочная функция, которая выдает оценку (число) для каждой позиции после очередного хода. Положительное значение этой оценки рассматривается как выигрыш для одного игрока и как проигрыш для другого (игра с нулевой суммой). Рассмотрим дерево конкретной игры, в узлах которого записываются оценки позиций. Дерево зададим скобочной записью: 
    (((5, 3) (6, -1, 8))((10, 6, 2) (-2, -4, -7)) )
    Здесь цифры, заключенные в скобки - это оценки в листьях, принадлежащих одному родителю. Игрок на нижнем уровне выбирает минимальную оценку. Каково значение цены игры для этого дерева?
    Гарри Поттер ищет важную для него информацию. Он надеется, что она может быть в одной из книг библиотеки Хогварда, содержащей N книг. Гарри наугад выбирает книгу и просматривает ее содержимое, на что у него уходит T минут. При неудаче он повторяет поиск, выбирая новую книгу. Для такого алгоритма поиска каковы значения времени поиска: минимальное, максимальное, в среднем?
    Какими свойствами обладает отношение строгого полного (тотального) порядка на множестве А? Отношение полного строгого порядка: