1.ง่าย
การท่องแบบ preorder ของต้นไม้ทวิภาคเยี่ยมโหนดตามลำดับใด
- Aทีละระดับจากด้านบน
- Bต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา แล้วโหนด
- Cโหนด แล้วต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา
- Dต้นไม้ย่อยซ้าย แล้วโหนด แล้วต้นไม้ย่อยขวา
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
ต้นไม้ที่มี n โหนดมีเส้นเชื่อมกี่เส้น
- An
- Bn − 1
- C2n
- Dn + 1
3.ง่าย
โครงสร้างข้อมูลใดเหมาะที่สุดสำหรับฟีเจอร์ "ย้อนกลับ" (undo) ในโปรแกรมแก้ไขข้อความ
- Aสแตก (stack)
- Bคิว (queue)
- Cเซตแฮช (hash set)
- Dกราฟ (graph)
4.ปานกลาง
วิธีแก้การชนกันแบบใดเก็บคีย์ที่ชนกันไว้ในลิสต์ที่ถังเดียวกัน
- Aการตรวจสอบกำลังสอง (quadratic probing)
- Bการตรวจสอบเชิงเส้น (linear probing)
- Cการแฮชซ้อน (double hashing)
- Dการเชื่อมโซ่แยก (separate chaining)
5.ปานกลาง
ต้นไม้ AVL และต้นไม้แดง–ดำ (red-black) รับประกัน
- Aไม่มีโหนดใดมีลูกสองตัว
- Bคีย์ถูกเก็บตามลำดับการแทรก
- Cการค้นหาในเวลาคงที่ทุกกรณี
- Dความสูง O(log n) ผ่านการปรับสมดุลใหม่
6.ปานกลาง
ในตารางแฮชที่ใช้ open addressing ตัวประกอบการโหลดสูงสุดที่เป็นไปได้คือเท่าใด
- A1
- B2
- Cไม่มีค่าสูงสุด
- D0.5
7.ยาก
ข้อใดเกี่ยวกับ heapsort ถูกต้อง
- Aเรียงในที่เดิมใน O(n log n) กรณีเลวร้ายที่สุด แต่ไม่เสถียร
- Bเสถียรและต้องใช้หน่วยความจำเพิ่ม O(n)
- Cทำงานใน O(n) กับอินพุตใด ๆ
- Dต้องใช้ binary search tree เป็นที่เก็บเพิ่มเติม จึงใช้หน่วยความจำเพิ่ม O(n)
8.ยาก
ความซับซ้อนเชิงเวลาของ decrease-key ในฮีปทวิภาค (เมื่อทราบตำแหน่งของสมาชิก) คือ
- AO(log n)
- BO(n log n)
- CO(n)
- DO(1)
เฉลย
- 1. C · โหนด แล้วต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา
- 2. B · n − 1
- 3. A · สแตก (stack)
- 4. D · การเชื่อมโซ่แยก (separate chaining)
- 5. D · ความสูง O(log n) ผ่านการปรับสมดุลใหม่
- 6. A · 1
- 7. A · เรียงในที่เดิมใน O(n log n) กรณีเลวร้ายที่สุด แต่ไม่เสถียร
- 8. A · O(log n)
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com