Estructura de Datos

🔗 Ayudantía: Grafos y Representaciones

📝 Ejercicio 1: Teoría de Grafos

🎯 Descripción

1. ¿Cuántos vértices y aristas tiene el grafo?
2. ¿Existe algún ciclo en el grafo? Si es así, indique uno.
3. Realice un recorrido BFS (Breadth-First Search) desde el vértice 0
4. Realice un recorrido DFS (Depth-First Search) desde el vértice 0

Visualización del Grafo:

📝 Ejercicio 2: Análisis de Representaciones de Grafos

🎯 Descripción

1. Analizar la matriz de adyacencia proporcionada y determinar:
   • ¿Cuántas amistades tiene cada usuario?
   • ¿Cuál es el usuario más popular (más conexiones)?
   • ¿Cuál es el usuario menos popular?
   • ¿Cuánta memoria ocupa la matriz? (cada elemento ocupa 4 bytes)
2. Convertir a lista de adyacencia y calcular:
   • ¿Cuánta memoria ocuparía la lista? (cada puntero ocupa 8 bytes, cada entero 4 bytes)
3. Operaciones sobre el grafo:
   • ¿Cuántos amigos en común tienen los usuarios 0 y 3?
   • ¿Existe un camino de amistad entre el usuario 0 y el usuario 5? (amigos de amigos)
   • Si el usuario 1 quiere enviar un mensaje al usuario 5 a través de amigos, ¿cuál es la cadena más corta?

💡 Ejemplo

      0  1  2  3  4  5
0 [   0  1  1  0  1  0  ]
1 [   1  0  1  1  0  0  ]
2 [   1  1  0  0  1  1  ]
3 [   0  1  0  0  1  1  ]
4 [   1  0  1  1  0  1  ]
5 [   0  0  1  1  1  0  ]

• Grafo no dirigido (amistad es bidireccional)
• Si matriz[i][j] = 1, entonces el usuario i y el usuario j son amigos
• La diagonal principal siempre es 0 (un usuario no es amigo de sí mismo)

📝 Ejercicio 3: Implementación de Conversiones

🎯 Descripción

1. matrizToLista(): Convertir matriz de adyacencia a lista de adyacencia
2. listaToMatriz(): Convertir lista de adyacencia a matriz de adyacencia

💡 Ejemplos de Uso

📥 Input: 
matriz = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 1],
    [0, 1, 1, 0]
]

📤 Output (lista):
[
    [1, 2],      // Vértice 0 conectado a 1 y 2
    [0, 3],      // Vértice 1 conectado a 0 y 3
    [0, 3],      // Vértice 2 conectado a 0 y 3
    [1, 2]       // Vértice 3 conectado a 1 y 2
]

📥 Input: 
lista = [
    [1, 2],
    [0, 2],
    [0, 1, 3],
    [2]
]
n = 4

📤 Output (matriz):
[
    [0, 1, 1, 0],
    [1, 0, 1, 0],
    [1, 1, 0, 1],
    [0, 0, 1, 0]
]

• 1 <= n <= 1000 (número de vértices)
• Grafo no dirigido (matriz simétrica)
• matriz[i][j] ∈ {0, 1}
• No hay aristas múltiples ni lazos (auto-conexiones)

• Para matrizToLista(): Recorrer la matriz y agregar vecinos
• Para listaToMatriz(): Crear matriz de ceros y llenar con unos donde hay aristas

🔗 Ayudantía 10: Binary Tree y Teoría de Grafos

📝 Ejercicio 1: Teoría de árboles

🎯 Descripción

1. ¿Cuál es la altura del árbol?
2. ¿Cuántos nodos hoja tiene?
3. Indique el recorrido preorder
4. Indique el recorrido inorder
5. Indique el recorrido postorder
6. ¿Es un árbol binario de búsqueda (BST)? Justifique.

💡 Ejemplo

         50
        /  \
      30    70
     /  \   /  \
   20   40 60  80
   /
  10

📝 Ejercicio 2: Teoría de grafos

🎯 Descripción

1. Liste todos los caminos posibles desde A hasta F
2. Calcule la distancia total en KM de cada camino
3. Determine cuál es el camino más corto
4. ¿Qué algoritmo usaría para encontrar el camino mas corto?

💡 Ejemplo

Grafo (distancias en KM):

    A ---8--- B ---7--- C
    |         |         |
    4         3         5
    |         |         |
    D ---2--- E ---6--- F
    |                   |
    10------------------+

Aristas:
A-B: 8 km
A-D: 4 km
B-C: 7 km
B-E: 3 km
C-F: 5 km
D-E: 2 km
D-F: 10 km
E-F: 6 km

📝 Ejercicio 3: Árboles

🎯 Descripción

Class TreeNode{
    public:
        int val;
        TreeNode* left;
        TreeNode* right;
        TreeNode(int x): val(x), left(nullptr), right(nullptr){}
        ~TreeNode(){}
};

💡 Ejemplo

📥 Input: 
preOrder:  [5, 3, 2, 4, 8, 7, 9]
inOrder:   [2, 3, 4, 5, 7, 8, 9]

📤 Output (árbol construido):
         5
        / \
       3   8
      / \ / \
     2  4 7  9

• Se recomienda utilizar recursividad.
• los recorridos preorder y inorder se entregan en forma de vector preOrder, vector inOrder.

🔗 Ayudantía 9: Árboles AVL

📝 Ejercicio 1: Secuencia Ascendente

🎯 Descripción

💡 Ejemplo

📥 Input: [5, 10, 15, 20, 25, 30, 35]

📝 Ejercicio 2: Secuencia Descendente

🎯 Descripción

💡 Ejemplo

📥 Input: [80, 70, 60, 50, 40, 30, 20]

📝 Ejercicio 3: Patrón Zigzag

🎯 Descripción

💡 Ejemplo

📥 Input: [50, 25, 75, 10, 60, 90, 5, 70]

📝 Ejercicio 4: Eliminación con Rebalanceo en Cascada

🎯 Descripción

💡 Ejemplo

📥 Input: [50, 25, 75, 10, 30, 60, 80, 5, 15, 27, 35, 55, 65, 77, 85]
Números a eliminar: [10, 30, 60]

📝 Ejercicio 5: Rango de Eliminación

🎯 Descripción

💡 Ejemplo

📥 Input: [50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 45, 55, 65, 75, 90]
Eliminar rango: [35, 65]

📝 Ejercicio 6: Desafío Extra (Operaciones Mixtas)

🎯 Descripción

💡 Ejemplo

📥 Operaciones:
1. Insertar: [45, 25, 65, 15, 35, 55, 75, 10, 30, 50, 60, 70, 80]
2. Eliminar: [15, 65]
3. Insertar: [5, 20, 40]
4. Eliminar: [25, 75]
5. Insertar: [85, 12]

✅ Resultado:
- Total de rotaciones: ___
- Altura final: ___
- Factor de equilibrio de la raíz: ___

🔧 Herramientas de Apoyo

Visualizador Interactivo de Árboles AVL

• Insertar y eliminar nodos uno por uno
• Visualizar las rotaciones en tiempo real
• Verificar los factores de equilibrio de cada nodo
• Comparar sus resultados con la solución correcta

🔗 Ayudantía 8: Árboles AVL

📝 Ejercicio 1: Rotaciones Simples (LL y RR)

🎯 Descripción

💡 Ejemplo

📥 Input: [30, 20, 10]

📝 Ejercicio 2: Rotaciones Dobles (LR y RL)

🎯 Descripción

💡 Ejemplo

📥 Input: [50, 30, 40]

📝 Ejercicio 3: Construcción de Árbol AVL Completo

🎯 Descripción

💡 Ejemplo

📥 Input: [10, 20, 30, 25, 5, 35, 40, 15, 38]

📝 Ejercicio 4: Inserciones y Eliminaciones

🎯 Descripción

💡 Ejemplo

📥 Input: [10, 20, 30, 25, 5, 35, 40, 15, 38]
Números a eliminar: [10, 35, 20]

📝 Ejercicio 5: Desafío (Mixto)

🎯 Descripción

💡 Ejemplo

📥 Input: [50, 30, 70, 20, 40, 60, 80, 10, 25, 35, 45]
Eliminar: [20, 35, 70]

✅ Árbol final balanceado:
         40
        /  \
      25    60
     / \    / \
   10  30  50  80

🔗 Ayudantía 7: Heapsort

📝 Ejercicio 1: MaxHeap

🎯 Descripción

💡 Ejemplo

📥 Input: [47, 46, 21, 44, 30, 10, 24, 7, 42, 34]

📤 Output: 

H1: 47, 46, 21, 44, 30, 10, 24
H2: 47, 46, 21, 44, 30, 10, 21, 7, 42, 34
H3: 47, 46, 24, 44, 34, 10, 21, 7, 42, 30

1. [30, 46, 24, 44, 34, 10, 21, 7, 42| 47]
 H1: [46, 30, 24, 44, 34, 10, 21, 7, 42| 47]
 H2: [46, 44, 24, 30, 34, 10, 21, 7, 42| 47]
 H3: [46, 44, 24, 42, 34, 10, 21, 7, 30| 47]
2. [30, 44, 24, 42, 34, 10, 21, 7| 46, 47]
 H1: [44, 30, 24, 42, 34, 10, 21, 7| 46, 47]
 .
 .
 .
X. [7, 10, 21, 24, 30, 34, 42, 44, 46, 47]

📝 Ejercicio 2: MinHeap

🎯 Descripción

💡 Ejemplo

📥 Input: [12, 4, 19, 8, 5, 21, 7]

📤 Output: 

H1: 12, 4
H2: 4, 12, 19, 8
.
.

1. [19, 5, 7, 12, 8, 21| 4]
 H1: [5, 19, 7, 12, 8, 21| 4]
 .
 .
 .
X. [21, 19, 12, 8, 7, 5, 4]

🔗 Ayudantía 6:

📝 Opción 1: Repaso Listas Enlazadas

🎯 Descripción

💡 Ejemplo

📥 Input:  
Lista 1: 1->2->3->4->6
Lista 2: 2->4->6->8

📤 Output: 2->4->6

📝 Opción 2: Resolución Ejercicio 4 Prueba (Stacks)

🎯 Descripción

bool canBeObtainable(int* pushed, int* popped, int size)

• Complejidad temporal: O(n)
• Complejidad espacial: O(n)
• Usar clase Node
• Solo librería <iostream>

💡 Ejemplo

📥 Input:  
pushed = [1, 2, 3, 4, 5]
popped = [4, 5, 3, 2, 1]

📤 Output: true

📝 Opción 3: Materia nueva

🎯 Descripción

💡 Ejemplo

       F
     /  \
    B     G
   / \     \
  A   D     I
     / \   /
    C   E H

class Node {
public:
int value;
Node* next;
Node() { next = nullptr; }
};

🔗 Ayudantía 5: Stacks y Queues

📝 Ejercicio 1: Ordenamiento de stack

🎯 Descripción

💡 Ejemplo

📥 Input:  
Stack: 11, 2, 32, 3, 41 

📤 Output: 2, 3, 11, 32, 41

📝 Ejercicio 2: Ordenamiento de stack

🎯 Descripción

💡 Ejemplo

📥 Input:  
Queue: 4 3 1 10 2 6 

📤 Output: 6 2 10 1 3 4

🔗 Ayudantía 5.5: Listas Enlazadas (Tipo prueba)

📝 Ejercicio 1: Suma de listas

🎯 Descripción

💡 Ejemplo

📥 Input:  
Lista 1: 2 -> 4 -> 3 (Representa 342)
Lista 2: 5 -> 6 -> 4 (Representa 465)

📤 Output: Resultado: 7 -> 0 -> 8 (Representa 807)

📝 Ejercicio 2: Rotar una Lista Enlazada en rango en subgrupos

🎯 Descripción

💡 Ejemplo

📥 Input:  
Lista: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> Null
m = 3, n = 6, k = 2

📤 Output:  1 -> 2 -> 5 -> 6 -> 3 -> 4 -> 7 -> 8 -> Null

🔗 Ayudantía 4: Doble Linked List Circular

📋 Estructura de un Nodo

class Node {
public:
    int data;
    Node *next;
    Node *prev;
    Node(int x) {
        data = x;
        next = this; // se apunta a sí mismo
        prev = this;
    }
};

📝 Ejercicio 1: Rotación de una Lista Doblemente Enlazada Circular

🎯 Descripción

💡 Ejemplo

📥 Input:  
Linked List: 10 ⇄ 20 ⇄ 30 ⇄ 40 ⇄ 50  
k = 2  

📤 Output: 40 ⇄ 50 ⇄ 10 ⇄ 20 ⇄ 30

⚠️ Consideraciones

• ✅ Una rotación hacia la derecha significa que cada elemento se mueve k posiciones hacia adelante en la lista.
• ✅ La lista es circular, por lo que los últimos elementos deben moverse al inicio sin necesidad de reconstruir la lista.
• ✅ El algoritmo debe aprovechar la naturaleza circular de la lista y no usar arreglos auxiliares.

📝 Ejercicio 2: Invertir una Lista Doblemente Enlazada Circular en grupos

🎯 Descripción

💡 Ejemplo

📥 Input:  
Linked List: 1 ⇄ 2 ⇄ 3 ⇄ 4 ⇄ 5 ⇄ 6 
k = 2  

📤 Output: 2 ⇄ 1 ⇄ 4 ⇄ 3 ⇄ 6 ⇄ 5


📥 Input:  
Linked List: 1 ⇄ 2 ⇄ 3 ⇄ 4 ⇄ 5 ⇄ 6 
k = 4  

📤 Output: 4 ⇄ 3 ⇄ 2 ⇄ 1 ⇄ 6 ⇄ 5

⚠️ Consideraciones

• ✅ Una rotación hacia la derecha significa que cada elemento se mueve k posiciones hacia adelante en la lista.
• ✅ La lista es circular, por lo que los últimos elementos deben moverse al inicio sin necesidad de reconstruir la lista.
• ✅ El algoritmo debe aprovechar la naturaleza circular de la lista y no usar arreglos auxiliares.

🔗 Ayudantía 3: Simple Linked List

📋 Estructura de un Nodo

struct Node{
    int data;
    Node* next;

    Node(int x){
        data = x;
        next = NULL;
    }
};

📝 Ejercicio 1: Omitir y Eliminar Nodos

🎯 Descripción

💡 Ejemplo

📥 Input:  
Linked List: 9→1→3→5→9→4→10→1  
n = 1, m = 2  

📤 Output: 9→1→5→9→10→1

⚠️ Restricciones

• ✅ El tamaño de la linked list va desde 1-1000
• ✅ n siempre será mayor a 0
• ✅ m siempre será menor o igual al tamaño de la lista

🔄 Ejercicio 2: Fusionar Listas Enlazadas Ordenadas

🎯 Descripción

💡 Ejemplo

📥 INPUT:
┌─ Lista 1: 1 → 3 → 7 → nullptr
├─ Lista 2: 2 → 4 → 8 → nullptr  
└─ Lista 3: 9 → nullptr

📤 OUTPUT: 1 → 2 → 3 → 4 → 7 → 8 → 9 → nullptr

Ayudantía 2: Simple Linked List

Estructura de un nodo

struct Node{
    int data;
    Node* next;

    Node(int x){
        data = x;
        next = NULL;
    }
};

Ejercicio 1

Código

Node *removeDuplicates(Node *head) {
    if(head == nullptr) return nullptr;
    
    if(head -> next == nullptr) return head;
    
    vector<int> numbers;
    Node* current = head;
    Node* prev = nullptr;
    while(current != nullptr){
        if(find(numbers, current -> data)){
            prev->next = current->next;
            delete current;
            current = prev->next;
        } else{
            prev = current;
            current = current -> next;
        }
    }
    return head;
}

bool find(vector<int>& numbers, int number){
    bool found = false;
    
    for(int i = 0; i < numbers.size(); i++){
        if(numbers[i] == number){
            found = true;
            break;
        }
    }
    
    if(!found){
        numbers.push_back(number);
    }
    
    return found;
}

Input

Ejemplo de respuesta

Ejercicio 2

Código

long long multiplyTwoLists(Node *first, Node *second) {
    if(first == nullptr || second == nullptr) {
        return 0;
    }
        
    long long firstNumber = convertToNumber(first);
    long long secondNumber = convertToNumber(second);
    return (firstNumber * secondNumber);
}
    
long long convertToNumber(Node* head) {
    long long num = 0;
    while (head != nullptr) {
        num = (num * 10 + head->data);
        head = head->next;
    }
    return num;
}

Input

Ejemplo de respuesta

• Ejecución principal

• Detalle - convertToNumber(first) → Lista: 1→2→5

• Paso a Paso Detallado - Primera Lista

Ayudantía 1: Punteros y referencias

• Variable normal: int x = 10;
• Dirección de memoria (señala la posición de la memoria donde se encuentra una variable): &x
• Puntero (Variable que almacena una dirección de memoria): int* ptr = &x;
• Referencia (permite acceder al valor guardado dentro de una dirección de memoria): int& ref = x;

Ejercicio

1. Pida al usuario 3 números enteros.
2. Guarde esos números en un arreglo.
3. Use un puntero para recorrer el arreglo y mostrar los valores junto a sus direcciones de memoria.
4. Cree una referencia hacia el primero número del arreglo y modifiquelo mediante la referencia.
5. Recorra nuevamente el arreglo mostrando los valores y direcciones de memoria.

Extra

• Use la librería vector para crear un array.
• Con el método push_back puede insertar elementos al arreglo.

Ejemplo de salida.

Ingrese su número 1: 5
Ingrese su número 2: 9
Ingrese su número 3: 12

Array original
Pos 0 -> Valor: 5 dirección: 0x6381eac76ad0
Pos 1 -> Valor: 9 dirección: 0x6381eac76ad4
Pos 2 -> Valor: 12 dirección: 0x6381eac76ad8

Array modificado
Pos 0 -> Valor: 14 dirección: 0x6381eac76ad0
Pos 1 -> Valor: 9 dirección: 0x6381eac76ad4
Pos 2 -> Valor: 12 dirección: 0x6381eac76ad8