Ejercicios: Listas, búsqueda binaria y procedimientos

Sea nums ← [4, 9, 1, 7]. Recuerda que las posiciones de las listas en AP empiezan en 1.

1. a) ¿Cuál es nums[2]?

1. b) ¿Cuál es LENGTH(nums)?

1. c) ¿Cuál es LENGTH(nums) después de APPEND(nums, 5)?

list ← [10, 20, 30]

INSERT(list, 2, 15)

REMOVE(list, 1)

¿Cuál es el contenido final de list? Muestra la lista después de cada paso.

La búsqueda binaria requiere algo de los datos. ¿Cuáles de estas listas se podrían buscar directamente con búsqueda binaria? Explica.

1. i) [2, 5, 8, 11]

ii) [9, 3, 7, 1]

iii) ["ant", "bee", "cat"]

Usa búsqueda binaria para buscar 26 en esta lista ordenada. En cada paso, revisa el elemento de la posición ⌊(low + high) / 2⌋, donde las posiciones empiezan en 1.

[3, 8, 12, 17, 21, 26, 30, 35, 41]

1. a) Escribe, en orden, los valores que se revisan.

1. b) ¿Cuántos elementos se revisaron en total? ¿Cómo se compara esto con una búsqueda secuencial del mismo valor?

PROCEDURE countAbove(list, limit)

{

  count ← 0

  FOR EACH item IN list

  {

    IF (item > limit)

    {

      count ← count + 1

    }

  }

  RETURN(count)

}

1. a) ¿Qué devuelve countAbove([72, 85, 90, 64, 88], 80)?

1. b) ¿Qué devuelve countAbove([72, 85, 90, 64, 88], 90)?

1. c) Describe en una oración qué hace el procedimiento.

PROCEDURE mystery(a, b)

{

  IF (a > b)

  {

    RETURN(a)

  }

  ELSE

  {

    RETURN(b)

  }

}

1. a) Evalúa mystery(4, 9).

1. b) Evalúa mystery(mystery(3, 8), 5).

1. c) ¿Qué hace el procedimiento? Identifica los parámetros y el valor que devuelve.

La lista ordenada de una escuela tiene 1,000,000 de nombres de estudiantes.

1. a) En el peor caso, ¿aproximadamente cuántos elementos revisa una búsqueda secuencial? ¿Y la búsqueda binaria? (Pista: $2^{20} = 1{,}048{,}576$.)

1. b) Supón que la lista no está ordenada y solo necesitas buscar una vez. ¿Es mejor ordenarla primero y usar búsqueda binaria, o usar búsqueda secuencial? Justifica tu respuesta.

1. c) Supón ahora que la lista se buscará miles de veces al día. ¿Qué enfoque es mejor y por qué?

PROCEDURE average(list)

{

  total ← 0

  FOR EACH x IN list

  {

    total ← total + x

  }

  RETURN(total / LENGTH(list))

}

1. a) Sigue paso a paso average([80, 90, 70, 100]). ¿Qué devuelve?

1. b) ¿Qué sale mal si la lista está vacía? Reescribe el procedimiento para que devuelva 0 cuando la lista esté vacía.

1. c) Explica cómo ayuda la abstracción procedimental a un maestro que usa este procedimiento en muchas partes de un programa de calificaciones.