Рубрики

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

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


1. Наиболее эффективный алгоритм нахождения числа связанных компонент в неориентированном графе по n вершинам и m ребрам имеет временную сложность.

(A) Θ (n)
(B) Θ (м)
(C) Θ (m + n)
(D) Θ (млн)

Ответ (С)
Связанные компоненты можно найти в O (m + n), используя алгоритм Тарьяна . Как только мы соединили компоненты, мы можем их посчитать.


2. Рассмотрим алгоритм быстрой сортировки. Предположим, что существует процедура поиска сводного элемента, который разбивает список на два подсписка, каждый из которых содержит не менее одной пятой элементов. Пусть T (n) будет количеством сравнений, необходимых для сортировки n элементов. потом

(A) T (n)
3 Алгоритм Дийкстры с одним источником кратчайшего пути при запуске из вершины а на приведенном ниже графике вычисляет правильное расстояние кратчайшего пути до

(А) только вершина а
(B) только вершины a, e, f, g, h
(C) только вершины a, b, c, d
(D) все вершины

Ответ (D)
Кратчайший путь Дейкстры с одним источником не гарантируется для графов с отрицательными весовыми ребрами, но он работает для данного графа.
Покажи нам…

Давайте запустим 1-й проход
б 1
b является минимальным, поэтому самое короткое расстояние до b равно 1.

После 1-го прохода расстояния
с 3, е -2.
е минимально, поэтому кратчайшее расстояние до е равно -2

После 2-го прохода расстояния
с 3, f 0.
f является минимальным, поэтому самое короткое расстояние до f равно 0

После 3-го прохода расстояния
с 3, г 3.
Оба одинаковы, давайте возьмем g. поэтому самое короткое расстояние до g составляет 3.

После 4-го прохода расстояния
с 3, ч 5
c является минимальным, поэтому самое короткое расстояние до c равно 3

После 5-го прохода расстояния
ч -2
h минимально, поэтому самое короткое расстояние до h равно -2

4. Следующая функция C принимает односвязный список целых чисел в качестве параметра и переупорядочивает элементы списка. Функция вызывается со списком, содержащим целые числа 1, 2, 3, 4, 5, 6, 7 в указанном порядке. Каким будет содержимое списка после завершения функции?

struct node 

{

  int value;

  struct node *next;

};

void rearrange(struct node *list)

{

  struct node *p, * q;

  int temp;

  if ((!list) || !list->next) 

      return;

  p = list;

  q = list->next;

  while(q) 

  {

     temp = p->value;

     p->value = q->value;

     q->value = temp;

     p = q->next;

     q = p?p->next:0;

  }

}

(А) 1,2,3,4,5,6,7
(В) 2,1,4,3,6,5,7
(С) 1,3,2,5,4,7,6
(D) 2,3,4,5,6,7,1

Ответ (Б)
Функцияrange () обменивается данными каждого узла со своим следующим узлом. Он начинает обмениваться данными с самого первого узла.

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

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

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

0.00 (0%) 0 votes