1.ง่าย
ความสูงของต้นไม้มักถูกนิยามว่า
- Aจำนวนโหนดทั้งหมดในต้นไม้ นับทั้งรากและใบทุกใบ
- Bจำนวนใบในต้นไม้
- Cจำนวนเส้นเชื่อมบนเส้นทางที่ยาวที่สุดจากรากไปยังใบ
- Dจำนวนลูกของราก
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
ความลึก (depth) ของโหนดในต้นไม้คือ
- Aจำนวนลูกของโหนดนั้น
- Bจำนวนเส้นเชื่อมจากรากถึงโหนดนั้น
- Cจำนวนโหนดในต้นไม้ย่อยของมัน
- Dจำนวนเส้นเชื่อมจากโหนดนั้นถึงใบที่ลึกที่สุด
3.ง่าย
ในต้นไม้ โหนดพี่น้อง (sibling) คืออะไร
- Aโหนดที่ระดับความลึกเดียวกันในต้นไม้ย่อยต่างกัน
- Bโหนดที่ไม่มีลูก
- Cโหนดและแม่ของมัน
- Dโหนดที่มีแม่เดียวกัน
4.ปานกลาง
ความซับซ้อนเชิงเวลาของการค้นหาคีย์ใน binary search tree ที่สมดุลคือเท่าใด
- AO(1)
- BO(log n)
- CO(n)
- DO(n log n)
5.ปานกลาง
โหนดใน binary search tree มีต้นไม้ย่อยขวา in-order successor ของมันอยู่ที่ใด
- Aแม่ของมันเสมอ
- Bโหนดซ้ายสุดของต้นไม้ย่อยขวา
- Cโหนดขวาสุดของต้นไม้ย่อยซ้าย
- Dลูกขวาของมันเสมอ
6.ปานกลาง
ใน min-heap ทวิภาคที่เก็บในอาร์เรย์ (ดัชนีเริ่มที่ 0) ลูกของโหนดที่ดัชนี i อยู่ที่
- Ai/2 และ i/2 + 1
- Bi + 1 และ i + 2
- C2i + 1 และ 2i + 2
- D2i และ 2i + 1
7.ยาก
splay tree ทำอะไรหลังการเข้าถึงแต่ละครั้ง
- Aย้ายโหนดที่เข้าถึงไปเป็นใบ
- Bสร้างต้นไม้ใหม่ทั้งหมดให้สมดุล
- Cเปลี่ยนสีโหนดตามเส้นทางการค้นหา
- Dหมุนโหนดที่เข้าถึงขึ้นไปที่ราก
8.ยาก
segment tree มักใช้เพื่อ
- Aเก็บเส้นเชื่อมของกราฟ
- Bตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)
- Cเรียงสตริงตามตัวอักษรโดยเก็บแต่ละคำนำหน้าไว้ในโหนดต้นไม้แยกกัน
- Dสร้างสแตก
เฉลย
- 1. C · จำนวนเส้นเชื่อมบนเส้นทางที่ยาวที่สุดจากรากไปยังใบ
- 2. B · จำนวนเส้นเชื่อมจากรากถึงโหนดนั้น
- 3. D · โหนดที่มีแม่เดียวกัน
- 4. B · O(log n)
- 5. B · โหนดซ้ายสุดของต้นไม้ย่อยขวา
- 6. C · 2i + 1 และ 2i + 2
- 7. D · หมุนโหนดที่เข้าถึงขึ้นไปที่ราก
- 8. B · ตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com