1.ง่าย
กราฟมีทิศทาง (directed graph) คืออะไร
- Aกราฟที่ทุกคู่ของจุดยอดที่ต่างกันเชื่อมกันด้วยเส้นเชื่อม
- Bกราฟที่ไม่มีวงจร
- Cกราฟที่เส้นเชื่อมทุกเส้นมีน้ำหนัก
- Dกราฟที่เส้นเชื่อมมีทิศทางจากจุดยอดหนึ่งไปอีกจุดหนึ่ง
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
ในกราฟ วงจร (cycle) คืออะไร
- Aเส้นเชื่อมที่มีน้ำหนักเป็นศูนย์
- Bเส้นทางที่เริ่มและสิ้นสุดที่จุดยอดเดียวกัน
- Cเส้นทางที่เยี่ยมทุกจุดยอด
- Dจุดยอดที่ไม่มีเส้นเชื่อม
3.ง่าย
รากของต้นไม้ (root) คืออะไร
- Aโหนดบนสุดที่ไม่มีโหนดแม่
- Bโหนดที่มีค่ามากที่สุด
- Cโหนดที่ไม่มีโหนดลูก
- Dโหนดใดก็ได้ตรงกลาง
4.ปานกลาง
ต้นไม้ทวิภาคมีราก 1 ลูกซ้าย 2 ลูกขวา 3 โหนด 2 มีลูก 4 (ซ้าย) และ 5 (ขวา) การท่องแบบ preorder คืออะไร
- A1 2 3 4 5
- B4 5 2 3 1
- C1 2 4 5 3
- D4 2 5 1 3
5.ปานกลาง
ต้นไม้ AVL และต้นไม้แดง–ดำ (red-black) รับประกัน
- Aคีย์ถูกเก็บตามลำดับการแทรก
- Bไม่มีโหนดใดมีลูกสองตัว
- Cการค้นหาในเวลาคงที่ทุกกรณี
- Dความสูง O(log n) ผ่านการปรับสมดุลใหม่
6.ปานกลาง
โปรแกรมที่ทำงานอยู่ใช้โครงสร้างข้อมูลใดติดตามการเรียกฟังก์ชันที่กำลังทำงานและตัวแปรท้องถิ่น
- Aคิวหน่วยความจำฮีป
- Bbinary search tree ของเฟรม
- Cตารางแฮชของฟังก์ชัน
- Dสแตกการเรียก (call stack)
7.ยาก
ภายใต้การแฮชสม่ำเสมออย่างง่าย เวลาคาดหมายของการค้นหาในตารางแฮชแบบ chaining ที่มี n คีย์และ m ถังคือเท่าใด
- AO(m)
- BO(log n)
- CO(n)
- DO(1 + α) เมื่อ α = n / m
8.ยาก
การแทรกคีย์ในต้นไม้ AVL ทำให้ต้นไม้ย่อยซ้ายของโหนดสูงเกินไป และคีย์ใหม่อยู่ในต้นไม้ย่อยซ้ายของลูกซ้าย (กรณีซ้าย–ซ้าย) ใช้วิธีแก้ใด
- Aเปลี่ยนสีโหนดและลูกของมัน
- Bหมุนซ้ายหนึ่งครั้งที่โหนดที่ไม่สมดุล
- Cหมุนขวาหนึ่งครั้งที่โหนดที่ไม่สมดุล
- Dหมุนซ้ายที่ลูก แล้วหมุนขวาที่โหนด
เฉลย
- 1. D · กราฟที่เส้นเชื่อมมีทิศทางจากจุดยอดหนึ่งไปอีกจุดหนึ่ง
- 2. B · เส้นทางที่เริ่มและสิ้นสุดที่จุดยอดเดียวกัน
- 3. A · โหนดบนสุดที่ไม่มีโหนดแม่
- 4. C · 1 2 4 5 3
- 5. D · ความสูง O(log n) ผ่านการปรับสมดุลใหม่
- 6. D · สแตกการเรียก (call stack)
- 7. D · O(1 + α) เมื่อ α = n / m
- 8. C · หมุนขวาหนึ่งครั้งที่โหนดที่ไม่สมดุล
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com