การเก็บรวบรวมข้อมูล

AP Computer Science A · หัวข้อ 4

ดูสไลด์ ฝึกฝน

บทเรียนวิดีโอสำหรับหัวข้อนี้ เปิดหน้าวิดีโอ

4.1

จริยธรรมในการเก็บรวบรวมข้อมูล

หลักสูตร

วัตถุประสงค์การเรียนรู้ 4.1.A: อธิบายความเสี่ยงต่อความเป็นส่วนตัวจากการเก็บรวบรวมและจัดเก็บข้อมูลส่วนบุคคลบนระบบคอมพิวเตอร์

4.1.A.1 เมื่อใช้คอมพิวเตอร์ ความเป็นส่วนตัวส่วนบุคคลอาจเสี่ยงต่อการถูกคุกคาม เมื่อพัฒนาโปรแกรมใหม่ๆ นักเขียนโปรแกรมควรพยายามปกป้องความเป็นส่วนตัวของผู้ใช้

วัตถุประสงค์การเรียนรู้ 4.1.B: อธิบายความสำคัญของการตระหนักถึงคุณภาพของข้อมูลและปัญหาที่อาจเกิดขึ้นเมื่อใช้ชุดข้อมูล

4.1.B.1 ความลำเอียงเชิงอัลกอริทึม (Algorithmic bias) อธิบายถึงความผิดพลาดในระบบและซ้ำซ้อนในโปรแกรมที่ก่อให้เกิดผลลัพธ์ที่ไม่เป็นธรรมต่อกลุ่มผู้ใช้บางกลุ่ม
4.1.B.2 นักเขียนโปรแกรมควรตระหนักถึงวิธีการเก็บรวบรวมชุดข้อมูลและความเสี่ยงของความลำเอียงก่อน使用该ข้อมูลเพื่อสรุปข้อมูลใหม่หรือดึงข้อสรุป
4.1.B.3 บางชุดข้อมูลไม่สมบูรณ์หรือมีข้อมูลที่ไม่ถูกต้อง การใช้ข้อมูลเช่นนี้ในการพัฒนาหรือใช้งานโปรแกรมอาจทำให้โปรแกรมทำงานผิดพลาดหรือไม่มีประสิทธิภาพ

วัตถุประสงค์การเรียนรู้ 4.1.C: ระบุชุดข้อมูลที่เหมาะสมเพื่อใช้ในการแก้ปัญหาหรือตอบคำถามเฉพาะ

4.1.C.1 เนื้อหาของชุดข้อมูลอาจเกี่ยวข้องกับคำถามหรือหัวข้อเฉพาะและอาจไม่เหมาะสมในการให้คำตอบที่ถูกต้องหรือสรุปข้อมูลสำหรับคำถามหรือหัวข้ออื่น

แหล่งที่มา: คำอธิบายหลักสูตรและข้อสอบ College Board AP

ตู้เซิร์ฟเวอร์ในศูนย์ข้อมูล — ข้อมูลขนาดใหญ่ยกประเด็นทางจริยธรรมเกี่ยวกับการเก็บรวบรวมและการใช้

โปรแกรมที่เก็บรวบรวมข้อมูลก่อให้เกิดคำถามเรื่อง ความเป็นส่วนตัว และ ความยินยอม เก็บเฉพาะสิ่งที่จำเป็น ปกป้องไว้ และrecursive sobre其真实性การใช้ ข้อมูลอาจมี อคติ หากไม่สะท้อนทุกคนอย่างเป็นธรรม นำไปสู่ผลลัพธ์ที่ไม่ยุติธรรม — ซึ่งเป็นความรับผิดชอบที่มาพร้อมกับการจัดเก็บข้อมูล

4.2

ทำไมเราจึงต้องใช้โครงสร้างข้อมูล

หลักสูตร

วัตถุประสงค์การเรียนรู้ 4.2.A: แสดงรูปแบบและอัลกอริทึมที่เกี่ยวข้องกับชุดข้อมูลที่พบในชีวิตประจำวันโดยใช้ภาษาเขียนหรือแผนภาพ

4.2.A.1 ชุดข้อมูล (Data set) คือกลุ่มของข้อมูลหรือชิ้นส่วนข้อมูลเฉพาะเจาะจง
4.2.A.2 ชุดข้อมูลสามารถถูกจัดการและวิเคราะห์เพื่อแก้ปัญหาหรือตอบคำถาม ในการวิเคราะห์ชุดข้อมูล ค่าต่างๆ ภายในชุดจะถูกเข้าถึงและใช้งานทีละค่า จากนั้นจะประมวลผลตามผลลัพธ์ที่ต้องการ
4.2.A.3 ข้อมูลสามารถแสดงในรูปแบบแผนภาพโดยใช้ตารางหรือกราฟ แผนภาพนี้สามารถใช้วางแผนอัลกอริทึมที่จะนำไปใช้จัดการข้อมูล

แหล่งที่มา: คำอธิบายหลักสูตรและข้อสอบ College Board AP

ตู้เอกสาร: โครงสร้างข้อมูลจัดเก็บหลายค่าภายใต้ชื่อเดียวเพื่อให้อัลกอริทึมประมวลผลได้

ตัวแปรหนึ่งตัวเก็บค่าได้เพียงหนึ่งค่า ปัญหาจริงต้องการจัดเก็บ หลาย ค่าที่เกี่ยวข้องกัน — รายชื่อนักเรียน, พิกเซล, ค่าอ่านเซ็นเซอร์ โครงสร้างข้อมูล จัดกลุ่มโครงสร้างข้อมูลเพื่อให้เราจัดเก็บ ค้นหา และประมวลผลรายการได้อย่างมีประสิทธิภาพ หลักสูตร AP ใช้สามอย่างคือ อาร์เรย์, ArrayList และ อาร์เรย์ 2 มิติ

คำศัพท์ ฝึกฝน

English	ไทย
array/əˈreɪ/	อาร์เรย์
Traverse/trəˈvɜːs/	การ traversal
ArrayList/əˈreɪ lɪst/	ArrayList

4.3

การสร้างและอ่านอาร์เรย์

หลักสูตร

วัตถุประสงค์การเรียนรู้ 4.3.A: พัฒนาโค้ด用於表示由一维(1D)数组对象组成的相关数据集合

4.3.A.1 แอรรے (Array) เก็บหลายค่าที่มีประเภทเดียวกัน ค่าเหล่านี้可以是基本类型或对象引用
4.3.A.2 ความยาวของแอรรےถูกกำหนดตอนสร้างและไม่สามารถเปลี่ยนได้ ความยาวของแอรรےสามารถเข้าถึงผ่านคุณสมบัติ length
4.3.A.3 เมื่อสร้างแอรรےโดยใช้คีย์เวิร์ด new องค์ประกอบทั้งหมดจะถูกเริ่มต้นด้วยค่าเริ่มต้นสำหรับประเภทข้อมูลขององค์ประกอบ ค่าเริ่มต้นสำหรับ int คือ 0, สำหรับ double คือ 0.0, สำหรับ boolean คือ false, และสำหรับประเภทอ้างอิงคือ null
4.3.A.4 สามารถใช้ List ตัวเริ่มต้น (Initializer lists) เพื่อสร้างและเริ่มต้นค่าแอรรے
4.3.A.5 ใช้วงเล็บเหลี่ยม [ ] ในการเข้าถึงและแก้ไของค์ประกอบใน 1D Array โดยใช้ Index
4.3.A.6 ค่า Index ที่ถูกต้องสำหรับแอรรےคือ 0 ถึงความยาวของแอรรےลบ 1 (รวมค่าทั้งสอง) การใช้ค่า Index นอกช่วงนี้จะส่งผลให้เกิด ArrayIndexOutOfBoundsException

แหล่งที่มา: คำอธิบายหลักสูตรและข้อสอบ College Board AP

อาร์เรย์ คือโครงสร้างข้อมูลที่จัดเรียงลำดับขนาดคงที่ของค่าชนิดเดียวกัน ดัชนีเริ่มจาก 0 ไปจนถึง length - 1:

อาร์เรย์หนึ่งมิติ (รายการ) พร้อมดัชนีและขอบเขต

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)

การเข้าถึงดัชนีนอกเหนือจาก 0..length-1 จะเกิดข้อผิดพลาด ArrayIndexOutOfBoundsException

4.4

การเยี่ยมชมแต่ละองค์ประกอบของอาร์เรย์

หลักสูตร

จุดประสงค์การเรียนรู้ 4.4.A: พัฒนาโค้ดที่ใช้สำรวจองค์ประกอบใน Arroz 1D และกำหนดผลลัพธ์จากการสำรวจเหล่านั้น

4.4.A.1 การสำรวจแอรรے คือการใช้คำสั่งทำซ้ำเพื่อเข้าถึงองค์ประกอบทั้งหมดหรือลำดับขององค์ประกอบในแอรรے
4.4.A.2 การสำรวจแอรรےด้วยวงลูป for แบบมี Index หรือ while loop ต้องเข้าถึงองค์ประกอบโดยใช้ Indices ของมัน
4.4.A.3 Header ของ enhanced for loop รวมถึงตัวแปร ซึ่งเรียกว่าตัวแปร enhanced for loop สำหรับแต่ละ Iteration ของ enhanced for loop, ตัวแปร enhanced for loop จะได้รับค่า Copy ขององค์ประกอบโดยไม่ใช้ Index ของมัน
4.4.A.4 การกำหนดค่าใหม่ให้กับตัวแปร enhanced for loop ไม่ทำให้ค่าที่จัดเก็บใน Arroz เปลี่ยนแปลง
4.4.A.5 เมื่อ Arroz เก็บ Object References, Attributes สามารถแก้ไขได้โดยการเรียก Methods บนตัวแปร enhanced for loop สิ่งนี้ไม่ทำให้ Object References ที่จัดเก็บใน Arroz เปลี่ยนแปลง
4.4.A.6 โค้ดที่เขียนโดยใช้ enhanced for loop เพื่อสำรวจองค์ประกอบใน Arroz สามารถเขียน ulangโดยใช้ Indexed for loop หรือ while loop ได้

แหล่งที่มา: คำอธิบายหลักสูตรและข้อสอบ College Board AP

ท่องผ่าน อาร์เรย์ด้วยลูป for (ให้ดัชนี) หรือลูป enhanced for / for-each (ให้แต่ละค่า, อ่านเท่านั้น):

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

อัลกอริทึมมาตรฐานสำหรับอาร์เรย์

หลักสูตร

จุดประสงค์การเรียนรู้ 4.5.A: เขียนโค้ดสำหรับอัลกอริทึมมาตรฐานและอัลกอริทึมต้นฉบับสำหรับบริบทหรือสเปกซิฟิกชันเฉพาะที่เกี่ยวข้องกับอาร์เรย์ และระบุผลลัพธ์ของอัลกอริทึมเหล่านี้

4.5.A.1 มีอัลกอริทึมมาตรฐานที่ใช้การ traversal ของอาร์เรย์เพื่อ:
- หาค่าต่ำสุดหรือสูงสุด
- คำนวณผลรวมหรือค่าเฉลี่ย
- ตรวจสอบว่ามีอย่างน้อยหนึ่งองค์ประกอบมีคุณสมบัติเฉพาะหรือไม่
- ตรวจสอบว่ามีองค์ประกอบทั้งหมดมีคุณสมบัติเฉพาะหรือไม่
- หานจำนวนองค์ประกอบที่มีคุณสมบัติเฉพาะ
- เข้าถึงคู่ขององค์ประกอบที่ต่อเนื่องกันทั้งหมด
- ตรวจสอบการมีอยู่หรือขาดหายขององค์ประกอบซ้ำ
- เลื่อนหรือหมุนองค์ประกอบไปทางซ้ายหรือขวา
- สลับลำดับขององค์ประกอบ

แหล่งที่มา: คำอธิบายหลักสูตรและข้อสอบ College Board AP

ทำให้อยู่ในใจในแพทเทิร์นเหล่านี้: คำนวณ ผลรวม หรือ ค่าเฉลี่ย, ค้นหา ค่าสูงสุด/ต่ำสุด, นับ รายการที่ตรงตามเงื่อนไข, ตรวจสอบหา ค่าซ้ำ และ ย้อนกลับ หรือ เลื่อน องค์ประกอบ แต่ละอันเป็นการท่องผ่านพร้อมผลลัพธ์สะสม:

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

4.6

การอ่านข้อมูลจากไฟล์ข้อความ

หลักสูตร

จุดประสงค์การเรียนรู้ 4.6.A: เขียนโค้ดเพื่ออ่านข้อมูลจากไฟล์ข้อความ

4.6.A.1 ไฟล์ คือพื้นที่จัดเก็บข้อมูลที่คงอยู่ได้แม้โปรแกรมจะไม่ทำงาน ข้อมูลในไฟล์สามารถเข้าถึงได้ระหว่างการทำงานโปรแกรม
4.6.A.2 ไฟล์สามารถเชื่อมต่อกับโปรแกรมโดยใช้คลาส File และ Scanner
4.6.A.3 สามารถเปิดไฟล์ได้โดยการสร้างวัตถุ File โดยใช้ชื่อไฟล์เป็นพารามิเตอร์ของ constructor
- File(String str) เป็น constructor File ที่รับชื่อไฟล์ String เพื่อเปิดสำหรับการอ่าน โดยที่ str คือ pathname สำหรับไฟล์นั้น
4.6.A.4 เมื่อใช้คลาส File จำเป็นต้องระบุว่าควรทำอย่างไรหากไม่สามารถเปิดไฟล์ที่มีชื่อนั้นได้ วิธีหนึ่งคือเพิ่ม throws IOException ไว้ที่ส่วนหัวของเมทโอดที่ใช้ไฟล์ หากชื่อไฟล์ไม่ถูกต้อง โปรแกรมจะหยุดทำงาน
4.6.A.5 คลาส File และ IOException เป็นส่วนหนึ่งของแพ็กเกจ java.io ต้องใช้ statement import เพื่อให้คลาสเหล่านี้พร้อมใช้งานในโปรแกรม
4.6.A.6 เมทโอดและ constructor ของ Scanner ด้านล่างนี้ รวมถึงหน้าที่การใช้งานของแต่ละอย่าง เป็นส่วนหนึ่งของ Java Quick Reference:
- Scanner(File f) เป็น constructor Scanner ที่รับ ⟨⟩ File สำหรับการอ่าน
- int nextInt() return 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() return 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() return 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() กลับบรรทัดถัดไปของข้อความในฐานะ ⟨⟩ String ที่อ่านจากไฟล์หรือแหล่งอินพุต; สามารถกลับค่า string ว่างได้หากถูกเรียกทันทีหลังจากเมทโอด Scanner อื่นที่อ่านจากไฟล์หรือแหล่งอินพุต
- String next() จะคืนค่า String ถัดไปที่ถูกอ่านจากไฟล์หรือแหล่งข้อมูลเข้า
- boolean hasNext() กลับค่า true หากมีรายการถัดไปให้อ่านในไฟล์หรือแหล่งอินพุต; กลับค่า false ในกรณีอื่น
- void close() ปิด Scanner นี้
- ข้อตัดออก: การรับข้อมูลจากคีย์บอร์ดอยู่นอกขอบเขตของหลักสูตรและข้อสอบ AP Computer Science A
4.6.A.7 การใช้ nextLine และเมทโッド Scanner อื่นๆ ร่วมกันบนแหล่งอินพุตเดียวกัน บางครั้งจำเป็นต้องมีโค้ดเพื่อปรับให้เข้ากับการจัดการ whitespace ที่แตกต่างกันของเมทโอดเหล่านี้
- ข้อตัดออก: การเขียนหรือวิเคราะห์โค้ดที่ใช้ทั้ง nextLine และเมทโッド Scanner อื่นๆ บนแหล่งอินพุตเดียวกันอยู่นอกขอบเขตของหลักสูตรและข้อสอบ AP Computer Science A
4.6.A.8 เมทโอด String เพิ่มเติมด้านล่างนี้ รวมถึงหน้าที่การใช้งาน เป็นส่วนหนึ่งของ Java Quick Reference:
- String[] split(String del) กลับค่า ⟨⟩ String Array โดยที่แต่ละองค์ประกอบเป็น substring ของ ⟨⟩ this String ซึ่งถูกแยกด้วย matches ของนิพจน์ที่ระบุ del
- ข้อตัดออก: พารามิเตอร์ del ใช้รูปแบบที่เรียกว่า regular expression การเขียนหรือวิเคราะห์โค้ดที่ใช้คุณสมบัติพิเศษใดๆ ของ regular expressions (เช่น \\*, \\.) นอกรอบของหลักสูตรและข้อสอบ AP Computer Science A
4.6.A.9 สามารถใช้ loop while เพื่อตรวจสอบว่ายังเหลือ ⟨⟩ ให้อ่านในไฟล์หรือไม่ โดยใช้เมทโอด hasNext เป็นเงื่อนไขของ loop
4.6.A.10 ควรปิดไฟล์เมื่อโปรแกรมใช้เสร็จแล้ว调用 closeメソッドจาก Scanner เพื่อปิดไฟล์

แหล่งที่มา: คำอธิบายหลักสูตรและข้อสอบ College Board AP

File และ IOException อยู่ภายใน java.io ดังนั้นโปรแกรมที่อ่านไฟล์จำเป็นต้องใช้ import java.io.*; การเปิดไฟล์อาจล้มเหลว (อาจไม่มีการมีอยู่), และ Java บังคับให้คุณจัดการกับสิ่งนั้น — วิธีที่ง่ายที่สุดคือการเพิ่ม throws IOException เข้าไปในหัวเมทόδ Scanner จากนั้นอ่านไฟล์บรรทัดต่อบรรทัด โดยใช้ hasNext... เพื่อทดสอบก่อนอ่าน:

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

การอ่านท็อกเคนที่ระบุประเภทด้วย nextInt(), nextDouble() หรือ nextBoolean() จะเกิดข้อผิดพลาด InputMismatchException หากท็อกเคนถัดไปไม่ใช่ประเภทที่ถูกต้อง — ตัวอย่างเช่นการเรียก nextInt() เมื่อสิ่งถัดไปในไฟล์คือคำ cat

4.7

การห่อหุ้มตัวเลขในวัตถุ

หลักสูตร

จุดประสงค์การเรียนรู้ 4.7.A: เขียนโค้ดเพื่อใช้วัตถุ Integer และ Double จากชนิด primitive ของพวกมัน และระบุผลลัพธ์ของการใช้วัตถุเหล่านี้

4.7.A.1 คลาส Integer และคลาส Double เป็นส่วนหนึ่งของแพ็กเกจ java.lang วัตถุ Integer เป็น immutable หมายความว่าเมื่อสร้างวัตถุ Integer แล้ว คุณสมบัติของมันไม่สามารถเปลี่ยนแปลงได้ วัตถุ Double เป็น immutable หมายความว่าเมื่อสร้างวัตถุ Double แล้ว คุณสมบัติของมันไม่สามารถเปลี่ยนแปลงได้
4.7.A.2 Autoboxing คือการแปลงอัตโนมัติที่ Java Compiler ทำระหว่างชนิด primitive กับ wrapper class ที่สอดคล้อง与之 This includes converting an int to an Integer and a double to a Double. The Java compiler applies autoboxing when a primitive value is:
- ส่งเป็นพารามิเตอร์ไปยังเมทโอดที่คาดหวังวัตถุของ wrapper class ที่สอดคล้อง与之
- ถูกกำหนดให้กับตัวแปรของ wrapper class ที่สอดคล้อง与之
4.7.A.3 Unboxing คือการแปลงอัตโนมัติที่ Java Compiler ทำจาก wrapper class เป็นชนิด primitive 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:
- ส่งเป็นพารามิเตอร์ไปยังเมทโอดที่คาดหวังค่าของชนิด primitive ที่สอดคล้อง与之
- ถูกกำหนดให้กับตัวแปรของชนิด primitive ที่สอดคล้อง与之
4.7.A.4 เมทโอด Integer ของคลาสด้านล่างนี้ รวมถึงหน้าที่การใช้งาน เป็นส่วนหนึ่งของ Java Quick Reference:
- static int parseInt(String s) กลับค่าพารามิเตอร์ String ในฐานะ int
4.7.A.5 เมทโอด Double ของคลาสด้านล่างนี้ รวมถึงหน้าที่การใช้งาน เป็นส่วนหนึ่งของ Java Quick Reference:
- static double parseDouble(String s) กลับค่าพารามิเตอร์ String ในฐานะ double

แหล่งที่มา: คำอธิบายหลักสูตรและข้อสอบ College Board AP

ArrayList เก็บ วัตถุ ไม่ใช่พรีมิทีฟ ดังนั้นพรีมิทีฟจะถูก ห่อหุ้ม ในวัตถุ: Integer ห่อหุ้ม int, Double ห่อหุ้ม double Java ทำสิ่งนี้ด้วย autoboxing (int เป็น Integer) และ unboxing (กลับคืนมา) โดยอัตโนมัติ ดังนั้นคุณสามารถเขียน list.add(5) และ int x = list.get(0)

คำศัพท์ ฝึกฝน

English	ไทย
autoboxing/ˌɔːtəʊˈbɒksɪŋ/	การห่อหุ้มอัตโนมัติ (Autoboxing)

4.8

ชุดเครื่องมือ ArrayList

หลักสูตร

จุดประสงค์การเรียนรู้ 4.8.A: เขียนโค้ดสำหรับกลุ่มของวัตถุที่เกี่ยวข้องกันโดยใช้วัตถุ ArrayList และระบุผลลัพธ์ของการเรียกเมทโอดบนวัตถุเหล่านี้

4.8.A.1 ArrayList เป็นออบเจกต์ที่ปรับขนาดได้และประกอบด้วยตัวอ้างอิงถึงออบเจกต์
4.8.A.2 ตัวสร้าง ArrayList ArrayList() สร้างลิสต์ว่าง
4.8.A.3 Java รองรับชนิดแบบ泛型 (generic type) ArrayList<E> โดยที่พารามิเตอร์ชนิด E ระบุชนิดขององค์ประกอบ เมื่อ ArrayList<E> ถูกกำหนดไว้ ชนิดของพารามิเตอร์อ้างอิงและชนิดกลับคืนเมื่อใช้วิธีการ ArrayList จะเป็นชนิด E 。 ArrayList<E> ดีกว่า ArrayList 。 ตัวอย่างเช่น ArrayList<String> names = new ArrayList<String>(); ช่วยให้ผู้Compileค้นหาข้อผิดพลาดที่จะพบได้ในเวลารัน
4.8.A.4 คลาส ArrayList เป็นส่วนหนึ่งของแพ็กเกจ java.util 。 ต้องใช้คำสั่ง import เพื่อให้คลาสนี้พร้อมใช้งานในโปรแกรม
4.8.A.5 วิธีการ ArrayList berikut—including what they do and when they are used—are part of the Java Quick Reference:
- int size() คืนค่าจำนวนองค์ประกอบในลิสต์
- boolean add(E obj) เพิ่ม obj เข้าไปท้ายลิสต์; คืนค่า true
- void add(int index, E obj)แทรก obj ที่ตำแหน่ง index (0 <= index <= size), ย้ายองค์ประกอบที่ตำแหน่ง index และสูงกว่าไปทางขวา (เพิ่ม 1 ให้กับดัชนี) และเพิ่ม 1 ให้กับขนาด
- E get(int index) คืนค่าองค์ประกอบที่ตำแหน่ง index ในลิสต์
- E set(int index, E obj) แทนที่องค์ประกอบที่ตำแหน่ง index ด้วย obj; คืนค่าองค์ประกอบที่เคยอยู่ที่ตำแหน่ง index
- E remove(int index) ลบองค์ประกอบออกจากตำแหน่ง index, ย้ายองค์ประกอบที่ตำแหน่ง index + 1 และต่ำกว่าไปทางซ้าย (ลบ 1 ออกจากดัชนี) และลบ 1 ออกจากขนาด; คืนค่าองค์ประกอบที่เคยอยู่ที่ตำแหน่ง index
4.8.A.6 ดัชนีสำหรับ ArrayList เริ่มที่ 0 และสิ้นสุดที่จำนวนองค์ประกอบ - 1

แหล่งที่มา: คำอธิบายหลักสูตรและข้อสอบ College Board AP

*ArrayList จริงๆ แล้วคืออะไร

ArrayList ขยายและหดตัวเมื่อคุณเพิ่มหรือลบรายการ ประกาศ它以 element type ใน <>:

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

การเยี่ยมชมแต่ละองค์ประกอบของ ArrayList

หลักสูตร

จุดประสงค์การเรียนรู้ 4.9.A: เขียนโค้ดเพื่อ traversal (สำรวจผ่าน) องค์ประกอบของ ArrayList และกำหนดผลลัพธ์ของการสำรวจเหล่านั้น

4.9.A.1 การ traversing ⟨ArrayList⟩ คือการใช้คำสั่ง iterative (วนซ้ำ) หรือ recursive เพื่อเข้าถึงองค์ประกอบทั้งหมดหรือลำดับที่กำหนดขององค์ประกอบใน ⟨ArrayList⟩
4.9.A.2 การลบองค์ประกอบระหว่างการวน遍历 ArrayList ต้องการการใช้เทคนิคพิเศษเพื่อหลีกเลี่ยงการข้ามองค์ประกอบ
4.9.A.3 การพยายามเข้าถึงค่าดัชนีนอกเหนือจากช่วงที่กำหนดจะส่งผลให้เกิด IndexOutOfBoundsException
4.9.A.4 การเปลี่ยนขนาดของ ArrayList ระหว่างการวน遍历โดยใช้ enhanced for loop อาจทำให้เกิด ConcurrentModificationException ดังนั้น เมื่อใช้ enhanced for loop ในการวน遍历 ArrayList คุณไม่ควรเพิ่มหรือลบองค์ประกอบ

แหล่งที่มา: คำอธิบายหลักสูตรและข้อสอบ College Board AP

ท่องผ่านด้วยลูปดัชนีหรือลูป for-each เหมือนกับอาร์เรย์ (ใช้ size() และ get(i)):

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

ทักษะสำหรับการสอบ: เมื่อ ลบ รายการในลูปดัชนี ให้either ลูป ย้อนกลับ หรือ อย่า เพิ่ม i หลังการลบ — ไม่เช่นนั้นการลบจะเลื่อนองค์ประกอบไปทางซ้ายและคุณจะข้ามหนึ่งรายการ และห้ามเพิ่มหรือลบองค์ประกอบในขณะที่ท่องผ่าน ArrayList ด้วยลูป for-each: การเปลี่ยนแปลงขนาดกลางลูปจะเกิดข้อผิดพลาด ConcurrentModificationException ดังนั้นใช้ลูปดัชนี (ย้อนกลับ ตามข้างต้น) ทุกครั้งที่จำเป็นต้องลบ

4.10

อัลกอริทึมมาตรฐานสำหรับ ArrayList

หลักสูตร

วัตถุประสงค์การเรียนรู้ 4.10.A: เขียนโค้ดสำหรับอัลกอริทึมมาตรฐานและต้นฉบับสำหรับบริบทหรือข้อกำหนดเฉพาะที่เกี่ยวข้องกับวัตถุ ArrayList และกำหนดผลลัพธ์ของอัลกอริทึมเหล่านี้

4.10.A.1 มี ArrayList อัลกอริทึมมาตรฐานที่ใช้การ traversals เพื่อ:
- หาค่าต่ำสุดหรือสูงสุด
- คำนวณผลรวมหรือค่าเฉลี่ย
- ตรวจสอบว่ามีอย่างน้อยหนึ่งองค์ประกอบมีคุณสมบัติเฉพาะหรือไม่
- ตรวจสอบว่ามีองค์ประกอบทั้งหมดมีคุณสมบัติเฉพาะหรือไม่
- หานจำนวนองค์ประกอบที่มีคุณสมบัติเฉพาะ
- เข้าถึงคู่ขององค์ประกอบที่ต่อเนื่องกันทั้งหมด
- ตรวจสอบการมีอยู่หรือขาดหายขององค์ประกอบซ้ำ
- เลื่อนหรือหมุนองค์ประกอบไปทางซ้ายหรือขวา
- สลับลำดับขององค์ประกอบ
- เพิ่มองค์ประกอบ
- ลบองค์ประกอบ
4.10.A.2 บางอัลกอริทึมต้องการหลาย String, array, หรือ ArrayList วัตถุต้องถูก traverses พร้อมกัน

แหล่งที่มา: คำอธิบายหลักสูตรและข้อสอบ College Board AP

อัลกอริทึมเดียวกันกับอาร์เรย์ — ค่าสูงสุด/ต่ำสุด, นับ, ผลรวม — plus การแทรก และ การลบ ที่อาร์เรย์ไม่สามารถทำได้ง่าย งานทั่วไปคือการลบองค์ประกอบทั้งหมดที่ตรงตามเงื่อนไข จัดการกับการเลื่อนดัชนีอย่างระมัดระวัง

4.11

ตาราง: อาร์เรย์สองมิติ

หลักสูตร

Learning Objective Essential Knowledge

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.

แหล่งที่มา: คำอธิบายหลักสูตรและข้อสอบ College Board AP

2D array คือตาราง (แถวและคอลัมน์) — อาร์เรย์ของอาร์เรย์:

อาร์เรย์สองมิติ (ตาราง) พร้อมดัชนียาวและคอลัมน์

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

สำรวจ

เข้าถึง 2D array ด้วยแถวและคอลัมน์

2D array คือตารางที่ระบุตำแหน่งด้วย [row][col] เลื่อนดัชนีเพื่อดูว่าเซลล์ใดถูกเลือก — แถวก่อน คอลัมน์ถัดไป โดยนับตั้งแต่ 0 ทั้งคู่

คำศัพท์ ฝึกฝน

English	ไทย
2D array/ˌtuː ˈdiː əˈreɪ/	2D Array
row-major order/rəʊ ˈmeɪdʒə ˈɔːdə/	ลำดับหลักแถว

4.12

การเดินผ่านตาราง

หลักสูตร

Learning Objective Essential Knowledge

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.

แหล่งที่มา: คำอธิบายหลักสูตรและข้อสอบ College Board AP

การ遍历 2-D array

เยี่ยมชมเซลล์ทั้งหมดด้วย ลูปซ้อน — ลูปภายนอกสำหรับแถว, ลูปภายในสำหรับคอลัมน์ (ลำดับ 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

อัลกอริทึมมาตรฐานสำหรับ 2D Array

หลักสูตร

Learning Objective

Essential Knowledge

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

แหล่งที่มา: คำอธิบายหลักสูตรและข้อสอบ College Board AP

งานตารางทั่วไป: รวมแถวหรือคอลัมน์, ค้นหาค่าสูงสุดในตาราง, นับเซลล์ที่ตรงกัน, หรือรวมเส้นทแยงมุม (ที่ r == c) แต่ละอันเป็นการท่องผ่านแบบซ้อนพร้อมผลลัพธ์สะสม

4.14

การค้นหาค่า: การค้นหาเชิงเส้นและการค้นหาแบบทวิภาค

หลักสูตร

วัตถุประสงค์การเรียนรู้ 4.14.A: พัฒนาโค้ด用於อัลกอริทึมการค้นหาเชิงเส้น (linear search algorithms) เพื่อค้นหาข้อมูลเฉพาะในชุดข้อมูลและตรวจสอบผลลัพธ์จากการดำเนินการค้นหา

4.14.A.1 อัลกอริทึมการค้นหาระดับเส้น เป็นอัลกอริทึมมาตรฐานที่ตรวจสอบแต่ละองค์ประกอบตามลำดับจนกว่าจะพบค่าที่ต้องการหรือตรวจสอบองค์ประกอบทั้งหมดในเมทริกซ์หรือ ArrayList แล้ว อัลกอริทึมการค้นหาระดับเส้นสามารถเริ่มกระบวนการค้นหาจากปลายด้านหนึ่งของเมทริกซ์หรือ ArrayList ได้
4.14.A.2 เมื่อใช้ Linear Search Algorithms กับ Arroz 2D, แต่ละแถวต้องถูกเข้าถึงก่อนแล้วจึงทำ Linear Search กับแต่ละแถวของ Arroz 2D

แหล่งที่มา: คำอธิบายหลักสูตรและข้อสอบ College Board AP

Binary search:减半และพิชิต

Linear search ตรวจสอบแต่ละองค์ประกอบตามลำดับ – ใช้ได้กับรายการใดๆ โดยใช้เวลาสูงสุด $n$ ขั้นตอน
Binary search ใช้งานได้เฉพาะกับรายการที่ เรียงลำดับแล้ว: ตรวจสอบค่าตรงกลาง แล้วตัดครึ่งที่ไม่อาจมีค่าเป้าหมายออก ทำซ้ำจนกว่าจะพบ ค่าใช้จ่ายประมาณ $\log_2 n$ ขั้นตอน – เร็วกว่ามากสำหรับข้อมูลขนาดใหญ่

Binary search halves the range at each step

การค้นหาแบบเชิงเส้นตรวจสอบแต่ละองค์ประกอบตามลำดับจนกว่าจะพบเป้าหมาย

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

ทักษะการสอบ: binary search ต้องการข้อมูลที่เรียงลำดับ; ต้องรู้จำนวนการเปรียบเทียบที่ทำ以及如何 lo, hi, mid อัปเดต

ตัวอย่างทำพร้อมคำตอบ. ค้นหา target = 40 ในอาเรย์ที่เรียงลำดับ {3, 9, 14, 23, 31, 42, 55} (indices 0–6). เริ่มต้น lo=0, hi=6:

mid = (0+6)/2 = 3, a[3]=23 < 40, ดังนั้น lo = 4;
mid = (4+6)/2 = 5, a[5]=42 > 40, ดังนั้น hi = 4;
mid = (4+4)/2 = 4, a[4]=31 < 40, ดังนั้น lo = 5;
ตอนนี้ lo (5) > hi (4), ดังนั้นลูปจบลง – 40 ไม่มีอยู่จริง

แต่ละขั้นตอนลดช่วงลงครึ่งหนึ่ง ดังนั้นแม้การค้นหาไม่พบก็ใช้เพียงสามครั้งในการเปรียบเทียบ

สำรวจ

เปรียบเทียบ linear search กับ binary search

Linear search ตรวจสอบทุกองค์ประกอบทีละตัว; binary search ลดรายการที่ เรียงลำดับแล้ว ลงครึ่งหนึ่งทุกขั้นตอน ดูว่า binary search ถึงเป้าหมายด้วยการเปรียบเทียบน้อยกว่ามาก

คำศัพท์ ฝึกฝน

English	ไทย
Linear search/ˈlɪnɪə sɜːtʃ/	การค้นหาแบบเชิงเส้น
Binary search/ˈbaɪnəri sɜːtʃ/	การค้นหาแบบทวิภาคี

4.15

การจัดระเบียบข้อมูล: Selection Sort และ Insertion Sort

หลักสูตร

วัตถุประสงค์การเรียนรู้ 4.15.A: ตรวจสอบผลลัพธ์จากการดำเนินการขั้นตอนต่างๆ ของอัลกอริทึมการจัดเรียงเพื่อจัดเรียงองค์ประกอบของชุดข้อมูล

4.15.A.1 Selection sort และ insertion sort เป็นอัลกอริทึมการจัดเรียงแบบวนซ้ำที่สามารถใช้用於จัดเรียงองค์ประกอบในเมทริกซ์หรือ ArrayList ได้
4.15.A.2 Selection sort เลือกองค์ประกอบที่เล็กที่สุด (หรือใหญ่ที่สุด) จากส่วนที่ยังไม่ได้จัดเรียงของรายการซ้ำๆ และสลับมันเข้ากับตำแหน่งที่ถูกต้อง (และสุดท้าย) ในส่วนที่จัดเรียงของรายการ
4.15.A.3 การเรียงลำดับด้วยการแทรก (Insertion sort) จะแทรกองค์ประกอบจากส่วนที่ยังไม่เรียงของรายการลงในตำแหน่งที่ถูกต้อง (แต่ไม่จำเป็นต้องเป็นตำแหน่งสุดท้าย) ในส่วนที่เรียงแล้วของรายการ โดยการเลื่อนองค์ประกอบในส่วนที่เรียงแล้วออกไปเพื่อเปิดพื้นที่สำหรับองค์ประกอบใหม่

แหล่งที่มา: คำอธิบายหลักสูตรและข้อสอบ College Board AP

Insertion sort

Bubble sort, pas-by-pass

Selection sort หาองค์ประกอบที่เหลือที่มีค่าน้อยที่สุดซ้ำๆ และสลับตำแหน่งให้เข้าที่
Insertion sort สร้างส่วนหน้าที่เป็นลำดับโดยเพิ่มองค์ประกอบใหม่เข้าไปในตำแหน่งที่เหมาะสม

การเรียงลำดับแบบแทรก ย้ายคีย์แต่ละตัวเข้าตำแหน่งทีละรอบผ่าน

ทั้งสองวิธีง่ายและใช้เวลาประมาณ $n^2$ ขั้นตอนเฉลี่ย – เหมาะกับอาเรย์ขนาดเล็ก สามารถติดตามอาเรย์ได้ หลังจากแต่ละรอบ

สำรวจ

ดูอัลกอริทึมการจัดเรียงลำดับรายการ

Sort จัดเรียงองค์ประกอบให้เป็นลำดับ ก้าวผ่าน selection/insertion sort เพื่อดูว่าพื้นที่ที่เรียงแล้วขยายขึ้นทีละองค์ประกอบ

คำศัพท์ ฝึกฝน

English	ไทย
Selection sort/sɪˈlekʃn sɔːt/	การจัดเรียงแบบเลือก
Insertion sort/ɪnˈsɜːʃn sɔːt/	Insertion sort

4.16

วิธีที่เรียกตัวเอง: Recursion

หลักสูตร

วัตถุประสงค์การเรียนรู้ 4.16.A: ประเมินผลลัพธ์ของการเรียกใช้ฟังก์ชันแบบเรียกซ้ำ

4.16.A.1 ฟังก์ชันแบบเรียกซ้ำ คือฟังก์ชันที่เรียกตัวเอง ฟังก์ชันแบบเรียกซ้ำจะมีอย่างน้อยหนึ่งกรณีฐาน (base case) ซึ่งหยุดการเรียกซ้ำ และมีอย่างน้อยหนึ่งการเรียกซ้ำ การเรียกซ้ำเป็นอีก的一种方式ของการทำซ้ำ
4.16.A.2 แต่ละการเรียกซ้ำจะมีชุดตัวแปรเฉพาะในท้องถิ่นของตนเอง รวมถึงพารามิเตอร์ ค่าพารามิเตอร์จะบันทึกความก้าวหน้าของกระบวนการแบบเรียกซ้ำ เปรียบเสมือนค่าตัวแปรควบคุมวงลูปที่จะบันทึกความก้าวหน้าของวงลูป
4.16.A.3 วิธีแก้ปัญหาแบบเรียกซ้ำสามารถทำซ้ำได้ผ่านการใช้อีทราทีฟ (iterative approach) และในทางกลับกัน亦然
- ข้อความยกเว้น: การเขียนโค้ดแบบเรียกซ้ำอยู่นอกขอบเขตของหลักสูตรและข้อสอบ AP Computer Science A

แหล่งที่มา: คำอธิบายหลักสูตรและข้อสอบ College Board AP

Recursion & the call stack

Recursion คือวิธีการที่เรียกตัวเองด้วยอินพุตที่เล็กลง จำเป็นต้องมี base case ที่หยุดการเรียก และมี recursive case ที่พาไปสู่ base case:

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

หากไม่มี base case ที่เข้าถึงได้ recursion จะไม่หยุด (stack overflow)

Recursion และ iteration เปลี่ยนแปลงกันได้ การแก้ปัญหาแบบ递归สามารถเขียนใหม่ด้วย loop (approach แบบ iterative) และ loop ก็เขียนใหม่ด้วย recursion ได้ – ทั้งคู่แก้ปัญหาร่วมกัน The factorial ข้างต้นมีผลเทียบเท่าแบบ iterative:

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

ดังนั้นการเลือกจึงเป็นเรื่องของ ความชัดเจน ไม่ใช่ความสามารถ: recursion อ่านง่ายสำหรับปัญหาที่มีโครงสร้างคล้ายกันเอง (trees, merge sort) ในขณะที่ iteration หลีกเลี่ยงค่าใช้จ่ายด้านหน่วยความจำจากการวาง call frame ต่อขั้นตอน การสอบอาจถามให้คุณแปลงอย่างหนึ่งเป็นอีกอย่างหนึ่ง

สำรวจ

คลี่Recursive call ออกมา

Recursive method เรียกตัวเองด้วยอินพุตที่เล็กลงจนกระทั่งถึง base case จากนั้นผลลัพธ์จะ folded กลับขึ้นมา ก้าวผ่านเพื่อดูว่า calls สะสมและคลายออกอย่างไร

คำศัพท์ ฝึกฝน

English	ไทย
Recursion/rɪˈkɜːʃn/	Recursion
base case/beɪs keɪs/	กรณีฐาน (Base Case)
Merge sort/mɜːdʒ sɔːt/	การเรียงลำดับแบบรวม (Merge sort)

4.17

การค้นหาแบบ Recursive และการเรียงลำดับแบบ Merge

หลักสูตร

วัตถุประสงค์การเรียนรู้ 4.17.A: ประเมินผลลัพธ์ของการดำเนินการอัลกอริทึมแบบเรียกซ้ำที่ใช้กับสตริงหรือคอลเลกชัน

4.17.A.1 การเรียกซ้ำสามารถใช้เพื่อสำรวจ String ออบเจกต์, แอรรے และ ArrayList ออบเจกต์

วัตถุประสงค์การเรียนรู้ 4.17.B: ประเมินผลลัพธ์ของแต่ละรอบ lặpของอัลกอริทึมการค้นหาแบบไบนารีที่ใช้ในการค้นหาข้อมูลในคอลเลกชัน

4.17.B.1 ข้อมูลต้องอยู่ในรูปแบบที่เรียงลำดับก่อนจึงจะใช้ อัลกอริทึมการค้นหาแบบไบนารีได้ การค้นหาแบบไบนารี เริ่มจากจุดกึ่งกลางของแอรรےที่เรียงลำดับแล้วหรือ ArrayList และตัดครึ่งหนึ่งของแอรรےหรือ ArrayList ออกในแต่ละการเรียกซ้ำ จนกว่าจะพบค่าที่ต้องการหรือ ELEMENTS ทั้งหมดถูกตัดออก
4.17.B.2 การค้นหาแบบไบนารีมีประสิทธิภาพมากกว่าการค้นหาแบบเส้นตรงโดยทั่วไป
- ข้อความยกเว้น: อัลกอริทึมการค้นหาอื่น ๆ ที่ไม่ใช่การค้นหาแบบเส้นตรงและแบบไบนารีอยู่นอกขอบเขตของหลักสูตรและข้อสอบ AP Computer Science A
4.17.B.3 อัลกอริทึมการค้นหาแบบไบนารีสามารถเขียนได้ทั้งแบบอีทราทีฟหรือแบบเรียกซ้ำ

วัตถุประสงค์การเรียนรู้ 4.17.C: ประเมินผลลัพธ์ของแต่ละรอบ lặpของอัลกอริทึม Merge Sort เมื่อใช้ในการเรียงลำดับคอลเลกชัน

4.17.C.1 Merge sort เป็นอัลกอริทึมการเรียงลำดับแบบเรียกซ้ำที่สามารถใช้เพื่อเรียงลำดับองค์ประกอบในแอรรےหรือ ArrayList
- ข้อความยกเว้น: อัลกอริทึมการเรียงลำดับอื่น ๆ ที่ไม่ใช่ Selection Sort, Insertion Sort และ Merge Sort Out of scope ของหลักสูตรและข้อสอบ AP Computer Science A
4.17.C.2 Merge sort จะแบ่งแอรรےออกเป็นแอรรےย่อยที่มีขนาดเล็กลงเรื่อยๆ จนกว่าแต่ละแอรรےย่อยจะมีเพียง 1 องค์ประกอบ แล้วจึงรวมแอรรےย่อยที่เรียงลำดับแล้วกลับเข้าด้วยกันแบบเรียกซ้ำเพื่อสร้างแอรรےที่เรียงลำดับสมบูรณ์

แหล่งที่มา: คำอธิบายหลักสูตรและข้อสอบ College Board AP

Merge sort: แยก แล้วรวม

Recursion เป็นพลังของอัลกอริทึมที่มีประสิทธิภาพ Binary search สามารถเขียนแบบ recursive ได้ (ค้นหาครึ่งที่ถูกต้อง) Merge sort แบ่งอาเรย์เป็นสองส่วน เรียงลำดับแต่ละส่วนแบบ recursive แล้ว merge ครึ่งทั้งสองส่วนที่เป็นลำดับเข้าด้วยกัน – ใช้เวลาประมาณ $n\log_2 n$ ขั้นตอน เร็วกว่า selection หรือ insertion sort มากสำหรับข้อมูลขนาดใหญ่

การเรียงลำดับแบบรวม แยกอาร์เรย์ออกเป็นองค์ประกอบเดี่ยว แล้วรวมครึ่งที่เรียงแล้วกลับขึ้นไป

ตัวอย่างทำพร้อมคำตอบ. ติดตาม factorial(4) Each call ยอมให้ smaller one: factorial(4) = 4 * factorial(3) = 4 * 3 * factorial(2) = 4 * 3 * 2 * factorial(1). factorial(1)触碰 base case และส่งกลับ 1, ดังนั้นการเรียกจะคลายตัวเข้าหาภายใน: 2 * 1 = 2, จากนั้น 3 * 2 = 6, แล้ว 4 * 6 = 24. การเขียนแต่ละ call เหนือค่าที่ส่งกลับคือวิธีที่เชื่อถือได้ในการติดตาม recursion

ทักษะการสอบ: ติดตาม recursive method โดยการเขียนแต่ละ call และค่าที่ส่งกลับออกมา และรู้ว่าประสิทธิภาพของ merge sort ($n\log n$) ดีกว่า $n^2$ sorting methods แบบง่าย

4.17

ข้อแนะนำสำหรับการสอบ

พิจารณาประโยชน์และอันตรายของการเก็บข้อมูล – หน่วยนี้จะทดสอบผ่านการอธิบายสั้นๆ ไม่ใช่โค้ด
ปกป้อง ** personally identifiable information (PII)** อธิบายความเสี่ยงด้านความเป็นส่วนตัวและความปลอดภัยในบริบทนั้น
ชื่อนิยามความเสียหายจริง: data breaches, การเฝ้าระวัง, และ algorithmic bias จากข้อมูลที่ไม่เป็นตัวแทน
เคารพ intellectual property และ licensing เมื่อนำโค้ดหรือข้อมูลกลับมาใช้ใหม่
ให้คำตอบที่เฉพาะเจาะจงและมีเหตุผล – คำตอบเบลอเช่น "มันอาจแย่" ไม่ได้คะแนน

คำศัพท์ ฝึกฝน

English	ไทย
privacy/ˈprɪvəsi/	ความเป็นส่วนตัว
consent/kənˈsent/	ฉันทามติ
bias/ˈbaɪəs/	อคติ
data structure/ˈdeɪtə ˈstrʌktʃə/	โครงสร้างข้อมูล

บทเรียนเชิงโต้ตอบสำหรับหัวข้อนี้

ทำทีละขั้นตอน พร้อมแบบฝึกหัดตรวจสอบผลทันที

ข้อสอบย้อนหลัง

หัวข้อเพิ่มเติมใน AP Computer Science A