Usted debe entregar los ejercicios impares.
1.- Un aficionado propone la siguiente función para clasificar triángulos según sus lados. La salida debe ser 1, 2, ó 3 dependiendo si el triángulo es equilátero, isósceles, o escaleno respectivamente.
int triangle (int a, int b, int b) {¿Es correcta la impementación?, Si no lo fuera, sugiera la corrección.
if (a==b) {
if (b==c)
return 1;
else
return 2;
}else if( b==c)
return 2;
else
return 3;
}
2.- Demuestre que si f(n) es O(g(n)), entonces f(n)+c es aún O(g(n)) para cualquier constante c. Obs: g(n) > 1 para todo n.
3.- Asuma que f1(n) < f2(n) para todo n mayor que no, y que f2(n) es O(g(n)). Demuestre que f1(n)+f2(n) es O(g(n)). Obs: g(n) > 1 para todo n.
4.- Ordene las siguientes funciones según su crecimiento asintólico. Use f(n) < g(n) si f(n) = o(g(n)); f(n) = g(n) si f(n) = Q (g(n)).
6.- ¿Cuántas hojas tiene un árbol binario lleno de n nodos?
7.- Muestre el contenido resultante luego de aplicar buildHeap a
|
|
|
|
|
|
|
|
|
|
|
8.- Resuelva la recurrencia: T(n) = T(n/2) + c*n en términos asintóticos.
9.- Codifique la rutina insertionSort(LIST L) donde L es una lista doblemente enlazada con centinela.
10.- considere la siguiente implementación de partition:
int partition (int a[], int p, int r ) {¿Cuál sería la correspondiente función para quicksort dada esta implementación de partition?
int i=p-1, j=r; int pivote =a[r], aux;
for (;;) {
while(a[++i] < pivote) ;
while( pivote < a[--j]) if (j==p) break;
if (i>=j) break;
aux=a[i];
a[i]=a[j];
a[j]=aux;
}
aux=a[i];
a[i]=a[r];
a[r]=aux;
return i;
}
¿Es este algoritmo estable?
11.- Considere que tiene una potencia de dos de datos. Muestre por qué el mejor caso para el problema de selección tiene costo de tiempo Q (n) y peor caso Q (n2).
12.- Haga la implementación de una cola usando la estructura de datos lista simplemente enlazada.