Algoritmos de Ordenación en Pseudocódigo
Nombre: ___________________________
Fecha: ____________________________
Puntaje: __________________________
1.
Observa el siguiente pseudocodigo:
para i desde 0 hasta n-2:
si a[i] > a[i+1] entonces
intercambia a[i] y a[i+1]
Fin para
¿A que algoritmo de ordenacion corresponde?
Burbuja
Seleccion
Insercion
Mezcla
Burbuja
2.
¿Cual es la complejidad temporal en el peor caso del ordenamiento burbuja?
O(n)
O(n log n)
O(n^2)
O(n^2)
3.
En el ordenamiento por seleccion, en cada paso se busca el ______ del subarreglo no ordenado.
Respuesta: ____________________________________________
minimo
4.
En el ordenamiento por insercion, ¿como se inserta cada nuevo elemento?
Buscando su posicion correcta dentro de la sublista ordenada
Intercambiandolo repetidamente con el adyacente
Seleccionando el minimo del resto
Usando recursion
Buscando su posicion correcta dentro de la sublista ordenada
5.
¿Cual de los siguientes algoritmos NO es estable?
Burbuja
Seleccion
Insercion
Seleccion
6.
En el pseudocodigo del ordenamiento burbuja optimizado, la variable 'intercambio' se utiliza para indicar si ______.
Respuesta: ____________________________________________
se realizo un intercambio
7.
Para una lista de 10 elementos, ¿cuantas comparaciones realiza el ordenamiento burbuja en el peor caso?
45
90
100
10
45
8.
¿En que situacion el ordenamiento por insercion es mas eficiente que burbuja?
Cuando la lista esta casi ordenada
Cuando la lista esta invertida
Cuando la lista tiene muchos elementos
Cuando la lista esta casi ordenada
9.
La complejidad temporal del ordenamiento por seleccion en todos los casos es O(______).
Respuesta: ____________________________________________
n^2
10.
¿Que algoritmo ordena buscando el minimo y colocandolo al inicio?
Burbuja
Seleccion
Insercion
Quicksort
Seleccion
11.
¿Cual de las siguientes afirmaciones diferencia correctamente al ordenamiento por insercion del de seleccion?
Insercion siempre intercambia elementos adyacentes
Seleccion ordena mediante intercambios de elementos adyacentes
Insercion mantiene una sublista ordenada e inserta el siguiente elemento en su lugar correcto
Insercion mantiene una sublista ordenada e inserta el siguiente elemento en su lugar correcto
12.
Un algoritmo de ordenacion se dice estable si preserva el orden relativo de elementos con ______.
Respuesta: ____________________________________________
valores iguales
13.
¿En que condicion el ordenamiento burbuja puede terminar antes de recorrer toda la lista?
Si no se realizan intercambios en una pasada
Si la lista esta invertida
Si se usa una bandera
Siempre termina en n-1 pasadas
Si no se realizan intercambios en una pasada
14.
La complejidad en el mejor caso del ordenamiento por insercion es:
O(n)
O(n^2)
O(n log n)
O(n)
15.
El ordenamiento por seleccion requiere exactamente ______ intercambios para ordenar una lista de n elementos.
Respuesta: ____________________________________________
n-1
16.
Respecto al ordenamiento por insercion, ¿cual afirmacion es verdadera?
En el mejor caso realiza n-1 comparaciones
En el mejor caso realiza n(n-1)/2 comparaciones
Intercambia elementos adyacentes en cada paso
Siempre requiere el mismo numero de intercambios
En el mejor caso realiza n-1 comparaciones
17.
¿Que algoritmo de ordenacion se basa en la estrategia 'divide y venceras'?
Burbuja
Insercion
Mezcla
Mezcla
18.
En el pseudocodigo del ordenamiento por seleccion, la variable 'minimo' almacena el indice del elemento ______ del subarreglo.
Respuesta: ____________________________________________
menor
19.
Si una lista ya esta ordenada ascendentemente, ¿que algoritmo realiza exactamente n-1 intercambios?
Burbuja
Seleccion
Insercion
Mezcla
Seleccion
20.
Examina estos fragmentos de pseudocodigo y senala cual corresponde al ordenamiento por insercion:
A: para i desde 0 hasta n-2: si a[i] > a[i+1] entonces intercambia a[i] y a[i+1]
B: para i desde 0 hasta n-2: minimo = i; para j desde i+1 hasta n-1: si a[j] < a[minimo] entonces minimo = j; intercambia a[i] y a[minimo]
C: para i desde 1 hasta n-1: clave = a[i]; j = i-1; mientras j >= 0 y a[j] > clave: a[j+1] = a[j]; j = j-1; a[j+1] = clave
Fragmento A
Fragmento B
Fragmento C
Fragmento C
Respuestas
-
A.
Burbuja
-
C.
O(n^2)
-
minimo
-
A.
Buscando su posicion correcta dentro de la sublista ordenada
-
B.
Seleccion
-
se realizo un intercambio
-
A.
45
-
A.
Cuando la lista esta casi ordenada
-
n^2
-
B.
Seleccion
-
C.
Insercion mantiene una sublista ordenada e inserta el siguiente elemento en su lugar correcto
-
valores iguales
-
A.
Si no se realizan intercambios en una pasada
-
A.
O(n)
-
n-1
-
A.
En el mejor caso realiza n-1 comparaciones
-
C.
Mezcla
-
menor
-
B.
Seleccion
-
C.
Fragmento C