Ejercicios del Capítulo 15
Volver al índice.
Asumiendo que nuestro programa realiza una búsqueda lineal, reponde a lo siguiente:
1. Si una lista tiene n elementos, ¿cuántos de ellos debería comprobar el ordenador, en el mejor de los casos, para encontrar el deseado?
2. Si una lista tiene n elementos, ¿cuántos de ellos debería comprobar el ordenador, en el peor de los casos, para encontrar el deseado?
3. Si una lista tiene n elementos, ¿cuántos de ellos deberíamos comprobar para poder saber que el elemento deseado no existe en la lista?
4. Si una lista tiene n elementos, ¿cuántos de ellos como media, debería comprobar el ordenador para encontrar el deseado?
5. (2 pts) Toma el código del ejemplo de búsqueda lineal e introdúcelo en una función llamada
busqueda_lineal. Toma como parámetros la lista y el elemento buscado. Devuelve la
posición del elemento o -1 si no lo encuentra. Recuerda, DEVUELVE (Return) el valor. Si tu
función tiene una declaración que use print, lo estás haciendo mal. Una vez que hayas escrito
la función, pruébala a ver si funciona con el siguiente código:
# --- Coloca debajo tu definición de busqueda_lineal:
# --- Bien, si la función es correcta, los siguientes tests deberían funcionar:
mi_lista = [4, 3, 2, 1, 5, 7, 6]
r = busqueda_lineal(mi_lista, 3)
if r == 1:
print("Test A bien")
else:
print("Test A mal. Esperaba 1 y obtuvimos", r)
r = busqueda_lineal(mi_lista, 2)
if r == 2:
print("Test B bien")
else:
print("Test B mal. Esperaba 1 y obtuvimos", r)
r = busqueda_lineal(mi_lista, 10)
if r == -1:
print("Test C bien")
else:
print("Test C mal. Esperaba -1 y obtuvimos", r)
Asumiendo que nuestro programa realiza una búsqueda binaria, y que la lista de búsqueda está ordenada, reponde a lo siguiente:
6. Si una lista tiene n elementos, ¿cuántos de ellos debería comprobar el ordenador, en el mejor de los casos, para encontrar el deseado?
7. Si una lista tiene n elementos, ¿cuántos de ellos debería comprobar el ordenador, en el peor de los casos, para encontrar el deseado?
8. Si una lista tiene n elementos, ¿cuántos de ellos deberíamos comprobar para poder saber que el elemento deseado no existe en la lista?
9. Si una lista tiene n elementos, ¿cuántos de ellos como media, debería comprobar el ordenador para encontrar el deseado?
10. (2 pts) Toma el código del ejemplo de búsqueda binaria e introdúcelo en una función llamada
busqueda_binaria. Toma como parámetros la lista y el elemento buscado. Devuelve la
posición del elemento, o -1 si no lo encuentra. Una vez que hayas escrito la función,
pruébala a ver si funciona con el siguiente código:
mi_lista = [0, 3, 5, 12, 18, 50, 70, 78]
r = busqueda_binaria(mi_lista, 3)
if r == 1:
print("Test A bien")
else:
print("Test A mal. Esperaba 1 y obtuvimos", r)
r = busqueda_binaria(mi_lista, 5)
if r == 2:
print("Test B bien")
else:
print("Test B mal. Esperaba 2 y obtuvimos", r)
r = busqueda_binaria(mi_lista, 10)
if r == -1:
print("Test C bien")
else:
print("Test C mal. Esperaba -1 y obtuvimos", r)
11. ¿Es posible que la siguiente función sea capaz de determinar correctamente
si una lista contiene al menos un elemento positivo? Escribe el código para
comprobarlo.Explica por qué crees que funciona o por qué no funciona.(1 punto).
Escribe el código necesario para que funcione (1 punto.)
def detectar_positivo(mi_lista):
for elemento in mi_lista:
if elemento > 0:
return True
else:
return False