Colecciones de datos

AP Ciencias de la Computación A · Tema 4

Lección de video para este tema Abrir la página de video

4.1

La Ética de la Recopilación de Datos

Syllabus

Objetivo de Aprendizaje 4.1.A: Explicar los riesgos para la privacidad derivados de la recopilación y almacenamiento de datos personales en sistemas informáticos.

4.1.A.1 Al utilizar una computadora, la privacidad personal corre riesgo. Al desarrollar nuevos programas, los programadores deben intentar salvaguardar la privacidad personal del usuario.

Objetivo de Aprendizaje 4.1.B: Explicar la importancia de reconocer la calidad de los datos y los posibles problemas al utilizar un conjunto de datos.

4.1.B.1 El sesgo algorítmico describe errores sistemáticos y repetidos en un programa que generan resultados injustos para un grupo específico de usuarios.
4.1.B.2 Los programadores deben ser conscientes del método de recopilación del conjunto de datos y del potencial de sesgo presente en dicho método antes de utilizar los datos para extraer nueva información o formular conclusiones.
4.1.B.3 Algunos conjuntos de datos son incompletos o contienen datos inexactos. El uso de dichos datos en el desarrollo o la ejecución de un programa puede causar que este funcione incorrectamente o de manera ineficiente.

Objetivo de Aprendizaje 4.1.C: Identificar un conjunto de datos adecuado para utilizar con el fin de resolver un problema o responder una pregunta específica.

4.1.C.1 El contenido de un conjunto de datos podría estar relacionado con una pregunta o tema específico y no ser apropiado para proporcionar respuestas correctas ni extraer información para una pregunta o tema diferente.

Fuente: College Board AP Course and Exam Description

Gabinetes de servidores en un centro de datos — las grandes colecciones de datos plantean preguntas éticas sobre su recopilación y uso

Los programas que recopilan datos generan interrogantes sobre la privacidad 隐私 y el consentimiento 同意. Recopile solo lo necesario, proteja la información y sea honesto respecto a su uso. Los datos pueden contener sesgos 偏见 si no representan a todos con equidad, lo que conduce a resultados injustos; una responsabilidad inherente al almacenar información.

Vocabulario Entrenar

Inglés	Chino	Pinyin
privacy/ˈprɪvəsi/	隐私	yǐn sī
consent/kənˈsent/	同意	tóng yì
bias/ˈbaɪəs/	偏见	piān jiàn
data structure/ˈdeɪtə ˈstrʌktʃə/	数据结构	shù jù jié gòu

4.2

¿Por qué Necesitamos Estructuras de Datos?

Syllabus

Objetivo de aprendizaje 4.2.A: Representar patrones y algoritmos que involucran conjuntos de datos encontrados en la vida cotidiana mediante lenguaje escrito o diagramas.

4.2.A.1 Un conjunto de datos es una colección de piezas específicas de información o datos.
4.2.A.2 Los conjuntos de datos pueden manipularse y analizarse para resolver un problema o responder una pregunta. Al analizar conjuntos de datos, los valores dentro del conjunto se acceden y utilizan uno a la vez, y luego se procesan según el resultado deseado.
4.2.A.3 Los datos pueden representarse en un diagrama utilizando un gráfico o una tabla. Esta visualización puede utilizarse para planificar el algoritmo que se empleará para manipular los datos.

Fuente: College Board AP Course and Exam Description

Un archivador: las colecciones almacenan muchos valores bajo un mismo nombre para que los algoritmos puedan procesarlos

Una variable individual contiene un solo valor; los problemas reales requieren almacenar muchos valores relacionados: una lista de alumnos, píxeles, lecturas de sensores. Una estructura de datos 数据结构 organiza una colección para que podamos almacenar, encontrar y procesar elementos de manera eficiente. El curso AP utiliza tres: el array, el ArrayList y el array 2D.

4.3

Creación y Lectura de un Array

Syllabus

Objetivo de aprendizaje 4.3.A: Desarrollar código para representar colecciones de datos relacionados utilizando objetos array unidimensionales (1D).

4.3.A.1 Un array almacena múltiples valores del mismo tipo. Los valores pueden ser valores primitivos o referencias a objetos.
4.3.A.2 La longitud de un array se establece en el momento de su creación y no puede modificarse. La longitud de un array puede consultarse mediante el atributo length.
4.3.A.3 Cuando se crea un array utilizando la palabra clave new, todos sus elementos se inicializan con los valores predeterminados correspondientes al tipo de dato del elemento. El valor predeterminado para int es 0, para double es 0.0, para boolean es false, y para un tipo de referencia es null.
4.3.A.4 Se pueden utilizar listas inicializadoras para crear e inicializar arrays.
4.3.A.5 Los corchetes [ ] se utilizan para acceder y modificar un elemento en un array 1D mediante un índice.
4.3.A.6 Los valores de índice válidos para un array van desde 0 hasta una unidad menos que la longitud del array, inclusive. Utilizar un valor de índice fuera de este rango provocará una ArrayIndexOutOfBoundsException.

Fuente: College Board AP Course and Exam Description

Un array 数组 es una colección ordenada de tamaño fijo con valores del mismo tipo. Los índices van desde 0 hasta length - 1:

Un array unidimensional (una lista) con sus índices y límites

int[] nums = new int[5];        // five zeros
int[] vals = {3, 1, 4, 1, 5};   // initialized
int first = vals[0];            // 3
int n = vals.length;            // 5 (a field, not a method)

Acceder a un índice fuera del rango 0..length-1 lanza una ArrayIndexOutOfBoundsException.

Vocabulario Entrenar

Inglés	Chino	Pinyin
array/əˈreɪ/	数组	shù zǔ
Traverse/trəˈvɜːs/	遍历	biàn lì

4.4

Recorrer Cada Elemento de un Array

Syllabus

Objetivo de aprendizaje 4.4.A: Desarrollar código utilizado para recorrer los elementos en un arreglo unidimensional y determinar el resultado de estos recorridos.

4.4.A.1 Recorrer un arreglo ocurre cuando se utilizan sentencias de repetición para acceder a todos o a una secuencia ordenada de elementos en un arreglo.
4.4.A.2 Recorrer un arreglo con un bucle for indexado o un bucle while requiere que los elementos sean accedidos mediante sus índices.
4.4.A.3 El encabezado de un bucle for mejorado incluye una variable, denominada variable del bucle for mejorado. Para cada iteración del bucle for mejorado, la variable del bucle for mejorado recibe una copia de un elemento sin utilizar su índice.
4.4.A.4 Asignar un nuevo valor a la variable del bucle for mejorado no cambia el valor almacenado en el arreglo.
4.4.A.5 Cuando un arreglo almacena referencias a objetos, los atributos pueden modificarse llamando a métodos sobre la variable del bucle for mejorado. Esto no cambia las referencias a objetos almacenadas en el arreglo.
4.4.A.6 El código escrito utilizando un bucle for mejorado para recorrer elementos en un arreglo puede reescribirse utilizando un bucle for indexado o un bucle while.

Fuente: College Board AP Course and Exam Description

Recorra 遍历 un array con un bucle for (proporciona el índice) o un bucle enhanced for / for-each (proporciona cada valor, lectura-only):

for (int i = 0; i < a.length; i++) { a[i] *= 2; }   // can modify
for (int v : a) { System.out.println(v); }          // read each value

4.5

Algoritmos Estándar de Arrays

Syllabus

Objetivo de Aprendizaje 4.5.A: Desarrollar código para algoritmos estándar y originales para un contexto o especificación particular que involucre arreglos, y determinar el resultado de dichos algoritmos.

4.5.A.1 Existen algoritmos estándar que utilizan recorridos por arreglos para:
- determinar un valor mínimo o máximo
- calcular una suma o promedio
- determinar si al menos un elemento tiene una propiedad particular
- determinar si todos los elementos tienen una propiedad particular
- determinar la cantidad de elementos que tienen una propiedad particular
- acceder a todos los pares consecutivos de elementos
- determinar la presencia o ausencia de elementos duplicados
- desplazar o rotar elementos hacia la izquierda o derecha
- invertir el orden de los elementos

Fuente: College Board AP Course and Exam Description

Domine estos patrones: calcular una suma o promedio, encontrar el máximo/mínimo, contar elementos que cumplen una condición, buscar un duplicado, y invertir o desplazar elementos. Cada uno es un recorrido con un resultado acumulado:

int sum = 0;
for (int v : a) sum += v;
double avg = (double) sum / a.length;

4.6

Lectura de Datos desde un Archivo de Texto

Syllabus

Objetivo de aprendizaje 4.6.A: Desarrollar código para leer datos de un archivo de texto.

4.6.A.1 Un archivo es almacenamiento para datos que persisten cuando el programa no está en ejecución. Los datos en un archivo pueden recuperarse durante la ejecución del programa.
4.6.A.2 Un archivo puede conectarse al programa usando las clases File y Scanner.
4.6.A.3 Un archivo se puede abrir creando un objeto File, utilizando el nombre del archivo como argumento del constructor.
- File(String str) es el constructor File que acepta un nombre de archivo String para abrirlo con fines de lectura, donde str es la ruta de acceso para el archivo.
4.6.A.4 Al usar la clase File, es necesario indicar qué hacer si el archivo con el nombre proporcionado no puede ser abierto. Una forma de lograr esto es agregar throws IOException al encabezado del método que usa el archivo. Si el nombre de archivo es inválido, el programa terminará.
4.6.A.5 Las clases File e IOException son parte del paquete java.io. Debe usarse una instrucción import para hacer disponibles estas clases para su uso en el programa.
4.6.A.6 Los siguientes métodos y constructores de Scanner —incluyendo lo que hacen y cuándo se usan— forman parte de la Referencia rápida de Java:
- Scanner(File f) es el constructor Scanner que acepta un File para lectura.
- int nextInt() devuelve el siguiente int leído desde el archivo o fuente de entrada si está disponible. Si el siguiente int no existe o está fuera de rango, resultará en una InputMismatchException.
- double nextDouble() devuelve el siguiente double leído desde el archivo o fuente de entrada. Si el siguiente double no existe, resultará en una InputMismatchException.
- boolean nextBoolean() devuelve el siguiente boolean leído desde el archivo o fuente de entrada. Si el siguiente boolean no existe, resultará en una InputMismatchException.
- String nextLine() devuelve la siguiente línea de texto como un String leído desde el archivo o fuente de entrada; puede devolver la cadena vacía si se llama inmediatamente después de otro método Scanner que esté leyendo desde el archivo o fuente de entrada.
- String next() devuelve el siguiente String leído desde el archivo o fuente de entrada.
- boolean hasNext() devuelve true si hay un próximo elemento para leer en el archivo o fuente de entrada; de lo contrario, devuelve false.
- void close() cierra este escáner.
- Afirmación de exclusión: Aceptar entrada desde el teclado está fuera del alcance del curso y examen de AP Computer Science A.
4.6.A.7 Usar nextLine junto con otros métodos Scanner en la misma fuente de entrada a veces requiere código para ajustar por las diferentes formas en que los métodos manejan los espacios en blanco.
- Afirmación de exclusión: Escribir o analizar código que use tanto nextLine como otros métodos Scanner en la misma fuente de entrada está fuera del alcance del curso y examen de AP Computer Science A.
4.6.A.8 El siguiente método adicional de String —incluyendo lo que hace y cuándo se usa— forma parte de la Referencia rápida de Java:
- String[] split(String del) devuelve un array de String donde cada elemento es un subcadena de this String, que ha sido dividida alrededor de coincidencias de la expresión dada del.
- Afirmación de exclusión: El parámetro del usa un formato llamado expresión regular. Escribir o analizar código que use cualquiera de las propiedades especiales de las expresiones regulares (ej., \\*, \\.) está fuera del alcance del curso y examen de AP Computer Science A.
4.6.A.9 Se puede usar un bucle while para detectar si el archivo aún contiene elementos para leer usando el método hasNext como condición del bucle.
4.6.A.10 Un archivo debe cerrarse cuando el programa haya terminado de usarlo. El método close de Scanner se llama para cerrar el archivo.

Fuente: College Board AP Course and Exam Description

File e IOException se encuentran en java.io, por lo que un programa que lee un archivo necesita import java.io.*;. Abrir un archivo puede fallar (podría no existir), y Java le obliga a manejarlo; la forma más sencilla es añadir throws IOException al encabezado del método. Un Scanner luego lee el archivo línea por línea, usando hasNext... para verificar antes de leer:

import java.io.*;
...
public static void readFile() throws IOException {
    Scanner f = new Scanner(new File("data.txt"));
    while (f.hasNextLine()) {
        String line = f.nextLine();
    }
}

Leer tokens tipificados con nextInt(), nextDouble() o nextBoolean() lanza una InputMismatchException si el siguiente token es del tipo incorrecto; por ejemplo, llamar a nextInt() cuando el siguiente elemento en el archivo es la palabra cat.

4.7

Envolver un Número en un Objeto

Syllabus

Objetivo de aprendizaje 4.7.A: Desarrollar código para usar objetos Integer y Double a partir de sus contrapartes primitivas y determinar el resultado de utilizar estos objetos.

4.7.A.1 La clase Integer y la clase Double forman parte del paquete java.lang. Un objeto Integer es inmutable, lo que significa que una vez creado un objeto Integer, sus atributos no pueden ser modificados. Un objeto Double es inmutable, lo que significa que una vez creado un objeto Double, sus atributos no pueden ser modificados.
4.7.A.2 El autoboxing es la conversión automática que realiza el compilador de Java entre los tipos primitivos y sus respectivas clases wrapper (envoltura). Esto incluye la conversión de un int a un Integer y de un double a un Double. El compilador de Java aplica autoboxing cuando un valor primitivo:
- se pasa como parámetro a un método que espera un objeto de la clase wrapper correspondiente
- se asigna a una variable de la clase wrapper correspondiente
4.7.A.3 El unboxing es la conversión automática que realiza el compilador de Java desde la clase wrapper al tipo primitivo. Esto incluye la conversión de un Integer a un int y de un Double a un double. El compilador de Java aplica unboxing cuando un objeto de la clase wrapper:
- se pasa como parámetro a un método que espera un valor del tipo primitivo correspondiente
- se asigna a una variable del tipo primitivo correspondiente
4.7.A.4 El siguiente método de la clase Integer —incluyendo su función y cuándo se utiliza— forma parte de la Referencia rápida de Java:
- static int parseInt(String s) devuelve el argumento String como un int.
4.7.A.5 El siguiente método de la clase Double —incluyendo su función y cuándo se utiliza— forma parte de la Referencia rápida de Java:
- static double parseDouble(String s) devuelve el argumento String como un double.

Fuente: College Board AP Course and Exam Description

Un ArrayList almacena objetos, no primitivas, por lo que una primitiva se envuelve en un objeto: Integer envuelve int, Double envuelve double. Java hace esto mediante autoboxing 自动装箱 (int a Integer) y unboxing (de vuelta) automáticamente, así puede escribir list.add(5) y int x = list.get(0).

Vocabulario Entrenar

Inglés	Chino	Pinyin
autoboxing/ˌɔːtəʊˈbɒksɪŋ/	自动装箱	zì dòng zhuāng xiāng

4.8

Herramienta de ArrayList

Syllabus

Objetivo de aprendizaje 4.8.A: Desarrollar código para colecciones de objetos relacionados utilizando objetos ArrayList y determinar el resultado de llamar a métodos en estos objetos.

4.8.A.1 Un objeto ArrayList es mutable en tamaño y contiene referencias a objetos.
4.8.A.2 El constructor ArrayList() de ArrayList construye una lista vacía.
4.8.A.3 Java permite el tipo genérico ArrayList<E>, donde el parámetro de tipo E especifica el tipo de los elementos. Cuando se especifica ArrayList<E>, los tipos de los parámetros de referencia y del tipo de retorno al utilizar los métodos de ArrayList son del tipo E. Se prefiere ArrayList<E> sobre ArrayList. Por ejemplo, ArrayList<String> names = new ArrayList<String>(); permite que el compilador encuentre errores que de otro modo se encontrarían en tiempo de ejecución.
4.8.A.4 La clase ArrayList forma parte del paquete java.util. Debe utilizarse una sentencia import para hacer disponible esta clase para su uso en el programa.
4.8.A.5 Los siguientes métodos de ArrayList —incluyendo lo que hacen y cuándo se utilizan— forman parte de la Referencia rápida de Java:
- int size() devuelve el número de elementos en la lista.
- boolean add(E obj) añade obj al final de la lista; devuelve true.
- void add(int index, E obj) inserta obj en la posición index (0 <= index <= size), moviendo los elementos en la posición index y superiores hacia la derecha (añade 1 a sus índices) y aumenta el tamaño en 1.
- E get(int index) devuelve el elemento en la posición index de la lista.
- E set(int index, E obj) reemplaza el elemento en la posición index con obj; devuelve el elemento que anteriormente estaba en la posición index.
- E remove(int index) elimina el elemento de la posición index, moviendo los elementos en la posición index + 1 y superiores hacia la izquierda (resta 1 a sus índices) y disminuye el tamaño en 1; devuelve el elemento que anteriormente estaba en la posición index.
4.8.A.6 Los índices de un ArrayList comienzan en 0 y terminan en el número de elementos - 1.

Fuente: College Board AP Course and Exam Description

Qué es realmente un ArrayList

Un ArrayList 动态数组 crece y decrece según añade o elimina elementos. Declárelo con el tipo de elemento en <>:

ArrayList<String> names = new ArrayList<String>();
names.add("Amy");           // append
names.add(0, "Bob");        // insert at index
names.get(0);               // read
names.set(1, "Cara");       // replace
names.remove(0);            // delete, shifts the rest left
names.size();               // count (a method, unlike array.length)

Vocabulario Entrenar

Inglés	Chino	Pinyin
ArrayList/əˈreɪ lɪst/	动态数组	dòng tài shù zǔ
2D array/ˌtuː ˈdiː əˈreɪ/	二维数组	èr wéi shù zǔ
row-major order/rəʊ ˈmeɪdʒə ˈɔːdə/	行主序	xíng zhǔ xù

4.9

Recorrer Cada Elemento de un ArrayList

Syllabus

Objetivo de Aprendizaje 4.9.A: Desarrollar código utilizado para recorrer los elementos de un ArrayList y determinar los resultados de estos recorridos.

4.9.A.1 Recorrer un ArrayList ocurre cuando se utilizan sentencias de iteración o recursivas para acceder a todos o a una secuencia ordenada de los elementos en un ArrayList.
4.9.A.2 Eliminar elementos durante el recorrido de un ArrayList requiere el uso de técnicas especiales para evitar saltarse elementos.
4.9.A.3 Intentar acceder a un valor de índice fuera de su rango resultará en una IndexOutOfBoundsException.
4.9.A.4 Cambiar el tamaño de un ArrayList mientras se recorre utilizando un bucle for mejorado puede resultar en una ConcurrentModificationException. Por lo tanto, al usar un bucle for mejorado para recorrer un ArrayList, no debe agregar ni eliminar elementos.

Fuente: College Board AP Course and Exam Description

Recorra con un bucle de índice o un bucle for-each, igual que los arrays (usando size() y get(i)):

for (int i = 0; i < list.size(); i++) { ... list.get(i) ... }
for (String s : list) { ... }

Habilidad de examen: al eliminar elementos en un bucle de índice, ya sea recorra hacia atrás o no incremente i después de una eliminación; de lo contrario, el desplazamiento de elementos hacia la izquierda hará que salte uno. Y nunca agregue ni elimine elementos mientras recorre un ArrayList con un bucle for-each: cambiar su tamaño a mitad del bucle lanza una ConcurrentModificationException, por lo que use un bucle de índice (hacia atrás, como se indicó arriba) siempre que deba eliminar.

4.10

Algoritmos Estándar de ArrayList

Syllabus

Objetivo de Aprendizaje 4.10.A: Desarrollar código para algoritmos estándar y originales en un contexto o especificación particular que involucre objetos ArrayList y determinar el resultado de dichos algoritmos.

4.10.A.1 Existen algoritmos estándar de ArrayList que utilizan recorridos para:
- determinar un valor mínimo o máximo
- calcular una suma o promedio
- determinar si al menos un elemento posee una propiedad particular
- determinar si todos los elementos poseen una propiedad particular
- determinar la cantidad de elementos que tienen una propiedad particular
- acceder a todos los pares consecutivos de elementos
- determinar la presencia o ausencia de elementos duplicados
- desplazar o rotar elementos hacia la izquierda o derecha
- invertir el orden de los elementos
- insertar elementos
- eliminar elementos
4.10.A.2 Algunos algoritmos requieren que múltiples objetos String, arrays u ArrayList sean recorridos simultáneamente.

Fuente: College Board AP Course and Exam Description

Los mismos algoritmos que en los arrays: máximo/mínimo, conteo, suma; además de inserción y eliminación que los arrays no pueden hacer fácilmente. Una tarea común es eliminar todos los elementos que coinciden con una condición, manejando cuidadosamente el desplazamiento de índices.

4.11

Cuadrículas: Arrays Bidimensionales

Syllabus

Objetivo de aprendizaje 4.11.A: Desarrollar código utilizado para representar colecciones de datos relacionados mediante objetos de matriz bidimensional (2D).

4.11.A.1 Una matriz 2D se almacena como una matriz de matrices. Por lo tanto, la forma en que se crean e indexan las matrices 2D es similar a los objetos de matriz unidimensional (1D). El tamaño de una matriz 2D se establece en el momento de la creación y no puede cambiarse. Las matrices 2D pueden almacenar ya sea datos primitivos o datos de referencia de objetos.
- Declaración de exclusión: Los objetos de matriz 2D no rectangulares están fuera del alcance del curso y del examen de AP Computer Science A.
4.11.A.2 Cuando se crea una matriz 2D utilizando la palabra clave new, todos sus elementos se inicializan con los valores predeterminados correspondientes al tipo de dato del elemento. El valor predeterminado para int es 0, para double es 0.0, para boolean es false, y para un tipo de referencia es null.
4.11.A.3 La lista de inicializadores utilizada para crear e inicializar una matriz 2D consta de listas de inicializadores que representan matrices 1D; por ejemplo, int[][] arr2D = { {1, 2, 3}, {4, 5, 6} };.
4.11.A.4 Los corchetes [row][col] se utilizan para acceder y modificar un elemento en una matriz 2D. Con fines de examen, al acceder al elemento en arr[first][second], el primer índice se utiliza para las filas y el segundo índice se utiliza para las columnas.
4.11.A.5 Una única matriz que constituye una fila de una matriz 2D puede accederse utilizando el nombre de la matriz 2D y un solo conjunto de corchetes que contiene el índice de la fila.
4.11.A.6 El número de filas contenidas en una matriz 2D puede accederse a través del atributo length. Los valores de índice de fila válidos para una matriz 2D van desde 0 hasta uno menos que el número de filas o la longitud de la matriz, inclusive. El número de columnas contenidas en una matriz 2D puede accederse a través del atributo length de una de las filas. Los valores de índice de columna válidos para una matriz 2D van desde 0 hasta uno menos que el número de columnas o la longitud de cualquier fila dada de la matriz, inclusive. Por ejemplo, dada una matriz 2D llamada values, el número de filas es values.length y el número de columnas es values[0].length. Utilizar un valor de índice fuera de estos rangos resultará en un ArrayIndexOutOfBoundsException.

Fuente: College Board AP Course and Exam Description

Un array 2D 二维数组 es una cuadrícula (filas y columnas) – un array de arrays:

Un array bidimensional (una tabla) con índices de fila y columna

int[][] grid = new int[3][4];   // 3 rows, 4 columns
grid[r][c] = 7;                 // row r, column c
int rows = grid.length;         // 3
int cols = grid[0].length;      // 4

Explorar

Indexar una matriz 2D por fila y columna

Una matriz 2D es una cuadrícula direccionada por [row][col]. Mueva los índices y observe qué celda seleccionan: primero la fila, luego la columna, ambas contando desde 0.

4.12

Recorrer una Cuadrícula

Syllabus

Objetivo de Aprendizaje 4.12.A: Desarrollar código utilizado para recorrer los elementos en un arreglo 2D y determinar el resultado de estos recorridos.

4.12.A.1 Se utilizan sentencias de iteración anidadas para recorrer y acceder a todos o una secuencia ordenada de elementos en un arreglo 2D. Dado que los arreglos 2D se almacenan como arreglos de arreglos, la forma en que se recorren los arreglos 2D utilizando bucles for y bucles for mejorados es similar a la de los objetos de arreglos 1D. Las sentencias de iteración anidadas pueden escribirse para recorrer el arreglo 2D en orden por filas, orden por columnas o un orden definido únicamente. El orden por filas se refiere a un ordenamiento de los elementos del arreglo 2D donde el recorrido ocurre a través de cada fila, mientras que el recorrido en orden por columnas ocurre hacia abajo por cada columna.
4.12.A.2 El bucle exterior de un bucle for mejorado anidado utilizado para recorrer un arreglo 2D recorre las filas. Por lo tanto, la variable del bucle for mejorado debe ser el tipo de cada fila, que es un arreglo 1D. El bucle interior recorre una sola fila. Por lo tanto, la variable del bucle for mejorado interior debe ser del mismo tipo que los elementos almacenados en el arreglo 1D. Asignar un nuevo valor a la variable del bucle for mejorado no cambia el valor almacenado en el arreglo.

Fuente: College Board AP Course and Exam Description

Recorriendo un array 2-D

Visite cada celda con bucles anidados – el exterior sobre filas, el interior sobre columnas (orden fila-mayor 行主序):

for (int r = 0; r < grid.length; r++)
    for (int c = 0; c < grid[0].length; c++)
        System.out.print(grid[r][c]);

4.13

Algoritmos Estándar de Arrays 2D

Syllabus

Objetivo de Aprendizaje 4.13.A: Desarrollar código para algoritmos estándar y originales en un contexto o especificación particular que involucre arreglos 2D y determinar el resultado de estos algoritmos.

4.13.A.1 Existen algoritmos estándar que utilizan el recorrido de arreglos 2D para:
- determinar un valor mínimo o máximo de todos los elementos o para una fila, columna u otra subsección designada
- calcular la suma o promedio de todos los elementos o para una fila, columna u otra subsección designada
- determinar si al menos un elemento posee una propiedad particular en todo el arreglo 2D o en una fila, columna u otra subsección designada
- determinar si todos los elementos del arreglo 2D o de una fila, columna u otra subsección designada poseen una propiedad particular
- determinar el número de elementos del arreglo 2D o en una fila, columna u otra subsección designada que tienen una propiedad particular
- acceder a todos los pares consecutivos de elementos
- determinar la presencia o ausencia de elementos duplicados en el arreglo 2D o en una fila, columna u otra subsección designada
- desplazar o rotar elementos hacia la izquierda o derecha en una fila, o hacia arriba o abajo en una columna
- invertir el orden de los elementos en una fila o columna

Fuente: College Board AP Course and Exam Description

Tareas típicas de cuadrículas: sumar una fila o columna, encontrar el máximo en la cuadrícula, contar celdas coincidentes, o sumar una diagonal (donde r == c). Cada una es una traversia anidada con un resultado acumulado.

4.14

Encontrar un Valor: Búsqueda Lineal y Binaria

Syllabus

Objetivo de aprendizaje 4.14.A: Desarrollar código utilizado para algoritmos de búsqueda lineal con el fin de buscar información específica en una colección y determinar los resultados de la ejecución de una búsqueda.

4.14.A.1 Los algoritmos de búsqueda lineal son algoritmos estándar que revisan cada elemento en orden hasta que se encuentra el valor deseado o se han revisado todos los elementos del array o ArrayList. Los algoritmos de búsqueda lineal pueden iniciar el proceso de búsqueda desde cualquiera de los extremos del array o ArrayList.
4.14.A.2 Al aplicar algoritmos de búsqueda lineal a arrays bidimensionales (2D), se debe acceder a cada fila y luego aplicar la búsqueda lineal a cada fila del array 2D.

Fuente: College Board AP Course and Exam Description

Búsqueda binaria: dividir y vencer

Búsqueda lineal 线性搜索 revisa cada elemento sucesivamente; funciona en cualquier lista, tomando hasta $n$ pasos.
Búsqueda binaria 二分搜索 funciona solo en una lista ordenada: revise el medio, luego descarte la mitad que no puede contener el objetivo, repitiendo. Toma aproximadamente $\log_2 n$ pasos; mucho más rápido en datos grandes.

La búsqueda binaria reduce a la mitad el rango en cada paso

La búsqueda lineal revisa cada elemento sucesivamente hasta encontrar el objetivo

int lo = 0, hi = a.length - 1;
while (lo <= hi) {
    int mid = (lo + hi) / 2;
    if (a[mid] == target) return mid;
    else if (a[mid] < target) lo = mid + 1;
    else hi = mid - 1;
}

Habilidad de examen: la búsqueda binaria requiere datos ordenados; sepa cuántas comparaciones realiza y cómo se actualizan lo, hi, mid.

Ejemplo resuelto. Busque target = 40 en el array ordenado {3, 9, 14, 23, 31, 42, 55} (índices 0–6). Inicie lo=0, hi=6:

mid = (0+6)/2 = 3, a[3]=23 < 40, entonces lo = 4;
mid = (4+6)/2 = 5, a[5]=42 > 40, entonces hi = 4;
mid = (4+4)/2 = 4, a[4]=31 < 40, entonces lo = 5;
ahora lo (5) > hi (4), así que el bucle termina – 40 no está presente.

Cada paso redujo a la mitad el rango, por lo que incluso este error tomó solo tres comparaciones.

Explorar

Comparar búsqueda lineal y binaria

La búsqueda lineal verifica cada elemento por turno; la búsqueda binaria divide una lista ordenada a la mitad en cada paso. Observe cómo la búsqueda binaria alcanza el objetivo en muchas menos comparaciones.

Vocabulario Entrenar

Inglés	Chino	Pinyin
Linear search/ˈlɪnɪə sɜːtʃ/	线性搜索	xiàn xìng sōu suǒ
Binary search/ˈbaɪnəri sɜːtʃ/	二分搜索	èr fēn sōu suǒ
Selection sort/sɪˈlekʃn sɔːt/	选择排序	xuǎn zé pái xù

4.15

Ordenar Datos: Ordenamiento por Selección e Inserción

Syllabus

Objetivo de aprendizaje 4.15.A: Determinar el resultado de ejecutar cada paso de los algoritmos de ordenación para clasificar los elementos de una colección.

4.15.A.1 El ordenamiento por selección y el ordenamiento por inserción son algoritmos de ordenación iterativos que pueden utilizarse para clasificar elementos en un array o ArrayList.
4.15.A.2 El ordenamiento por selección selecciona repetidamente el elemento más pequeño (o más grande) de la parte no ordenada de la lista y lo intercambia en su posición correcta (y definitiva) dentro de la parte ordenada de la lista.
4.15.A.3 El ordenamiento por inserción inserta un elemento de la parte no ordenada de una lista en su posición correcta (pero no necesariamente definitiva) dentro de la parte ordenada de la lista, desplazando los elementos de dicha parte para hacer espacio al nuevo elemento.

Fuente: College Board AP Course and Exam Description

Ordenamiento por inserción

Ordenamiento burbuja, paso a paso

Ordenamiento por selección 选择排序 encuentra repetidamente el elemento restante más pequeño y lo intercambia en su lugar.
Ordenamiento por inserción 插入排序 crece un frente ordenado, insertando cada nuevo elemento donde corresponde.

Un ordenamiento por inserción, desplazando cada clave a su lugar paso a paso

Ambos son simples y tardan aproximadamente $n^2$ pasos en promedio; adecuados para arrays pequeños. Debe poder rastrear el array después de cada pasada.

Explorar

Observar cómo un algoritmo de ordenamiento clasifica una lista

Un ordenamiento reorganiza los elementos en orden. Pase paso a paso por la selección/inserción para ver cómo crece la región ordenada un elemento a la vez.

Vocabulario Entrenar

Inglés	Chino	Pinyin
Insertion sort/ɪnˈsɜːʃn sɔːt/	插入排序	chā rù pái xù

4.16

Métodos que se Llaman a Sí Mismos: Recursión

Syllabus

Objetivo de aprendizaje 4.16.A: Determinar el resultado de llamar a métodos recursivos.

4.16.A.1 Un método recursivo es un método que se llama a sí mismo. Los métodos recursivos contienen al menos un caso base, que detiene la recursión, y al menos una llamada recursiva. La recursión es otra forma de repetición.
4.16.A.2 Cada llamada recursiva tiene su propio conjunto de variables locales, incluyendo los parámetros. Los valores de los parámetros capturan el progreso de un proceso recursivo, al igual que los valores de las variables de control de bucle capturan el progreso de un bucle.
4.16.A.3 Cualquier solución recursiva puede replicarse mediante el uso de un enfoque iterativo y viceversa.
- Afirmación de exclusión: Escribir código recursivo está fuera del alcance del curso y examen de AP Computer Science A.

Fuente: College Board AP Course and Exam Description

Recursión y la pila de llamadas

Recursión 递归 es un método que se llama a sí mismo con una entrada más pequeña. Requiere un caso base 基本情况 que detenga las llamadas, y un caso recursivo que avance hacia la base:

public static int factorial(int n) {
    if (n <= 1) return 1;          // base case
    return n * factorial(n - 1);   // recursive case
}

Sin un caso base alcanzable, la recursión nunca se detiene (desbordamiento de pila).

La recursión y la iteración son intercambiables. Cualquier solución recursiva puede reescribirse con un bucle (enfoque iterativo), y cualquier bucle puede reescribirse con recursión; resuelven los mismos problemas. El factorial anterior tiene el mismo efecto que una versión iterativa:

public static int factorial(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) result *= i;   // same answer, no self-call
    return result;
}

Por tanto, la elección radica en la claridad, no en la capacidad: la recursión se lee naturalmente para problemas con estructura autosimilar (árboles, ordenamiento fusionado), mientras que la iteración evita el costo de memoria de apilar un marco de llamada por paso. El examen podría pedirle convertir uno en el otro.

Explorar

Desplegar una llamada recursiva

Un método recursivo se llama a sí mismo con una entrada más pequeña hasta alcanzar un caso base, luego los resultados se pliegan hacia arriba. Pase paso a paso para ver cómo las llamadas se apilan y se deshacen.

Vocabulario Entrenar

Inglés	Chino	Pinyin
Recursion/rɪˈkɜːʃn/	递归	dì guī
base case/beɪs keɪs/	基本情况	jī běn qíng kuàng

4.17

Búsqueda Recursiva y Ordenamiento Fusionado

Syllabus

Objetivo de aprendizaje 4.17.A: Determinar el resultado de la ejecución de algoritmos recursivos que utilizan cadenas o colecciones.

4.17.A.1 La recursión puede utilizarse para recorrer objetos String, arrays y objetos ArrayList.

Objetivo de aprendizaje 4.17.B: Determinar el resultado de cada iteración de un algoritmo de búsqueda binaria utilizado para buscar información en una colección.

4.17.B.1 Los datos deben estar ordenados para utilizar el algoritmo de búsqueda binaria. La búsqueda binaria comienza en el medio de un array u ArrayList ordenado y elimina la mitad del array u ArrayList en cada llamada recursiva hasta que se encuentra el valor deseado o se han eliminado todos los elementos.
4.17.B.2 La búsqueda binaria es generalmente más eficiente que la búsqueda lineal.
- Declaración de exclusión: Los algoritmos de búsqueda distintos a la búsqueda lineal y binaria están fuera del alcance del curso y examen de Ciencias de la Computación AP.
4.17.B.3 El algoritmo de búsqueda binaria puede escribirse de manera iterativa o recursiva.

Objetivo de aprendizaje 4.17.C: Determinar el resultado de cada iteración del algoritmo de ordenamiento por fusión (merge sort) cuando se utiliza para ordenar una colección.

4.17.C.1 El ordenamiento por fusión es un algoritmo de ordenamiento recursivo que puede utilizarse para ordenar elementos en un array u ArrayList.
- Declaración de exclusión: Los algoritmos de ordenamiento distintos a la selección, inserción y fusión (merge sort) están fuera del alcance del curso y examen de Ciencias de la Computación AP.
4.17.C.2 El ordenamiento por fusión divide repetidamente un array en subarrays más pequeños hasta que cada subarray tiene un solo elemento, y luego fusiona recursivamente los subarrays ordenados de vuelta juntos en orden ascendente para formar el array final ordenado.

Fuente: College Board AP Course and Exam Description

Ordenamiento fusionado: dividir, luego fusionar

La recursión potencia algoritmos eficientes. La búsqueda binaria puede escribirse recursivamente (buscar en la mitad correcta). El ordenamiento fusionado 归并_recort divide el array a la mitad, ordena cada mitad recursivamente, y luego fusiona las dos mitades ordenadas; toma aproximadamente $n\log_2 n$ pasos, mucho más rápido que el ordenamiento por selección o inserción en datos grandes.

El ordenamiento fusionado divide el array en elementos individuales, luego fusiona las mitades ordenadas hacia arriba

Ejemplo resuelto. Rastree factorial(4). Cada llamada delega a una más pequeña: factorial(4) = 4 * factorial(3) = 4 * 3 * factorial(2) = 4 * 3 * 2 * factorial(1). factorial(1) alcanza el caso base y retorna 1, así que las llamadas se descomponen hacia adentro: 2 * 1 = 2, luego 3 * 2 = 6, luego 4 * 6 = 24. Escribir cada llamada sobre su valor de retorno es la forma confiable de rastrear la recursión.

Habilidad de examen: rastree un método recursivo escribiendo cada llamada y su valor de retorno, y sepa que la eficiencia del ordenamiento fusionado ($n\log n$) supera a los ordenamientos simples de $n^2$.

Vocabulario Entrenar

Inglés	Chino	Pinyin
Merge sort/mɜːdʒ sɔːt/	归并排序	guī bìng pái xù

4.17

Consejos para el Examen

Pense en ambos beneficios y perjuicios de recopilar datos; esta unidad se evalúa mediante justificaciones escritas breves, no código.
Proteja la información de identificación personal (PII) y explique riesgos de privacidad y seguridad en contexto.
Nomenre perjuicios reales: brechas de datos, vigilancia y sesgo algorítmico derivado de datos no representativos.
Respete la propiedad intelectual y las licencias al reutilizar código o datos.
Proporcione una respuesta específica y fundamentada; una vaga afirmación de "podría ser malo" no obtiene puntos.

Lecciones interactivas sobre este tema

Trátalo paso a paso, con ejercicios de verificación instantánea.

Exámenes Anteriores

Más temas en AP Ciencias de la Computación A