Material de Estudios resumido para el examenVersión en línea
Materia: Algorítmica 2 y Lenguaje C++
1
1. El principio fundamental que rige el comportamiento de una estructura de cola
es:
2
2. La operación enqueue en una cola se utiliza para:
3
3. Desde el punto de vista de la eficiencia (complejidad temporal), ¿cuál es la
principal ventaja de implementar una cola con una lista enlazada?
4
4. Al implementar una cola con un arreglo simple (no circular), ¿cuál es una de
sus principales desventajas?
5
5. Si se desea consultar el valor del próximo elemento a ser procesado en una
cola, pero sin eliminarlo de la estructura, ¿qué operación se debe utilizar?
6
6. ¿Cuál de las siguientes es una desventaja de usar listas enlazadas para
implementar colas en comparación con los arreglos?
7
7. El algoritmo de búsqueda en grafos conocido como Búsqueda en Anchura
(BFS) utiliza fundamentalmente una estructura de datos para gestionar los
nodos a visitar. ¿Cuál es esa estructura?
8
8. Un sistema de impresión que gestiona múltiples trabajos enviados por
diferentes usuarios, imprimiéndolos en el orden en que llegaron, es un ejemplo
clásico de la aplicación de:
9
9. Dada una cola vacía, se realizan las siguientes operaciones en
orden: encolar(10), encolar(20), desencolar(), encolar(30). ¿Cuál será
el elemento en el frente de la cola?
10
10. ¿En cuál de los siguientes escenarios una cola NO sería la estructura de
datos más apropiada?
11
II. Preguntas del Tipo Falso o Verdadero
1. Para lograr que tanto encolar como desencolar en una cola con lista enlazada,
es indispensable mantener punteros tanto al frente como al final de la lista.
12
2. Una cola es la estructura de datos ideal para implementar la funcionalidad
"Navegar Atrás" en un navegador web, ya que guarda el historial de páginas en el
orden en que fueron visitadas.
13
3. Debido a que los nodos de una lista enlazada pueden estar dispersos en la
memoria, una implementación de cola basada en arreglos generalmente ofrece
un mejor rendimiento de caché.
14
4. La principal ventaja de usar listas enlazadas para una cola es que garantizan
que el programa nunca se quedará sin memoria, sin importar cuántos elementos
se encolen.
15
5. En una implementación de cola con listas enlazadas, la
operación desencolar es de mayor complejidad porque se debe recorrer la lista
para encontrar el segundo elemento y actualizar el puntero frente.
16
6. Una cola implementada con una lista enlazada que contiene N elementos de
tipo int ocupará exactamente el mismo espacio en memoria que un arreglo
de N enteros.
17
7. En una cola, el elemento que se encuentra en la posición final es siempre el que
lleva más tiempo dentro de la estructura.
18
8. Si una cola contiene los elementos [A, B, C] (con A al frente), y se realizan las
operaciones desencolar() y luego encolar(D), la cola resultante será [B, C, D].
19
III. Preguntas del Tipo Cita:
1. Operaciones esenciales de una Cola
20
2. Ventajas de usar listas enlazadas para colas
21
3. Desventajas de usar listas enlazadas para colas
22
4. Aplicaciones de Colas al mundo real:
Explicación
"LA RESPUESTA CORRECTA ES FALSO" Fundamentación: La funcionalidad "Navegar Atrás" requiere un comportamiento
LIFO (Last-In, First-Out), ya que se debe volver a la última página visitada. La
estructura de datos ideal para esto es una pila (Stack), no una cola (que es FIFO).
"LA RESPUESTA CORRECTA ES FALSO" Fundamentación: Aunque las listas enlazadas tienen tamaño dinámico, están
limitadas por la memoria total disponible en el sistema operativo. Si se intenta
encolar un elemento y no hay memoria para crear un nuevo nodo, el programa
fallará. La ventaja es la flexibilidad, no la memoria infinita.
"LA RESPUESTA CORRECTA ES FALSO" Fundamentación: La operación desencolar es de complejidad O(1). Gracias al
puntero frente, tenemos acceso directo al primer nodo. La operación solo implica
mover el puntero frente a frente->siguiente y liberar el nodo antiguo, acciones que
no dependen del tamaño de la cola.
"LA RESPUESTA CORRECTA ES FALSO" Fundamentación: La versión con lista enlazada ocupará más memoria. Cada
nodo de la lista no solo almacena el dato (int), sino también un puntero al
siguiente nodo. Este puntero adicional constituye una sobrecarga de memoria
(overhead) que no existe en la implementación con un arreglo simple.
"LA RESPUESTA CORRECTA ES FALSO" Fundamentación: El principio FIFO dicta que el elemento que lleva más tiempo
es el que está en el frente (front), listo para ser el próximo en salir. El elemento en
el final (rear) es, por definición, el que se ha añadido más recientemente.
SON CORRECTOS:
a) Encolar
b) Desencolar
c) Front
d) isEmpty (está vacía)
e) size Tamaño.
SON CORRECTOS:
a) Tamaño Dinámico
b) Operaciones encolar() y desencolar en tiempo constante
SON CORRECTOS:
a) Sobre carga de memoria
b) Localidad de Caché pobre
SON CORRECTO:
a) Sistemas Operativos
b) Redes de Computadoras
c) Algoritmos de búsquedas en Grafos
d) Sistemas de Impresión
e) Sistemas de mensajería asíncrona
|
este test esta basado en las diapositivas que pudimos ver con anterioridad, consta de 10 preguntas las cuales tienen alternativas para poder resolverlas.