---

Estructuras de Datos y Algoritmos – enunciados + soluciones completas

Cómo sacarle partido

1. Despliega sólo los enunciados (oculta las soluciones con el bloque spoiler de WordPress).
2. Márcate 2 h 30 min de reloj y resuélvelo a mano.
3. Abre cada spoiler y corrige con la clave oficial.
4. Repite hasta que obtengas ≥ 8 / 10 sin mirar ayuda.

---

1️⃣ Enunciados

Implementa la clase stack_2queue_t<T> que simule una pila LIFO usando exclusivamente dos colas queue_l_t<T>:

template <typename T>
class stack_2queue_t {
public:
    void push(const T& x);   // O(1)
    void pop();              // O(n)
    const T& top() const;
    bool empty() const;
private:
    queue_l_t<T> q1_, q2_;
};

---

Convierte una expresión infija que puede incluir ( ) a notación postfija usando el algoritmo shunting-yard.

queue_l_t<char> infixToPostfix(const vector_t<char>& expr);

Ejemplo de entrada:

( 8 + 2 ) * 3 - 4 / 2

Salida esperada:

8 2 + 3 * 4 2 / -

---

Ordena el vector en orden ascendente in-place:

void quicksort(vector_t<int>& v, int l, int r);

La llamada inicial será quicksort(v, 0, v.get_size()-1);. Complejidad esperada O(n log n) promedio.

---

Crea una clase plantilla que represente un polinomio:

template<typename T>
class polynomial_t {
public:
    explicit polynomial_t(const vector_t<T>& coeffs);   // coeffs[i] = a_i
    T eval(T x) const;            // Horner
    polynomial_t<T> deriv() const; // derivada
private:
    vector_t<T> c_;
};

• Debe funcionar con int, float, double.
• eval en O(n).
• La derivada de ∑ aᵢ xᶦ es ∑ i·aᵢ x⁽ⁱ⁻¹⁾.

---

Dado un grafo no dirigido representado por lista de adyacencia:

using graph_t = vector_t< vector_t<int> >;  // g[u] = vecinos de u

Implementa una función que:

1. Recorra el grafo con BFS desde un vértice s.
2. Devuelva true si encuentra un ciclo, false si es acíclico.

bool bfs_cycle(const graph_t& g, int s);

Complejidad O(V + E).

---

2️⃣ Soluciones oficiales

📌 Consejo WordPress: rodea cada bloque de código con la etiqueta <pre><code class="language-cpp"> … </code></pre> para resaltado sintáctico.

---

Ejercicio 1 – stack_2queue_t

Costes: push O(1), pop/top O(n).

---

Ejercicio 2 – Infix → Postfix con ( )

---

Ejercicio 3 – Quicksort

Promedio: O(n log n), peor caso O(n²) si el pivote es muy desbalanceado (solución aceptada en exámenes).

---

Ejercicio 4 – polynomial_t

Prueba:

---

Ejercicio 5 – BFS y ciclo

---

3️⃣ Minitests de autocorrección

int main()
{
    // Quick check stack_2queue
    stack_2queue_t<int> st;
    for(int k:{1,2,3}) st.push(k);
    st.pop();              // elimina 3
    assert(st.top()==2);

    // quicksort
    vector_t<int> v({5,2,4,1,3});
    quicksort(v,0,v.get_size()-1);
    for(int i=0;i<5;++i) assert(v[i]==i+1);

    // polynomial
    vector_t<int> c({0,0,1});             // x²
    polynomial_t<int> P(c);
    assert(P.eval(3)==9 && P.deriv().eval(3)==6);

    std::cout<<"✓ Todo OK\n";
}

---

4️⃣ Cierre y próximos pasos

• Repite el simulacro con límite de tiempo real.
• Cambia tipos (float, double) y tamaños para probar casos borde.
• Pásale valgrind o g++ -fsanitize=address si trabajas con memoria dinámica.

---

¡Listo! Ya tienes otro examen completo, con soluciones listas para tu blog.
¿Te ha sido útil? — Compártelo o deja tu duda en comentarios. 🚀