1.ง่าย
ตัวประกอบการโหลด (load factor) ของตารางแฮชคืออะไร
- Aจำนวนการชนกันจนถึงตอนนี้
- Bจำนวนถังหารด้วยความยาวเฉลี่ยของคีย์ที่เก็บ
- Cเวลาที่ใช้โหลดตารางจากดิสก์
- Dจำนวนสมาชิกที่เก็บหารด้วยจำนวนถัง
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
ในลิงก์ลิสต์เชิงเดี่ยว (singly linked list) แต่ละโหนดประกอบด้วย
- Aข้อมูลและการอ้างอิงไปยังโหนดถัดไป
- Bข้อมูลและการอ้างอิงไปยังโหนดอื่นทั้งหมด
- Cข้อมูลและดัชนี
- Dข้อมูลเท่านั้น
3.ง่าย
การดำเนินการ peek (หรือ top) บนสแตกทำอะไร
- Aเอาสมาชิกทั้งหมดออกจากสแตก
- Bคืนสมาชิกบนสุดโดยไม่เอาออก
- Cคืนสมาชิกล่างสุดของสแตก
- Dเอาสมาชิกบนสุดออกและคืนค่า
4.ปานกลาง
ตารางแฮชขนาด 7 ใช้ h(k) = k mod 7 และ linear probing หลังแทรก 10 แล้ว 17 ถูกเก็บที่ใด
- Aดัชนี 4
- Bดัชนี 3
- Cดัชนี 6
- Dดัชนี 0
5.ปานกลาง
ในคิววงกลมที่เก็บในอาร์เรย์ความจุ n ตำแหน่งถัดจากดัชนี i คำนวณอย่างไร
- Ai + 1
- B2i + 1
- C(i + 1) mod n
- D(i − 1) mod n
6.ปานกลาง
ในตารางแฮชที่ใช้ open addressing ตัวประกอบการโหลดสูงสุดที่เป็นไปได้คือเท่าใด
- A2
- B0.5
- C1
- Dไม่มีค่าสูงสุด
7.ยาก
การแทรกคีย์ในต้นไม้ AVL ทำให้ต้นไม้ย่อยซ้ายของโหนดสูงเกินไป และคีย์ใหม่อยู่ในต้นไม้ย่อยซ้ายของลูกซ้าย (กรณีซ้าย–ซ้าย) ใช้วิธีแก้ใด
- Aหมุนซ้ายที่ลูก แล้วหมุนขวาที่โหนด
- Bหมุนซ้ายหนึ่งครั้งที่โหนดที่ไม่สมดุล
- Cหมุนขวาหนึ่งครั้งที่โหนดที่ไม่สมดุล
- Dเปลี่ยนสีโหนดและลูกของมัน
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 · ดัชนี 4
- 5. C · (i + 1) mod n
- 6. C · 1
- 7. C · หมุนขวาหนึ่งครั้งที่โหนดที่ไม่สมดุล
- 8. C · O(α(n)) ซึ่งเป็นฟังก์ชันผกผันของอัคเคอร์มันน์ ที่แทบเป็นค่าคงที่ในทางปฏิบัติ
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com