Capítulo 5: Operaciones de Búsqueda y Eficiencia
Ejercicios Prácticos: Capítulo 5
Ejercicio 1
Implementa una función que realice una búsqueda lineal en una lista dada.
Entrada: Una lista y un valor objetivo.
Salida: El índice del valor objetivo en la lista. Si el valor objetivo no está presente, devuelve -1.
def linear_search(lst, target):
for i in range(len(lst)):
if lst[i] == target:
return i
return -1
# Test
lst = [1, 3, 5, 7, 9, 11]
print(linear_search(lst, 5)) # Output: 2
print(linear_search(lst, 6)) # Output: -1Ejercicio 2
Implementa una función de búsqueda binaria sin usar recursión.
Entrada: Una lista ordenada y un valor objetivo.
Salida: El índice del valor objetivo en la lista. Si el valor objetivo no está presente, devuelve -1.
def binary_search(lst, target):
low, high = 0, len(lst) - 1
while low <= high:
mid = (low + high) // 2
if lst[mid] == target:
return mid
elif lst[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
# Test
lst = [1, 3, 5, 7, 9, 11]
print(binary_search(lst, 5)) # Output: 2
print(binary_search(lst, 6)) # Output: -1Ejercicio 3
Dada la explicación anterior sobre el hashing, implementa una función hash básica para cadenas que distribuya los caracteres de manera uniforme.
Sugerencia: Para simplificar, asume que la cadena de entrada consiste solo en letras minúsculas del alfabeto inglés, y el tamaño de la tabla hash es 100.
def simple_hash(s):
total = 0
for char in s:
total += ord(char) - ord('a') + 1
return total % 100
# Test
print(simple_hash('hello')) # This will give an output between 0 and 99.Ejercicio 4
Evalúa las complejidades temporales:
- Un bucle que se ejecuta n veces dentro de otro bucle que se ejecuta m veces.
- Una función que divide una lista por la mitad repetidamente hasta que la lista tenga una longitud de 1.
- Un algoritmo que procesa cada elemento en una lista, y para cada elemento, verifica todos los demás elementos en la lista.
Soluciones:
- O(n * m)
- O(log n)
- O(n^2)
Ejercicio 5
Reflexionando sobre la eficiencia del hashing: Si tenemos una tabla hash de tamaño 100 y 50 entradas, ¿cuál es el factor de carga? Cálculalo.
Soluciones:
Factor de carga = número de entradas / tamaño de la tabla = 50/100 = 0.5 o 50%.
Estos ejercicios te darán una exposición práctica a los conceptos presentados en el Capítulo 5. Están diseñados para combinar preguntas de implementación y teóricas para una comprensión completa.
Ejercicios Prácticos: Capítulo 5
Ejercicio 1
Implementa una función que realice una búsqueda lineal en una lista dada.
Entrada: Una lista y un valor objetivo.
Salida: El índice del valor objetivo en la lista. Si el valor objetivo no está presente, devuelve -1.
def linear_search(lst, target):
for i in range(len(lst)):
if lst[i] == target:
return i
return -1
# Test
lst = [1, 3, 5, 7, 9, 11]
print(linear_search(lst, 5)) # Output: 2
print(linear_search(lst, 6)) # Output: -1Ejercicio 2
Implementa una función de búsqueda binaria sin usar recursión.
Entrada: Una lista ordenada y un valor objetivo.
Salida: El índice del valor objetivo en la lista. Si el valor objetivo no está presente, devuelve -1.
def binary_search(lst, target):
low, high = 0, len(lst) - 1
while low <= high:
mid = (low + high) // 2
if lst[mid] == target:
return mid
elif lst[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
# Test
lst = [1, 3, 5, 7, 9, 11]
print(binary_search(lst, 5)) # Output: 2
print(binary_search(lst, 6)) # Output: -1Ejercicio 3
Dada la explicación anterior sobre el hashing, implementa una función hash básica para cadenas que distribuya los caracteres de manera uniforme.
Sugerencia: Para simplificar, asume que la cadena de entrada consiste solo en letras minúsculas del alfabeto inglés, y el tamaño de la tabla hash es 100.
def simple_hash(s):
total = 0
for char in s:
total += ord(char) - ord('a') + 1
return total % 100
# Test
print(simple_hash('hello')) # This will give an output between 0 and 99.Ejercicio 4
Evalúa las complejidades temporales:
- Un bucle que se ejecuta n veces dentro de otro bucle que se ejecuta m veces.
- Una función que divide una lista por la mitad repetidamente hasta que la lista tenga una longitud de 1.
- Un algoritmo que procesa cada elemento en una lista, y para cada elemento, verifica todos los demás elementos en la lista.
Soluciones:
- O(n * m)
- O(log n)
- O(n^2)
Ejercicio 5
Reflexionando sobre la eficiencia del hashing: Si tenemos una tabla hash de tamaño 100 y 50 entradas, ¿cuál es el factor de carga? Cálculalo.
Soluciones:
Factor de carga = número de entradas / tamaño de la tabla = 50/100 = 0.5 o 50%.
Estos ejercicios te darán una exposición práctica a los conceptos presentados en el Capítulo 5. Están diseñados para combinar preguntas de implementación y teóricas para una comprensión completa.
Ejercicios Prácticos: Capítulo 5
Ejercicio 1
Implementa una función que realice una búsqueda lineal en una lista dada.
Entrada: Una lista y un valor objetivo.
Salida: El índice del valor objetivo en la lista. Si el valor objetivo no está presente, devuelve -1.
def linear_search(lst, target):
for i in range(len(lst)):
if lst[i] == target:
return i
return -1
# Test
lst = [1, 3, 5, 7, 9, 11]
print(linear_search(lst, 5)) # Output: 2
print(linear_search(lst, 6)) # Output: -1Ejercicio 2
Implementa una función de búsqueda binaria sin usar recursión.
Entrada: Una lista ordenada y un valor objetivo.
Salida: El índice del valor objetivo en la lista. Si el valor objetivo no está presente, devuelve -1.
def binary_search(lst, target):
low, high = 0, len(lst) - 1
while low <= high:
mid = (low + high) // 2
if lst[mid] == target:
return mid
elif lst[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
# Test
lst = [1, 3, 5, 7, 9, 11]
print(binary_search(lst, 5)) # Output: 2
print(binary_search(lst, 6)) # Output: -1Ejercicio 3
Dada la explicación anterior sobre el hashing, implementa una función hash básica para cadenas que distribuya los caracteres de manera uniforme.
Sugerencia: Para simplificar, asume que la cadena de entrada consiste solo en letras minúsculas del alfabeto inglés, y el tamaño de la tabla hash es 100.
def simple_hash(s):
total = 0
for char in s:
total += ord(char) - ord('a') + 1
return total % 100
# Test
print(simple_hash('hello')) # This will give an output between 0 and 99.Ejercicio 4
Evalúa las complejidades temporales:
- Un bucle que se ejecuta n veces dentro de otro bucle que se ejecuta m veces.
- Una función que divide una lista por la mitad repetidamente hasta que la lista tenga una longitud de 1.
- Un algoritmo que procesa cada elemento en una lista, y para cada elemento, verifica todos los demás elementos en la lista.
Soluciones:
- O(n * m)
- O(log n)
- O(n^2)
Ejercicio 5
Reflexionando sobre la eficiencia del hashing: Si tenemos una tabla hash de tamaño 100 y 50 entradas, ¿cuál es el factor de carga? Cálculalo.
Soluciones:
Factor de carga = número de entradas / tamaño de la tabla = 50/100 = 0.5 o 50%.
Estos ejercicios te darán una exposición práctica a los conceptos presentados en el Capítulo 5. Están diseñados para combinar preguntas de implementación y teóricas para una comprensión completa.
Ejercicios Prácticos: Capítulo 5
Ejercicio 1
Implementa una función que realice una búsqueda lineal en una lista dada.
Entrada: Una lista y un valor objetivo.
Salida: El índice del valor objetivo en la lista. Si el valor objetivo no está presente, devuelve -1.
def linear_search(lst, target):
for i in range(len(lst)):
if lst[i] == target:
return i
return -1
# Test
lst = [1, 3, 5, 7, 9, 11]
print(linear_search(lst, 5)) # Output: 2
print(linear_search(lst, 6)) # Output: -1Ejercicio 2
Implementa una función de búsqueda binaria sin usar recursión.
Entrada: Una lista ordenada y un valor objetivo.
Salida: El índice del valor objetivo en la lista. Si el valor objetivo no está presente, devuelve -1.
def binary_search(lst, target):
low, high = 0, len(lst) - 1
while low <= high:
mid = (low + high) // 2
if lst[mid] == target:
return mid
elif lst[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1
# Test
lst = [1, 3, 5, 7, 9, 11]
print(binary_search(lst, 5)) # Output: 2
print(binary_search(lst, 6)) # Output: -1Ejercicio 3
Dada la explicación anterior sobre el hashing, implementa una función hash básica para cadenas que distribuya los caracteres de manera uniforme.
Sugerencia: Para simplificar, asume que la cadena de entrada consiste solo en letras minúsculas del alfabeto inglés, y el tamaño de la tabla hash es 100.
def simple_hash(s):
total = 0
for char in s:
total += ord(char) - ord('a') + 1
return total % 100
# Test
print(simple_hash('hello')) # This will give an output between 0 and 99.Ejercicio 4
Evalúa las complejidades temporales:
- Un bucle que se ejecuta n veces dentro de otro bucle que se ejecuta m veces.
- Una función que divide una lista por la mitad repetidamente hasta que la lista tenga una longitud de 1.
- Un algoritmo que procesa cada elemento en una lista, y para cada elemento, verifica todos los demás elementos en la lista.
Soluciones:
- O(n * m)
- O(log n)
- O(n^2)
Ejercicio 5
Reflexionando sobre la eficiencia del hashing: Si tenemos una tabla hash de tamaño 100 y 50 entradas, ¿cuál es el factor de carga? Cálculalo.
Soluciones:
Factor de carga = número de entradas / tamaño de la tabla = 50/100 = 0.5 o 50%.
Estos ejercicios te darán una exposición práctica a los conceptos presentados en el Capítulo 5. Están diseñados para combinar preguntas de implementación y teóricas para una comprensión completa.