1.ง่าย
ความสูงของต้นไม้มักถูกนิยามว่า
- Aจำนวนใบในต้นไม้
- Bจำนวนโหนดทั้งหมดในต้นไม้ นับทั้งรากและใบทุกใบ
- Cจำนวนลูกของราก
- Dจำนวนเส้นเชื่อมบนเส้นทางที่ยาวที่สุดจากรากไปยังใบ
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
ในลิงก์ลิสต์เชิงเดี่ยว ตัวชี้ next ของโหนดสุดท้ายมีค่าเป็น
- Aที่อยู่ของโหนดแรก
- Bที่อยู่ของโหนดก่อนหน้า
- Cจำนวนโหนดในลิสต์
- DNull (ไม่มีโหนด)
3.ง่าย
โครงสร้างข้อมูลใดทำงานตามหลักการ "เข้าหลังออกก่อน" (last in, first out)
- Aลิงก์ลิสต์ (linked list)
- Bตารางแฮช (hash table)
- Cสแตก (stack)
- Dคิว (queue)
4.ปานกลาง
บัฟเฟอร์วงกลม (circular buffer หรือ ring buffer) มักใช้สร้าง
- Aฟังก์ชันแฮช
- Bการท่องกราฟ
- Cต้นไม้ค้นหาแบบทวิภาค
- Dคิวขนาดคงที่
5.ปานกลาง
คุณมีการอ้างอิงถึงโหนดกลางลิสต์ ในลิสต์ชนิดใดลบมันได้ใน O(1)
- Aอาร์เรย์เรียงลำดับ
- Bลิงก์ลิสต์เชิงเดี่ยว
- Cอาร์เรย์พลวัต
- Dลิงก์ลิสต์สองทิศทาง
6.ปานกลาง
เหตุใดฮีปทวิภาคจึงเก็บในอาร์เรย์ได้โดยไม่ต้องใช้ตัวชี้
- Aเป็นต้นไม้ทวิภาคสมบูรณ์ ตำแหน่งจึงเป็นไปตามสูตรดัชนีง่าย ๆ
- Bคีย์ทั้งหมดในฮีปเท่ากัน
- Cอาร์เรย์เก็บคีย์ให้เรียงลำดับโดยอัตโนมัติ จึงไม่ต้องใช้ตัวชี้
- Dฮีปมีสมาชิกไม่เกิน 100 ตัวเสมอ
7.ยาก
Bloom filter ตอบคำถาม "สมาชิกนี้อยู่ในเซตหรือไม่" ได้ด้วย
- Aอาจมีผลบวกเท็จ แต่ไม่มีผลลบเท็จ
- Bอาจมีผลลบเท็จ แต่ไม่มีผลบวกเท็จ
- Cคำตอบสำหรับตัวเลขเท่านั้น
- Dคำตอบที่แม่นยำเสมอ
8.ยาก
ในตารางแฮชที่ใช้ open addressing เหตุใดการลบจึงมักทำด้วยเครื่องหมาย "tombstone"
- Aการทำให้ช่องว่างอาจทำลายลำดับการตรวจสอบสำหรับคีย์อื่น
- Bคีย์ที่ลบต้องเก็บไว้ตลอดไปเพื่อความปลอดภัย จึงใช้ช่องนั้นซ้ำไม่ได้
- Ctombstone เร่งการแฮช
- Dทำให้ตารางเรียงลำดับ
เฉลย
- 1. D · จำนวนเส้นเชื่อมบนเส้นทางที่ยาวที่สุดจากรากไปยังใบ
- 2. D · Null (ไม่มีโหนด)
- 3. C · สแตก (stack)
- 4. D · คิวขนาดคงที่
- 5. D · ลิงก์ลิสต์สองทิศทาง
- 6. A · เป็นต้นไม้ทวิภาคสมบูรณ์ ตำแหน่งจึงเป็นไปตามสูตรดัชนีง่าย ๆ
- 7. A · อาจมีผลบวกเท็จ แต่ไม่มีผลลบเท็จ
- 8. A · การทำให้ช่องว่างอาจทำลายลำดับการตรวจสอบสำหรับคีย์อื่น
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com