Análisis de Algoritmos

Control 1. Estructuras de Datos

Natalia Patricia Moreno Sepúlveda

Análisis de Algoritmos

Instituto IACC

10-05-2020

Desarrollo

1. De acuerdo a lo visto en los contenidos de la semana y al hecho de que las estructuras de datos pueden ser implementadas utilizando otras estructuras de datos, ¿cómo sería una estrategia para contar los elementos existentes en una pila? (Es decir, ¿cómo sería una forma eficiente de construir la función Count?).

Respuesta:

De acuerdo al material de la semana, una pila es un conjunto de nodos almacenados de forma dinámica, donde cada elemento del nodo contiene la información y un puntero al siguiente elemento por lo cual es posible implementarla mediante una lista enlazada que es otro tipo de estructura de datos y con lo cual se cumple la primera premisa de la pregunta.

Ahora una estrategia para contar (función Count) los elementos existentes de una pila, sería primero implementarla como lista enlazada, a partir de la definición del puntero el cual será la cima de la pila.

Es importante tener en cuenta que se debe verificar primero que la pila no esté vacía antes de hacer el conteo. Esto se realiza con la operación IsEmpty que retornará True si la lista esta vacía y False si la lista no está vacía

1. La empresa ferroviaria ABC-Ferrocarriles está en proceso de remodelación de algunos de sus terminales de trenes y necesita mover un tren completo (locomotora y 4 vagones) desde el terminal A al terminal C, como muestra la figura. La dificultad en esta operación es que el tren debe quedar en el terminal C en el mismo orden del que salió del terminal A, frente a esta situación se le ha pedido a Ud. que ayude con una estrategia para cumplir con el objetivo. Entonces, ¿qué tipo de estructura de datos utilizaría para resolver el problema?

Respuesta:

Primero definiría al tren como una estructura de datos de tipo Pila, siendo la locomotora la cima y el resto de los vagones, los siguientes nodos.

Luego, con el procedimiento Pop o Sacar comenzaría a sacar los elementos de la Pila del terminal A (o sea saldría primero la locomotora que es la cima de esa pila) para pasarlos al terminal B (el cual declararía como una nueva pila) con el procedimiento Push o Insertar, en donde quedarían en el siguiente orden: Locomotora – vagon1 – vagon2 – vagon3 – vagon4.

Finalmente, generaría una nueva pila en el terminal 3 y mediante el procedimiento descrito anteriormente traspasaría los nodos quedando entonces en el mismo orden que se encontraba en la pila del terminal A

Bibliografía

Material de estudio semana 1. Tema 3. Estructuras lineales de datos: listas, pilas, colas

[pic 1]

...