1.ง่าย
ความลึก (depth) ของโหนดในต้นไม้คือ
- Aจำนวนลูกของโหนดนั้น
- Bจำนวนเส้นเชื่อมจากรากถึงโหนดนั้น
- Cจำนวนเส้นเชื่อมจากโหนดนั้นถึงใบที่ลึกที่สุด
- Dจำนวนโหนดในต้นไม้ย่อยของมัน
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
ในการแทนกราฟด้วยรายการประชิด (adjacency list) เก็บอะไรสำหรับแต่ละจุดยอด
- Aแถวของค่าบูลีน V ค่า
- Bเส้นทางสั้นที่สุดไปยังทุกจุดยอดอื่น
- Cจำนวนเส้นเชื่อมทั้งหมดในกราฟ
- Dรายการของจุดยอดข้างเคียง
3.ง่าย
กราฟประกอบด้วย
- Aรากและใบเท่านั้น
- Bคีย์และแฮชเท่านั้น
- Cจุดยอด (โหนด) ที่เชื่อมต่อกันด้วยเส้นเชื่อม
- Dแถวและคอลัมน์
4.ปานกลาง
การท่องแบบ in-order ของ binary search tree เยี่ยมคีย์ตามลำดับ
- Aตามระดับ
- Bเรียงจากมากไปน้อยเสมอ
- Cตามลำดับการแทรก
- Dเรียงจากน้อยไปมาก
5.ปานกลาง
extract-min ใน min-heap ทวิภาคทำงานอย่างไร
- Aลบสมาชิกสุดท้ายของอาร์เรย์
- Bย้ายสมาชิกสุดท้ายไปที่รากและเลื่อนลง (sift down)
- Cค้นหาใบทั้งหมดเพื่อหาค่าต่ำสุดใหม่
- Dลบรากและเลื่อนสมาชิกทั้งหมดไปทางซ้ายหนึ่งตำแหน่ง
6.ปานกลาง
ในฮีปทวิภาคที่เก็บในอาร์เรย์เริ่มที่ดัชนี 0 แม่ของโหนดที่ดัชนี i อยู่ที่ใด
- Aที่ดัชนี i − 1
- Bที่ดัชนี 2i + 1
- Cที่ดัชนี ⌊i / 2⌋ + 1
- Dที่ดัชนี ⌊(i − 1) / 2⌋
7.ยาก
คุณสมบัติใดทำให้ B-tree ทุกต้นสมดุลอย่างสมบูรณ์
- Aใบทั้งหมดอยู่ที่ความลึกเดียวกัน
- Bคีย์ถูกเก็บเฉพาะที่ราก
- Cทุกโหนดมีลูกสองตัวพอดี
- Dแต่ละโหนดเก็บหนึ่งคีย์
8.ยาก
โครงสร้าง union-find (เซตไม่เชื่อมกัน) ที่ใช้ union by rank และ path compression มีต้นทุนกระจายต่อการดำเนินการเป็น
- AO(n²)
- BO(log n) พอดี
- CO(n)
- DO(α(n)) ซึ่งเป็นฟังก์ชันผกผันของอัคเคอร์มันน์ ที่แทบเป็นค่าคงที่ในทางปฏิบัติ
เฉลย
- 1. B · จำนวนเส้นเชื่อมจากรากถึงโหนดนั้น
- 2. D · รายการของจุดยอดข้างเคียง
- 3. C · จุดยอด (โหนด) ที่เชื่อมต่อกันด้วยเส้นเชื่อม
- 4. D · เรียงจากน้อยไปมาก
- 5. B · ย้ายสมาชิกสุดท้ายไปที่รากและเลื่อนลง (sift down)
- 6. D · ที่ดัชนี ⌊(i − 1) / 2⌋
- 7. A · ใบทั้งหมดอยู่ที่ความลึกเดียวกัน
- 8. D · O(α(n)) ซึ่งเป็นฟังก์ชันผกผันของอัคเคอร์มันน์ ที่แทบเป็นค่าคงที่ในทางปฏิบัติ
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com