Examen Parcial - Teoría - Algoritmos y Estructuras de Datos UPC

Cual de las siguientes estructuras de datos tiene una Complejidad O(1), en sus operaciones principales para agregar y remover nodos:

• Arreglo

• Quick Sort

• Cola

• Función Recursiva

Answer explanation

En una cola tenemos mapeada el último y primer elemento. Pues en una cola real, se atiende al primero en llegar, y los nuevos en venir deben colocarse detrás del último. Este seguimiento nos permite realizar operaciones de inserción y eliminación en O(1).

Las Listas enlazadas:

• Pueden contener datos de cualquier tipo

• Siempre deben definirse como estructuras(struct, no como clases (class)

• Solo se puede implementar como clases (class)

• Deben tener un número constante y definido de elementos de datos

Answer explanation

Queremos que nuestras estructuras de datos alberguen cualquier tipo de dato, por eso las desarrollamos de manera genérica usando templates. Una lista es una estructura de datos dinámica, por lo que crece en tamaño. Sus nodos pueden crearse con clases o con struct.

Para invertir una cadena de caracteres, es mejor usar:

• Arreglo

• Pila

• Cola

• Vector

Answer explanation

Podríamos usar cualquiera de aquellas estructuras de datos para lograr con la tarea, pero una pila en específico permitiría poder invertir un string más fácilmente, pues los últimos elementos estarían en su tope entonces al quitarlos uno por uno imprimiéndolos estaríamos mostrando el arreglo de caracteres de manera inversa.

¿Cuál de las siguientes técnicas de diseño de algoritmos se utiliza en Merge Sort (ordenamiento Merge)?

• Divide y Vencerás

• Big-O

• Programación Dinamica

• PreOrden

Answer explanation

Merge sort es conocido por usar la técnica de Divide & Conquer (Divide y Vencerás) pues parte y parte un conjunto de elementos hasta llegar a los arreglos unitarios de este para empezar a ordenarlos.

¿Qué hace el Ordenamiento por Burbuja (Bubble Sort)?

• Ordena la lista eligiendo un elemento pivote (pivot)

• Encuentra un elemento de datos en una lista

• Ordena una lista comparando dos elementos que están uno al lado del otro, para ver cuál está desordenado

• Ninguna de las anteriores

Answer explanation

Bubblesort es conocido por hacer que sus elementos más grandes burbujeen hasta el final del arreglo. Esto se consigue comparando los elementos adyacentes (juntos) intercambiándose de ser el caso estén en el orden incorrecto.

El espacio adicional del ordenamiento por inserción (Insertion Sort) es O(1), ¿qué significa O(1)?

• Es la velocidad a la que se recorren los elementos.

• Significa que la cantidad de memoria adicional que consume la ordenación por inserción no depende de la entrada. El

  algoritmo debe usar la misma cantidad de memoria para todas las entradas.

• Se necesita sólo 1 KB de memoria.

• La memoria (espacio) requerida para procesar los datos no es constante

¿Cuál de los siguientes algoritmos de ordenamiento tiene la menor complejidad en el peor de los casos?

• Merge Sort

• Selection Sort

• Bubble Sort

• Quick Sort

En una Lista Simplemente Enlazada, la forma de acceder a sus elementos o nodos es:

• Secuencial

• Pública

• Aleatoria

• Privada

Answer explanation

El acceso a uno de los elementos de la lista es O(n)

Una lista de reproducción de música con botones de navegación para adelantar y retroceder las pistas musicales, puede ser diseñada y

manejada, usando:

• Lista Simplemente Enlazada

• Lista Circular Simplemente Enlazada

• Lista Doblemente Enlazada

• Pila

Explica qué significa LIFO para una pila y FIFO para una cola brevemente

(a)