1.ง่าย
ในตารางแฮช การชนกัน (collision) คืออะไร
- Aตารางหน่วยความจำหมด
- Bคีย์ที่เท่ากันสองตัวถูกเก็บสองครั้ง
- Cคีย์ไม่สามารถแฮชได้เลย
- Dคีย์สองตัวที่ต่างกันแปลงเป็นดัชนีเดียวกัน
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
ความสูงของต้นไม้มักถูกนิยามว่า
- Aจำนวนเส้นเชื่อมบนเส้นทางที่ยาวที่สุดจากรากไปยังใบ
- Bจำนวนโหนดทั้งหมดในต้นไม้ นับทั้งรากและใบทุกใบ
- Cจำนวนลูกของราก
- Dจำนวนใบในต้นไม้
3.ง่าย
ตัวประกอบการโหลด (load factor) ของตารางแฮชคืออะไร
- Aจำนวนการชนกันจนถึงตอนนี้
- Bจำนวนสมาชิกที่เก็บหารด้วยจำนวนถัง
- Cเวลาที่ใช้โหลดตารางจากดิสก์
- Dจำนวนถังหารด้วยความยาวเฉลี่ยของคีย์ที่เก็บ
4.ปานกลาง
การท่องแบบ in-order ของ binary search tree เยี่ยมคีย์ตามลำดับ
- Aเรียงจากน้อยไปมาก
- Bตามระดับ
- Cตามลำดับการแทรก
- Dเรียงจากมากไปน้อยเสมอ
5.ปานกลาง
บัฟเฟอร์วงกลม (circular buffer หรือ ring buffer) มักใช้สร้าง
- Aการท่องกราฟ
- Bฟังก์ชันแฮช
- Cต้นไม้ค้นหาแบบทวิภาค
- Dคิวขนาดคงที่
6.ปานกลาง
ต้นไม้ทวิภาคมีราก 1 ลูกซ้าย 2 ลูกขวา 3 โหนด 2 มีลูก 4 (ซ้าย) และ 5 (ขวา) การท่องแบบ preorder คืออะไร
- A4 5 2 3 1
- B1 2 4 5 3
- C1 2 3 4 5
- D4 2 5 1 3
7.ยาก
ข้อได้เปรียบหลักของ skip list เหนือลิงก์ลิสต์ที่เรียงลำดับคืออะไร
- Aเก็บคีย์โดยไม่เรียงลำดับ
- Bการค้นหา O(log n) คาดหมาย โดยใช้ตัวชี้ไปข้างหน้าหลายระดับ
- Cไม่ใช้หน่วยความจำเพิ่ม
- Dรับประกันการค้นหา O(1) เพราะทุกโหนดเก็บตัวชี้ไปยังทุกโหนดอื่น
8.ยาก
โครงสร้าง union-find (เซตไม่เชื่อมกัน) ที่ใช้ union by rank และ path compression มีต้นทุนกระจายต่อการดำเนินการเป็น
- AO(α(n)) ซึ่งเป็นฟังก์ชันผกผันของอัคเคอร์มันน์ ที่แทบเป็นค่าคงที่ในทางปฏิบัติ
- BO(log n) พอดี
- CO(n²)
- DO(n)
เฉลย
- 1. D · คีย์สองตัวที่ต่างกันแปลงเป็นดัชนีเดียวกัน
- 2. A · จำนวนเส้นเชื่อมบนเส้นทางที่ยาวที่สุดจากรากไปยังใบ
- 3. B · จำนวนสมาชิกที่เก็บหารด้วยจำนวนถัง
- 4. A · เรียงจากน้อยไปมาก
- 5. D · คิวขนาดคงที่
- 6. B · 1 2 4 5 3
- 7. B · การค้นหา O(log n) คาดหมาย โดยใช้ตัวชี้ไปข้างหน้าหลายระดับ
- 8. A · O(α(n)) ซึ่งเป็นฟังก์ชันผกผันของอัคเคอร์มันน์ ที่แทบเป็นค่าคงที่ในทางปฏิบัติ
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com