Test sobre Ordenamiento por mezcla (merge sort)

Pregunta 1: Durante la fase de 'Vencer' en el algoritmo Merge Sort, se aplican algoritmos de ordenamiento adicionales para resolver los subproblemas más pequeños, ya que estos no se consideran ordenados por defecto.

A. Sí

B. No

Explicación: Según el material de estudio, en el contexto de Merge Sort, el paso de 'Vencer' es trivial. Esto se debe a que las sublistas ya se han dividido hasta su mínima expresión (listas de un solo elemento), las cuales se consideran ordenadas por definición y no requieren la aplicación de algoritmos de ordenamiento adicionales.

Pregunta 2: ¿Cuál es la razón fundamental por la que la complejidad temporal del algoritmo de Ordenamiento por Mezcla (Merge Sort) es O(n log n)?

A. Las divisiones recursivas de la lista hasta elementos individuales contribuyen con un factor de 'n' y las fusiones contribuyen con 'log n'.

B. El proceso de división de la lista genera un factor de 'log n' y cada nivel de fusión procesa todos los 'n' elementos.

C. Se realizan 'n' comparaciones en la fase de división y 'log n' operaciones en la fase de fusión.

D. La complejidad O(n log n) es una característica inherente a todos los algoritmos de ordenamiento basados en comparaciones.

Explicación: La complejidad temporal O(n log n) del Merge Sort se deriva de dos aspectos clave de su funcionamiento. El proceso de división recursiva reduce la lista a la mitad en cada paso, lo que resulta en 'log n' niveles de división. En cada uno de estos niveles de fusión, se procesan y combinan todos los 'n' elementos del arreglo, lo que contribuye con un costo de 'n' por nivel. Multiplicando los niveles por el costo por nivel, se obtiene O(n log n).

Pregunta 3: Un manejo impreciso de los índices `inicio`, `medio` y `fin` en el algoritmo Merge Sort no afecta la capacidad de procesar todas las sublistas por completo, solo su rendimiento.

A. Sí

B. No

Explicación: El material de estudio indica explícitamente que los índices `inicio`, `medio` y `fin` deben manejarse con precisión para asegurar que todas las sublistas se procesen correctamente y que no haya desbordamientos o accesos fuera de los límites del arreglo. Un manejo impreciso, por lo tanto, sí afectaría la capacidad de procesar todas las sublistas correctamente, no solo el rendimiento.

Pregunta 4: Merge Sort es un algoritmo que puede implementarse eficientemente con listas enlazadas sin necesidad de acceso aleatorio a los elementos.

A. Sí

B. No

Explicación: El Merge Sort es adecuado para listas enlazadas, ya que puede implementarse de manera eficiente con ellas sin requerir acceso aleatorio a los elementos, a diferencia de otros algoritmos.

Pregunta 5: ¿Cuál es una de las ventajas clave de Merge Sort relacionada con su capacidad de ser paralelizado, según los materiales de estudio?

A. Reduce la necesidad de espacio auxiliar O(n) cuando se ejecuta en paralelo.

B. Permite aprovechar múltiples núcleos de procesador para acelerar el ordenamiento de grandes conjuntos de datos.

C. Transforma el algoritmo en uno de tipo in-situ, eliminando copias de elementos.

D. Simplifica la fase de división, haciéndola irrelevante para el rendimiento en sistemas multiprocesador.

Explicación: Según los materiales de estudio, una de las ventajas de Merge Sort es que es 'relativamente fácil de paralelizar, lo que permite aprovechar múltiples núcleos de procesador para acelerar el ordenamiento de grandes conjuntos de datos'. Las otras opciones no se mencionan como ventajas de la paralelización de Merge Sort.