Coleções de Dados

Ciência da Computação A do AP · Tópico 4

Videoaula para este tópico Abrir a página do vídeo

4.1

Ética na Coleta de Dados

Programa

Objetivo de Aprendizagem 4.1.A: Explicar os riscos à privacidade decorrentes da coleta e armazenamento de dados pessoais em sistemas computacionais.

4.1.A.1 Ao usar um computador, a privacidade pessoal está em risco. Ao desenvolver novos programas, programadores devem tentar salvaguardar a privacidade pessoal do usuário.

Objetivo de Aprendizagem 4.1.B: Explicar a importância de reconhecer a qualidade dos dados e potenciais problemas ao usar um conjunto de dados.

4.1.B.1 Viés algorítmico descreve erros sistêmicos e repetitivos em um programa que criam resultados injustos para um grupo específico de usuários.
4.1.B.2 Programadores devem estar cientes do método de coleta do conjunto de dados e do potencial de viés ao usar esse método antes de usar os dados para extrapolar novas informações ou tirar conclusões.
4.1.B.3 Alguns conjuntos de dados são incompletos ou contêm dados imprecisos. O uso de tais dados no desenvolvimento ou uso de um programa pode causar o funcionamento incorreto ou ineficiente do programa.

Objetivo de Aprendizagem 4.1.C: Identificar um conjunto de dados apropriado para usar a fim de resolver um problema ou responder a uma pergunta específica.

4.1.C.1 Os conteúdos de um conjunto de dados podem estar relacionados a uma pergunta ou tópico específico e podem não ser adequados para fornecer respostas corretas ou extrapolar informações para uma pergunta ou tópico diferente.

Fonte: College Board AP Course and Exam Description

racks de servidores em um centro de dados – grandes coleções de dados levantam questões éticas sobre coleta e uso

Programas que coletam dados levantam questões de privacidade 隐私 e consentimento 同意. Colete apenas o necessário, proteja os dados e seja honesto sobre seu uso. Dados podem carregar viés 偏见 se não representarem todos com justiça, levando a resultados injustos – uma responsabilidade que vem com armazenar informações.

Vocabulário Treinar

Inglês	Chinês	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 Que Precisamos de Estruturas de Dados

Programa

Objetivo de Aprendizagem 4.2.A: Representar padrões e algoritmos que envolvem conjuntos de dados encontrados no cotidiano usando linguagem escrita ou diagramas.

4.2.A.1 Um conjunto de dados é uma coleção de peças específicas de informação ou dados.
4.2.A.2 Conjuntos de dados podem ser manipulados e analisados para resolver um problema ou responder a uma pergunta. Ao analisar conjuntos de dados, os valores dentro do conjunto são acessados e utilizados um de cada vez e depois processados de acordo com o resultado desejado.
4.2.A.3 Dados podem ser representados em um diagrama usando um gráfico ou tabela. Este visual pode ser usado para planejar o algoritmo que será usado para manipular os dados.

Fonte: College Board AP Course and Exam Description

Um arquivo de arquivos: coleções armazenam muitos valores sob um único nome para que algoritmos possam processá-los

Uma única variável segura um valor; problemas reais precisam armazenar muitos valores relacionados – uma lista de alunos, pixels, leituras de sensores. Uma estrutura de dados 数据结构 organiza uma coleção para podermos armazenar, encontrar e processar itens eficientemente. O curso AP usa três: o array, o ArrayList e o array 2D.

Vocabulário Treinar

Inglês	Chinês	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.3

Criando e Lendo um Array

Programa

Objetivo de Aprendizagem 4.3.A: Desenvolver código usado para representar coleções de dados relacionados usando objetos array unidimensional (1D).

4.3.A.1 Um array armazena múltiplos valores do mesmo tipo. Os valores podem ser valores primitivos ou referências de objeto.
4.3.A.2 O comprimento de um array é estabelecido no momento da criação e não pode ser alterado. O comprimento de um array pode ser acessado através do atributo length.
4.3.A.3 Quando um array é criado usando a palavra-chave new, todos os seus elementos são inicializados com os valores padrão para o tipo de dado do elemento. O valor padrão para int é 0, para double é 0.0, para boolean é false, e para um tipo de referência é null.
4.3.A.4 Listas de inicialização podem ser usadas para criar e inicializar arrays.
4.3.A.5 Colchetes [ ] são usados para acessar e modificar um elemento em um array 1D usando um índice.
4.3.A.6 Os valores de índice válidos para um array variam de 0 a um menos que o comprimento do array, inclusive. Usar um valor de índice fora desse intervalo resultará em uma ArrayIndexOutOfBoundsException.

Fonte: College Board AP Course and Exam Description

Um array 数组 é uma coleção ordenada de tamanho fixo de valores do mesmo tipo. Os índices variam de 0 a length - 1:

Um array unidimensional (uma lista) com seus índices e limites

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)

Acessar um índice fora 0..length-1 lança um ArrayIndexOutOfBoundsException.

Vocabulário Treinar

Inglês	Chinês	Pinyin
array/əˈreɪ/	数组	shù zǔ

4.4

Visitando Cada Elemento de um Array

Programa

Objetivo de Aprendizagem 4.4.A: Desenvolver código usado para percorrer os elementos em um array 1D e determinar o resultado desses percursos.

4.4.A.1 Percorrer um array ocorre quando instruções de repetição são usadas para acessar todos ou uma sequência ordenada de elementos em um array.
4.4.A.2 Percorrer um array com um loop indexado for ou loop while requer que os elementos sejam acessados usando seus índices.
4.4.A.3 Um cabeçalho de loop melhorado for inclui uma variável, referida como a variável de loop melhorado for. Para cada iteração do loop melhorado for, a variável de loop melhorado for recebe uma cópia de um elemento sem usar seu índice.
4.4.A.4 Atribuir um novo valor à variável de loop melhorado for não altera o valor armazenado no array.
4.4.A.5 Quando um array armazena referências de objeto, os atributos podem ser modificados chamando métodos na variável de loop melhorado for. Isso não altera as referências de objeto armazenadas no array.
4.4.A.6 Código escrito usando um loop melhorado for para percorrer elementos em um array pode ser reescrito usando um loop indexado for ou um loop while.

Fonte: College Board AP Course and Exam Description

Traverse 遍历 um array com um loop for (dá o índice) ou um loop enhanced for / for-each (dá cada valor, leitura-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

Vocabulário Treinar

Inglês	Chinês	Pinyin
Traverse/trəˈvɜːs/	遍历	biàn lì

4.5

Algoritmos Padrão de Array

Programa

Objetivo de Aprendizagem 4.5.A: Desenvolver código para algoritmos padrão e originais para um contexto ou especificidade particular que envolva arrays e determinar o resultado desses algoritmos.

4.5.A.1 Existem algoritmos padrão que utilizam percursos de array para:
- determinar um valor mínimo ou máximo
- computar uma soma ou média
- determinar se pelo menos um elemento possui uma propriedade particular
- determinar se todos os elementos possuem uma propriedade particular
- determinar o número de elementos que possuem uma propriedade particular
- acessar todosos pares consecutivos de elementos
- determinar a presença ou ausência de elementos duplicados
- deslocar ou rotacionar elementos para a esquerda ou direita
- inverter a ordem dos elementos

Fonte: College Board AP Course and Exam Description

Domine esses padrões: calcular uma soma ou média, encontrar o max/mín, contar itens atendendo a uma condição, verificar uma duplicata, e reverter ou deslocar elementos. Cada um é uma travessia com um resultado acumulado:

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

4.6

Lendo Dados de um Arquivo de Texto

Programa

Objetivo de Aprendizagem 4.6.A: Desenvolver código para ler dados de um arquivo de texto.

4.6.A.1 Um arquivo é armazenamento para dados que persiste quando o programa não está em execução. Os dados em um arquivo podem ser recuperados durante a execução do programa.
4.6.A.2 Um arquivo pode ser conectado ao programa usando as classes File e Scanner.
4.6.A.3 Um arquivo pode ser aberto criando um objeto File, usando o nome do arquivo como argumento do construtor.
- File(String str) é o construtor File que aceita um nome de arquivo String para abrir para leitura, onde str é o caminho de acesso para o arquivo.
4.6.A.4 Ao usar a classe File, é necessário indicar o que fazer se o arquivo com o nome fornecido não puder ser aberto. Uma maneira de fazer isso é adicionar throws IOException ao cabeçalho do método que usa o arquivo. Se o nome do arquivo for inválido, o programa será encerrado.
4.6.A.5 As classes File e IOException fazem parte do pacote java.io. Uma instrução import deve ser usada para tornar essas classes disponíveis para uso no programa.
4.6.A.6 Os seguintes métodos e construtor Scanner — incluindo o que eles fazem e quando são usados — fazem parte da Referência Rápida do Java:
- Scanner(File f) é o construtor Scanner que aceita um File para leitura.
- int nextInt() retorna o próximo int lido do arquivo ou fonte de entrada se disponível. Se o próximo int não existir ou estiver fora do intervalo, resultará em uma InputMismatchException.
- double nextDouble() retorna o próximo double lido do arquivo ou fonte de entrada. Se o próximo double não existir, resultará em uma InputMismatchException.
- boolean nextBoolean() retorna o próximo boolean lido do arquivo ou fonte de entrada. Se o próximo boolean não existir, resultará em uma InputMismatchException.
- String nextLine() retorna a próxima linha de texto como um String lido do arquivo ou fonte de entrada; pode retornar a string vazia se chamado imediatamente após outro método Scanner que está lendo do arquivo ou fonte de entrada.
- String next() retorna o próximo String lido do arquivo ou fonte de entrada.
- boolean hasNext() retorna true se houver um próximo item para ler no arquivo ou fonte de entrada; retorna false caso contrário.
- void close() fecha este scanner.
- Declaração de exclusão: Aceitar entrada do teclado está fora do escopo do curso e exame AP Computer Science A.
4.6.A.7 Usar nextLine e outros métodos Scanner juntos na mesma fonte de entrada às vezes requer código para ajustar pelas diferentes maneiras que os métodos lidam com espaços em branco.
- Declaração de exclusão: Escrever ou analisar código que usa tanto nextLine quanto outros métodos Scanner na mesma fonte de entrada está fora do escopo do curso e exame AP Computer Science A.
4.6.A.8 O seguinte método adicional String — incluindo o que ele faz e quando é usado — faz parte da Referência Rápida do Java:
- String[] split(String del) retorna um array de String onde cada elemento é um subarray de this String, que foi dividido em torno de correspondências da expressão dada del.
- Declaração de exclusão: O parâmetro del usa um formato chamado expressão regular. Escrever ou analisar código que usa qualquer uma das propriedades especiais de expressões regulares (p. ex., \\*, \\.) está fora do escopo do curso e exame AP Computer Science A.
4.6.A.9 Um loop melhorado while pode ser usado para detectar se o arquivo ainda contém elementos para ler usando o método hasNext como condição do loop.
4.6.A.10 Um arquivo deve ser fechado quando o programa termina de usá-lo. O método close de Scanner é chamado para fechar o arquivo.

Fonte: College Board AP Course and Exam Description

File e IOException vivem em java.io, então um programa que lê um arquivo precisa de import java.io.*;. Abrir um arquivo pode falhar (ele pode não existir), e o Java obriga você a lidar com isso – a maneira mais simples é adicionar throws IOException ao cabeçalho do método. Um Scanner então lê o arquivo linha por linha, usando hasNext... para testar antes de ler:

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

Lendo tokens tipados com nextInt(), nextDouble(), ou nextBoolean() lança um InputMismatchException se o próximo token for do tipo errado – por exemplo, chamar nextInt() quando a próxima coisa no arquivo é a palavra cat.

4.7

Envolvendo um Número em um Objeto

Programa

Objetivo de Aprendizagem 4.7.A: Desenvolver código para usar objetos Integer e Double a partir de seus equivalentes primitivos e determinar o resultado do uso desses objetos.

4.7.A.1 As classes Integer e Double fazem parte do pacote java.lang. Um objeto Integer é imutável, o que significa que, uma vez criado um objeto Integer, seus atributos não podem ser alterados. Um objeto Double é imutável, o que significa que, uma vez criado um objeto Double, seus atributos não podem ser alterados.
4.7.A.2 Autoboxing é a conversão automática que o compilador Java faz entre tipos primitivos e suas respectivas classes wrapper de objeto. Isso inclui converter um int para um Integer e um double para um Double. O compilador Java aplica autoboxing quando um valor primitivo é:
- passado como parâmetro para um método que espera um objeto da classe wrapper correspondente
- atribuído a uma variável da classe wrapper correspondente
4.7.A.3 Unboxing é a conversão automática que o compilador Java faz da classe wrapper para o tipo primitivo. Isso inclui converter um Integer para um int e um Double para um double. O compilador Java aplica unboxing quando um objeto de classe wrapper é:
- passado como parâmetro para um método que espera um valor do tipo primitivo correspondente
- atribuído a uma variável do tipo primitivo correspondente
4.7.A.4 O seguinte método de classe Integer — incluindo o que ele faz e quando é usado — faz parte da Referência Rápida do Java:
- static int parseInt(String s) retorna o argumento String como um int.
4.7.A.5 O seguinte método de classe Double — incluindo o que ele faz e quando é usado — faz parte da Referência Rápida do Java:
- static double parseDouble(String s) retorna o argumento String como um double.

Fonte: College Board AP Course and Exam Description

Um ArrayList armazena objetos, não primitivos, então um primitivo é envolvido em um objeto: Integer envolve int, Double envolve double. Java faz isso automaticamente com autoboxing 自动装箱 (int para Integer) e unboxing (para trás novamente), então você pode escrever list.add(5) e int x = list.get(0).

Vocabulário Treinar

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

4.8

O Kit de Ferramentas ArrayList

Programa

Objetivo de Aprendizagem 4.8.A: Desenvolver código para coleções de objetos relacionados usando objetos ArrayList e determinar o resultado de chamar métodos nesses objetos.

4.8.A.1 Um objeto ArrayList é mutável em tamanho e contém referências de objeto.
4.8.A.2 O construtor ArrayList ArrayList() constrói uma lista vazia.
4.8.A.3 O Java permite o tipo genérico ArrayList<E>, onde o parâmetro de tipo E especifica o tipo dos elementos. Quando ArrayList<E> é especificado, os tipos dos parâmetros de referência e tipo de retorno ao usar os métodos ArrayList são do tipo E. ArrayList<E> é preferível a ArrayList. Por exemplo, ArrayList<String> names = new ArrayList<String>(); permite que o compilador encontre erros que seriam encontrados apenas em tempo de execução.
4.8.A.4 A classe ArrayList faz parte do pacote java.util. Uma instrução import deve ser usada para tornar esta classe disponível para uso no programa.
4.8.A.5 Os seguintes métodos ArrayList — incluindo o que eles fazem e quando são usados — fazem parte do Java Quick Reference:
- int size() retorna o número de elementos na lista.
- boolean add(E obj) adiciona obj ao final da lista; retorna true.
- void add(int index, E obj) insere obj na posição index (0 <= index <= size), movendo os elementos nas posições index e superiores para a direita (soma 1 aos seus índices) e soma 1 ao tamanho.
- E get(int index) retorna o elemento na posição index na lista.
- E set(int index, E obj) substitui o elemento na posição index por obj; retorna o elemento anteriormente na posição index.
- E remove(int index) remove o elemento da posição index, movendo os elementos nas posições index + 1 e superiores para a esquerda (subtrai 1 dos seus índices) e subtrai 1 do tamanho; retorna o elemento anteriormente na posição index.
4.8.A.6 Os índices para um ArrayList começam em 0 e terminam no número de elementos - 1.

Fonte: College Board AP Course and Exam Description

O que um ArrayList realmente é

Um ArrayList (array dinâmico) expande e encolhe conforme você adiciona ou remove itens. Declare-o com o tipo de elemento em <>:

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)

4.9

Visitando Cada Elemento de um ArrayList

Programa

Objetivo de Aprendizagem 4.9.A: Desenvolver código usado para percorrer os elementos de um ArrayList e determinar os resultados desses percursos.

4.9.A.1 Percorrer um ArrayList ocorre quando instruções de iteração ou recursivas são usadas para acessar todos ou uma sequência ordenada dos elementos em um ArrayList.
4.9.A.2 Excluir elementos durante um percurso de um ArrayList requer o uso de técnicas especiais para evitar pular elementos.
4.9.A.3 Tentar acessar um valor de índice fora do seu intervalo resultará em uma IndexOutOfBoundsException.
4.9.A.4 Alterar o tamanho de um ArrayList enquanto o percorre usando um loop melhorado for pode resultar em uma ConcurrentModificationException. Portanto, ao usar um loop melhorado for para percorrer um ArrayList, você não deve adicionar ou remover elementos.

Fonte: College Board AP Course and Exam Description

Percorra usando um loop por índice ou um loop for-each, assim como os arrays (use size() e get(i)):

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

Habilidade para prova: ao remover itens em um loop por índice, faça o loop de trás para frente ou não increment i após uma remoção – caso contrário, a remoção desloca os elementos para a esquerda e você pulará um. E nunca adicione ou remova elementos enquanto percorre um ArrayList com um loop for-each: alterar seu tamanho durante o loop gera um ConcurrentModificationException, então use um loop por índice (de trás para frente, como acima) sempre que precisar remover.

4.10

Algoritmos Padrão de ArrayList

Programa

Objetivo de Aprendizagem 4.10.A: Desenvolver código para algoritmos padrão e originais para um contexto ou especificidade particular que envolvam objetos ArrayList e determinar o resultado desses algoritmos.

4.10.A.1 Existem algoritmos ArrayList padrão que utilizam travessias para:
- determinar um valor mínimo ou máximo
- computar uma soma ou média
- determinar se pelo menos um elemento possui uma propriedade particular
- determinar se todos os elementos possuem uma propriedade particular
- determinar o número de elementos que possuem uma propriedade particular
- acessar todosos pares consecutivos de elementos
- determinar a presença ou ausência de elementos duplicados
- deslocar ou rotacionar elementos para a esquerda ou direita
- inverter a ordem dos elementos
- inserir elementos
- excluir elementos
4.10.A.2 Alguns algoritmos requerem múltiplos String, array, ou objetos ArrayList a serem percorridos simultaneamente.

Fonte: College Board AP Course and Exam Description

Os mesmos algoritmos dos arrays – máximo/mínimo, contagem, soma – mais inserção e exclusão que os arrays não conseguem fazer facilmente. Uma tarefa comum é remover todos os elementos que correspondem a uma condição, manuseando cuidadosamente o deslocamento do índice.

4.11

Matrizes: Arrays Bidimensionais

Programa

Objetivo de Aprendizagem 4.11.A: Desenvolver código usado para representar coleções de dados relacionados usando objetos array bidimensional (2D).

4.11.A.1 Um array 2D é armazenado como um array de arrays. Portanto, a forma como arrays 2D são criados e indexados é semelhante a objetos array unidimensionais (1D). O tamanho de um array 2D é estabelecido no momento da criação e não pode ser alterado. Arrays 2D podem armazenar dados primitivos ou dados de referência de objeto.
- Declaração de exclusão: Objetos array 2D não retangulares estão fora do escopo do curso e exame AP Computer Science A.
4.11.A.2 Quando um array 2D é criado usando a palavra-chave new, todos os seus elementos são inicializados com os valores padrão para o tipo de dado do elemento. O valor padrão para int é 0, para double é 0.0, para boolean é false, e para um tipo de referência é null.
4.11.A.3 A lista de inicialização usada para criar e inicializar um array 2D consiste em listas de inicialização que representam arrays 1D; por exemplo, int[][] arr2D = { {1, 2, 3}, {4, 5, 6} };.
4.11.A.4 Os colchetes [row][col] são usados para acessar e modificar um elemento em um array 2D. Para fins de exame, ao acessar o elemento em arr[first][second], o primeiro índice é usado para linhas, o segundo índice é usado para colunas.
4.11.A.5 Um único array que é uma linha de um array 2D pode ser acessado usando o nome do array 2D e um único par de colchetes contendo o índice da linha.
4.11.A.6 O número de linhas contidas em um array 2D pode ser acessado através do atributo length. Os valores de índice de linha válidos para um array 2D são 0 até um menos que o número de linhas ou o comprimento do array, inclusive. O número de colunas contidas em um array 2D pode ser acessado através do atributo length de uma das linhas. Os valores de índice de coluna válidos para um array 2D são 0 até um menos que o número de colunas ou o comprimento de qualquer linha dada do array, inclusive. Por exemplo, dado um array 2D chamado values, o número de linhas é values.length e o número de colunas é values[0].length. Usar um valor de índice fora desses intervalos resultará em um erro de ArrayIndexOutOfBoundsException.

Fonte: College Board AP Course and Exam Description

Um array 2D (matriz bidimensional) é uma grade (linhas e colunas) – um array de arrays:

Uma matriz bidimensional (uma tabela) com índices de linha e coluna

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 uma matriz 2D por linha e coluna

Uma matriz 2D é uma grade endereçada por [row][col]. Mova os índices e observe qual célula eles selecionam — linha primeiro, depois coluna, ambas contando a partir de 0.

4.12

Percorrendo uma Grade

Programa

Objetivo de Aprendizagem 4.12.A: Desenvolver código usado para percorrer os elementos em um array 2D e determinar o resultado desses percursos.

4.12.A.1 Estruturas de iteração aninhadas são usadas para percorrer e acessar todos ou uma sequência ordenada de elementos em um array 2D. Como arrays 2D são armazenados como arrays de arrays, a forma como arrays 2D são percorridos usando loops for e loops enhanced for é semelhante a objetos array 1D. Estruturas de iteração aninhadas podem ser escritas para percorrer o array 2D em ordem row-major (maioria por linha), ordem column-major (maioria por coluna) ou uma ordem definida unicamente. Ordem row-major refere-se a uma ordenação de elementos de array 2D onde a traversa ocorre através de cada linha, enquanto a traversa column-major ocorre para baixo em cada coluna.
4.12.A.2 O loop externo de um loop aninhado enhanced for usado para percorrer um array 2D percorre as linhas. Portanto, a variável do loop enhanced for deve ser o tipo de cada linha, que é um array 1D. O loop interno percorre uma única linha. Portanto, a variável do loop enhanced interno for deve ser do mesmo tipo que os elementos armazenados no array 1D. Atribuir um novo valor à variável do loop enhanced for não altera o valor armazenado no array.

Fonte: College Board AP Course and Exam Description

Percorrendo um array 2-D

Visite cada célula com loops aninhados – o externo sobre linhas, o interno sobre colunas (ordem row-major 行主序):

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 Padrão de Array 2D

Programa

Objetivo de Aprendizagem 4.13.A: Desenvolver código para algoritmos padrão e originais para um contexto ou especificidade particular que envolve arrays 2D e determinar o resultado desses algoritmos.

4.13.A.1 Existem algoritmos padrão que utilizam percursos de array 2D para:
- determinar um valor mínimo ou máximo de todos os elementos ou para uma linha, coluna ou outra subseção designada
- computar uma soma ou média de todos os elementos ou para uma linha, coluna ou outra subseção designada
- determinar se pelo menos um elemento tem uma propriedade particular em todo o array 2D ou para uma linha, coluna ou outra subseção designada
- determinar se todos os elementos do array 2D ou uma linha, coluna ou outra subseção designada têm uma propriedade particular
- determinar o número de elementos no array 2D ou em uma linha, coluna ou outra subseção designada que possuem uma propriedade particular
- acessar todosos pares consecutivos de elementos
- determinar a presença ou ausência de elementos duplicados no array 2D ou em uma linha, coluna ou outra subseção designada
- deslocar ou rotacionar elementos em uma linha para a esquerda ou direita ou em uma coluna para cima ou para baixo
- inverter a ordem dos elementos em uma linha ou coluna

Fonte: College Board AP Course and Exam Description

Tarefas típicas de grade: somar uma linha ou coluna, encontrar o máximo na grade, contar células correspondentes ou somar uma diagonal (onde r == c). Cada uma é uma travessia aninhada com um resultado acumulado.

4.14

Encontrando um Valor: Busca Linear e Binária

Programa

Objetivo de Aprendizagem 4.14.A: Desenvolver código usado para algoritmos de busca linear para buscar informações específicas em uma coleção e determinar os resultados da execução de uma busca.

4.14.A.1 Algoritmos de busca linear são algoritmos padrão que verificam cada elemento na ordem até que o valor desejado seja encontrado ou todos os elementos no array ou ArrayList tenham sido verificados. Algoritmos de busca linear podem iniciar o processo de busca desde qualquer extremidade do array ou ArrayList.
4.14.A.2 Ao aplicar algoritmos de busca linear em arrays 2D, cada linha deve ser acessada e então a busca linear aplicada a cada linha do array 2D.

Fonte: College Board AP Course and Exam Description

Busca binária: divida pela metade e conquiste

Busca linear 线性搜索 verifica cada elemento sucessivamente – funciona em qualquer lista, levando até $n$ passos.
Busca binária 二分搜索 funciona apenas em uma lista ordenada: verifica o meio, depois descarta a metade que não pode conter o alvo, repetindo. Leva cerca de $\log_2 n$ passos – muito mais rápido em grandes quantidades de dados.

A busca binária reduz pela metade o intervalo em cada passo

A busca linear verifica cada elemento sucessivamente até encontrar o alvo

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;
}

Habilidade de prova: a busca binária requer dados ordenados; saiba quantas comparações ela faz e como lo, hi, mid são atualizados.

Exemplo resolvido. Buscar target = 40 no 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, então lo = 4;
mid = (4+6)/2 = 5, a[5]=42 > 40, então hi = 4;
mid = (4+4)/2 = 4, a[4]=31 < 40, então lo = 5;
agora lo (5) > hi (4), então o loop termina – 40 não está presente.

Cada passo reduziu o intervalo pela metade, então mesmo esse erro levou apenas três comparações.

Explorar

Comparar busca linear e binária

Busca linear verifica cada elemento por vez; busca binária divide uma lista ordenada pela metade a cada etapa. Observe a busca binária alcançar o alvo em muitas menos comparações.

Vocabulário Treinar

Inglês	Chinês	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

Colocando Dados em Ordem: Ordenação por Seleção e Inserção

Programa

Objetivo de Aprendizagem 4.15.A: Determinar o resultado da execução de cada etapa de algoritmos de ordenação para ordenar os elementos de uma coleção.

4.15.A.1 Selection sort (ordenação por seleção) e insertion sort (ordenação por inserção) são algoritmos de ordenação iterativos que podem ser usados para ordenar elementos em um array ou ArrayList.
4.15.A.2 Selection sort seleciona repetidamente o menor (ou maior) elemento da porção não ordenada da lista e o troca para sua posição correta (e final) na porção ordenada da lista.
4.15.A.3 Insertion sort insere um elemento da porção não ordenada de uma lista em sua posição correta (mas não necessariamente final) na porção ordenada da lista, deslocando elementos da porção ordenada para fazer espaço para o novo elemento.

Fonte: College Board AP Course and Exam Description

Ordenação por Inserção

Ordenação bolha, passo a passo

Ordenação por Seleção 选择排序 encontra repetidamente o menor elemento restante e o troca para a posição correta.
Ordenação por Inserção 插入排序 cresce uma parte frontal ordenada, inserindo cada novo elemento onde ele pertence.

Uma ordenação por inserção, deslocando cada chave para o lugar certo, passada após passada

Ambas são simples e levam cerca de $n^2$ passos em média – adequadas para pequenos arrays. Saiba rastrear o array após cada passada.

Explorar

Observar um algoritmo de ordenação classificar uma lista

Uma ordenação rearranja elementos em ordem. Avance pela seleção/ordenação de inserção para ver a região ordenada crescer um elemento de cada vez.

Vocabulário Treinar

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

4.16

Métodos que se Chamam Recursivamente: Recursão

Programa

Objetivo de Aprendizagem 4.16.A: Determinar o resultado de chamadas de métodos recursivos.

4.16.A.1 Um método recursivo é um método que se chama a si mesmo. Métodos recursivos contêm pelo menos um caso base, que interrompe a recursão, e pelo menos uma chamada recursiva. Recursão é outra forma de repetição.
4.16.A.2 Cada chamada recursiva possui seu próprio conjunto de variáveis locais, incluindo os parâmetros. Os valores dos parâmetros capturam o progresso de um processo recursivo, assim como os valores das variáveis de controle de loop capturam o progresso de um loop.
4.16.A.3 Qualquer solução recursiva pode ser replicada através do uso de uma abordagem iterativa e vice-versa.
- Declaração de exclusão: Escrever código recursivo está fora do escopo do curso e exame AP Computer Science A.

Fonte: College Board AP Course and Exam Description

Recursão e a pilha de chamadas

Recursão 递归 é um método que se chama com uma entrada menor. Ela precisa de um caso base 基本情况 que pare as chamadas, e de um caso recursivo que avance em direção à base:

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

Sem um caso base alcançável, a recursão nunca para (um estouro de pilha).

Recursão e iteração são intercambiáveis. Qualquer solução recursiva pode ser reescrita com um laço (abordagem iterativa), e qualquer loop pode ser reescrito com recursão - eles resolvem os mesmos problemas. A factorial acima tem efeito idêntico a uma versão 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;
}

Então a escolha trata-se de clareza, não capacidade: a recursão lê naturalmente para problemas com estrutura autorreferente (árvores, merge sort), enquanto a iteração evita o custo de memória de empilhar um frame de chamada por passo. A prova pode pedir para converter um no outro.

Explorar

Desdobrar uma chamada recursiva

Um método recursivo chama a si mesmo em uma entrada menor até atingir um caso base, então os resultados se dobram de volta. Avance para ver as chamadas empilharem e se desfazerem.

Vocabulário Treinar

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

4.17

Busca Recursiva e Merge Sort

Programa

Objetivo de Aprendizagem 4.17.A: Determinar o resultado da execução de algoritmos recursivos que usam strings ou coleções.

4.17.A.1 A recursão pode ser usada para percorrer objetos String, arrays e objetos ArrayList.

Objetivo de Aprendizagem 4.17.B: Determinar o resultado de cada iteração de um algoritmo de busca binária usado para buscar informações em uma coleção.

4.17.B.1 Os dados devem estar em ordem ordenada para usar o algoritmo de busca binária. Busca binária começa no meio de um array ordenado ou ArrayList e elimina metade do array ou ArrayList em cada chamada recursiva até que o valor desejado seja encontrado ou todos os elementos tenham sido eliminados.
4.17.B.2 A busca binária é tipicamente mais eficiente que a busca linear.
- Declaração de exclusão: Algoritmos de busca outros que linear e binária estão fora do escopo do curso e exame AP Computer Science A.
4.17.B.3 O algoritmo de busca binária pode ser escrito tanto iterativamente quanto recursivamente.

Objetivo de Aprendizagem 4.17.C: Determinar o resultado de cada iteração do algoritmo merge sort quando usado para ordenar uma coleção.

4.17.C.1 Merge sort é um algoritmo de ordenação recursivo que pode ser usado para ordenar elementos em um array ou ArrayList.
- Declaração de exclusão: Algoritmos de ordenação outros que selection sort, insertion sort e merge sort estão fora do escopo do curso e exame AP Computer Science A.
4.17.C.2 Merge sort divide repetidamente um array em subarrays menores até que cada subarray tenha um único elemento e então mescla recursivamente os subarrays ordenados de volta juntos em ordem ordenada para formar o array final ordenado.

Fonte: College Board AP Course and Exam Description

Merge sort: divide, depois mescla

A recursão impulsiona algoritmos eficientes. A busca binária pode ser escrita recursivamente (busque na metade correta). O merge sort 归并排序 divide o array pela metade, ordena cada metade recursivamente, depois mescla as duas metades ordenadas – levando cerca de $n\log_2 n$ passos, muito mais rápido que a ordenação por seleção ou inserção em grandes quantidades de dados.

O merge sort divide o array em elementos individuais, depois mescla as metades ordenadas de volta para cima

Exemplo resolvido. Rastreie factorial(4). Cada chamada adia para uma menor: factorial(4) = 4 * factorial(3) = 4 * 3 * factorial(2) = 4 * 3 * 2 * factorial(1). factorial(1) atinge o caso base e retorna 1, então as chamadas desdobram-se para dentro: 2 * 1 = 2, depois 3 * 2 = 6, depois 4 * 6 = 24. Escrever cada chamada acima de seu valor retornado é a maneira confiável de rastrear recursão.

Habilidade para prova: rastreie um método recursivo escrevendo cada chamada e seu valor retornado, e saiba que a eficiência do merge sort ($n\log n$) supera as $n^2$ ordenações simples.

Vocabulário Treinar

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

4.17

Dicas de prova

Avalie ambos os benefícios e danos da coleta de dados — esta unidade é testada através de justificações escritas curtas, não de código.
Proteja informações pessoais identificáveis (PII) e explique riscos de privacidade e segurança no contexto.
Nomeie danos reais: violações de dados, vigilância e viés algorítmico devido a dados não representativos.
Respeite a propriedade intelectual e licenças quando reutilizar código ou dados.
Dê uma resposta específica e fundamentada — uma resposta vaga como "pode ser ruim" não ganha pontos.

Aulas interativas sobre este tópico

Passe por ele passo a passo, com exercícios de verificação instantânea.

Provas Anteriores

Mais tópicos em Ciência da Computação A do AP