PUERTA | PUERTA CS 1996 | Pregunta 12

Considere las siguientes declaraciones:

i.   First-in-first out types of computations are efficiently supported by STACKS.
ii.  Implementing LISTS on linked lists is more efficient than implementing LISTS on
     an array for almost all the basic LIST operations.
iii. Implementing QUEUES on a circular array is more efficient than implementing QUEUES
     on a linear array with two indices.
iv.  Last-in-first-out type of computations are efficiently supported by QUEUES.

¿Cual de los siguientes es correcto?

(A) (ii) y (iii) son verdaderas
(B) (i) y (ii) son verdaderas
(C) (iii) y (iv) son verdaderas
(D) (ii) y (iv) son verdaderas

Respuesta: (A)
Explicación: i -STACK es la estructura de datos que sigue el orden Último en entrar, primero en salir (LIFO) o Primero en entrar, último en salir (FILO), en el que el último elemento que se inserta se elimina primero.

ii – Implementar LISTAS en listas enlazadas es más eficiente que implementarlo en una array para casi todas las operaciones básicas de LISTA porque la inserción y eliminación de elementos se puede hacer en O(1) en Lista enlazada pero lleva O(N) tiempo en arrays.

iii- Implementar QUEUES en una array circular es más eficiente que implementarlo en una array lineal con dos índices porque al usar arrays circulares, ocupa menos espacio y puede reutilizarlo nuevamente.

iv – COLA es la estructura de datos que sigue el orden Primero en entrar, primero en salir (FIFO) o Último en entrar, Último en salir (LILO), en el que el elemento que se inserta primero se elimina primero.

solo (ii) y (iii) son VERDADEROS.
La opción (A) es correcta.
Cuestionario de esta pregunta