Data Collections · ⁨Bộ thu thập dữ liệu⁩

AP Computer Science A · ⁨AP Khoa học máy tính A⁩ · Topic 4 · ⁨Chủ đề 4⁩

View Slides · ⁨Xem Slides⁩ Train · ⁨Luyện tập⁩

Video lesson for this topic · ⁨Bài học video cho chủ đề này⁩ Open the video page · ⁨Mở trang video⁩

4.1

The Ethics of Collecting Data · ⁨Đạo đức thu thập dữ liệu⁩

Syllabus · ⁨Chương trình⁩

English

Learning Objective 4.1.A: Explain the risks to privacy from collecting and storing personal data on computer systems.

4.1.A.1 When using a computer, personal privacy is at risk. When developing new programs, programmers should attempt to safeguard the personal privacy of the user.

Learning Objective 4.1.B: Explain the importance of recognizing data quality and potential issues when using a data set.

4.1.B.1 Algorithmic bias describes systemic and repeated errors in a program that create unfair outcomes for a specific group of users.
4.1.B.2 Programmers should be aware of the data set collection method and the potential for bias when using this method before using the data to extrapolate new information or drawing conclusions.
4.1.B.3 Some data sets are incomplete or contain inaccurate data. Using such data in the development or use of a program can cause the program to work incorrectly or inefficiently.

Learning Objective 4.1.C: Identify an appropriate data set to use in order to solve a problem or answer a specific question.

4.1.C.1 Contents of a data set might be related to a specific question or topic and might not be appropriate to give correct answers or extrapolate information for a different question or topic.

Tiếng Việt

Mục tiêu học tập 4.1.A: Giải thích những rủi ro đối với quyền riêng tư do thu thập và lưu trữ dữ liệu cá nhân trên hệ thống máy tính.

4.1.A.1 Khi sử dụng máy tính, quyền riêng tư cá nhân có nguy cơ bị xâm phạm. Khi phát triển các chương trình mới, các lập trình viên nên cố gắng bảo vệ quyền riêng tư của người dùng.

Mục tiêu học tập 4.1.B: Giải thích tầm quan trọng của việc nhận biết chất lượng dữ liệu và các vấn đề tiềm ẩn khi sử dụng một tập dữ liệu.

4.1.B.1 Thiên kiến thuật toán mô tả các lỗi hệ thống và lặp lại trong một chương trình tạo ra kết quả không công bằng cho một nhóm người dùng cụ thể.
4.1.B.2 Các lập trình viên cần nhận thức về phương pháp thu thập tập dữ liệu và khả năng xuất hiện thiên kiến khi sử dụng phương pháp này trước khi sử dụng dữ liệu để suy diễn thông tin mới hoặc rút ra kết luận.
4.1.B.3 Một số tập dữ liệu bị thiếu sót hoặc chứa dữ liệu không chính xác. Việc sử dụng dữ liệu như vậy trong quá trình phát triển hoặc vận hành một chương trình có thể khiến chương trình hoạt động sai hoặc kém hiệu quả.

Mục tiêu học tập 4.1.C: Xác định một tập dữ liệu phù hợp để sử dụng nhằm giải quyết một vấn đề hoặc trả lời một câu hỏi cụ thể.

4.1.C.1 Nội dung của một tập dữ liệu có thể liên quan đến một câu hỏi hoặc chủ đề cụ thể và có thể không phù hợp để đưa ra câu trả lời đúng đắn hoặc suy diễn thông tin cho một câu hỏi hoặc chủ đề khác.

Source: College Board AP Course and Exam Description · ⁨Nguồn: Mô tả Khóa học và Bài thi College Board AP⁩

English

Programs that gather data raise questions of privacy 隐私 and consent 同意. Collect only what is needed, protect it, and be honest about its use. Data can carry bias 偏见 if it does not represent everyone fairly, leading to unfair results – a responsibility that comes with storing information.

Tiếng Việt

Các机柜 máy chủ trong trung tâm dữ liệu — lượng dữ liệu lớn dấy lên những câu hỏi đạo đức về việc thu thập và sử dụng

Các chương trình thu thập dữ liệu dấy lên các vấn đề về quyền riêng tư và sự đồng ý. Chỉ thu thập những gì cần thiết, bảo vệ chúng, và trung thực về cách sử dụng. Dữ liệu có thể chứa thiên kiến nếu nó không đại diện công bằng cho tất cả mọi người, dẫn đến kết quả bất công – đây là trách nhiệm đi kèm với việc lưu trữ thông tin.

4.2

Why We Need Data Structures · ⁨Tại sao chúng ta cần cấu trúc dữ liệu⁩

Syllabus · ⁨Chương trình⁩

English

Learning Objective 4.2.A: Represent patterns and algorithms that involve data sets found in everyday life using written language or diagrams.

4.2.A.1 A data set is a collection of specific pieces of information or data.
4.2.A.2 Data sets can be manipulated and analyzed to solve a problem or answer a question. When analyzing data sets, values within the set are accessed and utilized one at a time and then processed according to the desired outcome.
4.2.A.3 Data can be represented in a diagram by using a chart or table. This visual can be used to plan the algorithm that will be used to manipulate the data.

Tiếng Việt

Mục tiêu học tập 4.2.A: Biểu diễn các mẫu và thuật toán liên quan đến tập dữ liệu trong cuộc sống hàng ngày bằng ngôn ngữ viết hoặc sơ đồ.

4.2.A.1 Một tập dữ liệu là một bộ sưu tập các mảnh thông tin cụ thể hoặc dữ liệu.
4.2.A.2 Tập dữ liệu có thể được thao tác và phân tích để giải quyết vấn đề hoặc trả lời câu hỏi. Khi phân tích tập dữ liệu, các giá trị bên trong tập hợp được truy cập và sử dụng từng cái một, sau đó được xử lý theo kết quả mong muốn.
4.2.A.3 Dữ liệu có thể được biểu diễn dưới dạng sơ đồ bằng cách sử dụng biểu đồ hoặc bảng. Hình ảnh trực quan này có thể được sử dụng để lập kế hoạch thuật toán sẽ được sử dụng để thao tác dữ liệu.

Source: College Board AP Course and Exam Description · ⁨Nguồn: Mô tả Khóa học và Bài thi College Board AP⁩

English

A single variable holds one value; real problems need to store many related values – a class roster, pixels, sensor readings. A data structure 数据结构 organizes a collection so we can store, find, and process items efficiently. The AP course uses three: the array, the ArrayList, and the 2D array.

Tiếng Việt

Tủ hồ sơ: các cấu trúc dữ liệu lưu trữ nhiều giá trị dưới một tên duy nhất để thuật toán có thể xử lý chúng — Mục hồ sơ: các bộ sưu tập lưu trữ nhiều giá trị dưới một tên duy nhất để thuật toán có thể xử lý chúng

Một biến đơn lẻ chỉ lưu một giá trị; các vấn đề thực tế cần lưu trữ nhiều giá trị liên quan — danh sách học sinh, điểm ảnh, số đo cảm biến. Một cấu trúc dữ liệu tổ chức một bộ sưu tập để chúng ta có thể lưu trữ, tìm kiếm và xử lý các mục một cách hiệu quả. Khóa AP sử dụng ba loại: mảng, ArrayList, và mảng 2D.

Vocabulary · ⁨Từ vựng⁩ Train · ⁨Luyện tập⁩

English	Tiếng Việt
privacy/ˈprɪvəsi/	quyền riêng tư
consent/kənˈsent/	sự đồng thuận
bias/ˈbaɪəs/	sự thiên lệch
data structure/ˈdeɪtə ˈstrʌktʃə/	cấu trúc dữ liệu
array/əˈreɪ/	mảng (array)
Traverse/trəˈvɜːs/	Duyệt qua
ArrayList/əˈreɪ lɪst/	ArrayList
2D array/ˌtuː ˈdiː əˈreɪ/	mảng 2D
row-major order/rəʊ ˈmeɪdʒə ˈɔːdə/	thứ tự theo hàng

4.3

Making and Reading an Array · ⁨Tạo và Đọc Mảng⁩

Syllabus · ⁨Chương trình⁩

English

Learning Objective 4.3.A: Develop code used to represent collections of related data using one-dimensional (1D) array objects.

4.3.A.1 An array stores multiple values of the same type. The values can be either primitive values or object references.
4.3.A.2 The length of an array is established at the time of creation and cannot be changed. The length of an array can be accessed through the length attribute.
4.3.A.3 When an array is created using the keyword new, all of its elements are initialized to the default values for the element data type. The default value for int is 0, for double is 0.0, for boolean is false, and for a reference type is null.
4.3.A.4 Initializer lists can be used to create and initialize arrays.
4.3.A.5 Square brackets [ ] are used to access and modify an element in a 1D array using an index.
4.3.A.6 The valid index values for an array are 0 through one less than the length of the array, inclusive. Using an index value outside of this range will result in an ArrayIndexOutOfBoundsException.

Tiếng Việt

Mục tiêu học tập 4.3.A: Phát triển mã dùng để biểu diễn các tập hợp dữ liệu liên quan bằng cách sử dụng các đối tượng mảng một chiều (1D).

4.3.A.1 Một mảng lưu trữ nhiều giá trị cùng một kiểu. Các giá trị này có thể là giá trị nguyên thủy hoặc tham chiếu đối tượng.
4.3.A.2 Chiều dài của mảng được xác định tại thời điểm tạo và không thể thay đổi. Chiều dài của mảng có thể được truy cập thông qua thuộc tính length.
4.3.A.3 Khi mảng được tạo bằng từ khóa new, tất cả các phần tử của nó được khởi tạo với giá trị mặc định cho kiểu dữ liệu phần tử. Giá trị mặc định cho int là 0, cho double là 0.0, cho boolean là false, và cho kiểu tham chiếu là null.
4.3.A.4 Danh sách khởi tạo có thể được sử dụng để tạo và khởi tạo mảng.
4.3.A.5 Dấu ngoặc vuông [ ] được sử dụng để truy cập và sửa đổi một phần tử trong mảng 1D bằng chỉ số.
4.3.A.6 Các giá trị chỉ số hợp lệ cho mảng là từ 0 đến nhỏ hơn chiều dài của mảng một đơn vị, bao gồm cả hai đầu mút. Sử dụng giá trị chỉ số nằm ngoài khoảng này sẽ dẫn đến một lỗi ArrayIndexOutOfBoundsException.

Source: College Board AP Course and Exam Description · ⁨Nguồn: Mô tả Khóa học và Bài thi College Board AP⁩

English

An array 数组 is a fixed-size, ordered collection of same-type values. Indices run from 0 to length - 1:

Accessing an index outside 0..length-1 throws an ArrayIndexOutOfBoundsException.

Tiếng Việt

Một mảng là một bộ sưu tập có kích thước cố định, thứ tự và chứa các giá trị cùng kiểu. Các chỉ mục chạy từ 0 đến length - 1:

Mảng một chiều (một danh sách) kèm theo chỉ số và giới hạn của nó — Một mảng một chiều (danh sách) với các chỉ mục và giới hạn của nó

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)

Truy cập vào chỉ mục nằm ngoài 0..length-1 sẽ gây ra lỗi ArrayIndexOutOfBoundsException.

4.4

Visiting Every Element of an Array · ⁨Truy cập Every Element of an Array⁩

Syllabus · ⁨Chương trình⁩

English

Learning Objective 4.4.A: Develop code used to traverse the elements in a 1D array and determine the result of these traversals.

4.4.A.1 Traversing an array is when repetition statements are used to access all or an ordered sequence of elements in an array.
4.4.A.2 Traversing an array with an indexed for loop or while loop requires elements to be accessed using their indices.
4.4.A.3 An enhanced for loop header includes a variable, referred to as the enhanced for loop variable. For each iteration of the enhanced for loop, the enhanced for loop variable is assigned a copy of an element without using its index.
4.4.A.4 Assigning a new value to the enhanced for loop variable does not change the value stored in the array.
4.4.A.5 When an array stores object references, the attributes can be modified by calling methods on the enhanced for loop variable. This does not change the object references stored in the array.
4.4.A.6 Code written using an enhanced for loop to traverse elements in an array can be rewritten using an indexed for loop or a while loop.

Tiếng Việt

Mục tiêu học tập 4.4.A: Phát triển mã dùng để duyệt qua các phần tử trong mảng 1D và xác định kết quả của các lần duyệt này.

4.4.A.1 Duyệt qua mảng là khi các câu lệnh lặp lại được sử dụng để truy cập toàn bộ hoặc một dãy thứ tự các phần tử trong mảng.
4.4.A.2 Duyệt qua mảng với vòng lặp for có chỉ số hoặc vòng lặp while yêu cầu các phần tử phải được truy cập bằng chỉ số của chúng.
4.4.A.3 Tiêu đề vòng lặp for nâng cao bao gồm một biến, được gọi là biến vòng lặp for nâng cao. Với mỗi lần lặp của vòng lặp for nâng cao, biến vòng lặp for nâng cao được gán một bản sao của một phần tử mà không cần sử dụng chỉ số của nó.
4.4.A.4 Gán một giá trị mới cho biến vòng lặp for nâng cao không làm thay đổi giá trị được lưu trữ trong mảng.
4.4.A.5 Khi mảng lưu trữ các tham chiếu đối tượng, các thuộc tính có thể được sửa đổi bằng cách gọi các phương pháp trên biến vòng lặp for nâng cao. Điều này không làm thay đổi các tham chiếu đối tượng được lưu trữ trong mảng.
4.4.A.6 Mã được viết bằng vòng lặp for nâng cao để duyệt qua các phần tử trong mảng có thể được viết lại bằng vòng lặp for có chỉ số hoặc vòng lặp while.

Source: College Board AP Course and Exam Description · ⁨Nguồn: Mô tả Khóa học và Bài thi College Board AP⁩

English

Traverse 遍历 an array with a for loop (gives the index) or an enhanced for / for-each loop (gives each value, read-only):

Tiếng Việt

Duyệt qua mảng bằng vòng lặp for (cung cấp chỉ mục) hoặc vòng lặp enhanced for / for-each (cung cấp từng giá trị, chỉ đọc):

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

Standard Array Algorithms · ⁨Thuật toán Mảng Tiêu chuẩn⁩

Syllabus · ⁨Chương trình⁩

English

Learning Objective 4.5.A: Develop code for standard and original algorithms for a particular context or specification that involves arrays and determine the result of these algorithms.

4.5.A.1 There are standard algorithms that utilize array traversals to:
- determine a minimum or maximum value
- compute a sum or average
- determine if at least one element has a particular property
- determine if all elements have a particular property
- determine the number of elements having a particular property
- access all consecutive pairs of elements
- determine the presence or absence of duplicate elements
- shift or rotate elements left or right
- reverse the order of the elements

Tiếng Việt

Mục tiêu Học tập 4.5.A: Phát triển mã cho các thuật toán chuẩn và thuật toán tự thiết kế trong một ngữ cảnh hoặc yêu cầu cụ thể liên quan đến mảng và xác định kết quả của các thuật toán này.

4.5.A.1 Có các thuật toán chuẩn sử dụng việc duyệt qua mảng để:
- xác định giá trị tối thiểu hoặc tối đa
- tính tổng hoặc trung bình cộng
- xác định xem có ít nhất một phần tử nào có thuộc tính đặc biệt hay không
- xác định xem tất cả các phần tử có thuộc tính đặc biệt hay không
- xác định số lượng phần tử có thuộc tính đặc biệt
- truy cập tất cả các cặp phần tử liên tiếp
- xác định sự tồn tại hoặc không tồn tại của các phần tử trùng lặp
- dịch chuyển hoặc xoay các phần tử sang trái hoặc phải
- đảo ngược thứ tự của các phần tử

Source: College Board AP Course and Exam Description · ⁨Nguồn: Mô tả Khóa học và Bài thi College Board AP⁩

English

Master these patterns: compute a sum or average, find the max/min, count items meeting a condition, check for a duplicate, and reverse or shift elements. Each is a traversal with a running result:

Tiếng Việt

Nắm vững các mẫu này: tính tổng hoặc trung bình, tìm giá trị lớn nhất/nhỏ nhất, đếm các mục thỏa mãn điều kiện, kiểm tra sự tồn tại của lặp lại, và đảo ngược hoặc dịch chuyển các phần tử. Mỗi cái là một lần duyệt với kết quả tích lũy:

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

4.6

Reading Data from a Text File · ⁨Đọc Dữ liệu từ Tập tin Văn bản⁩

Syllabus · ⁨Chương trình⁩

English

Learning Objective 4.6.A: Develop code to read data from a text file.

4.6.A.1 A file is storage for data that persists when the program is not running. The data in a file can be retrieved during program execution.
4.6.A.2 A file can be connected to the program using the File and Scanner classes.
4.6.A.3 A file can be opened by creating a File object, using the name of the file as the argument of the constructor.
- File(String str) is the File constructor that accepts a String file name to open for reading, where str is the pathname for the file.
4.6.A.4 When using the File class, it is required to indicate what to do if the file with the provided name cannot be opened. One way to accomplish this is to add throws IOException to the header of the method that uses the file. If the file name is invalid, the program will terminate.
4.6.A.5 The File and IOException classes are part of the java.io package. An import statement must be used to make these classes available for use in the program.
4.6.A.6 The following Scanner methods and constructor—including what they do and when they are used—are part of the Java Quick Reference:
- Scanner(File f) is the Scanner constructor that accepts a File for reading.
- int nextInt() returns the next int read from the file or input source if available. If the next int does not exist or is out of range, it will result in an InputMismatchException.
- double nextDouble() returns the next double read from the file or input source. If the next double does not exist, it will result in an InputMismatchException.
- boolean nextBoolean() returns the next boolean read from the file or input source. If the next boolean does not exist, it will result in an InputMismatchException.
- String nextLine() returns the next line of text as a String read from the file or input source; can return the empty string if called immediately after another Scanner method that is reading from the file or input source.
- String next() returns the next String read from the file or input source.
- boolean hasNext() returns true if there is a next item to read in the file or input source; returns false otherwise.
- void close() closes this scanner.
- Exclusion statement: Accepting input from the keyboard is outside the scope of the AP Computer Science A course and exam.
4.6.A.7 Using nextLine and the other Scanner methods together on the same input source sometimes requires code to adjust for the methods' different ways of handling whitespace.
- Exclusion statement: Writing or analyzing code that uses both nextLine and other Scanner methods on the same input source is outside the scope of the AP Computer Science A course and exam.
4.6.A.8 The following additional String method—including what it does and when it is used—is part of the Java Quick Reference:
- String[] split(String del) returns a String array where each element is a substring of this String, which has been split around matches of the given expression del.
- Exclusion statement: The parameter del uses a format called a regular expression. Writing or analyzing code that uses any of the special properties of regular expressions (e.g., \\*, \\.) is outside the scope of the AP Computer Science A course and exam.
4.6.A.9 A while loop can be used to detect if the file still contains elements to read by using the hasNext method as the condition of the loop.
4.6.A.10 A file should be closed when the program is finished using it. The close method from Scanner is called to close the file.

Tiếng Việt

Mục tiêu Học tập 4.6.A: Phát triển mã để đọc dữ liệu từ một tập tin văn bản.

4.6.A.1 Một tập tin là nơi lưu trữ dữ liệu tồn tại ngay cả khi chương trình không chạy. Dữ liệu trong tập tin có thể được truy xuất trong quá trình thực thi chương trình.
4.6.A.2 Một tập tin có thể được kết nối với chương trình bằng cách sử dụng File và Scanner class.
4.6.A.3 Một tập tin có thể được mở bằng cách tạo một đối tượng File, sử dụng tên tập tin làm tham số của constructor.
- File(String str) là File constructor chấp nhận một String tên file để mở để đọc, trong đó str là đường dẫn đến file.
4.6.A.4 Khi sử dụng File class, bắt buộc phải chỉ ra hành động nếu tập tin có tên được cung cấp không thể mở. Một cách để thực hiện điều này là thêm throws IOException vào phần đầu của method sử dụng tập tin. Nếu tên file không hợp lệ, chương trình sẽ bị dừng lại.
4.6.A.5 File và IOException class là một phần của java.io package. Một statement import phải được sử dụng để làm cho các class này khả dụng trong chương trình.
4.6.A.6 Các Scanner methods sau đây và constructor—bao gồm cả chức năng của chúng và thời điểm sử dụng—là một phần của Java Quick Reference:
- Scanner(File f) là Scanner constructor chấp nhận một File để đọc.
- int nextInt() trả về int tiếp theo được đọc từ file hoặc nguồn đầu vào nếu có sẵn. Nếu int tiếp theo không tồn tại hoặc nằm ngoài phạm vi, nó sẽ gây ra một InputMismatchException.
- double nextDouble() trả về double tiếp theo được đọc từ file hoặc nguồn đầu vào. Nếu double tiếp theo không tồn tại, nó sẽ gây ra một InputMismatchException.
- boolean nextBoolean() trả về boolean tiếp theo được đọc từ file hoặc nguồn đầu vào. Nếu boolean tiếp theo không tồn tại, nó sẽ gây ra một InputMismatchException.
- String nextLine() trả về dòng văn bản tiếp theo dưới dạng một String được đọc từ file hoặc nguồn đầu vào; có thể trả về chuỗi rỗng nếu được gọi ngay sau một Scanner method khác đang đọc từ file hoặc nguồn đầu vào.
- String next() trả về String tiếp theo được đọc từ file hoặc nguồn đầu vào.
- boolean hasNext() trả về true nếu còn một item để đọc trong file hoặc nguồn đầu vào; trả về false ngược lại.
- void close() đóng Scanner này.
- Câu loại trừ: Nhận đầu vào từ bàn phím nằm ngoài phạm vi của khóa học và kỳ thi AP Computer Science A.
4.6.A.7 Việc sử dụng nextLine cùng với các Scanner methods khác trên cùng một nguồn đầu vào đôi khi đòi hỏi mã để điều chỉnh cho các cách xử lý khoảng trắng khác nhau của các methods.
- Câu loại trừ: Viết hoặc phân tích mã sử dụng cả nextLine và các Scanner methods khác trên cùng một nguồn đầu vào nằm ngoài phạm vi của khóa học và kỳ thi AP Computer Science A.
4.6.A.8 String method bổ sung sau đây—including cả chức năng và thời điểm sử dụng—là một phần của Java Quick Reference:
- String[] split(String del) trả về một String array mà mỗi phần tử là một substring của this String, đã được tách ra dựa trên các matches của biểu thức del đã cho.
- Câu loại trừ: Tham số del sử dụng một định dạng gọi là regular expression. Viết hoặc phân tích mã sử dụng bất kỳ tính chất đặc biệt nào của regular expressions (ví dụ: \\*, \\.) nằm ngoài phạm vi của khóa học và kỳ thi AP Computer Science A.
4.6.A.9 Một vòng lặp while có thể được sử dụng để phát hiện xem file vẫn còn chứa các phần tử để đọc hay không bằng cách sử dụng hasNext method như là điều kiện của vòng lặp.
4.6.A.10 Một tập tin nên được đóng khi chương trình đã sử dụng xong. Method close từ Scanner được gọi để đóng tập tin.

Source: College Board AP Course and Exam Description · ⁨Nguồn: Mô tả Khóa học và Bài thi College Board AP⁩

English

File and IOException live in java.io, so a program that reads a file needs import java.io.*;. Opening a file can fail (it might not exist), and Java forces you to handle that – the simplest way is to add throws IOException to the method header. A Scanner then reads the file line by line, using hasNext... to test before reading:

Reading typed tokens with nextInt(), nextDouble(), or nextBoolean() throws an InputMismatchException if the next token is the wrong type – for example calling nextInt() when the next thing in the file is the word cat.

Tiếng Việt

File và IOException nằm trong java.io, vì vậy một chương trình đọc tập tin cần import java.io.*;. Mở một tập tin có thể thất bại (có thể không tồn tại), và Java bắt buộc bạn phải xử lý điều đó — cách đơn giản nhất là thêm throws IOException vào tiêu đề phương thức. Sau đó, một Scanner sẽ đọc tập tin dòng theo dòng, sử dụng hasNext... để kiểm tra trước khi đọc:

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

Đọc các token đã định dạng với nextInt(), nextDouble(), hoặc nextBoolean() sẽ gây ra lỗi InputMismatchException nếu token tiếp theo sai kiểu — ví dụ như gọi nextInt() khi thứ tiếp theo trong tập tin là từ cat.

4.7

Wrapping a Number in an Object · ⁨Bao bọc một Số trong Đối tượng⁩

Syllabus · ⁨Chương trình⁩

English

Learning Objective 4.7.A: Develop code to use Integer and Double objects from their primitive counterparts and determine the result of using these objects.

4.7.A.1 The Integer class and Double class are part of the java.lang package. An Integer object is immutable, meaning once an Integer object is created, its attributes cannot be changed. A Double object is immutable, meaning once a Double object is created, its attributes cannot be changed.
4.7.A.2 Autoboxing is the automatic conversion that the Java compiler makes between primitive types and their corresponding object wrapper classes. This includes converting an int to an Integer and a double to a Double. The Java compiler applies autoboxing when a primitive value is:
- passed as a parameter to a method that expects an object of the corresponding wrapper class
- assigned to a variable of the corresponding wrapper class
4.7.A.3 Unboxing is the automatic conversion that the Java compiler makes from the wrapper class to the primitive type. This includes converting an Integer to an int and a Double to a double. The Java compiler applies unboxing when a wrapper class object is:
- passed as a parameter to a method that expects a value of the corresponding primitive type
- assigned to a variable of the corresponding primitive type
4.7.A.4 The following class Integer method—including what it does and when it is used—is part of the Java Quick Reference:
- static int parseInt(String s) returns the String argument as an int.
4.7.A.5 The following class Double method—including what it does and when it is used—is part of the Java Quick Reference:
- static double parseDouble(String s) returns the String argument as a double.

Tiếng Việt

Mục tiêu Học tập 4.7.A: Phát triển mã để sử dụng Integer và Double objects từ các đối tác primitive của chúng và xác định kết quả của việc sử dụng các objects này.

4.7.A.1 Class Integer và class Double là một phần của java.lang package. Một đối tượng Integer là immutable, nghĩa là một khi đối tượng Integer được tạo ra, các thuộc tính của nó không thể thay đổi. Một đối tượng Double là immutable, nghĩa là một khi đối tượng Double được tạo ra, các thuộc tính của nó không thể thay đổi.
4.7.A.2 Autoboxing là phép chuyển đổi tự động mà bộ biên dịch Java thực hiện giữa các kiểu primitive và các class wrapper object tương ứng của chúng. Điều này bao gồm việc chuyển đổi một int thành một Integer và một double thành một Double. Bộ biên dịch Java áp dụng autoboxing khi một giá trị primitive được:
- truyền làm tham số cho một method chờ đợi một object của class wrapper tương ứng
- gán cho một biến của class wrapper tương ứng
4.7.A.3 Unboxing là phép chuyển đổi tự động mà bộ biên dịch Java thực hiện từ class wrapper sang kiểu primitive. Điều này bao gồm việc chuyển đổi một Integer thành một int và một Double thành một double. Bộ biên dịch Java áp dụng unboxing khi một object của class wrapper được:
- truyền làm tham số cho một method chờ đợi một giá trị của kiểu primitive tương ứng
- gán cho một biến của kiểu primitive tương ứng
4.7.A.4 Class Integer method sau đây—including cả chức năng và thời điểm sử dụng—là một phần của Java Quick Reference:
- static int parseInt(String s) trả về tham số String dưới dạng một int.
4.7.A.5 Class Double method sau đây—including cả chức năng và thời điểm sử dụng—là một phần của Java Quick Reference:
- static double parseDouble(String s) trả về tham số String dưới dạng một double.

Source: College Board AP Course and Exam Description · ⁨Nguồn: Mô tả Khóa học và Bài thi College Board AP⁩

English

An ArrayList stores objects, not primitives, so a primitive is wrapped in an object: Integer wraps int, Double wraps double. Java does this with autoboxing 自动装箱 (int to Integer) and unboxing (back again) automatically, so you can write list.add(5) and int x = list.get(0).

Tiếng Việt

Một ArrayList lưu trữ đối tượng, không phải nguyên thủy, vì vậy một nguyên thủy được bao bọc trong một đối tượng: Integer bao bọc int, Double bao bọc double. Java thực hiện điều này tự động bằng autoboxing (int sang Integer) và unboxing (ngược lại), vì vậy bạn có thể viết list.add(5) và int x = list.get(0).

Vocabulary · ⁨Từ vựng⁩ Train · ⁨Luyện tập⁩

English	Tiếng Việt
autoboxing/ˌɔːtəʊˈbɒksɪŋ/	autoboxing

4.8

The ArrayList Toolbox · ⁨Bộ dụng cụ ArrayList⁩

Syllabus · ⁨Chương trình⁩

Learning Objective Essential Knowledge

4.8.A
Develop code for collections of related objects using ArrayList objects and determine the result of calling methods on these objects.

4.8.A.1 An ArrayList object is mutable in size and contains object references.
4.8.A.2 The ArrayList constructor ArrayList() constructs an empty list.
4.8.A.3 Java allows the generic type ArrayList<E>, where the type parameter E specifies the type of the elements. When ArrayList<E> is specified, the types of the reference parameters and return type when using the ArrayList methods are type E. ArrayList<E> is preferred over ArrayList. For example, ArrayList<String> names = new ArrayList<String>(); allows the compiler to find errors that would otherwise be found at run-time.
4.8.A.4 The ArrayList class is part of the java.util package. An import statement must be used to make this class available for use in the program.
4.8.A.5 The following ArrayList methods—including what they do and when they are used—are part of the Java Quick Reference:
- int size() returns the number of elements in the list.
- boolean add(E obj) appends obj to end of list; returns true.
- void add(int index, E obj) inserts obj at position index (0 <= index <= size), moving elements at position index and higher to the right (adds 1 to their indices) and adds 1 to size.
- E get(int index) returns the element at position index in the list.
- E set(int index, E obj) replaces the element at position index with obj; returns the element formerly at position index.
- E remove(int index) removes element from position index, moving elements at position index + 1 and higher to the left (subtracts 1 from their indices) and subtracts 1 from size; returns the element formerly at position index.
4.8.A.6 The indices for an ArrayList start at 0 and end at the number of elements - 1.

Source: College Board AP Course and Exam Description · ⁨Nguồn: Mô tả Khóa học và Bài thi College Board AP⁩

English

What an ArrayList really is

An ArrayList 动态数组 grows and shrinks as you add or remove items. Declare it with the element type in <>:

Tiếng Việt

ArrayList thực sự là gì

Một ArrayList tăng và giảm kích thước khi bạn thêm hoặc xóa các mục. Khai báo nó với kiểu phần tử trong <>:

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

Visiting Every Element of an ArrayList · ⁨Truy cập Every Element of an ArrayList⁩

Syllabus · ⁨Chương trình⁩

English

Learning Objective 4.9.A: Develop code used to traverse the elements of an ArrayList and determine the results of these traversals.

4.9.A.1 Traversing an ArrayList is when iteration or recursive statements are used to access all or an ordered sequence of the elements in an ArrayList.
4.9.A.2 Deleting elements during a traversal of an ArrayList requires the use of special techniques to avoid skipping elements.
4.9.A.3 Attempting to access an index value outside of its range will result in an IndexOutOfBoundsException.
4.9.A.4 Changing the size of an ArrayList while traversing it using an enhanced for loop can result in a ConcurrentModificationException. Therefore, when using an enhanced for loop to traverse an ArrayList, you should not add or remove elements.

Tiếng Việt

Mục tiêu học tập 4.9.A: Viết mã để duyệt qua các phần tử của một ArrayList và xác định kết quả của các lần duyệt này.

4.9.A.1 Duyệt qua một ArrayList là khi sử dụng các câu lệnh lặp hoặc đệ quy để truy cập tất cả hoặc một chuỗi có thứ tự các phần tử trong một ArrayList.
4.9.A.2 Xóa các phần tử trong quá trình duyệt qua một ArrayList đòi hỏi việc sử dụng các kỹ thuật đặc biệt để tránh bỏ sót các phần tử.
4.9.A.3 Cố gắng truy cập giá trị chỉ số nằm ngoài phạm vi hợp lệ sẽ dẫn đến một IndexOutOfBoundsException.
4.9.A.4 Thay đổi kích thước của một ArrayList trong lúc đang duyệt nó bằng vòng lặp for nâng cao có thể gây ra một ConcurrentModificationException. Do đó, khi sử dụng vòng lặp for nâng cao để duyệt qua một ArrayList, bạn không nên thêm hay xóa các phần tử.

Source: College Board AP Course and Exam Description · ⁨Nguồn: Mô tả Khóa học và Bài thi College Board AP⁩

English

Traverse with an index loop or a for-each loop, just like arrays (use size() and get(i)):

Exam skill: when removing items in an index loop, either loop backwards or do not increment i after a removal – otherwise removing shifts elements left and you skip one. And never add or remove elements while traversing an ArrayList with a for-each loop: changing its size mid-loop throws a ConcurrentModificationException, so use an index loop (backwards, as above) whenever you must remove.

Tiếng Việt

Duyệt qua bằng vòng lặp chỉ mục hoặc vòng lặp for-each, giống như mảng (sử dụng size() và get(i)):

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

Kỹ năng làm bài thi: khi xóa các mục trong vòng lặp chỉ mục, hãy duyệt ngược hoặc không tăng i sau khi xóa — nếu không, việc xóa sẽ dịch chuyển các phần tử sang trái và bạn sẽ bỏ sót một phần tử. Và tuyệt đối không thêm hoặc xóa các phần tử trong khi duyệt một ArrayList bằng vòng lặp for-each: thay đổi kích thước của nó giữa chừng vòng lặp sẽ gây ra lỗi ConcurrentModificationException, vì vậy hãy sử dụng vòng lặp chỉ mục (ngược, như trên) mỗi khi bạn phải xóa.

4.10

Standard ArrayList Algorithms · ⁨Thuật toán ArrayList Tiêu chuẩn⁩

Syllabus · ⁨Chương trình⁩

English

Learning Objective 4.10.A: Develop code for standard and original algorithms for a particular context or specification that involve ArrayList objects and determine the result of these algorithms.

4.10.A.1 There are standard ArrayList algorithms that utilize traversals to:
- determine a minimum or maximum value
- compute a sum or average
- determine if at least one element has a particular property
- determine if all elements have a particular property
- determine the number of elements having a particular property
- access all consecutive pairs of elements
- determine the presence or absence of duplicate elements
- shift or rotate elements left or right
- reverse the order of the elements
- insert elements
- delete elements
4.10.A.2 Some algorithms require multiple String, array, or ArrayList objects to be traversed simultaneously.

Tiếng Việt

Mục tiêu học tập 4.10.A: Viết mã cho các thuật toán tiêu chuẩn và nguyên bản cho một ngữ cảnh hoặc tài liệu mô tả cụ thể liên quan đến các đối tượng ArrayList và xác định kết quả của các thuật toán này.

4.10.A.1 Có các thuật toán ArrayList tiêu chuẩn sử dụng phép duyệt để:
- xác định giá trị tối thiểu hoặc tối đa
- tính tổng hoặc trung bình cộng
- xác định xem có ít nhất một phần tử nào có thuộc tính đặc biệt hay không
- xác định xem tất cả các phần tử có thuộc tính đặc biệt hay không
- xác định số lượng phần tử có thuộc tính đặc biệt
- truy cập tất cả các cặp phần tử liên tiếp
- xác định sự tồn tại hoặc không tồn tại của các phần tử trùng lặp
- dịch chuyển hoặc xoay các phần tử sang trái hoặc phải
- đảo ngược thứ tự của các phần tử
- chèn phần tử
- xóa phần tử
4.10.A.2 Một số thuật toán yêu cầu nhiều đối tượng String, mảng, hoặc ArrayList được duyệt đồng thời.

Source: College Board AP Course and Exam Description · ⁨Nguồn: Mô tả Khóa học và Bài thi College Board AP⁩

English

The same algorithms as arrays – max/min, count, sum – plus insertion and deletion that arrays cannot do easily. A common task is to remove all elements matching a condition, handling the index-shift carefully.

Tiếng Việt

Cùng các thuật toán như mảng — giá trị lớn nhất/nhỏ nhất, đếm, tổng — cộng thêm chèn và xóa mà mảng không thể thực hiện dễ dàng. Một nhiệm vụ phổ biến là xóa tất cả các phần tử khớp với một điều kiện, xử lý sự dịch chuyển chỉ mục cẩn thận.

4.11

Grids: Two-Dimensional Arrays · ⁨Lưới: Mảng Hai Chiều⁩

Syllabus · ⁨Chương trình⁩

English

Learning Objective 4.11.A: Develop code used to represent collections of related data using two-dimensional (2D) array objects.

4.11.A.1 A 2D array is stored as an array of arrays. Therefore, the way 2D arrays are created and indexed is similar to 1D array objects. The size of a 2D array is established at the time of creation and cannot be changed. 2D arrays can store either primitive data or object reference data.
- Exclusion statement: Nonrectangular 2D array objects are outside the scope of the AP Computer Science A course and exam.
4.11.A.2 When a 2D array is created using the keyword new, all of its elements are initialized to the default values for the element data type. The default value for int is 0, for double is 0.0, for boolean is false, and for a reference type is null.
4.11.A.3 The initializer list used to create and initialize a 2D array consists of initializer lists that represent 1D arrays; for example, int[][] arr2D = { {1, 2, 3}, {4, 5, 6} };.
4.11.A.4 The square brackets [row][col] are used to access and modify an element in a 2D array. For the purposes of the exam, when accessing the element at arr[first][second], the first index is used for rows, the second index is used for columns.
4.11.A.5 A single array that is a row of a 2D array can be accessed using the 2D array name and a single set of square brackets containing the row index.
4.11.A.6 The number of rows contained in a 2D array can be accessed through the length attribute. The valid row index values for a 2D array are 0 through one less than the number of rows or the length of the array, inclusive. The number of columns contained in a 2D array can be accessed through the length attribute of one of the rows. The valid column index values for a 2D array are 0 through one less than the number of columns or the length of any given row of the array, inclusive. For example, given a 2D array named values, the number of rows is values.length and the number of columns is values[0].length. Using an index value outside of these ranges will result in an ArrayIndexOutOfBoundsException.

Tiếng Việt

Mục tiêu học tập 4.11.A: Viết mã dùng để biểu diễn các bộ dữ liệu liên quan bằng cách sử dụng các đối tượng mảng hai chiều (2D).

4.11.A.1 Mảng 2D được lưu trữ dưới dạng mảng của các mảng. Do đó, cách tạo và truy cập mảng 2D tương tự như các đối tượng mảng 1D. Kích thước của mảng 2D được xác định tại thời điểm tạo và không thể thay đổi. Mảng 2D có thể lưu trữ dữ liệu nguyên thủy hoặc dữ liệu tham chiếu đến đối tượng.
- Câu loại trừ: Các đối tượng mảng 2D không hình chữ nhật nằm ngoài phạm vi của khóa học và kỳ thi AP Computer Science A.
4.11.A.2 Khi tạo mảng 2D bằng từ khóa new, tất cả các phần tử của nó sẽ được khởi tạo với giá trị mặc định cho kiểu dữ liệu phần tử. Giá trị mặc định cho int là 0, cho double là 0.0, cho boolean là false, và cho kiểu tham chiếu là null.
4.11.A.3 Danh sách khởi tạo dùng để tạo và khởi tạo mảng 2D bao gồm các danh sách khởi tạo đại diện cho mảng 1D; ví dụ, int[][] arr2D = { {1, 2, 3}, {4, 5, 6} };.
4.11.A.4 Các dấu ngoặc vuông [row][col] được sử dụng để truy cập và thay đổi một phần tử trong mảng nhiều chiều 2D. Đối với mục đích của kỳ thi, khi truy cập phần tử tại vị trí arr[first][second], chỉ số đầu tiên dùng cho hàng, chỉ số thứ hai dùng cho cột.
4.11.A.5 Một mảng đơn lẻ là một hàng của mảng 2D có thể được truy cập bằng tên mảng 2D và một cặp dấu ngoặc vuông chứa chỉ số hàng.
4.11.A.6 Số lượng hàng chứa trong mảng 2D có thể truy cập thông qua thuộc tính length. Các giá trị chỉ số hàng hợp lệ cho mảng 2D là từ 0 đến ít hơn một so với số lượng hàng hoặc độ dài của mảng, bao gồm cả hai đầu mút. Số lượng cột chứa trong mảng 2D có thể truy cập thông qua thuộc tính length của một trong các hàng. Các giá trị chỉ số cột hợp lệ cho mảng 2D là từ 0 đến ít hơn một so với số lượng cột hoặc độ dài của bất kỳ hàng nào đã cho của mảng, bao gồm cả hai đầu mút. Ví dụ, với mảng 2D có tên là values, số lượng hàng là values.length và số lượng cột là values[0].length. Sử dụng giá trị chỉ số nằm ngoài các khoảng này sẽ dẫn đến lỗi ArrayIndexOutOfBoundsException.

Source: College Board AP Course and Exam Description · ⁨Nguồn: Mô tả Khóa học và Bài thi College Board AP⁩

English

A 2D array 二维数组 is a grid (rows and columns) – an array of arrays:

Tiếng Việt

Một mảng 2D là một lưới (hàng và cột) — một mảng của các mảng:

Mảng hai chiều (bảng) với chỉ số dòng và cột — Một mảng hai chiều (bảng) với các chỉ mục hàng và cột

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

Explore · ⁨Khám phá⁩

Index a 2D array by row and column · ⁨Truy xuất mảng 2D theo hàng và cột⁩

A 2D array is a grid addressed by [row][col]. Move the indices and watch which cell they select — row first, then column, both counting from 0. · ⁨Một mảng 2D là lưới được truy xuất bằng [row][col]. Di chuyển các chỉ mục và xem chúng chọn ô nào — hàng trước, sau đó cột, cả hai đều đếm từ 0.⁩

4.12

Walking Through a Grid · ⁨Duyệt qua Lưới⁩

Syllabus · ⁨Chương trình⁩

English

Learning Objective 4.12.A: Develop code used to traverse the elements in a 2D array and determine the result of these traversals.

4.12.A.1 Nested iteration statements are used to traverse and access all or an ordered sequence of elements in a 2D array. Since 2D arrays are stored as arrays of arrays, the way 2D arrays are traversed using for loops and enhanced for loops is similar to 1D array objects. Nested iteration statements can be written to traverse the 2D array in row-major order, column-major order, or a uniquely defined order. Row-major order refers to an ordering of 2D array elements where traversal occurs across each row, whereas column-major order traversal occurs down each column.
4.12.A.2 The outer loop of a nested enhanced for loop used to traverse a 2D array traverses the rows. Therefore, the enhanced for loop variable must be the type of each row, which is a 1D array. The inner loop traverses a single row. Therefore, the inner enhanced for loop variable must be the same type as the elements stored in the 1D array. Assigning a new value to the enhanced for loop variable does not change the value stored in the array.

Tiếng Việt

Mục tiêu học tập 4.12.A: Phát triển mã để duyệt qua các phần tử trong mảng 2D và xác định kết quả của việc duyệt này.

4.12.A.1 Các câu lệnh lặp lồng nhau được sử dụng để duyệt và truy cập tất cả hoặc một chuỗi có thứ tự các phần tử trong mảng 2D. Vì mảng 2D được lưu trữ dưới dạng mảng của các mảng, cách duyệt mảng 2D sử dụng vòng lặp for và vòng lặp for nâng cao tương tự như các đối tượng mảng 1D. Các câu lệnh lặp lồng nhau có thể được viết để duyệt mảng 2D theo thứ tự chính hàng (row-major order), thứ tự chính cột (column-major order), hoặc một thứ tự được xác định độc lập. Thứ tự chính hàng đề cập đến thứ tự các phần tử mảng 2D nơi việc duyệt diễn ra dọc theo mỗi hàng, trong khi thứ tự chính cột duyệt xuống từng cột.
4.12.A.2 Vòng lặp ngoài của vòng lặp lồng nhau for nâng cao dùng để duyệt mảng 2D sẽ duyệt qua các hàng. Do đó, biến của vòng lặp for nâng cao phải là kiểu của mỗi hàng, tức là mảng 1D. Vòng lặp bên trong duyệt một hàng duy nhất. Do đó, biến của vòng lặp for nâng cao bên trong phải cùng kiểu với các phần tử được lưu trữ trong mảng 1D. Gán một giá trị mới cho biến của vòng lặp for nâng cao không làm thay đổi giá trị được lưu trữ trong mảng.

Source: College Board AP Course and Exam Description · ⁨Nguồn: Mô tả Khóa học và Bài thi College Board AP⁩

English

Traversing a 2-D array

Visit every cell with nested loops – the outer over rows, the inner over columns (row-major order 行主序):

Tiếng Việt

Duyệt qua mảng 2-D

Truy cập every cell bằng vòng lặp lồng nhau — vòng ngoài duyệt hàng, vòng trong duyệt cột (thứ tự major hàng):

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

Standard 2D Array Algorithms · ⁨Thuật toán Mảng 2D Tiêu chuẩn⁩

Syllabus · ⁨Chương trình⁩

English

Learning Objective 4.13.A: Develop code for standard and original algorithms for a particular context or specification that involves 2D arrays and determine the result of these algorithms.

4.13.A.1 There are standard algorithms that utilize 2D array traversals to:
- determine a minimum or maximum value of all the elements or for a designated row, column, or other subsection
- compute a sum or average of all the elements or for a designated row, column, or other subsection
- determine if at least one element has a particular property in the entire 2D array or for a designated row, column, or other subsection
- determine if all elements of the 2D array or a designated row, column, or other subsection have a particular property
- determine the number of elements in the 2D array or in a designated row, column, or other subsection having a particular property
- access all consecutive pairs of elements
- determine the presence or absence of duplicate elements in the 2D array or in a designated row, column, or other subsection
- shift or rotate elements in a row left or right or in a column up or down
- reverse the order of the elements in a row or column

Tiếng Việt

Mục tiêu học tập 4.13.A: Phát triển mã cho các thuật toán tiêu chuẩn và thuật toán gốc cho một ngữ cảnh hoặc yêu cầu cụ thể liên quan đến mảng 2D và xác định kết quả của các thuật toán này.

4.13.A.1 Có các thuật toán tiêu chuẩn sử dụng việc duyệt mảng 2D để:
- xác định giá trị nhỏ nhất hoặc lớn nhất của tất cả các phần tử hoặc cho một hàng, cột hoặc phân đoạn khác được chỉ định
- tính tổng hoặc trung bình của tất cả các phần tử hoặc cho một hàng, cột hoặc phân đoạn khác được chỉ định
- xác định xem có ít nhất một phần tử có đặc tính nhất định trong toàn bộ mảng 2D hoặc cho một hàng, cột hoặc phân đoạn khác được chỉ định hay không
- xác định xem tất cả các phần tử của mảng 2D hoặc một hàng, cột hoặc phân đoạn khác được chỉ định có đặc tính nhất định hay không
- xác định số lượng phần tử trong mảng 2D hoặc trong một hàng, cột hoặc phân đoạn khác được chỉ định có đặc tính nhất định
- truy cập tất cả các cặp phần tử liên tiếp
- xác định sự hiện diện hoặc vắng mặt của các phần tử trùng lặp trong mảng 2D hoặc trong một hàng, cột hoặc phân đoạn khác được chỉ định
- dịch chuyển hoặc xoay các phần tử trong một hàng sang trái hoặc phải, hoặc trong một cột lên hoặc xuống
- đảo ngược thứ tự các phần tử trong một hàng hoặc cột

Source: College Board AP Course and Exam Description · ⁨Nguồn: Mô tả Khóa học và Bài thi College Board AP⁩

English

Typical grid tasks: sum a row or column, find the max in the grid, count matching cells, or sum a diagonal (where r == c). Each is a nested traversal with a running result.

Tiếng Việt

Các nhiệm vụ lưới điển hình: tính tổng một hàng hoặc cột, tìm giá trị lớn nhất trong lưới, đếm các ô khớp, hoặc tính tổng đường chéo (nơi r == c). Mỗi cái là một lần duyệt lồng nhau với kết quả tích lũy.

4.14

Finding a Value: Linear and Binary Search · ⁨Tìm Giá trị: Tìm kiếm Tuyến tính và Tìm kiếm Nhị phân⁩

Syllabus · ⁨Chương trình⁩

English

Learning Objective 4.14.A: Develop code used for linear search algorithms to search for specific information in a collection and determine the results of executing a search.

4.14.A.1 Linear search algorithms are standard algorithms that check each element in order until the desired value is found or all elements in the array or ArrayList have been checked. Linear search algorithms can begin the search process from either end of the array or ArrayList.
4.14.A.2 When applying linear search algorithms to 2D arrays, each row must be accessed then linear search applied to each row of the 2D array.

Tiếng Việt

Mục tiêu học tập 4.14.A: Phát triển mã sử dụng cho thuật toán tìm kiếm tuyến tính để tìm kiếm thông tin cụ thể trong một tập hợp và xác định kết quả của việc thực thi tìm kiếm.

4.14.A.1 Thuật toán tìm kiếm tuyến tính là các thuật toán tiêu chuẩn kiểm tra từng phần tử theo thứ tự cho đến khi tìm thấy giá trị mong muốn hoặc tất cả các phần tử trong mảng hoặc ArrayList đã được kiểm tra. Thuật toán tìm kiếm tuyến tính có thể bắt đầu quá trình tìm kiếm từ một trong hai đầu của mảng hoặc ArrayList.
4.14.A.2 Khi áp dụng thuật toán tìm kiếm tuyến tính vào mảng 2D, mỗi hàng phải được truy cập trước sau đó áp dụng tìm kiếm tuyến tính cho từng hàng của mảng 2D.

Source: College Board AP Course and Exam Description · ⁨Nguồn: Mô tả Khóa học và Bài thi College Board AP⁩

English

Binary search: halve and conquer

Linear search 线性搜索 checks each element in turn – works on any list, taking up to $n$ steps.
Binary search 二分搜索 works only on a sorted list: check the middle, then discard the half that cannot contain the target, repeating. It takes about $\log_2 n$ steps – far faster on large data.

Exam skill: binary search requires sorted data; know how many comparisons it makes and how lo, hi, mid update.

Worked example. Search for target = 40 in the sorted array {3, 9, 14, 23, 31, 42, 55} (indices 0–6). Start lo=0, hi=6:

mid = (0+6)/2 = 3, a[3]=23 < 40, so lo = 4;
mid = (4+6)/2 = 5, a[5]=42 > 40, so hi = 4;
mid = (4+4)/2 = 4, a[4]=31 < 40, so lo = 5;
now lo (5) > hi (4), so the loop ends – 40 is not present.

Each step halved the range, so even this miss took only three comparisons.

Tiếng Việt

Tìm kiếm nhị phân: chia đôi và chinh phục

Tìm kiếm tuyến tính kiểm tra từng phần tử lần lượt – hoạt động trên mọi danh sách, tốn tối đa $n$ bước.
Tìm kiếm nhị phân chỉ hoạt động trên danh sách đã được sắp xếp: kiểm tra phần tử giữa, sau đó loại bỏ nửa không chứa mục tiêu, lặp lại. Tốn khoảng $\log_2 n$ bước – nhanh hơn nhiều với dữ liệu lớn.

Tìm kiếm nhị phân thu hẹp phạm vi một nửa ở mỗi bước

Tìm kiếm tuyến tính kiểm tra từng phần tử lần lượt cho đến khi tìm thấy mục tiêu

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

Kỹ năng làm bài thi: tìm kiếm nhị phân yêu cầu dữ liệu đã sắp xếp; hãy biết số phép so sánh và cách lo, hi, mid cập nhật.

Ví dụ minh họa. Tìm target = 40 trong mảng đã sắp xếp {3, 9, 14, 23, 31, 42, 55} (chỉ số 0–6). Bắt đầu lo=0, hi=6:

mid = (0+6)/2 = 3, a[3]=23 < 40, nên lo = 4;
mid = (4+6)/2 = 5, a[5]=42 > 40, nên hi = 4;
mid = (4+4)/2 = 4, a[4]=31 < 40, nên lo = 5;
giờ lo (5) > hi (4), nên vòng lặp kết thúc – 40 không tồn tại.

Mỗi bước đều thu hẹp phạm vi một nửa, nên ngay cả lần thất bại này cũng chỉ tốn ba phép so sánh.

Explore · ⁨Khám phá⁩

Compare linear and binary search · ⁨So sánh tìm kiếm tuyến tính và nhị phân⁩

Linear search checks every element in turn; binary search halves a sorted list each step. Watch binary search reach the target in far fewer comparisons. · ⁨Tìm kiếm tuyến tính kiểm tra từng phần tử theo thứ tự; tìm kiếm nhị phân chia đôi một danh sách đã sắp xếp ở mỗi bước. Quan sát tìm kiếm nhị phân đạt đích trong ít so sánh hơn nhiều.⁩

Vocabulary · ⁨Từ vựng⁩ Train · ⁨Luyện tập⁩

English	Tiếng Việt
Linear search/ˈlɪnɪə sɜːtʃ/	Tìm kiếm tuyến tính
Binary search/ˈbaɪnəri sɜːtʃ/	Tìm kiếm nhị phân

4.15

Putting Data in Order: Selection and Insertion Sort · ⁨Sắp Xếp Dữ Liệu: Selection Sort và Insertion Sort⁩

Syllabus · ⁨Chương trình⁩

English

Learning Objective 4.15.A: Determine the result of executing each step of sorting algorithms to sort the elements of a collection.

4.15.A.1 Selection sort and insertion sort are iterative sorting algorithms that can be used to sort elements in an array or ArrayList.
4.15.A.2 Selection sort repeatedly selects the smallest (or largest) element from the unsorted portion of the list and swaps it into its correct (and final) position in the sorted portion of the list.
4.15.A.3 Insertion sort inserts an element from the unsorted portion of a list into its correct (but not necessarily final) position in the sorted portion of the list by shifting elements of the sorted portion to make room for the new element.

Tiếng Việt

Mục tiêu học tập 4.15.A: Xác định kết quả của việc thực thi từng bước của các thuật toán sắp xếp để sắp xếp các phần tử của một tập hợp.

4.15.A.1 Sắp xếp chọn (selection sort) và sắp xếp chèn (insertion sort) là các thuật toán sắp xếp lặp lại có thể được sử dụng để sắp xếp các phần tử trong mảng hoặc ArrayList.
4.15.A.2 Sắp xếp chọn liên tục chọn phần tử nhỏ nhất (hoặc lớn nhất) từ phần chưa sắp xếp của danh sách và hoán đổi nó vào đúng (và cuối cùng) vị trí trong phần đã sắp xếp của danh sách.
4.15.A.3 Sắp xếp chèn (Insertion sort) chèn một phần tử từ phần chưa sắp xếp của danh sách vào vị trí đúng (nhưng không nhất thiết là vị trí cuối cùng) trong phần đã sắp xếp của danh sách bằng cách dịch chuyển các phần tử của phần đã sắp xếp để tạo chỗ cho phần tử mới.

Source: College Board AP Course and Exam Description · ⁨Nguồn: Mô tả Khóa học và Bài thi College Board AP⁩

English

Insertion sort

Bubble sort, pass by pass

Selection sort 选择排序 repeatedly finds the smallest remaining element and swaps it into place.
Insertion sort 插入排序 grows a sorted front, inserting each new element where it belongs.

Both are simple and take about $n^2$ steps on average – fine for small arrays. Be able to trace the array after each pass.

Tiếng Việt

Insertion sort

Thuật toán sắp xếp nổi bọt, qua từng lượt

Selection sort liên tục tìm phần tử nhỏ nhất còn lại và hoán đổi nó vào đúng vị trí.
Insertion sort xây dựng phần đầu đã sắp xếp, chèn mỗi phần tử mới vào nơi phù hợp.

Sắp xếp chèn, dịch chuyển mỗi khóa vào đúng vị trí qua từng lượt — Một thuật toán insertion sort, dịch chuyển từng khóa vào đúng vị trí qua từng lượt

Cả hai đều đơn giản và tốn khoảng $n^2$ bước trung bình – tốt cho mảng nhỏ. Bạn cần có thể theo dõi trạng thái mảng sau mỗi lượt.

Explore · ⁨Khám phá⁩

Watch a sorting algorithm order a list · ⁨Quan sát thuật toán sắp xếp sắp xếp một danh sách⁩

A sort rearranges elements into order. Step through selection/insertion sort to see the sorted region grow one element at a time. · ⁨Một sắp xếp sắp xếp lại các phần tử theo thứ tự. Bước qua selection/insertion sort để thấy vùng đã sắp xếp mở rộng thêm một phần tử mỗi lần.⁩

Vocabulary · ⁨Từ vựng⁩ Train · ⁨Luyện tập⁩

English	Tiếng Việt
Selection sort/sɪˈlekʃn sɔːt/	Sắp xếp theo lựa chọn
Insertion sort/ɪnˈsɜːʃn sɔːt/	Sắp xếp chèn

4.16

Methods That Call Themselves: Recursion · ⁨Phương Thức Gọi Chính Nó: Đệ Quy⁩

Syllabus · ⁨Chương trình⁩

English

Learning Objective 4.16.A: Determine the result of calling recursive methods.

4.16.A.1 A recursive method is a method that calls itself. Recursive methods contain at least one base case, which halts the recursion, and at least one recursive call. Recursion is another form of repetition.
4.16.A.2 Each recursive call has its own set of local variables, including the parameters. Parameter values capture the progress of a recursive process, much like loop control variable values capture the progress of a loop.
4.16.A.3 Any recursive solution can be replicated through the use of an iterative approach and vice versa.
- Exclusion statement: Writing recursive code is outside the scope of the AP Computer Science A course and exam.

Tiếng Việt

Mục tiêu học tập 4.16.A: Xác định kết quả của việc gọi các phương pháp đệ quy.

4.16.A.1 Một phương pháp đệ quy là phương pháp gọi chính nó. Các phương pháp đệ quy chứa ít nhất một trường hợp cơ sở, giúp dừng quá trình đệ quy, và ít nhất một lời gọi đệ quy. Đệ quy là một hình thức lặp lại khác.
4.16.A.2 Mỗi lần gọi đệ quy có bộ biến cục bộ riêng, bao gồm cả tham số. Giá trị tham số ghi nhận tiến trình của quá trình đệ quy, tương tự như giá trị biến điều khiển vòng lặp ghi nhận tiến trình của vòng lặp.
4.16.A.3 Bất kỳ giải pháp nào sử dụng đệ quy cũng có thể được tái tạo thông qua phương pháp lặp, và ngược lại.
- Khẳng định loại trừ: Việc viết mã đệ quy nằm ngoài phạm vi của khóa học và bài thi AP Computer Science A.

Source: College Board AP Course and Exam Description · ⁨Nguồn: Mô tả Khóa học và Bài thi College Board AP⁩

English

Recursion & the call stack

Recursion 递归 is a method that calls itself on a smaller input. It needs a base case 基本情况 that stops the calls, and a recursive case that moves toward the base:

Without a reachable base case, recursion never stops (a stack overflow).

Recursion and iteration are interchangeable. Any recursive solution can be rewritten with a loop (an iterative approach), and any loop can be rewritten with recursion - they solve the same problems. The factorial above is identical in effect to an iterative version:

So the choice is about clarity, not capability: recursion reads naturally for problems with a self-similar structure (trees, merge sort), while iteration avoids the memory cost of stacking a call frame per step. The exam may ask you to convert one into the other.

Tiếng Việt

Đệ quy và ngăn gọi hàm

Đệ quy là phương thức gọi chính nó với đầu vào nhỏ hơn. Nó cần một trường hợp cơ sở để dừng các cuộc gọi, và một trường hợp đệ quy tiến gần về trường hợp cơ sở:

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

Không có trường hợp cơ sở đạt được, đệ quy sẽ không bao giờ dừng (lỗi tràn ngăn gọi hàm).

Đệ quy và lặp có thể thay thế cho nhau. Mọi giải pháp đệ quy đều có thể viết lại bằng vòng lặp (phương pháp lặp), và mọi vòng lặp đều có thể viết lại bằng đệ quy - chúng giải quyết cùng một vấn đề. Code factorial ở trên tương đương về hiệu quả với phiên bản lặp:

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

Vì vậy, sự lựa chọn nằm ở sự rõ ràng, không phải khả năng: đệ quy đọc tự nhiên đối với các vấn đề có cấu trúc tự tương đồng (cây, merge sort), trong khi lặp tránh chi phí bộ nhớ của việc lưu khung gọi hàm cho mỗi bước. Đề thi có thể yêu cầu bạn chuyển đổi từ dạng này sang dạng kia.

Explore · ⁨Khám phá⁩

Unfold a recursive call · ⁨Phân rã một cuộc gọi đệ quy⁩

A recursive method calls itself on a smaller input until it hits a base case, then the results fold back up. Step through to watch the calls stack and unwind. · ⁨Một phương thức đệ quy gọi chính nó trên đầu vào nhỏ hơn cho đến khi chạm trạng thái cơ sở, sau đó các kết quả được gộp lại. Bước qua để quan sát các cuộc gọi xếp chồng và giải tán.⁩

Vocabulary · ⁨Từ vựng⁩ Train · ⁨Luyện tập⁩

English	Tiếng Việt
Recursion/rɪˈkɜːʃn/	Recursion
base case/beɪs keɪs/	trường hợp cơ sở
Merge sort/mɜːdʒ sɔːt/	Sắp xếp gộp

4.17

Recursive Search and Merge Sort · ⁨Tìm Kiếm và Sắp Xếp Lặp Trong Đệ Quy⁩

Syllabus · ⁨Chương trình⁩

English

Learning Objective 4.17.A: Determine the result of executing recursive algorithms that use strings or collections.

4.17.A.1 Recursion can be used to traverse String objects, arrays, and ArrayList objects.

Learning Objective 4.17.B: Determine the result of each iteration of a binary search algorithm used to search for information in a collection.

4.17.B.1 Data must be in sorted order to use the binary search algorithm. Binary search starts at the middle of a sorted array or ArrayList and eliminates half of the array or ArrayList in each recursive call until the desired value is found or all elements have been eliminated.
4.17.B.2 Binary search is typically more efficient than linear search.
- Exclusion statement: Search algorithms other than linear and binary search are outside the scope of the AP Computer Science A course and exam.
4.17.B.3 The binary search algorithm can be written either iteratively or recursively.

Learning Objective 4.17.C: Determine the result of each iteration of the merge sort algorithm when used to sort a collection.

4.17.C.1 Merge sort is a recursive sorting algorithm that can be used to sort elements in an array or ArrayList.
- Exclusion statement: Sorting algorithms other than selection, insertion, and merge sort are outside the scope of the AP Computer Science A course and exam.
4.17.C.2 Merge sort repeatedly divides an array into smaller subarrays until each subarray is one element and then recursively merges the sorted subarrays back together in sorted order to form the final sorted array.

Tiếng Việt

Mục tiêu học tập 4.17.A: Xác định kết quả của việc thực thi các thuật toán đệ quy sử dụng chuỗi hoặc tập hợp dữ liệu.

4.17.A.1 Đệ quy có thể được sử dụng để duyệt qua String đối tượng, mảng và ArrayList đối tượng.

Mục tiêu học tập 4.17.B: Xác định kết quả của mỗi lần lặp của thuật toán tìm kiếm nhị phân được sử dụng để tìm thông tin trong một tập hợp dữ liệu.

4.17.B.1 Dữ liệu phải được sắp xếp theo thứ tự để sử dụng thuật toán tìm kiếm nhị phân. Tìm kiếm nhị phân bắt đầu ở giữa mảng hoặc ArrayList đã sắp xếp và loại bỏ một nửa mảng hoặc ArrayList trong mỗi lần gọi đệ quy cho đến khi giá trị mong muốn được tìm thấy hoặc tất cả các phần tử đã bị loại bỏ.
4.17.B.2 Tìm kiếm nhị phân thường hiệu quả hơn tìm kiếm tuyến tính.
- Khẳng định loại trừ: Các thuật toán tìm kiếm khác ngoài tìm kiếm tuyến tính và nhị phân nằm ngoài phạm vi của khóa học và bài thi AP Computer Science A.
4.17.B.3 Thuật toán tìm kiếm nhị phân có thể được viết theo dạng lặp hoặc đệ quy.

Mục tiêu học tập 4.17.C: Xác định kết quả của mỗi lần lặp của thuật toán sắp xếp gộp (merge sort) khi được sử dụng để sắp xếp một tập hợp dữ liệu.

4.17.C.1 Sắp xếp gộp (Merge sort) là thuật toán sắp xếp đệ quy có thể được sử dụng để sắp xếp các phần tử trong mảng hoặc ArrayList.
- Khẳng định loại trừ: Các thuật toán sắp xếp khác ngoài sắp xếp chọn, sắp xếp chèn và sắp xếp gộp nằm ngoài phạm vi của khóa học và bài thi AP Computer Science A.
4.17.C.2 Sắp xếp gộp liên tục chia mảng thành các mảng con nhỏ hơn cho đến khi mỗi mảng con chỉ còn một phần tử, sau đó đệ quy gộp các mảng con đã sắp xếp trở lại với nhau theo thứ tự để tạo thành mảng đã sắp xếp cuối cùng.

Source: College Board AP Course and Exam Description · ⁨Nguồn: Mô tả Khóa học và Bài thi College Board AP⁩

English

Merge sort: split, then merge

Recursion powers efficient algorithms. Binary search can be written recursively (search the correct half). Merge sort 归并排序 splits the array in half, sorts each half recursively, then merges the two sorted halves – taking about $n\log_2 n$ steps, much faster than selection or insertion sort on large data.

Worked example. Trace factorial(4). Each call defers to a smaller one: factorial(4) = 4 * factorial(3) = 4 * 3 * factorial(2) = 4 * 3 * 2 * factorial(1). factorial(1) hits the base case and returns 1, so the calls unwind inward: 2 * 1 = 2, then 3 * 2 = 6, then 4 * 6 = 24. Writing each call above its returned value is the reliable way to trace recursion.

Exam skill: trace a recursive method by writing out each call and its return value, and know that merge sort's efficiency ($n\log n$) beats the $n^2$ simple sorts.

Tiếng Việt

Sắp xếp hợp nhất: chia, sau đó gộp

Đệ quy cung cấp sức mạnh cho các thuật toán hiệu quả. Tìm kiếm nhị phân có thể viết dưới dạng đệ quy (tìm kiếm trong nửa đúng). Merge sort chia đôi mảng, sắp xếp mỗi nửa đệ quy, sau đó gộp hai nửa đã sắp xếp lại với nhau – tốn khoảng $n\log_2 n$ bước, nhanh hơn nhiều so với selection sort hoặc insertion sort trên dữ liệu lớn.

Sắp xếp gộp chia mảng thành các phần tử đơn lẻ, sau đó gộp các nửa đã sắp xếp lại lên trên — Merge sort chia mảng thành từng phần tử đơn lẻ, sau đó gộp các nửa đã sắp xếp trở lên

Ví dụ minh họa. Theo dõi factorial(4). Mỗi lần gọi sẽ chuyển sang một lần gọi nhỏ hơn: factorial(4) = 4 * factorial(3) = 4 * 3 * factorial(2) = 4 * 3 * 2 * factorial(1). factorial(1) chạm đến trạng thái cơ sở và trả về 1, do đó các lần gọi được giải nén từ ngoài vào trong: 2 * 1 = 2, sau đó là 3 * 2 = 6, rồi 4 * 6 = 24. Việc viết mỗi lần gọi ngay trên giá trị mà nó trả về là cách theo dõi đệ quy đáng tin cậy nhất.

Kỹ năng làm bài thi: theo dõi một phương thức đệ quy bằng cách viết ra từng cuộc gọi và giá trị trả về, và biết rằng độ hiệu quả của merge sort ($n\log n$) vượt trội hơn so với các thuật toán sắp xếp đơn giản ($n^2$).

4.17

Exam tips · ⁨Mẹo làm bài thi⁩

English

Weigh both benefits and harms of collecting data — this unit is tested through short written justification, not code.
Protect personally identifiable information (PII) and explain privacy and security risks in context.
Name real harms: data breaches, surveillance, and algorithmic bias from unrepresentative data.
Respect intellectual property and licensing when you reuse code or data.
Give a specific, reasoned answer — a vague "it could be bad" earns no marks.

Tiếng Việt

Cân nhắc cả lợi ích và tác hại của việc thu thập dữ liệu — đơn vị này được kiểm tra qua đoạn văn giải thích ngắn, không phải code.
Bảo vệ thông tin cá nhân nhận diện được (PII) và giải thích các rủi ro về quyền riêng tư và bảo mật trong ngữ cảnh cụ thể.
Nêu các tác hại thực tế: rò rỉ dữ liệu, giám sát, và thiên kiến thuật toán do dữ liệu không đại diện.
Tôn trọng quyền sở hữu trí tuệ và giấy phép khi tái sử dụng code hoặc dữ liệu.
Đưa ra câu trả lời cụ thể, có lý lẽ — một câu trả lời mơ hồ như "nó có thể gây hại" sẽ không được điểm.

Interactive lessons on this topic · ⁨Bài học tương tác về chủ đề này⁩

Work through it step by step, with instant-check exercises. · ⁨Làm theo từng bước, kèm theo bài tập kiểm tra ngay lập tức.⁩

Past Papers · ⁨Đề thi cũ⁩

More topics in AP Computer Science A · ⁨AP Khoa học máy tính A⁩ · ⁨Nhiều chủ đề hơn trong AP Computer Science A · ⁨AP Khoa học máy tính A⁩⁩