1.ง่าย
กราฟมีน้ำหนัก (weighted graph) คืออะไร
- Aกราฟที่มีเส้นเชื่อมมากกว่าจุดยอด
- Bกราฟที่จุดยอดบางจุดหนักกว่าจุดอื่นเพราะมีเส้นเชื่อมมากกว่า
- Cกราฟที่เก็บบนดิสก์
- Dกราฟที่แต่ละเส้นเชื่อมมีค่าตัวเลข เช่น ต้นทุนหรือระยะทาง
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
โครงสร้างใดมักใช้สร้างคิวลำดับความสำคัญ (priority queue)
- Aลิงก์ลิสต์เชิงเดี่ยวที่ไม่เรียงลำดับ
- Bฮีป (heap)
- Cสแตก (stack)
- Dสตริง
3.ง่าย
ในกราฟ วงจร (cycle) คืออะไร
- Aเส้นเชื่อมที่มีน้ำหนักเป็นศูนย์
- Bจุดยอดที่ไม่มีเส้นเชื่อม
- Cเส้นทางที่เริ่มและสิ้นสุดที่จุดยอดเดียวกัน
- Dเส้นทางที่เยี่ยมทุกจุดยอด
4.ปานกลาง
ในตารางแฮชที่ใช้ open addressing ตัวประกอบการโหลดสูงสุดที่เป็นไปได้คือเท่าใด
- A2
- Bไม่มีค่าสูงสุด
- C0.5
- D1
5.ปานกลาง
โครงสร้างข้อมูลใดที่การค้นหาในแนวลึก (DFS) แบบวนซ้ำใช้
- Aสแตก
- Bตารางแฮชเท่านั้น
- Cฮีป
- Dคิว
6.ปานกลาง
ในฮีปทวิภาคที่เก็บในอาร์เรย์เริ่มที่ดัชนี 0 แม่ของโหนดที่ดัชนี i อยู่ที่ใด
- Aที่ดัชนี ⌊(i − 1) / 2⌋
- Bที่ดัชนี 2i + 1
- Cที่ดัชนี i − 1
- Dที่ดัชนี ⌊i / 2⌋ + 1
7.ยาก
โครงสร้าง union-find (เซตไม่เชื่อมกัน) ที่ใช้ union by rank และ path compression มีต้นทุนกระจายต่อการดำเนินการเป็น
- AO(n)
- BO(n²)
- CO(log n) พอดี
- DO(α(n)) ซึ่งเป็นฟังก์ชันผกผันของอัคเคอร์มันน์ ที่แทบเป็นค่าคงที่ในทางปฏิบัติ
8.ยาก
ข้อได้เปรียบหลักของ skip list เหนือลิงก์ลิสต์ที่เรียงลำดับคืออะไร
- Aเก็บคีย์โดยไม่เรียงลำดับ
- Bไม่ใช้หน่วยความจำเพิ่ม
- Cรับประกันการค้นหา O(1) เพราะทุกโหนดเก็บตัวชี้ไปยังทุกโหนดอื่น
- Dการค้นหา O(log n) คาดหมาย โดยใช้ตัวชี้ไปข้างหน้าหลายระดับ
เฉลย
- 1. D · กราฟที่แต่ละเส้นเชื่อมมีค่าตัวเลข เช่น ต้นทุนหรือระยะทาง
- 2. B · ฮีป (heap)
- 3. C · เส้นทางที่เริ่มและสิ้นสุดที่จุดยอดเดียวกัน
- 4. D · 1
- 5. A · สแตก
- 6. A · ที่ดัชนี ⌊(i − 1) / 2⌋
- 7. D · O(α(n)) ซึ่งเป็นฟังก์ชันผกผันของอัคเคอร์มันน์ ที่แทบเป็นค่าคงที่ในทางปฏิบัติ
- 8. D · การค้นหา O(log n) คาดหมาย โดยใช้ตัวชี้ไปข้างหน้าหลายระดับ
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com