Taller P1_2018c2

Descargar como pdf o txt
Descargar como pdf o txt
Está en la página 1de 2

Taller Pre-Parcialito 1 [19/09] - Miércoles

1. Implementar en C el TDA ComposiciónFunciones que emula la composición de funciones (i.e. f(g(h(x))).


Se debe definir la estructura del TDA, y las siguientes primitivas:
• composicion_t* composicion_crear( );
• void composicion_destruir(composicion_t*);
• bool composicion_agregar_funcion(composicion_t, double ( f)(double));
• double composicion_aplicar(composicion_t*, double);
Considerar que primero se irán agregando las funciones como se leen, pero tener en cuenta el correcto orden
de aplicación. Por ejemplo: para emular f(g(x)), se debe hacer:
composicion_agregar_funcion(composicion, f) composicion_agregar_funcion(composicion, g)
composicion_aplicar(composicion, x)
Indicar el orden de las primitivas.
2. Dada una lista enlazada implementada con las siguientes estructuras:
typedef struct nodo_lista { typedef struct lista {
struct nodo_lista* prox; nodo_lista_t* prim;
void* dato; } lista_t;
} nodo_lista_t;
Escribir una primitiva que reciba una lista y devuelva el elemento que esté a k posiciones del final (el
ante-k-último), recorriendo la lista una sola vez y sin usar estructuras auxiliares. Considerar que
k es siempre menor al largo de la lista.
Por ejemplo, si se recibe la lista [ 1, 5, 10, 3, 6, 8 ], y k = 4, debe devolver 10.
Indicar el orden de complejidad de la primitiva.
3. Implementar una función en C que reciba un arreglo de n enteros sin repetir y ordenado ascendentemente,
y determine en O(logn) si es mágico. Un arreglo es mágico si existe algún valor i (entre 0 y n - 1) tal que
arr[i] = i.
Ejemplos:
• A = [ -3, 0, 1, 3, 7, 9 ] es mágico porque A[3] = 3.
• B = [ 1, 2, 4, 6, 7, 9 ] no es mágico porque B[i] != i para todo i.
Justificar el orden del algoritmo.
4. Dada una pila de enteros, escribir una función que determine si es piramidal. Una pila de enteros es
piramidal si cada elemento es menor a su elemento inferior (en el sentido que va desde el tope de la pila hacia
el otro extremo). La pila no debe ser modificada al terminar la función.
Indicar el orden del algoritmo propuesto.
5. Implementar la primitiva void** cola_multiprimeros(const cola_t* cola, size_t k) que dada
una cola y un número k, devuelva los primeros k elementos de la cola, en el mismo orden en el que habrían
salido de la cola. En caso que la cola tenga menos de k elementos, rellenar con NULL.
La cola debe quedar en el mismo estado que al invocarse la primitiva.
Indicar el orden de ejecución del algoritmo. Justificar.
B. Implementar la función void** cola_multiprimeros(cola_t* cola, size_t k) con el mismo com-
portamiento de la primitiva anterior.
6. El StoogeSort es un algoritmo de ordenamiento basado en Los Tres Chiflados que aplica el siguiente
procedimiento:

1
1. Si el primer elemento es más grande que el último, los intercambia.
2. Si la cantidad de elementos del vector es mayor o igual a 3:
• Llama a StoogeSort recursivamente con los primeros dos tercios del vector (desde 0 hasta 2/3 *
cantidad)
• Llama a StoogeSort recursivamente con los segundos dos tercios (desde 1/3 * cantidad, hasta
cantidad - 1)
• Vuelve a llamar recursivamente a StoogeSort con los primeros dos tercios del vector.
Utilizando el teorema del maestro, calcular el orden del algoritmo, suponiendo que la operación de dividir es
de tiempo constante.

También podría gustarte