Рубрики

Структуры данных | Очередь | Вопрос 11

Реализация очереди 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 <= x <2n и 2m <= y <= n + m
(B) n + m <= x <2n и 2m <= y <= 2n
(C) 2m <= x <2n и 2m <= y <= n + m
(D) 2m <= x <2n и 2m <= y <= 2n

Ответ: (А)
Объяснение: Здесь важен порядок выполнения операций вставки и удаления.
Лучший вариант: операции вставки и удаления выполняются поочередно. В каждой операции удаления выполняются 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 () и n push для delete ())
Тест на этот вопрос

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

Структуры данных | Очередь | Вопрос 11

0.00 (0%) 0 votes