1.ง่าย
โครงสร้างใดมักใช้สร้างคิวลำดับความสำคัญ (priority queue)
- Aลิงก์ลิสต์เชิงเดี่ยวที่ไม่เรียงลำดับ
- Bสตริง
- Cสแตก (stack)
- Dฮีป (heap)
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
ตัวประกอบการโหลด (load factor) ของตารางแฮชคืออะไร
- Aจำนวนสมาชิกที่เก็บหารด้วยจำนวนถัง
- Bจำนวนถังหารด้วยความยาวเฉลี่ยของคีย์ที่เก็บ
- Cจำนวนการชนกันจนถึงตอนนี้
- Dเวลาที่ใช้โหลดตารางจากดิสก์
3.ง่าย
การดำเนินการของสแตกที่เพิ่มสมาชิกไว้ด้านบนเรียกว่าอะไร
- APeek
- BPush
- CEnqueue
- DPop
4.ปานกลาง
ต้นไม้ทวิภาคมีราก 1 ลูกซ้าย 2 ลูกขวา 3 โหนด 2 มีลูก 4 (ซ้าย) และ 5 (ขวา) การท่องแบบ postorder คืออะไร
- A4 5 2 3 1
- B5 4 3 2 1
- C1 2 4 5 3
- D4 2 5 1 3
5.ปานกลาง
ต้นไม้ AVL รักษาเงื่อนไขสมดุลใดที่ทุกโหนด
- Aต้นไม้ย่อยทั้งสองของทุกโหนดมีจำนวนโหนดเท่ากันพอดี
- Bใบทั้งหมดอยู่ที่ความลึกเดียวกันพอดี
- Cความสูงของต้นไม้ย่อยซ้ายและขวาต่างกันไม่เกิน 1
- Dทุกโหนดถูกระบายสีแดงหรือดำ
6.ปานกลาง
รายการประชิดใช้หน่วยความจำเท่าใดสำหรับกราฟที่มี V จุดยอดและ E เส้นเชื่อม
- AO(E²)
- BO(V × E)
- CO(V + E)
- DO(V²)
7.ยาก
segment tree มักใช้เพื่อ
- Aเก็บเส้นเชื่อมของกราฟ
- Bสร้างสแตก
- Cเรียงสตริงตามตัวอักษรโดยเก็บแต่ละคำนำหน้าไว้ในโหนดต้นไม้แยกกัน
- Dตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)
8.ยาก
ในอัลกอริทึมต้นไม้ทอดข้ามที่น้อยที่สุดของ Kruskal โครงสร้าง union-find ใช้เพื่อ
- Aเก็บระยะทางปัจจุบันของแต่ละจุดยอดจากต้นทางระหว่างการค้นหา
- Bเรียงเส้นเชื่อมตามน้ำหนัก
- Cตรวจว่าปลายทั้งสองของเส้นเชื่อมเชื่อมต่อกันอยู่แล้วหรือไม่
- Dเลือกจุดยอดเริ่มต้น
เฉลย
- 1. D · ฮีป (heap)
- 2. A · จำนวนสมาชิกที่เก็บหารด้วยจำนวนถัง
- 3. B · Push
- 4. A · 4 5 2 3 1
- 5. C · ความสูงของต้นไม้ย่อยซ้ายและขวาต่างกันไม่เกิน 1
- 6. C · O(V + E)
- 7. D · ตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)
- 8. C · ตรวจว่าปลายทั้งสองของเส้นเชื่อมเชื่อมต่อกันอยู่แล้วหรือไม่
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com