1.ง่าย
ในการแทนกราฟด้วยรายการประชิด (adjacency list) เก็บอะไรสำหรับแต่ละจุดยอด
- Aเส้นทางสั้นที่สุดไปยังทุกจุดยอดอื่น
- Bจำนวนเส้นเชื่อมทั้งหมดในกราฟ
- Cแถวของค่าบูลีน V ค่า
- Dรายการของจุดยอดข้างเคียง
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
ความลึก (depth) ของโหนดในต้นไม้คือ
- Aจำนวนเส้นเชื่อมจากโหนดนั้นถึงใบที่ลึกที่สุด
- Bจำนวนโหนดในต้นไม้ย่อยของมัน
- Cจำนวนลูกของโหนดนั้น
- Dจำนวนเส้นเชื่อมจากรากถึงโหนดนั้น
3.ง่าย
โครงสร้างข้อมูลใดใช้ท่องต้นไม้แบบ level-order
- Aคิว
- Bสแตก
- Cตารางแฮช
- Dคิวลำดับความสำคัญ
4.ปานกลาง
วิธีแก้การชนกันแบบใดเก็บคีย์ที่ชนกันไว้ในลิสต์ที่ถังเดียวกัน
- Aการเชื่อมโซ่แยก (separate chaining)
- Bการตรวจสอบเชิงเส้น (linear probing)
- Cการตรวจสอบกำลังสอง (quadratic probing)
- Dการแฮชซ้อน (double hashing)
5.ปานกลาง
บัฟเฟอร์วงกลม (circular buffer หรือ ring buffer) มักใช้สร้าง
- Aต้นไม้ค้นหาแบบทวิภาค
- Bคิวขนาดคงที่
- Cการท่องกราฟ
- Dฟังก์ชันแฮช
6.ปานกลาง
ในฮีปทวิภาคที่เก็บในอาร์เรย์เริ่มที่ดัชนี 0 แม่ของโหนดที่ดัชนี i อยู่ที่ใด
- Aที่ดัชนี ⌊i / 2⌋ + 1
- Bที่ดัชนี 2i + 1
- Cที่ดัชนี ⌊(i − 1) / 2⌋
- Dที่ดัชนี i − 1
7.ยาก
Fenwick tree (binary indexed tree) บนอาร์เรย์ที่มีตัวเลข n ตัว รองรับการดำเนินการใดใน O(log n)
- Aการหามัธยฐานใน O(1)
- Bการเรียงอาร์เรย์และการค้นหาแบบทวิภาค
- Cการแทรกสมาชิกที่ตำแหน่งใดก็ได้
- Dคำถามผลรวมคำนำหน้าและการอัปเดตสมาชิกเดียว
8.ยาก
โครงสร้างใดช่วยคำนวณค่าสูงสุดของทุกหน้าต่างขนาด k ในอาร์เรย์ในเวลารวม O(n)
- Aลิงก์ลิสต์เชิงเดี่ยวของสมาชิกในหน้าต่าง
- Bmin-heap ที่สร้างใหม่ทุกหน้าต่าง
- Cdeque ที่เก็บดัชนีเรียงตามค่าจากมากไปน้อย
- Dอาร์เรย์เรียงลำดับที่อัปเดตด้วยการเลื่อน
เฉลย
- 1. D · รายการของจุดยอดข้างเคียง
- 2. D · จำนวนเส้นเชื่อมจากรากถึงโหนดนั้น
- 3. A · คิว
- 4. A · การเชื่อมโซ่แยก (separate chaining)
- 5. B · คิวขนาดคงที่
- 6. C · ที่ดัชนี ⌊(i − 1) / 2⌋
- 7. D · คำถามผลรวมคำนำหน้าและการอัปเดตสมาชิกเดียว
- 8. C · deque ที่เก็บดัชนีเรียงตามค่าจากมากไปน้อย
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com