PUERTA | GATE-CS-2017 (Conjunto 2) | Pregunta 30

Se implementó una cola circular utilizando una lista enlazada individualmente donde cada Node consta de un valor y un puntero al siguiente Node. Mantenemos exactamente dos punteros FRONT y REAR que apuntan al Node delantero y al Node trasero de la cola. ¿Cuál de las siguientes afirmaciones es correcta para la cola circular, de modo que las operaciones de inserción y eliminación se puedan realizar en O (1), es decir, en tiempo constante?

I. Next pointer of front node points to the rear node.
II. Next pointer of rear node points to the front node.

(A) Yo solo

(B) Solo II
(C) Tanto I como II
(D) Ni I ni II

Respuesta: (B)
Explicación: Dado que la cola circular elimina un elemento con el puntero frontal e inserta un elemento con el puntero trasero . Si queremos insertar un elemento en la cola circular, debemos incrementar el puntero trasero al siguiente Node y luego insertar el elemento. Luego, después de actualizar el siguiente puntero del Node Posterior al Node Frontal. Este método tendrá tiempo O(1) para Inserción y Eliminación.
Sólo la afirmación (ii) es verdadera. Entonces, la opción (B).
Cuestionario de esta pregunta