Рубрики

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

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

1. Реализация очереди Q с использованием двух стеков S1 и S2 приведена ниже:

void insert(Q, x) {

   push (S1, x);

}

  

void delete(Q){

   if(stack-empty(S2)) then 

      if(stack-empty(S1)) then {

          print(“Q is empty”);

          return;

      }

      else while (!(stack-empty(S1))){

          x=pop(S1);

          push(S2,x);

      }

   x=pop(S2);

}

Пусть n операций вставки и m (<= n) удаления будут выполняться в произвольном порядке в пустой очереди Q. Пусть x и y будут количеством операций push и pop, выполненных соответственно в процессе. Что из следующего верно для всех m и n?
(A) n + m Лучший вариант: операции вставки и удаления выполняются поочередно. В каждой операции удаления выполняются 2 всплывающих и 1 нажатие. Итак, всего m + n push (n push для insert () и m push для delete ()) и 2m pop операций.

Худший случай:
сначала вставляются n элементов, а затем m элементов. В первой операции удаления выполняются операции n + 1 pop и операция n push. За исключением первого, во всех операциях удаления выполняется 1 операция всплывающего окна. Таким образом, выполняется всего m + n pop-операций и 2n push-операций (n push для insert () и m push для delete ())

2. Рассмотрим следующий график:

Какое из следующих утверждений не может быть последовательностью ребер, добавленной в указанном порядке к минимальному остовному дереву с использованием алгоритма Крускала?
(A) (a-b), (d-f), (b-f), (d-c), (d-e)
(B) (a-b), (d-f), (d-c), (b-f), (d-e)
(C) (d-f), (a-b), (d-c), (b-f), (d-e)
(D) (d-f), (a-b), (b-f), (d-e), (d-c)

Ответ (D)
Край (de) не может быть рассмотрен раньше (dc) в алгоритме минимального остовного дерева Крускала, потому что алгоритм Крускала выбирает ребро с минимальным весом из текущего набора ребер на каждом шаге.

3. Медиана из n элементов может быть найдена за O (n) времени. Какие один из следующего правильно о сложности быстрой сортировки, в котором медиана выбрана в качестве опоры?
(A) Θ (n)
(B) Θ (nlogn)
(C) Θ (n ^ 2)
(D) Θ (n ^ 3)

Ответ (Б)
Если медиана всегда используется как опорная точка, то рекурсия остается T (n) = 2T (n / 2) + cn для всех случаев, когда cn — это объединенное время для поиска и разбиения медианы. Таким образом, наихудшая временная сложность этой быстрой сортировки становится Θ (nlogn) Однако в практических реализациях этот вариант в среднем значительно медленнее (см. Http://en.wikipedia.org/wiki/Quicksort#Selection-based_pivoting )

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

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

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

0.00 (0%) 0 votes