AAED PARTE 3

¿Qué es una cola?. Una estructura lineal donde las inserciones y extracciones se realizan por el mismo extremo. Una secuencia de elementos donde se inserta por un extremo y se extrae por el opuesto, siguiendo FIFO. Un conjunto de datos que permite acceso aleatorio a cualquier elemento almacenado. Una colección ordenada de elementos que permite eliminar cualquiera de ellos, independientemente de la posición que ocupen dentro de la estructura.

Ventajas e inconvenientes de una representación vectorial del TAD cola. Es flexible en tamaño, pero requiere gestión compleja de punteros. Tiene buena eficiencia espacial si el tamaño es estable, pero eliminar es costoso. Permite realizar operaciones en tiempo constante, pero requiere el uso de memoria adicional para almacenar punteros. Evita desplazamientos de elementos al eliminar desde el frente, aunque implica una mayor complejidad en la gestión de memoria.

Ventajas e inconvenientes de una representación circular del TAD cola. Simplifica la implementación pero aumenta el coste temporal de las operaciones. Permite crecimiento dinámico sin consumo adicional de memoria. Logra inserciones y extracciones O(1), pero complica la gestión de índices. Reduce el uso de memoria eliminando la necesidad de posiciones vacías.

Ventajas e inconvenientes de la representación con celdas enlazadas del TAD cola. Ofrece acceso aleatorio rápido, pero tiene tamaño fijo. Permite tamaño dinámico y operaciones O(1), con mayor uso de memoria. Reduce el consumo de memoria al eliminar el uso de punteros. Obliga a desplazar elementos para mantener el orden FIFO.

Ventajas e inconvenientes de la representación con celdas doblemente enlazadas del TAD cola. Permite recorrer la cola en ambos sentidos con menor coste temporal. Aumenta el consumo de memoria al usar dos punteros por nodo. Impide realizar inserciones y eliminaciones en tiempo constante. Reduce la complejidad de implementación respecto a listas simples.

Eres un diseñador del TAD Cola y un usuario te solicita una operación de acceso al n-ésimo elemento de la misma. ¿Incluirías esta operación en el TAD?. Sí, porque mejora la funcionalidad sin afectar al rendimiento. Sí, siempre que se use una implementación vectorial. No, porque el acceso aleatorio no pertenece al TAD Cola. No, salvo que se use una cola circular.

¿Por qué en la implementación vectorial circular de las colas, existe una posición que siempre está vacía?. Para simplificar las operaciones de inserción en el vector. Para evitar el desplazamiento de elementos al eliminar. Para distinguir de forma clara entre cola llena y cola vacía. Para mejorar el aprovechamiento de la memoria disponible.

La representación de una cola mediante estructuras enlazadas, ¿por qué se representa usando dos punteros a cada extremo de la misma?. Para permitir recorrer la cola en ambos sentidos. Para garantizar operaciones eficientes y simplificar la implementación. Para evitar el uso de listas circulares. Para reducir el número de nodos necesarios.

¿Para qué se utiliza el nodo cabecera en el TAD Cola, en su implementación de celdas enlazadas?. Para almacenar información adicional sobre el número de elementos. Para eliminar casos especiales y simplificar inserciones y borrados. Para permitir acceso directo al último elemento de la cola. Para reducir el número de punteros necesarios.

Con la implementación de colas mediante un vector circular de tamaño n, ¿cuántos elementos pueden almacenarse?. n elementos, utilizando todas las posiciones del vector. n−2 elementos, para evitar ambigüedad entre estados. n−1 elementos, reservando una posición para control. n/2 elementos para optimizar el acceso.

Con la representación de colas mediante una estructura enlazada, con puntero al final y circular, ¿cuántos elementos pueden almacenarse?. Un número fijo determinado en tiempo de compilación. Un máximo de n−1 elementos por razones de diseño. Tantos como permita la memoria disponible del sistema. Solo tantos como permita el tamaño del puntero.

Comente la siguiente afirmación: En la representación del TAD cola circular mediante una estructura de celdas enlazadas es necesario usar un nodo cabecera. Es cierta, ya que la circularidad lo exige. Es falsa, el nodo cabecera es solo una ayuda de diseño. Es cierta únicamente en colas dinámicas. Es falsa, debido a que las colas nunca pueden ser circulares.

¿En qué programas utilizarías el TAD Cola?. En aplicaciones donde se requiere acceso aleatorio a los datos. En programas que procesan elementos en orden inverso. En sistemas que gestionan elementos en el orden de llegada. En aplicaciones con estructuras jerárquicas complejas.

Dado un vector circular de tamaño N “hecho” de colas, ¿cuántos elementos puede almacenar?. N elementos, utilizando todas las posiciones del vector. N−1 elementos, reservando una posición de control. N/2 elementos para evitar colisiones. Un número ilimitado de elementos.