Рубрики

ВОРОТА | GATE-CS-2014- (Set-3) | Вопрос 65

Рассмотрим псевдокод, приведенный ниже. Функция DoSomething () принимает в качестве аргумента указатель на корень произвольного дерева, представленного представлением leftMostChild-rightSibling.
Каждый узел дерева имеет тип treeNode.

typedef struct treeNode* treeptr;

struct treeNode

{

    treeptr leftMostChild, rightSibling;

};

int DoSomething (treeptr tree)

{

    int value=0;

    if (tree != NULL)

    {

        if (tree->leftMostChild == NULL)

            value = 1;

        else

            value = DoSomething(tree->leftMostChild);

        value = value + DoSomething(tree->rightSibling);

    }

    return(value);

}

Когда указатель на корень дерева передается в качестве аргумента DoSomething, значение, возвращаемое функцией, соответствует
(A) количество внутренних узлов в дереве.

(Б) высота дерева.
(C) количество узлов без правильного брата в дереве.

(D) количество листовых узлов в дереве.

Ответ: (D)
Объяснение: Функция считает конечные узлы для дерева, представленного с использованием представления leftMostChild-rightSibling.

Ниже функция с добавленными комментариями, чтобы продемонстрировать, как работает функция.

int DoSomething (treeptr tree)

{

    // Если дерево пусто, возвращается 0

    int value = 0;

  

    // если дерево не пустое

    if (tree != NULL)

    {

        // Если это листовой узел, то значения инициализируются как 1

        if (tree->leftMostChild == NULL)

            value = 1;

  

        // Иначе значение инициализируется как значение, возвращаемое крайним левым

        // дочерний элемент, который в свою очередь вызывает других дочерних элементов этого узла

        // Используя последний вызов "value = value + DoSomething (tree-> rightSibling);"

        else

            value = DoSomething(tree->leftMostChild);

  

        // Добавить значение, возвращаемое правильным братом

        value = value + DoSomething(tree->rightSibling);

    }

    return(value);

}

Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2014- (Set-3) | Вопрос 65

0.00 (0%) 0 votes