You've learned this already. ✅
Click here to view the next lesson.
Capítulo 6: Árboles y Grafos: Estructuras de Datos Jerárquicas
Ejercicios Prácticos para el Capítulo 6
Para el Capítulo 6, hemos preparado una serie de ejercicios prácticos. Estas actividades están diseñadas para profundizar tu comprensión de las estructuras de datos de árboles y gráficos, proporcionando experiencia práctica en la implementación y comprensión de sus conceptos clave.
Ejercicio 1: Implementar un Árbol de Búsqueda Binaria
- Crea un Árbol de Búsqueda Binaria (BST) básico con métodos de inserción y recorrido en orden.
- Inserta los números 10, 5, 15, 2, 5, 13, 22, 1, 14 y luego realiza un recorrido en orden.
Solución:
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, value):
new_node = Node(value)
if self.root is None:
self.root = new_node
return
current = self.root
while True:
if value < current.value:
if current.left is None:
current.left = new_node
return
current = current.left
else:
if current.right is None:
current.right = new_node
return
current = current.right
def in_order_traversal(self, node, result=[]):
if node:
self.in_order_traversal(node.left, result)
result.append(node.value)
self.in_order_traversal(node.right, result)
return result
# Test
bst = BinarySearchTree()
for value in [10, 5, 15, 2, 5, 13, 22, 1, 14]:
bst.insert(value)
print(bst.in_order_traversal(bst.root)) # Output: [1, 2, 5, 5, 10, 13, 14, 15, 22]Ejercicio 2: Implementar un Grafo usando una Lista de Adyacencia
- Crea una clase Grafo con métodos para agregar aristas y realizar un BFS (Búsqueda en Amplitud).
- Agrega aristas para conectar los nodos 0, 1, 2, 3 y 4 de manera no lineal y realiza un BFS comenzando desde el nodo 0.
Solución:
from collections import defaultdict, deque
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
def bfs(self, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
print(vertex, end=' ')
visited.add(vertex)
queue.extend(set(self.graph[vertex]) - visited)
# Test
g = Graph()
edges = [(0, 1), (1, 2), (1, 3), (2, 4)]
for u, v in edges:
g.add_edge(u, v)
g.bfs(0) # Output: 0 1 2 3 4Ejercicio 3: Búsqueda en Profundidad (DFS) en un Grafo
- Implementa DFS para el grafo creado en el Ejercicio 2.
- Realiza un DFS comenzando desde el nodo 0.
Solución:
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for neighbor in graph.graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
# Test
dfs(g, 0) # Output: 0 1 2 4 3Ejercicio 4: Implementar una Tabla de Hash Simple
- Crea una clase Tabla de Hash con métodos básicos de inserción y recuperación.
- Inserta pares clave-valor ('clave1', 'valor1'), ('clave2', 'valor2') y recupera 'clave1'.
Solución:
class HashTable:
def __init__(self, size=10):
self.size = size
self.table = [[] for _ in range(size)]
def _hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self._hash_function(key)
self.table[index].append((key, value))
def get(self, key):
index = self._hash_function(key)
for k, v in self.table[index]:
if k == key:
return v
return None
# Test
ht = HashTable()
ht.insert('key1', 'value1')
ht.insert('key2', 'value2')
print(ht.get('key1')) # Output: 'value1'Ejercicios Prácticos para el Capítulo 6
Para el Capítulo 6, hemos preparado una serie de ejercicios prácticos. Estas actividades están diseñadas para profundizar tu comprensión de las estructuras de datos de árboles y gráficos, proporcionando experiencia práctica en la implementación y comprensión de sus conceptos clave.
Ejercicio 1: Implementar un Árbol de Búsqueda Binaria
- Crea un Árbol de Búsqueda Binaria (BST) básico con métodos de inserción y recorrido en orden.
- Inserta los números 10, 5, 15, 2, 5, 13, 22, 1, 14 y luego realiza un recorrido en orden.
Solución:
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, value):
new_node = Node(value)
if self.root is None:
self.root = new_node
return
current = self.root
while True:
if value < current.value:
if current.left is None:
current.left = new_node
return
current = current.left
else:
if current.right is None:
current.right = new_node
return
current = current.right
def in_order_traversal(self, node, result=[]):
if node:
self.in_order_traversal(node.left, result)
result.append(node.value)
self.in_order_traversal(node.right, result)
return result
# Test
bst = BinarySearchTree()
for value in [10, 5, 15, 2, 5, 13, 22, 1, 14]:
bst.insert(value)
print(bst.in_order_traversal(bst.root)) # Output: [1, 2, 5, 5, 10, 13, 14, 15, 22]Ejercicio 2: Implementar un Grafo usando una Lista de Adyacencia
- Crea una clase Grafo con métodos para agregar aristas y realizar un BFS (Búsqueda en Amplitud).
- Agrega aristas para conectar los nodos 0, 1, 2, 3 y 4 de manera no lineal y realiza un BFS comenzando desde el nodo 0.
Solución:
from collections import defaultdict, deque
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
def bfs(self, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
print(vertex, end=' ')
visited.add(vertex)
queue.extend(set(self.graph[vertex]) - visited)
# Test
g = Graph()
edges = [(0, 1), (1, 2), (1, 3), (2, 4)]
for u, v in edges:
g.add_edge(u, v)
g.bfs(0) # Output: 0 1 2 3 4Ejercicio 3: Búsqueda en Profundidad (DFS) en un Grafo
- Implementa DFS para el grafo creado en el Ejercicio 2.
- Realiza un DFS comenzando desde el nodo 0.
Solución:
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for neighbor in graph.graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
# Test
dfs(g, 0) # Output: 0 1 2 4 3Ejercicio 4: Implementar una Tabla de Hash Simple
- Crea una clase Tabla de Hash con métodos básicos de inserción y recuperación.
- Inserta pares clave-valor ('clave1', 'valor1'), ('clave2', 'valor2') y recupera 'clave1'.
Solución:
class HashTable:
def __init__(self, size=10):
self.size = size
self.table = [[] for _ in range(size)]
def _hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self._hash_function(key)
self.table[index].append((key, value))
def get(self, key):
index = self._hash_function(key)
for k, v in self.table[index]:
if k == key:
return v
return None
# Test
ht = HashTable()
ht.insert('key1', 'value1')
ht.insert('key2', 'value2')
print(ht.get('key1')) # Output: 'value1'Ejercicios Prácticos para el Capítulo 6
Para el Capítulo 6, hemos preparado una serie de ejercicios prácticos. Estas actividades están diseñadas para profundizar tu comprensión de las estructuras de datos de árboles y gráficos, proporcionando experiencia práctica en la implementación y comprensión de sus conceptos clave.
Ejercicio 1: Implementar un Árbol de Búsqueda Binaria
- Crea un Árbol de Búsqueda Binaria (BST) básico con métodos de inserción y recorrido en orden.
- Inserta los números 10, 5, 15, 2, 5, 13, 22, 1, 14 y luego realiza un recorrido en orden.
Solución:
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, value):
new_node = Node(value)
if self.root is None:
self.root = new_node
return
current = self.root
while True:
if value < current.value:
if current.left is None:
current.left = new_node
return
current = current.left
else:
if current.right is None:
current.right = new_node
return
current = current.right
def in_order_traversal(self, node, result=[]):
if node:
self.in_order_traversal(node.left, result)
result.append(node.value)
self.in_order_traversal(node.right, result)
return result
# Test
bst = BinarySearchTree()
for value in [10, 5, 15, 2, 5, 13, 22, 1, 14]:
bst.insert(value)
print(bst.in_order_traversal(bst.root)) # Output: [1, 2, 5, 5, 10, 13, 14, 15, 22]Ejercicio 2: Implementar un Grafo usando una Lista de Adyacencia
- Crea una clase Grafo con métodos para agregar aristas y realizar un BFS (Búsqueda en Amplitud).
- Agrega aristas para conectar los nodos 0, 1, 2, 3 y 4 de manera no lineal y realiza un BFS comenzando desde el nodo 0.
Solución:
from collections import defaultdict, deque
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
def bfs(self, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
print(vertex, end=' ')
visited.add(vertex)
queue.extend(set(self.graph[vertex]) - visited)
# Test
g = Graph()
edges = [(0, 1), (1, 2), (1, 3), (2, 4)]
for u, v in edges:
g.add_edge(u, v)
g.bfs(0) # Output: 0 1 2 3 4Ejercicio 3: Búsqueda en Profundidad (DFS) en un Grafo
- Implementa DFS para el grafo creado en el Ejercicio 2.
- Realiza un DFS comenzando desde el nodo 0.
Solución:
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for neighbor in graph.graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
# Test
dfs(g, 0) # Output: 0 1 2 4 3Ejercicio 4: Implementar una Tabla de Hash Simple
- Crea una clase Tabla de Hash con métodos básicos de inserción y recuperación.
- Inserta pares clave-valor ('clave1', 'valor1'), ('clave2', 'valor2') y recupera 'clave1'.
Solución:
class HashTable:
def __init__(self, size=10):
self.size = size
self.table = [[] for _ in range(size)]
def _hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self._hash_function(key)
self.table[index].append((key, value))
def get(self, key):
index = self._hash_function(key)
for k, v in self.table[index]:
if k == key:
return v
return None
# Test
ht = HashTable()
ht.insert('key1', 'value1')
ht.insert('key2', 'value2')
print(ht.get('key1')) # Output: 'value1'Ejercicios Prácticos para el Capítulo 6
Para el Capítulo 6, hemos preparado una serie de ejercicios prácticos. Estas actividades están diseñadas para profundizar tu comprensión de las estructuras de datos de árboles y gráficos, proporcionando experiencia práctica en la implementación y comprensión de sus conceptos clave.
Ejercicio 1: Implementar un Árbol de Búsqueda Binaria
- Crea un Árbol de Búsqueda Binaria (BST) básico con métodos de inserción y recorrido en orden.
- Inserta los números 10, 5, 15, 2, 5, 13, 22, 1, 14 y luego realiza un recorrido en orden.
Solución:
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
class BinarySearchTree:
def __init__(self):
self.root = None
def insert(self, value):
new_node = Node(value)
if self.root is None:
self.root = new_node
return
current = self.root
while True:
if value < current.value:
if current.left is None:
current.left = new_node
return
current = current.left
else:
if current.right is None:
current.right = new_node
return
current = current.right
def in_order_traversal(self, node, result=[]):
if node:
self.in_order_traversal(node.left, result)
result.append(node.value)
self.in_order_traversal(node.right, result)
return result
# Test
bst = BinarySearchTree()
for value in [10, 5, 15, 2, 5, 13, 22, 1, 14]:
bst.insert(value)
print(bst.in_order_traversal(bst.root)) # Output: [1, 2, 5, 5, 10, 13, 14, 15, 22]Ejercicio 2: Implementar un Grafo usando una Lista de Adyacencia
- Crea una clase Grafo con métodos para agregar aristas y realizar un BFS (Búsqueda en Amplitud).
- Agrega aristas para conectar los nodos 0, 1, 2, 3 y 4 de manera no lineal y realiza un BFS comenzando desde el nodo 0.
Solución:
from collections import defaultdict, deque
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v):
self.graph[u].append(v)
def bfs(self, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
print(vertex, end=' ')
visited.add(vertex)
queue.extend(set(self.graph[vertex]) - visited)
# Test
g = Graph()
edges = [(0, 1), (1, 2), (1, 3), (2, 4)]
for u, v in edges:
g.add_edge(u, v)
g.bfs(0) # Output: 0 1 2 3 4Ejercicio 3: Búsqueda en Profundidad (DFS) en un Grafo
- Implementa DFS para el grafo creado en el Ejercicio 2.
- Realiza un DFS comenzando desde el nodo 0.
Solución:
def dfs(graph, start, visited=None):
if visited is None:
visited = set()
visited.add(start)
print(start, end=' ')
for neighbor in graph.graph[start]:
if neighbor not in visited:
dfs(graph, neighbor, visited)
# Test
dfs(g, 0) # Output: 0 1 2 4 3Ejercicio 4: Implementar una Tabla de Hash Simple
- Crea una clase Tabla de Hash con métodos básicos de inserción y recuperación.
- Inserta pares clave-valor ('clave1', 'valor1'), ('clave2', 'valor2') y recupera 'clave1'.
Solución:
class HashTable:
def __init__(self, size=10):
self.size = size
self.table = [[] for _ in range(size)]
def _hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self._hash_function(key)
self.table[index].append((key, value))
def get(self, key):
index = self._hash_function(key)
for k, v in self.table[index]:
if k == key:
return v
return None
# Test
ht = HashTable()
ht.insert('key1', 'value1')
ht.insert('key2', 'value2')
print(ht.get('key1')) # Output: 'value1'