1.ง่าย
สมาชิกที่เล็กที่สุดของ min-heap ทวิภาคอยู่ที่ใด
- Aในใบซ้ายสุด
- Bที่ราก
- Cในใบใดก็ได้ ซึ่งต้องค้นหา
- Dในตำแหน่งสุดท้ายของอาร์เรย์
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
ในตารางแฮช การชนกัน (collision) คืออะไร
- Aคีย์ที่เท่ากันสองตัวถูกเก็บสองครั้ง
- Bคีย์ไม่สามารถแฮชได้เลย
- Cตารางหน่วยความจำหมด
- Dคีย์สองตัวที่ต่างกันแปลงเป็นดัชนีเดียวกัน
3.ง่าย
การท่องแบบ preorder ของต้นไม้ทวิภาคเยี่ยมโหนดตามลำดับใด
- Aโหนด แล้วต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา
- Bต้นไม้ย่อยซ้าย แล้วโหนด แล้วต้นไม้ย่อยขวา
- Cทีละระดับจากด้านบน
- Dต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา แล้วโหนด
4.ปานกลาง
ต้นไม้ AVL และต้นไม้แดง–ดำ (red-black) รับประกัน
- Aการค้นหาในเวลาคงที่ทุกกรณี
- Bคีย์ถูกเก็บตามลำดับการแทรก
- Cความสูง O(log n) ผ่านการปรับสมดุลใหม่
- Dไม่มีโหนดใดมีลูกสองตัว
5.ปานกลาง
รายการประชิดใช้หน่วยความจำเท่าใดสำหรับกราฟที่มี V จุดยอดและ E เส้นเชื่อม
- AO(V + E)
- BO(E²)
- CO(V × E)
- DO(V²)
6.ปานกลาง
ในตารางแฮชที่ใช้ open addressing ตัวประกอบการโหลดสูงสุดที่เป็นไปได้คือเท่าใด
- A2
- B0.5
- C1
- Dไม่มีค่าสูงสุด
7.ยาก
segment tree มักใช้เพื่อ
- Aสร้างสแตก
- Bเก็บเส้นเชื่อมของกราฟ
- Cตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)
- Dเรียงสตริงตามตัวอักษรโดยเก็บแต่ละคำนำหน้าไว้ในโหนดต้นไม้แยกกัน
8.ยาก
Bloom filter ตอบคำถาม "สมาชิกนี้อยู่ในเซตหรือไม่" ได้ด้วย
- Aอาจมีผลบวกเท็จ แต่ไม่มีผลลบเท็จ
- Bคำตอบที่แม่นยำเสมอ
- Cอาจมีผลลบเท็จ แต่ไม่มีผลบวกเท็จ
- Dคำตอบสำหรับตัวเลขเท่านั้น
เฉลย
- 1. B · ที่ราก
- 2. D · คีย์สองตัวที่ต่างกันแปลงเป็นดัชนีเดียวกัน
- 3. A · โหนด แล้วต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา
- 4. C · ความสูง O(log n) ผ่านการปรับสมดุลใหม่
- 5. A · O(V + E)
- 6. C · 1
- 7. C · ตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)
- 8. A · อาจมีผลบวกเท็จ แต่ไม่มีผลลบเท็จ
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com