Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 2 vistas

    Taller P1_2019c2

    Cargado por

    Martin Regini
    Lenguaje Python

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd

    Taller P1_2019c2

    Cargado por

    Martin Regini
    2 vistas2 páginas
    Lenguaje Python

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Lenguaje Python

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    2 vistas2 páginas

    Taller P1_2019c2

    Cargado por

    Martin Regini
    Lenguaje Python

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    Está en la página 1de 2

    Taller Pre-Parcialito 1 [18/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 siguientesprimitivas:

    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 enterossin repetir y ordenados 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 quearr[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 unafunció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


    comportamiento de la primitiva anterior.

    6. Implementar en C una función que dado un número, encuentre porDivisión y Conquista la parte entera de
    su raíz cuadrada, en tiempo O(logn). Demostrar, utilizando el Teorema Maestro, el orden de dicho algoritmo.
    Ejemplos: - raiz(10) ---> 3 - raiz(11) ---> 3 - raiz(25) ---> 5

    7. Implementar en C una primitiva void lista_invertir(lista_t* lista) que invierta la lista recibida
    por parámetro. Indicar y justificar el orden de la primitiva.

    También podría gustarte