1.ง่าย
การท่องแบบ postorder ของต้นไม้ทวิภาคเยี่ยมโหนดตามลำดับใด
- Aโหนด แล้วต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา
- Bต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา แล้วโหนด
- Cต้นไม้ย่อยซ้าย แล้วโหนด แล้วต้นไม้ย่อยขวา
- Dต้นไม้ย่อยขวา แล้วโหนด แล้วต้นไม้ย่อยซ้าย
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
โครงสร้างข้อมูลใดใช้ท่องต้นไม้แบบ level-order
- Aสแตก
- Bตารางแฮช
- Cคิว
- Dคิวลำดับความสำคัญ
3.ง่าย
สมาชิกที่เล็กที่สุดของ min-heap ทวิภาคอยู่ที่ใด
- Aที่ราก
- Bในใบซ้ายสุด
- Cในตำแหน่งสุดท้ายของอาร์เรย์
- Dในใบใดก็ได้ ซึ่งต้องค้นหา
4.ปานกลาง
ในฮีปทวิภาคที่เก็บในอาร์เรย์เริ่มที่ดัชนี 0 แม่ของโหนดที่ดัชนี i อยู่ที่ใด
- Aที่ดัชนี i − 1
- Bที่ดัชนี ⌊i / 2⌋ + 1
- Cที่ดัชนี ⌊(i − 1) / 2⌋
- Dที่ดัชนี 2i + 1
5.ปานกลาง
ต้นไม้ AVL รักษาเงื่อนไขสมดุลใดที่ทุกโหนด
- Aทุกโหนดถูกระบายสีแดงหรือดำ
- Bความสูงของต้นไม้ย่อยซ้ายและขวาต่างกันไม่เกิน 1
- Cต้นไม้ย่อยทั้งสองของทุกโหนดมีจำนวนโหนดเท่ากันพอดี
- Dใบทั้งหมดอยู่ที่ความลึกเดียวกันพอดี
6.ปานกลาง
extract-min ใน min-heap ทวิภาคทำงานอย่างไร
- Aย้ายสมาชิกสุดท้ายไปที่รากและเลื่อนลง (sift down)
- Bลบสมาชิกสุดท้ายของอาร์เรย์
- Cลบรากและเลื่อนสมาชิกทั้งหมดไปทางซ้ายหนึ่งตำแหน่ง
- Dค้นหาใบทั้งหมดเพื่อหาค่าต่ำสุดใหม่
7.ยาก
ในอัลกอริทึมต้นไม้ทอดข้ามที่น้อยที่สุดของ Kruskal โครงสร้าง union-find ใช้เพื่อ
- Aเรียงเส้นเชื่อมตามน้ำหนัก
- Bเก็บระยะทางปัจจุบันของแต่ละจุดยอดจากต้นทางระหว่างการค้นหา
- Cเลือกจุดยอดเริ่มต้น
- Dตรวจว่าปลายทั้งสองของเส้นเชื่อมเชื่อมต่อกันอยู่แล้วหรือไม่
8.ยาก
ภายใต้การแฮชสม่ำเสมออย่างง่าย เวลาคาดหมายของการค้นหาในตารางแฮชแบบ chaining ที่มี n คีย์และ m ถังคือเท่าใด
- AO(log n)
- BO(n)
- CO(1 + α) เมื่อ α = n / m
- DO(m)
เฉลย
- 1. B · ต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา แล้วโหนด
- 2. C · คิว
- 3. A · ที่ราก
- 4. C · ที่ดัชนี ⌊(i − 1) / 2⌋
- 5. B · ความสูงของต้นไม้ย่อยซ้ายและขวาต่างกันไม่เกิน 1
- 6. A · ย้ายสมาชิกสุดท้ายไปที่รากและเลื่อนลง (sift down)
- 7. D · ตรวจว่าปลายทั้งสองของเส้นเชื่อมเชื่อมต่อกันอยู่แล้วหรือไม่
- 8. C · O(1 + α) เมื่อ α = n / m
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com