1.ง่าย
การท่องแบบ postorder ของต้นไม้ทวิภาคเยี่ยมโหนดตามลำดับใด
- Aโหนด แล้วต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา
- Bต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา แล้วโหนด
- Cต้นไม้ย่อยขวา แล้วโหนด แล้วต้นไม้ย่อยซ้าย
- Dต้นไม้ย่อยซ้าย แล้วโหนด แล้วต้นไม้ย่อยขวา
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
รากของต้นไม้ (root) คืออะไร
- Aโหนดบนสุดที่ไม่มีโหนดแม่
- Bโหนดที่มีค่ามากที่สุด
- Cโหนดที่ไม่มีโหนดลูก
- Dโหนดใดก็ได้ตรงกลาง
3.ง่าย
deque (double-ended queue) คืออะไร
- Aคิวสองคิวที่ใช้อาร์เรย์ร่วมกัน
- Bคิวที่อนุญาตให้เอาออกจากด้านหลังเท่านั้น
- Cคิวที่เรียงตามลำดับความสำคัญ
- Dโครงสร้างที่อนุญาตให้แทรกและเอาออกที่ทั้งสองปลาย
4.ปานกลาง
ในตารางแฮชที่ใช้ open addressing ตัวประกอบการโหลดสูงสุดที่เป็นไปได้คือเท่าใด
- Aไม่มีค่าสูงสุด
- B0.5
- C2
- D1
5.ปานกลาง
ความซับซ้อนเชิงเวลาของการค้นหาคีย์ใน binary search tree ที่สมดุลคือเท่าใด
- AO(n log n)
- BO(log n)
- CO(n)
- DO(1)
6.ปานกลาง
เครือข่ายถนนมี 100,000 ทางแยก แต่ละแห่งเชื่อมกับประมาณ 4 แห่ง การแทนแบบใดเหมาะที่สุด
- Aเมทริกซ์ประชิด
- Bรายการประชิด
- Cอาร์เรย์เรียงลำดับเดียวของจุดยอด
- Dฮีปทวิภาคของเส้นเชื่อม
7.ยาก
เวลาทำงานของการค้นหาในแนวกว้างบนกราฟที่มี V จุดยอดที่เก็บเป็นเมทริกซ์ประชิดคือเท่าใด
- AO(V + E)
- BO(V)
- CO(V²)
- DO(E log V)
8.ยาก
การลบโหนดที่มีลูกสองตัวจาก binary search tree มักทำโดย
- Aลบต้นไม้ย่อยทั้งหมด
- Bสร้างต้นไม้ย่อยที่อยู่ใต้โหนดนั้นขึ้นใหม่ทั้งหมดแล้วแทรกคีย์ทุกตัวที่เคยมีอยู่ลงไปใหม่
- Cสลับกับราก
- Dแทนที่ด้วย in-order successor (หรือ predecessor) แล้วลบโหนดนั้น
เฉลย
- 1. B · ต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา แล้วโหนด
- 2. A · โหนดบนสุดที่ไม่มีโหนดแม่
- 3. D · โครงสร้างที่อนุญาตให้แทรกและเอาออกที่ทั้งสองปลาย
- 4. D · 1
- 5. B · O(log n)
- 6. B · รายการประชิด
- 7. C · O(V²)
- 8. D · แทนที่ด้วย in-order successor (หรือ predecessor) แล้วลบโหนดนั้น
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com