Certamen1 2008Paraestudiar
Páginas: 2 (257 palabras)
Publicado: 19 de marzo de 2015
Algoritmos y Estructuras de Datos (INF3101)
Alumno:
Certamen No. 1
1. (30 pts.) La función de Ackerman se define enforma recursiva para enteros no negativos de la siguiente manera :
A(m,n) =n+1, si m=0
A(m,n) = A(m-1,1) , si m 0, n=0
A(m,n)= A(m-1, A(m,n-1)) , si m 0, n0
a) Tiene caso base (si m=0)
b) Tiene caso general(si m es distinto de 0 y n=0; m esdistinto de 0 y n es distinto de 0)
c) Parámetro que se acerca al caso base
Implemente un subprograma recursivo en C con lafunción de Ackerman
Determine la salida para A(2,1)= ?
2. (30 pts.) Implemente en JAVA la solución para el siguienteproblema
Determinar si una cadena de caracteres es de la forma xCy donde x es una cadena que consta de las letras A y B y donde yes el inverso de x. Si x = ABABBA entonces y = ABBABA.
3. (20pts.) Implemente la función potencia iterativa. Indique elorden de complejidad del algoritmo.
Int potencia(int a,int b){
Int i ,pot=1;
For(i=0;i
}
Return(pot);
}Caso mejor: si b=1
O(1) es de orden 1
Caso peor: si b=n
O(n) es de orden n
4. (20 pts.) Compare la búsqueda secuencial, binariay hash desde el punto de vista de sus complejidades.
Hacer tabla comparando el mejor y peor caso entre las 3 busquedas
Algoritmos y Estructuras de Datos (INF3101)
Alumno:
Certamen No. 1
1. (30 pts.) La función de Ackerman se define enforma recursiva para enteros no negativos de la siguiente manera :
A(m,n) =n+1, si m=0
A(m,n) = A(m-1,1) , si m 0, n=0
A(m,n)= A(m-1, A(m,n-1)) , si m 0, n0
a) Tiene caso base (si m=0)
b) Tiene caso general(si m es distinto de 0 y n=0; m esdistinto de 0 y n es distinto de 0)
c) Parámetro que se acerca al caso base
Implemente un subprograma recursivo en C con lafunción de Ackerman
Determine la salida para A(2,1)= ?
2. (30 pts.) Implemente en JAVA la solución para el siguienteproblema
Determinar si una cadena de caracteres es de la forma xCy donde x es una cadena que consta de las letras A y B y donde yes el inverso de x. Si x = ABABBA entonces y = ABBABA.
3. (20pts.) Implemente la función potencia iterativa. Indique elorden de complejidad del algoritmo.
Int potencia(int a,int b){
Int i ,pot=1;
For(i=0;i
}
Return(pot);
}Caso mejor: si b=1
O(1) es de orden 1
Caso peor: si b=n
O(n) es de orden n
4. (20 pts.) Compare la búsqueda secuencial, binariay hash desde el punto de vista de sus complejidades.
Hacer tabla comparando el mejor y peor caso entre las 3 busquedas
Leer documento completo
Regístrate para leer el documento completo.