Taller estructura de datos

PRESENTADO POR JUAN CARLOS PEREZ MORA

Taller estructura de datos.
Cada punto tiene un valor de 100 puntos.
Entregar

del taller máximo el 3 de abril de 2015.

1. Escribir un programa que compare dos vectores y diga si son iguales o no.
2. Escribir un programa que ordene un vector de 10 posiciones con el método de
ordenamiento de la burbuja.

3. Explicar detalladamente el método de seleccióndirecta utilizando para ello el
siguiente arreglo inicial.
20

96

08

44

70

46

14

57

4. Explicar la organización de árboles de búsqueda óptimos ilustrándolo mediante un
ejemplo.
5. Se tiene una lista enlazada que almacena números enteros. Realizar un
procedimiento que suprima de la lista todos los elementos mayores que uno dado
como límite. Por
Ejemplo, si la lista inicial es

PRESENTADO PORJUAN CARLOS PEREZ MORA

DESARROLLO

1)

R/TA

#include
int l[100],v2[100];
int a,b=0,c=0,d=0,tamanio1,tamanio2;
void main()
{
cout<<"ingrese el tamaño para el primer vector"< cin>>tamanio1;
cout<<"ingrese el tamanio para el segundo vector"< cin>>tamanio2;
cout<<"ingrese los elementos del primer vector"< for(a=0;a cout<<"ingrese elemento de la posición["< cin>>l[a];
}
cout< for(a=0;a cout<<"ingrese elemento de la posición ["< cin>>v2[a];
}
//pienso que lo primero seria ver si los vectores tienen el mismo tamaño
//o mejor dicho la misma cantidad de elementos
for(a=0;l[a];a++){
c++;//contador de elementos del vector l
}
for(a=0;v2[a];a++){
d++;//contador deelementos del vector v2
}
if(c==d){//si tienen la misma cantidad de elementos entonces
for(a=0;a<4;a++){
if(l[a]==v2[a]){
b++;//contador de cantidad de elementos iguales
}
}
}
if(b==4)
cout< else

PRESENTADO POR JUAN CARLOS PEREZ MORA
cout<
2) R/TA
#include
using namespace std;
int numeros[10];
void burbuja (intordenacion);

int main () {
cout << \"Introduzca 10 enteros... \" << endl;
for (int i=0; i<10; i++) {
cout << \"Introduzca el número para la posición \" << i << \": \";
cin >> numeros[i];
}
for (int i=0; i<10; i++)
cout << numeros[i] << \" \";
cout << endl;
burbuja(0);
for (int i=0; i<10; i++)
cout << numeros[i] << \" \";
cout << endl;
burbuja(1);
for (int i=0; i<10; i++)
cout << numeros[i] << \"\";
cout << endl;

PRESENTADO POR JUAN CARLOS PEREZ MORA

3)RTA
20

96

08

44

70

46

14

57

Primera pasada
A[2] < A[1] 96 < 20 No hay intercambio
A: 20, 96, 08, 44, 70, 46, 14, 57
Segunda pasada
A[3] < A[2] 08 < 96 Si hay intercambio
A[2] < A[1] 08 < 20 Si hay
A: 20, 08, 96, 44, 44, 46, 14, 57
Tercera pasada
A[4] < A[3] 08 < 20 Si hay intercambio
A[3] < A[2] 08 < 20 Si hay intercambio
A= 08,20, 96, 44, 70, 46, 14, 57

Hasta la septima pasada el arreglo queda ordenado: 08, 14, 20, 44, 46, 57, 70, 96
En general, si el arreglo se encuentra ordenado se efectúan como máximo n-1 comparaciones y o movimientos entre
elementos Cmin = n-1.
El número máximo de comparaciones y movimientos se produce cuando los elementos del arreglo están en orden
inverso
Cmax = 1+2+3+............+(n-1) =n*(n-1)/2
Cmax= (n2-n)/2
El número de comparaciones promedio que es cuando los elementos aparecen en el arreglo en forma aleatoria, puede
ser calculado mediante la suma de las comparaciones mínimas y máximas divididas entre 2.
Cmed = [(n-1) + (n2-n)/2]/2
Al hacer la operación, nos queda:
Cmed = (n2+n-2)/4
Respecto al número de movimientos, según Knuth obtiene los siguiente:
Mmin = 0
Mmed = (n2-n)/4PRESENTADO POR JUAN CARLOS PEREZ MORA
Mmax = (n2-n)/2

4) R/TA

considérese el conjunto de claves 1, 2, 3, con probabilidades de acceso p1=1/7, p2=2/7 y p3=4/7.
Estas claves pueden organizarse como árboles de búsqueda de 5 maneras diferentes
(como esta en la ilustración). Las longitudes de camino ponderadas, establecidas como la suma
de todos los pasos de la raíz a cada nodo multiplicados por la...

Leer documento completo

Regístrate para leer el documento completo.