PUERTA | PUERTA CS 1997 | Pregunta 32

Se utiliza una cola de prioridad Q para implementar una pila S que almacena caracteres. PUSH(C) se implementa como INSERT(Q, C, K) donde K es una clave entera apropiada elegida por la implementación. POP se implementa como DELETEMIN(Q). Para una secuencia de operaciones, las teclas elegidas están en
(A) orden no creciente
(B) orden no decreciente
(C) orden estrictamente creciente
(D) orden estrictamente decreciente

Respuesta: (D)
Explicación: Estamos implementando un STACK usando cola de prioridad. Tenga en cuenta que la implementación de Stack siempre es el último en entrar, primero en salir (LIFO).

Como se indica, «POP se implementa como DELETEMIN (Q)», lo que significa que Stack siempre devuelve el elemento mínimo.

Entonces, necesitamos implementar PUSH(C) usando INSERT(Q, C, K) donde K es la clave elegida de un orden estrictamente decreciente (solo este orden garantizará que la pila devuelva el elemento mínimo cuando hagamos POP un elemento). Eso satisfará la propiedad Last In First Out (LIFO) de la pila.

Esa es la respuesta, la opción (D) es verdadera.

El orden no creciente de la opción (A) no puede ser cierto porque dos números iguales (idénticos) no pueden tener la misma prioridad, ya que la prioridad debe distinguirse para cada número.

Cuestionario de esta pregunta