Рубрики

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

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

1. Рассмотрим следующий сегмент программы на C, где CellNode представляет узел в двоичном дереве:

struct CellNode 

{

  struct CellNOde *leftChild;

  int element;

  struct CellNode *rightChild;

};

  

int GetValue(struct CellNode *ptr) 

{

  int value = 0;

  if (ptr != NULL) 

  {

   if ((ptr->leftChild == NULL) &&

        (ptr->rightChild == NULL))

      value = 1;

   else

      value = value + GetValue(ptr->leftChild)

                   + GetValue(ptr->rightChild);

  }

  return(value);

}

Значение, возвращаемое GetValue (), когда указатель на корень двоичного дерева передается в качестве аргумента:
(A) количество узлов в дереве
(B) количество внутренних узлов в дереве
(C) количество листовых узлов в дереве
(D) высота дерева

Ответ (С)
Для объяснения, пожалуйста, смотрите наш пост http://espressocode.top/?p=2755 для подсчета конечных узлов.

2. Рассмотрим процесс вставки элемента в Max Heap, где Max Heap представлен массивом. Предположим, что мы выполняем двоичный поиск по пути от нового листа к корню, чтобы найти позицию для вновь вставленного элемента, число выполненных сравнений:
(A) Θ (logn)
(B) Θ (LogLogn)
(С) Θ (н)
(D) Θ (nLogn)

Ответ (Б)
Высота Max Heap составляет Θ (logn). Если мы выполняем бинарный поиск для нахождения правильной позиции, то нам нужно сделать Θ (LogLogn) сравнения.

3. Пусть w будет минимальным весом среди всех весов ребер в неориентированном связном графе. Пусть е — конкретное ребро веса w. Что из следующего является ЛОЖНЫМ?
(A) Существует минимальное связующее дерево, содержащее e.
(B) Если e не находится в минимальном остовном дереве T, то в цикле, образованном добавлением e к T, все ребра имеют одинаковый вес.
(C) Каждое минимальное остовное дерево имеет ребро веса w.
(D) е присутствует в каждом минимальном остовном дереве.

Ответ (D)
(A), (B) и (C) являются правильными.
(D) неверно, так как на графике может быть много краев w, и e может не быть подобрано в некоторых минимальных охватывающих деревьях.

4. Дан массив из n чисел, где n — четное число. Максимум, а также минимум этих n чисел должны быть определены. Что из следующего является ИСТИННЫМ о количестве необходимых сравнений?
(A) Требуется как минимум 2n-c сравнений для некоторой константы c.
(B) Требуется максимум 1,5n — 2 сравнения.
(C) Необходимо по крайней мере сравнение nLog2n.
(D) Ничего из вышеперечисленного.

Ответ (Б)

Пожалуйста, смотрите пост http://espressocode.top/?p=4583 для деталей.

5. Рассмотрим следующий сегмент кода C:

int IsPrime(n)

{

  int i,n;

  for(i=2;i<=sqrt(n);i++)

   if(n%i == 0)

     {printf(“Not Prime\n”); return 0;}

  return 1;

}

Пусть T (n) обозначает количество раз, которое цикл for выполняется программой на входе n. Что из перечисленного правда?
(A) T (n) = O (sqrt (n)) и T (n) = Ω (sqrt (n))
(B) T (n) = O (sqrt (n)) и T (n) = Ω (1)
(C) T (n) = O (n) и T (n) = Ω (sqrt (n))
(D) Ничего из вышеперечисленного

Ответ (Б)
Нотация Big O описывает верхнюю границу, а нотация Big Omega — нижнюю границу для алгоритма.

Цикл for в вопросе выполняется максимум sqrt (n) раз и минимум 1 раз. Следовательно, T (n) = O (sqrt (n)) и T (n) = Ω (1)

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

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

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

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

0.00 (0%) 0 votes