1.ง่าย
โครงสร้างข้อมูลใดทำงานตามหลักการ "เข้าหลังออกก่อน" (last in, first out)
- Aลิงก์ลิสต์ (linked list)
- Bตารางแฮช (hash table)
- Cคิว (queue)
- Dสแตก (stack)
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
การดำเนินการใดเป็น O(1) สำหรับอาร์เรย์แต่เป็น O(n) สำหรับลิงก์ลิสต์เชิงเดี่ยว
- Aการเข้าถึงสมาชิกที่ดัชนี i
- Bการลบสมาชิกหัว
- Cการอ่านสมาชิกตัวแรก
- Dการแทรกที่หัว
3.ง่าย
การดำเนินการ peek (หรือ top) บนสแตกทำอะไร
- Aเอาสมาชิกทั้งหมดออกจากสแตก
- Bเอาสมาชิกบนสุดออกและคืนค่า
- Cคืนสมาชิกล่างสุดของสแตก
- Dคืนสมาชิกบนสุดโดยไม่เอาออก
4.ปานกลาง
extract-min ใน min-heap ทวิภาคทำงานอย่างไร
- Aลบรากและเลื่อนสมาชิกทั้งหมดไปทางซ้ายหนึ่งตำแหน่ง
- Bลบสมาชิกสุดท้ายของอาร์เรย์
- Cย้ายสมาชิกสุดท้ายไปที่รากและเลื่อนลง (sift down)
- Dค้นหาใบทั้งหมดเพื่อหาค่าต่ำสุดใหม่
5.ปานกลาง
ในคิววงกลมที่เก็บในอาร์เรย์ความจุ n ตำแหน่งถัดจากดัชนี i คำนวณอย่างไร
- A(i + 1) mod n
- B(i − 1) mod n
- Ci + 1
- D2i + 1
6.ปานกลาง
การท่องแบบ in-order ของ binary search tree เยี่ยมคีย์ตามลำดับ
- Aตามระดับ
- Bตามลำดับการแทรก
- Cเรียงจากน้อยไปมาก
- Dเรียงจากมากไปน้อยเสมอ
7.ยาก
การแทรกคีย์ในต้นไม้ AVL ทำให้ต้นไม้ย่อยซ้ายของโหนดสูงเกินไป และคีย์ใหม่อยู่ในต้นไม้ย่อยซ้ายของลูกซ้าย (กรณีซ้าย–ซ้าย) ใช้วิธีแก้ใด
- Aเปลี่ยนสีโหนดและลูกของมัน
- Bหมุนซ้ายที่ลูก แล้วหมุนขวาที่โหนด
- Cหมุนซ้ายหนึ่งครั้งที่โหนดที่ไม่สมดุล
- Dหมุนขวาหนึ่งครั้งที่โหนดที่ไม่สมดุล
8.ยาก
segment tree มักใช้เพื่อ
- Aตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)
- Bเก็บเส้นเชื่อมของกราฟ
- Cเรียงสตริงตามตัวอักษรโดยเก็บแต่ละคำนำหน้าไว้ในโหนดต้นไม้แยกกัน
- Dสร้างสแตก
เฉลย
- 1. D · สแตก (stack)
- 2. A · การเข้าถึงสมาชิกที่ดัชนี i
- 3. D · คืนสมาชิกบนสุดโดยไม่เอาออก
- 4. C · ย้ายสมาชิกสุดท้ายไปที่รากและเลื่อนลง (sift down)
- 5. A · (i + 1) mod n
- 6. C · เรียงจากน้อยไปมาก
- 7. D · หมุนขวาหนึ่งครั้งที่โหนดที่ไม่สมดุล
- 8. A · ตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com