1.ง่าย
โครงสร้างข้อมูลใดทำงานตามหลักการ "เข้าหลังออกก่อน" (last in, first out)
- Aลิงก์ลิสต์ (linked list)
- Bคิว (queue)
- Cสแตก (stack)
- Dตารางแฮช (hash table)
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
ในลิงก์ลิสต์เชิงเดี่ยว ตัวชี้ next ของโหนดสุดท้ายมีค่าเป็น
- Aที่อยู่ของโหนดแรก
- Bจำนวนโหนดในลิสต์
- CNull (ไม่มีโหนด)
- Dที่อยู่ของโหนดก่อนหน้า
3.ง่าย
ในต้นไม้ค้นหาแบบทวิภาค (binary search tree) ค่าในต้นไม้ย่อยซ้ายของโหนดมีค่า
- Aน้อยกว่าค่าของโหนด
- Bเท่ากับค่าของโหนด
- Cมากกว่าค่าของโหนด
- Dเรียงลำดับแบบสุ่ม
4.ปานกลาง
ใน min-heap ทวิภาคที่เก็บในอาร์เรย์ (ดัชนีเริ่มที่ 0) ลูกของโหนดที่ดัชนี i อยู่ที่
- Ai + 1 และ i + 2
- B2i และ 2i + 1
- Ci/2 และ i/2 + 1
- D2i + 1 และ 2i + 2
5.ปานกลาง
วิธีแก้การชนกันแบบใดเก็บคีย์ที่ชนกันไว้ในลิสต์ที่ถังเดียวกัน
- Aการแฮชซ้อน (double hashing)
- Bการเชื่อมโซ่แยก (separate chaining)
- Cการตรวจสอบกำลังสอง (quadratic probing)
- Dการตรวจสอบเชิงเส้น (linear probing)
6.ปานกลาง
ทราย (trie หรือ prefix tree) มีประสิทธิภาพเป็นพิเศษสำหรับ
- Aการเรียงตัวเลข
- Bการหาเส้นทางสั้นที่สุด
- Cการค้นหาด้วยคำนำหน้า เช่น autocomplete
- Dการเก็บเมทริกซ์
7.ยาก
ในอัลกอริทึมต้นไม้ทอดข้ามที่น้อยที่สุดของ Kruskal โครงสร้าง union-find ใช้เพื่อ
- Aตรวจว่าปลายทั้งสองของเส้นเชื่อมเชื่อมต่อกันอยู่แล้วหรือไม่
- Bเลือกจุดยอดเริ่มต้น
- Cเรียงเส้นเชื่อมตามน้ำหนัก
- Dเก็บระยะทางปัจจุบันของแต่ละจุดยอดจากต้นทางระหว่างการค้นหา
8.ยาก
โครงสร้างข้อมูลใดรองรับแคช LRU (least recently used) ที่ get และ put เป็น O(1)
- Ahash map ร่วมกับลิงก์ลิสต์สองทิศทาง
- Bสแตกเท่านั้น
- Cbinary search tree เท่านั้น
- Dอาร์เรย์เรียงลำดับเดียว
เฉลย
- 1. C · สแตก (stack)
- 2. C · Null (ไม่มีโหนด)
- 3. A · น้อยกว่าค่าของโหนด
- 4. D · 2i + 1 และ 2i + 2
- 5. B · การเชื่อมโซ่แยก (separate chaining)
- 6. C · การค้นหาด้วยคำนำหน้า เช่น autocomplete
- 7. A · ตรวจว่าปลายทั้งสองของเส้นเชื่อมเชื่อมต่อกันอยู่แล้วหรือไม่
- 8. A · hash map ร่วมกับลิงก์ลิสต์สองทิศทาง
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com