Quiz de practica — Parcial 2

a) Respuesta: 3 — $O(n)$

buildHeap con sift-down es $O(n)$, NO $O(n \log n)$. La intuicion es que la mayoria de nodos estan cerca del fondo del arbol y hacen poco trabajo. Formalmente, la suma $\sum_{k=0}^{\log n} \frac{n}{2^{k+1}} \cdot k$ converge a $O(n)$ por serie geometrica.

b) Respuesta: 3 — Insertion sort

Insertion sort tiene mejor caso $O(n)$ cuando el arreglo ya esta ordenado (solo hace $n-1$ comparaciones, cero swaps). Selection sort siempre es $O(n^2)$ porque busca el minimo en toda la parte no ordenada. Merge sort siempre es $O(n \log n)$. Heap sort siempre es $O(n \log n)$.

c) Respuesta: 4 — Bubble sort es estable

• Quick sort tiene peor caso $O(n^2)$ (datos ya ordenados con mal pivote) — falso.
• Merge sort usa $O(n)$ de memoria extra — falso.
• Heap sort no es estable (percolateDown salta niveles) — falso.
• Bubble sort solo hace swaps adyacentes y nunca cruza elementos iguales — verdadero.

a) Construccion paso a paso:

Insert 35:       35

Insert 20:       35
                /
              20

Insert 45:       35
                / \
              20   45

Insert 10:       35
                / \
              20   45
             /
           10

Insert 25:       35
                / \
              20   45
             / \
           10   25

Insert 40:       35
                / \
              20   45
             / \  /
           10  25 40

Insert 55:       35
                / \
              20   45
             / \  / \
           10  25 40  55

Insert 5:       35
               / \
             20   45
            / \  / \
          10  25 40  55
         /
        5

Insert 30:       35
                / \
              20   45
             / \  / \
           10  25 40  55
          /     \
         5      30

Arbol final:

              35
            /    \
          20      45
         / \     /  \
       10   25  40   55
      /      \
     5       30

b) Inorden (LNR): 5, 10, 20, 25, 30, 35, 40, 45, 55

(Verificacion: el recorrido inorden de un BST siempre da los datos en orden ascendente.)

c) Preorden (NLR): 35, 20, 10, 5, 25, 30, 45, 40, 55

Construccion paso a paso:

Insert 50:    50 (BF=0)

Insert 30:    50 (BF=+1)
             /
           30 (BF=0)

Insert 70:    50 (BF=0)
             / \
           30   70

Insert 20:    50 (BF=+1)
             / \
           30   70
          /
        20

Insert 40:    50 (BF=+1)
             / \
           30   70
          / \
        20   40

Hasta aqui todo esta balanceado. Todos los BF estan en 1.

Insert 10:    50 (BF=+2)  ← ¡DESBALANCEADO!
             / \
           30   70 (BF=0)
          / \
        20   40
       /
     10

a) El desbalanceo ocurre al insertar 10. El nodo 50 tiene $BF = h(izq) - h(der) = 3 - 1 = +2$.

b) Caso LL: $BF(50) = +2$ y $BF(30) = +1 \geq 0$. Como ambos desbalanceos van hacia la izquierda (misma direccion), es rotacion simple.

Rotacion: simple derecha en el nodo 50.

c) Antes de la rotacion:

         50
        / \
      30   70
     / \
   20   40
  /
10

Despues de la rotacion simple derecha en 50:

         30
        /  \
      20    50
     /     / \
   10    40   70

d) Factores de balance del arbol final:

         30 (BF=0)
        /  \
  20 (BF=+1)  50 (BF=0)
     /        / \
 10 (BF=0) 40(BF=0) 70(BF=0)

• Nodo 30: $h(izq)=2, h(der)=2 \Rightarrow BF=0$
• Nodo 20: $h(izq)=1, h(der)=0 \Rightarrow BF=+1$
• Nodo 50: $h(izq)=1, h(der)=1 \Rightarrow BF=0$
• Nodos 10, 40, 70: hojas, $BF=0$

Todos los BF estan en $\{-1, 0, +1\}$ — el arbol esta balanceado.

a) Inserciones paso a paso:

Tabla final:

Indice:  [0]  [1]  [2]  [3]  [4]  [5]  [6]  [7]  [8]  [9]  [10]
Valor:    22    1   13   11   24   33   46    -    -    -     -

Notar el clustering primario: las posiciones 0-6 forman un bloque contiguo.

b) Buscar 46: $h(46) = 2$. Sondear posiciones: 2 (13 $\neq$ 46), 3 (11 $\neq$ 46), 4 (24 $\neq$ 46), 5 (33 $\neq$ 46), 6 (46 = 46). 5 sondeos.

c) Buscar 35: $h(35) = 2$. Sondear posiciones: 2 (13 $\neq$ 35), 3 (11 $\neq$ 35), 4 (24 $\neq$ 35), 5 (33 $\neq$ 35), 6 (46 $\neq$ 35), 7 (vacio $\Rightarrow$ no existe). 6 sondeos (se detiene al encontrar un slot vacio).

Fase de division (top-down):

                [42, 15, 63, 8, 31, 27, 50]
                /                           \
       [42, 15, 63]                    [8, 31, 27, 50]
        /        \                      /            \
   [42, 15]     [63]              [8, 31]        [27, 50]
    /     \                        /    \          /     \
  [42]   [15]                    [8]   [31]      [27]   [50]

Fase de merge (bottom-up):

Nivel 1 — merge de pares individuales:

• $[42] + [15]$: comparar $42$ vs $15 \Rightarrow$ tomar $15$, luego $42$. Resultado: $[15, 42]$
• $[63]$ queda solo: $[63]$
• $[8] + [31]$: comparar $8$ vs $31 \Rightarrow$ tomar $8$, luego $31$. Resultado: $[8, 31]$
• $[27] + [50]$: comparar $27$ vs $50 \Rightarrow$ tomar $27$, luego $50$. Resultado: $[27, 50]$

Nivel 2 — merge de sublistas:

• $[15, 42] + [63]$: comparar $15$ vs $63 \Rightarrow 15$; comparar $42$ vs $63 \Rightarrow 42$; copiar $63$. Resultado: $[15, 42, 63]$
• $[8, 31] + [27, 50]$: comparar $8$ vs $27 \Rightarrow 8$; comparar $31$ vs $27 \Rightarrow 27$; comparar $31$ vs $50 \Rightarrow 31$; copiar $50$. Resultado: $[8, 27, 31, 50]$

Nivel 3 — merge final:

$[15, 42, 63] + [8, 27, 31, 50]$:

Arreglo final: $[8, 15, 27, 31, 42, 50, 63]$

Complejidad: $O(n \log n)$. Se necesitan $\lceil \log_2 7 \rceil = 3$ niveles de merge, y cada nivel procesa $n = 7$ elementos. Espacio extra: $O(n)$.

Recordar: en un max-heap, el padre siempre es $\geq$ que sus hijos. Al insertar, se coloca al final y se hace percolate up.

Insert 15:

arr = [15]

  15

No hay padre. Fin.

Insert 40:

arr = [15, 40]  →  40 > 15 (padre) → swap  →  arr = [40, 15]

  40
 /
15

Insert 30:

arr = [40, 15, 30]  →  30 < 40 (padre) → stop

    40
   /  \
 15    30

Insert 50:

arr = [40, 15, 30, 50]
50 en indice 3, padre = indice 1 (valor 15). 50 > 15 → swap → arr = [40, 50, 30, 15]
50 en indice 1, padre = indice 0 (valor 40). 50 > 40 → swap → arr = [50, 40, 30, 15]

    50
   /  \
 40    30
/
15

Insert 10:

arr = [50, 40, 30, 15, 10]
10 en indice 4, padre = indice 1 (valor 40). 10 < 40 → stop

      50
     /  \
   40    30
  / \
15   10

Insert 45:

arr = [50, 40, 30, 15, 10, 45]
45 en indice 5, padre = indice 2 (valor 30). 45 > 30 → swap → arr = [50, 40, 45, 15, 10, 30]
45 en indice 2, padre = indice 0 (valor 50). 45 < 50 → stop

      50
     /  \
   40    45
  / \   /
15  10  30

Insert 20:

arr = [50, 40, 45, 15, 10, 30, 20]
20 en indice 6, padre = indice 2 (valor 45). 20 < 45 → stop

       50
      /  \
    40    45
   / \   / \
 15  10 30  20

Arreglo final: $[50, 40, 45, 15, 10, 30, 20]$

Verificacion de la propiedad max-heap:

• $50 \geq 40$ y $50 \geq 45$ (raiz)
• $40 \geq 15$ y $40 \geq 10$
• $45 \geq 30$ y $45 \geq 20$

Todos los padres son mayores o iguales que sus hijos.

a) $C = A \times B$:

$c_{11} = a_{11} \cdot b_{11} + a_{12} \cdot b_{21} = 3 \cdot 5 + 1 \cdot 1 = 15 + 1 = 16$

$c_{12} = a_{11} \cdot b_{12} + a_{12} \cdot b_{22} = 3 \cdot 0 + 1 \cdot 2 = 0 + 2 = 2$

$c_{21} = a_{21} \cdot b_{11} + a_{22} \cdot b_{21} = 2 \cdot 5 + 4 \cdot 1 = 10 + 4 = 14$

$c_{22} = a_{21} \cdot b_{12} + a_{22} \cdot b_{22} = 2 \cdot 0 + 4 \cdot 2 = 0 + 8 = 8$

$C = A \times B = \begin{pmatrix} 16 & 2 \\ 14 & 8 \end{pmatrix}$

b) $D = B \times A$:

$d_{11} = 5 \cdot 3 + 0 \cdot 2 = 15$

$d_{12} = 5 \cdot 1 + 0 \cdot 4 = 5$

$d_{21} = 1 \cdot 3 + 2 \cdot 2 = 7$

$d_{22} = 1 \cdot 1 + 2 \cdot 4 = 9$

$D = B \times A = \begin{pmatrix} 15 & 5 \\ 7 & 9 \end{pmatrix}$

c) $C \neq D$. Esto demuestra que la multiplicacion de matrices no es conmutativa: $AB \neq BA$ en general.

d) $E_{3 \times 2} \times F_{2 \times 5} = G_{3 \times 5}$.

Las dimensiones internas ($2$) coinciden, asi que la multiplicacion esta definida. La complejidad es $O(m \cdot n \cdot p) = O(3 \cdot 2 \cdot 5) = O(30)$, o en general $O(mnp)$.

a)

• Doubly linked con tail: $O(1)$. Se accede al ultimo nodo via tail, se actualiza tail = tail->prev, y se elimina el nodo. Gracias al puntero prev, no es necesario recorrer la lista.

• Singly linked sin tail: $O(n)$. Para eliminar el ultimo, se necesita actualizar el puntero next del penultimo nodo, pero no hay forma de encontrarlo sin recorrer toda la lista desde head.

b)

• push: $O(1)$ — incrementar el indice top y escribir el valor.
• pop: $O(1)$ — leer el valor en top y decrementar.
• top (peek): $O(1)$ — leer el valor en el indice top sin modificar.

Cuando la pila esta llena y se hace push:

• Tamano fijo: se produce un stack overflow (error). Se debe verificar antes de insertar.
• Tamano dinamico (como std::vector): se redimensiona el arreglo (tipicamente al doble), copiando los elementos. El push individual es $O(n)$ en ese caso, pero es $O(1)$ amortizado porque las redimensiones son infrecuentes.

c) Una cola necesita enqueue al final y dequeue del frente:

• Dequeue del frente: $O(1)$ con singly linked (avanzar head).
• Enqueue al final: Sin puntero a tail, hay que recorrer toda la lista para encontrar el ultimo nodo, lo cual es $O(n)$.

Con puntero a tail, enqueue tambien es $O(1)$, haciendo la implementacion eficiente. Por eso las colas con listas enlazadas siempre usan puntero a tail.

a) Sucesor inorden de 40:

El sucesor inorden es el menor valor del subarbol derecho. Partiendo de 40:

• Ir al hijo derecho: 60
• Ir todo a la izquierda: 50 (no tiene hijo izquierdo)

Sucesor inorden = 50.

b) Proceso de eliminacion:

Paso 1: Nodo 40 tiene dos hijos → caso 3 (reemplazar con sucesor inorden).

Paso 2: Copiar el valor del sucesor (50) al nodo raiz.

Paso 3: Eliminar el nodo 50 del subarbol derecho. El nodo 50 es una hoja (no tiene hijos), asi que simplemente se borra.

Arbol original:              Despues de reemplazar 40→50    Despues de borrar 50 original:
          40                           50                           50
        /    \                       /    \                       /    \
      25      60                   25      60                   25      60
     / \     / \                  / \     / \                  / \       \
   15   30  50  75              15   30  50  75              15   30      75
        /       /                    /       /                    /       /
      28      70                   28      70                   28      70

Arbol final:

          50
        /    \
      25      60
     / \       \
   15   30      75
        /       /
      28      70

c) Recorrido inorden del arbol resultante:

$15, 25, 28, 30, 50, 60, 70, 75$

Verificacion: la secuencia esta en orden ascendente, lo que confirma que la propiedad BST se mantiene.

(Nota: en el arbol original, el inorden era $15, 25, 28, 30, 40, 50, 60, 70, 75$. Al eliminar 40, desaparece de la secuencia y todo lo demas se mantiene.)

a) VERDADERO.

Un arbol AVL es un BST auto-balanceado. Todo AVL cumple la propiedad BST (izquierdo < nodo < derecho), y el recorrido inorden de cualquier BST produce los datos en orden ascendente. El balanceo AVL no afecta esta propiedad, solo garantiza que la altura sea $O(\log n)$.

b) FALSO.

En un Red-Black tree, todo camino raiz-hoja NIL tiene el mismo numero de nodos negros (propiedad 5: black-height), NO el mismo numero total de nodos. Los caminos pueden tener diferente cantidad de nodos rojos intercalados.

c) VERDADERO.

Se puede demostrar matematicamente que con $m$ primo y $\lambda < 0.5$, los sondeos cuadraticos $(h(k) + i^2) \mod m$ para $i = 0, 1, \ldots, \lfloor m/2 \rfloor$ generan posiciones distintas, garantizando encontrar un slot libre. Si $\lambda \geq 0.5$ o $m$ no es primo, esta garantia se pierde.

d) FALSO (parcialmente).

La complejidad de Heap Sort si es $O(n \log n)$ en el peor caso — eso es correcto. Sin embargo, Heap Sort NO es estable. Durante el proceso de percolateDown, los elementos pueden saltar niveles del arbol, desordenando elementos con la misma clave. La afirmacion es falsa porque dice que es estable.

e) FALSO.

Con preorden + postorden, el arbol binario NO queda determinado de forma unica (es ambiguo cuando un nodo tiene un solo hijo, porque no se puede distinguir si es hijo izquierdo o derecho). Para reconstruir de forma unica se necesita:

• Preorden + inorden, o
• Postorden + inorden.

El inorden es la clave porque permite determinar que nodos van a la izquierda y cuales a la derecha de cada raiz.