Рубрики

Структуры данных и алгоритмы | Набор 4

Следующие вопросы были заданы на экзамене GATE CS.

1. Рассмотрим следующий сегмент программы на C

struct CellNode

{

  struct CelINode *leftchild;

  int element;

  struct CelINode *rightChild;

}

  

int Dosomething(struct CelINode *ptr)

{

    int value = 0;

    if (ptr != NULL)

    {

      if (ptr->leftChild != NULL)

        value = 1 + DoSomething(ptr->leftChild);

      if (ptr->rightChild != NULL)

        value = max(value, 1 + DoSomething(ptr->rightChild));

    }

    return (value);

}

Значение, возвращаемое функцией DoSomething, когда в качестве аргумента передается указатель на корень непустого дерева (GATE CS 2004)
а) Количество листовых узлов в дереве
б) Количество узлов в дереве
в) количество внутренних узлов в дереве
г) высота дерева

Ответ: (г)
Объяснение: DoSomething () возвращает max (высота левого ребенка + 1, высота левого ребенка + 1). Таким образом, учитывая, что указатель на корень дерева передается в DoSomething (), он будет возвращать высоту дерева. Обратите внимание, что эта реализация следует соглашению, где высота одного узла равна 0.

2. Предположим, что мы запускаем алгоритм кратчайшего пути Дейкстры с одним источником на следующем ребристом ориентированном графе с вершиной P в качестве источника. В каком порядке узлы включаются в набор вершин, для которых финализируются кратчайшие расстояния? (GATE CS 2004)

а) P, Q, R, S, T, U
б) P, Q, R, U, S, T
в) P, Q, R, U, T, S
г) P, Q, T, R, U, S

Ответ (б)

3. Предположим, что каждый набор представлен в виде связанного списка с элементами в произвольном порядке. Какая из операций среди объединения, пересечения, членства, кардинальности будет самой медленной? (GATE CS 2004)
а) только союз
б) пересечение, членство
в) членство, количество элементов
г) объединение, пересечение

Ответ (г)
Кардинальность и членство определенно не самые медленные. Для кардинальности просто посчитайте количество узлов в списке. Для членства, просто просмотрите список и найдите совпадение

Чтобы получить пересечение L1 и L2, найдите каждый элемент L1 в L2 и напечатайте элементы, которые мы находим в L2.

Там может быть много способов получить объединение L1 и L2. Одним из них является следующее
а) Вывести все узлы L1 и распечатать только те, которые отсутствуют в L2.
б) Печать узлов L2.

4. Временная сложность следующей функции C равна (предположим, что n> 0 (GATE CS 2004)

int recursive (mt n)

{

   if (n == 1)

     return (1);

   else

     return (recursive (n-1) + recursive (n-1));

}

а) 0 (н)
б) 0 (нет)
в) 0 (п ^ 2)
г) 0 (2 ^ n)

Ответ (г)
Объяснение:
Рекурсивное выражение для вышеуказанной программы будет.

  T(n) = 2T(n-1) + c
  T(1) = c1.

Позвольте нам решить это.

  T(n) = 2(2T(n-2) + c) + c        = 4T(n-2) + 3c
  T(n) = 8T(n-3) + 6c + c          =  8T(n-3) + 7c
  T(n) = 16T(n-4) + 14c + c        =  16T(n-4) + 15c
  ............................................................
  .............................................................
  T(n) = (2^(n-1))T(1) +  (2^(n-1) - 1)c

  T(n) = O(2^n)

Пожалуйста, напишите комментарии, если вы найдете какие-либо из приведенных выше ответов / объяснений неверными.

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

Структуры данных и алгоритмы | Набор 4

0.00 (0%) 0 votes