1.ง่าย
ตัวประกอบการโหลด (load factor) ของตารางแฮชคืออะไร
- Aเวลาที่ใช้โหลดตารางจากดิสก์
- Bจำนวนถังหารด้วยความยาวเฉลี่ยของคีย์ที่เก็บ
- Cจำนวนการชนกันจนถึงตอนนี้
- Dจำนวนสมาชิกที่เก็บหารด้วยจำนวนถัง
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
การดำเนินการของสแตกที่เพิ่มสมาชิกไว้ด้านบนเรียกว่าอะไร
- AEnqueue
- BPop
- CPush
- DPeek
3.ง่าย
ในกราฟ วงจร (cycle) คืออะไร
- Aเส้นทางที่เริ่มและสิ้นสุดที่จุดยอดเดียวกัน
- Bจุดยอดที่ไม่มีเส้นเชื่อม
- Cเส้นทางที่เยี่ยมทุกจุดยอด
- Dเส้นเชื่อมที่มีน้ำหนักเป็นศูนย์
4.ปานกลาง
เหตุใดฮีปทวิภาคจึงเก็บในอาร์เรย์ได้โดยไม่ต้องใช้ตัวชี้
- Aเป็นต้นไม้ทวิภาคสมบูรณ์ ตำแหน่งจึงเป็นไปตามสูตรดัชนีง่าย ๆ
- Bฮีปมีสมาชิกไม่เกิน 100 ตัวเสมอ
- Cอาร์เรย์เก็บคีย์ให้เรียงลำดับโดยอัตโนมัติ จึงไม่ต้องใช้ตัวชี้
- Dคีย์ทั้งหมดในฮีปเท่ากัน
5.ปานกลาง
จุดประสงค์ของโหนดยามเฝ้า (sentinel หรือ dummy) ในลิงก์ลิสต์คืออะไร
- Aเก็บจำนวนสมาชิก
- Bทำให้โค้ดง่ายขึ้นโดยตัดกรณีพิเศษที่หัวหรือท้าย
- Cเพื่อป้องกันไม่ให้ลิสต์ขยายเกินจำนวนโหนดสูงสุดที่กำหนดไว้
- Dทำให้ลิสต์เรียงลำดับ
6.ปานกลาง
หาคีย์ที่น้อยที่สุดใน binary search tree ได้อย่างไร
- Aดูเฉพาะราก
- Bเยี่ยมทุกใบและเปรียบเทียบกัน
- Cตามลูกขวาจากรากจนไม่มีลูกขวา
- Dตามลูกซ้ายจากรากจนไม่มีลูกซ้าย
7.ยาก
คุณสมบัติใดทำให้ B-tree ทุกต้นสมดุลอย่างสมบูรณ์
- Aทุกโหนดมีลูกสองตัวพอดี
- Bแต่ละโหนดเก็บหนึ่งคีย์
- Cใบทั้งหมดอยู่ที่ความลึกเดียวกัน
- Dคีย์ถูกเก็บเฉพาะที่ราก
8.ยาก
ตรวจว่าลิงก์ลิสต์เชิงเดี่ยวมีวงจรหรือไม่โดยใช้หน่วยความจำเพิ่ม O(1) ได้อย่างไร
- Aนับโหนดจนเกินกว่าฟิลด์ความยาวของลิสต์
- Bเก็บทุกโหนดที่เยี่ยมในเซตแฮช
- Cเลื่อนตัวชี้หนึ่งทีละหนึ่งก้าวและอีกตัวสองก้าว แล้วตรวจว่าพบกันหรือไม่
- Dเรียงลิสต์และหาตัวซ้ำ
เฉลย
- 1. D · จำนวนสมาชิกที่เก็บหารด้วยจำนวนถัง
- 2. C · Push
- 3. A · เส้นทางที่เริ่มและสิ้นสุดที่จุดยอดเดียวกัน
- 4. A · เป็นต้นไม้ทวิภาคสมบูรณ์ ตำแหน่งจึงเป็นไปตามสูตรดัชนีง่าย ๆ
- 5. B · ทำให้โค้ดง่ายขึ้นโดยตัดกรณีพิเศษที่หัวหรือท้าย
- 6. D · ตามลูกซ้ายจากรากจนไม่มีลูกซ้าย
- 7. C · ใบทั้งหมดอยู่ที่ความลึกเดียวกัน
- 8. C · เลื่อนตัวชี้หนึ่งทีละหนึ่งก้าวและอีกตัวสองก้าว แล้วตรวจว่าพบกันหรือไม่
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com