1.ง่าย
โครงสร้างข้อมูลใดทำงานตามหลักการ "เข้าหลังออกก่อน" (last in, first out)
- Aสแตก (stack)
- Bลิงก์ลิสต์ (linked list)
- Cคิว (queue)
- Dตารางแฮช (hash table)
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
การท่องแบบ preorder ของต้นไม้ทวิภาคเยี่ยมโหนดตามลำดับใด
- Aโหนด แล้วต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา
- Bทีละระดับจากด้านบน
- Cต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา แล้วโหนด
- Dต้นไม้ย่อยซ้าย แล้วโหนด แล้วต้นไม้ย่อยขวา
3.ง่าย
ในลิงก์ลิสต์เชิงเดี่ยว ตัวชี้ next ของโหนดสุดท้ายมีค่าเป็น
- ANull (ไม่มีโหนด)
- Bจำนวนโหนดในลิสต์
- Cที่อยู่ของโหนดก่อนหน้า
- Dที่อยู่ของโหนดแรก
4.ปานกลาง
โหนดใน binary search tree มีต้นไม้ย่อยขวา in-order successor ของมันอยู่ที่ใด
- Aโหนดซ้ายสุดของต้นไม้ย่อยขวา
- Bโหนดขวาสุดของต้นไม้ย่อยซ้าย
- Cลูกขวาของมันเสมอ
- Dแม่ของมันเสมอ
5.ปานกลาง
แอปพลิเคชันต้องการค้นหาเร็ว และต้องแสดงรายการคีย์เรียงลำดับและตอบคำถามช่วง โครงสร้างใดเหมาะที่สุด
- Aลิงก์ลิสต์ที่ไม่เรียงลำดับ
- Bตารางแฮช
- Cbinary search tree แบบสมดุล
- Dสแตก
6.ปานกลาง
หาคีย์ที่น้อยที่สุดใน binary search tree ได้อย่างไร
- Aเยี่ยมทุกใบและเปรียบเทียบกัน
- Bดูเฉพาะราก
- Cตามลูกขวาจากรากจนไม่มีลูกขวา
- Dตามลูกซ้ายจากรากจนไม่มีลูกซ้าย
7.ยาก
การลบโหนดที่มีลูกสองตัวจาก binary search tree มักทำโดย
- Aสลับกับราก
- Bลบต้นไม้ย่อยทั้งหมด
- Cสร้างต้นไม้ย่อยที่อยู่ใต้โหนดนั้นขึ้นใหม่ทั้งหมดแล้วแทรกคีย์ทุกตัวที่เคยมีอยู่ลงไปใหม่
- Dแทนที่ด้วย in-order successor (หรือ predecessor) แล้วลบโหนดนั้น
8.ยาก
ต้นไม้แดง–ดำ (red-black tree) ต้องมีคุณสมบัติใด
- Aทุกโหนดต้องเป็นสีแดง
- Bรากต้องเป็นสีแดง
- Cโหนดสีแดงทุกโหนดต้องมีลูกสีแดง โหนดสีแดงจึงต่อเป็นสายไม่ขาดตอนไปจนถึงใบ
- Dทุกเส้นทางจากโหนดไปยังใบของลูกหลานมีจำนวนโหนดสีดำเท่ากัน
เฉลย
- 1. A · สแตก (stack)
- 2. A · โหนด แล้วต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา
- 3. A · Null (ไม่มีโหนด)
- 4. A · โหนดซ้ายสุดของต้นไม้ย่อยขวา
- 5. C · binary search tree แบบสมดุล
- 6. D · ตามลูกซ้ายจากรากจนไม่มีลูกซ้าย
- 7. D · แทนที่ด้วย in-order successor (หรือ predecessor) แล้วลบโหนดนั้น
- 8. D · ทุกเส้นทางจากโหนดไปยังใบของลูกหลานมีจำนวนโหนดสีดำเท่ากัน
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com