PUERTA | PUERTA CS 1997 | Pregunta 62

Considere el siguiente fragmento de código ‘C’ que elimina los duplicados de una lista ordenada de enteros.

Node  *remove-duplicates(Node *head, int *j)
{
    Node *t1, *t2;
    *j=0;
    t1 = head;
    if (t1! = NULL) t2 = t1 →next;
    else return head;
    *j = 1;
    if(t2 == NULL)
        return head;
    while t2 != NULL)
    {
        if (t1.val != t2.val) --------------------------→ (S1)
        {
            (*j)++; t1 -> next = t2; t1 = t2: ----------→ (S2)
        }
        t2 = t2 →next;
    }
    t1 →next = NULL;
    return head;
}

Suponga que la lista contiene n elementos (n≥2) en las siguientes preguntas.
a). ¿Cuántas veces se hace la comparación en el enunciado S1 ?
b). ¿Cuál es el número mínimo y máximo de veces que se ejecutan las sentencias marcadas S2 ?
C). ¿Cuál es el significado del valor en el número entero señalado por j cuando la función se completa?

Respuesta:
Explicación:

• (a). n-1 veces, ya que la comparación es por pares para n elementos.
• (b). máximo: n-1 para todos los elementos distintos, mínimo: 0 para todos los mismos elementos.
• (C). j lleva la cuenta de los distintos Nodes en la lista.

Cuestionario de esta pregunta