1.ง่าย
กราฟมีน้ำหนัก (weighted graph) คืออะไร
- Aกราฟที่จุดยอดบางจุดหนักกว่าจุดอื่นเพราะมีเส้นเชื่อมมากกว่า
- Bกราฟที่มีเส้นเชื่อมมากกว่าจุดยอด
- Cกราฟที่แต่ละเส้นเชื่อมมีค่าตัวเลข เช่น ต้นทุนหรือระยะทาง
- Dกราฟที่เก็บบนดิสก์
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
ในต้นไม้ค้นหาแบบทวิภาค (binary search tree) ค่าในต้นไม้ย่อยซ้ายของโหนดมีค่า
- Aมากกว่าค่าของโหนด
- Bน้อยกว่าค่าของโหนด
- Cเท่ากับค่าของโหนด
- Dเรียงลำดับแบบสุ่ม
3.ง่าย
การดำเนินการของสแตกที่เพิ่มสมาชิกไว้ด้านบนเรียกว่าอะไร
- AEnqueue
- BPop
- CPeek
- DPush
4.ปานกลาง
บัฟเฟอร์วงกลม (circular buffer หรือ ring buffer) มักใช้สร้าง
- Aการท่องกราฟ
- Bคิวขนาดคงที่
- Cต้นไม้ค้นหาแบบทวิภาค
- Dฟังก์ชันแฮช
5.ปานกลาง
จะเกิดอะไรขึ้นเมื่อตารางแฮช rehash หลังตัวประกอบการโหลดเกินเกณฑ์
- Aย้ายเฉพาะคีย์ที่ชนกันไปยังลิสต์ล้นใหม่ที่ท้ายตาราง
- Bคีย์ที่มีอยู่ถูกเรียงในที่เดิม
- Cคีย์เก่าที่สุดถูกลบเพื่อให้มีที่ว่าง
- Dจัดสรรตารางใหม่ที่ใหญ่กว่าและแทรกทุกคีย์ใหม่
6.ปานกลาง
โหนดใน binary search tree มีต้นไม้ย่อยขวา in-order successor ของมันอยู่ที่ใด
- Aแม่ของมันเสมอ
- Bลูกขวาของมันเสมอ
- Cโหนดขวาสุดของต้นไม้ย่อยซ้าย
- Dโหนดซ้ายสุดของต้นไม้ย่อยขวา
7.ยาก
การค้นหาคีย์ใด ๆ ในฮีป min ทวิภาคที่มี n สมาชิกใช้เวลาเท่าใด
- AO(log n)
- BO(log log n)
- CO(1)
- DO(n)
8.ยาก
คุณสมบัติใดทำให้ B-tree ทุกต้นสมดุลอย่างสมบูรณ์
- Aคีย์ถูกเก็บเฉพาะที่ราก
- Bแต่ละโหนดเก็บหนึ่งคีย์
- Cทุกโหนดมีลูกสองตัวพอดี
- Dใบทั้งหมดอยู่ที่ความลึกเดียวกัน
เฉลย
- 1. C · กราฟที่แต่ละเส้นเชื่อมมีค่าตัวเลข เช่น ต้นทุนหรือระยะทาง
- 2. B · น้อยกว่าค่าของโหนด
- 3. D · Push
- 4. B · คิวขนาดคงที่
- 5. D · จัดสรรตารางใหม่ที่ใหญ่กว่าและแทรกทุกคีย์ใหม่
- 6. D · โหนดซ้ายสุดของต้นไม้ย่อยขวา
- 7. D · O(n)
- 8. D · ใบทั้งหมดอยู่ที่ความลึกเดียวกัน
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com