Ejercicios del Capítulo 15

Volver al índice.

Repaso: Búsqueda Lineal

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)    
   

Repaso: Búsqueda Binaria

Asumiendo que nuestro programa realiza una búsqueda binaria, y que la lista de búsqueda está ordenada, 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 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)
   

   Pregunta Con Un Plus de Dificultad

6. ¿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