1.ง่าย
ความสูงของต้นไม้มักถูกนิยามว่า
- Aจำนวนใบในต้นไม้
- Bจำนวนเส้นเชื่อมบนเส้นทางที่ยาวที่สุดจากรากไปยังใบ
- Cจำนวนโหนดทั้งหมดในต้นไม้ นับทั้งรากและใบทุกใบ
- Dจำนวนลูกของราก
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
อะไรคือนิยามของต้นไม้ทวิภาค (binary tree)
- Aทุกโหนดเก็บเลขฐานสอง
- Bทุกโหนดมีลูกไม่เกินสองตัว
- Cทุกโหนดมีลูกสองตัวพอดี
- Dต้นไม้มีสองระดับพอดี
3.ง่าย
โครงสร้างข้อมูลใดเหมาะที่สุดสำหรับฟีเจอร์ "ย้อนกลับ" (undo) ในโปรแกรมแก้ไขข้อความ
- Aสแตก (stack)
- Bกราฟ (graph)
- Cเซตแฮช (hash set)
- Dคิว (queue)
4.ปานกลาง
ทราย (trie หรือ prefix tree) มีประสิทธิภาพเป็นพิเศษสำหรับ
- Aการเก็บเมทริกซ์
- Bการค้นหาด้วยคำนำหน้า เช่น autocomplete
- Cการหาเส้นทางสั้นที่สุด
- Dการเรียงตัวเลข
5.ปานกลาง
ในคิววงกลมที่เก็บในอาร์เรย์ความจุ n ตำแหน่งถัดจากดัชนี i คำนวณอย่างไร
- Ai + 1
- B2i + 1
- C(i − 1) mod n
- D(i + 1) mod n
6.ปานกลาง
คุณมีการอ้างอิงถึงโหนดกลางลิสต์ ในลิสต์ชนิดใดลบมันได้ใน O(1)
- Aลิงก์ลิสต์สองทิศทาง
- Bลิงก์ลิสต์เชิงเดี่ยว
- Cอาร์เรย์พลวัต
- Dอาร์เรย์เรียงลำดับ
7.ยาก
หากไม่มี union by rank หรือ path compression ต้นทุนในกรณีเลวร้ายที่สุดของ find หนึ่งครั้งในโครงสร้าง union-find ที่มี n สมาชิกคือเท่าใด
- AO(1)
- BO(n)
- CO(α(n))
- DO(log n)
8.ยาก
โครงสร้าง union-find (เซตไม่เชื่อมกัน) ที่ใช้ union by rank และ path compression มีต้นทุนกระจายต่อการดำเนินการเป็น
- AO(n²)
- BO(n)
- CO(α(n)) ซึ่งเป็นฟังก์ชันผกผันของอัคเคอร์มันน์ ที่แทบเป็นค่าคงที่ในทางปฏิบัติ
- DO(log n) พอดี
เฉลย
- 1. B · จำนวนเส้นเชื่อมบนเส้นทางที่ยาวที่สุดจากรากไปยังใบ
- 2. B · ทุกโหนดมีลูกไม่เกินสองตัว
- 3. A · สแตก (stack)
- 4. B · การค้นหาด้วยคำนำหน้า เช่น autocomplete
- 5. D · (i + 1) mod n
- 6. A · ลิงก์ลิสต์สองทิศทาง
- 7. B · O(n)
- 8. C · O(α(n)) ซึ่งเป็นฟังก์ชันผกผันของอัคเคอร์มันน์ ที่แทบเป็นค่าคงที่ในทางปฏิบัติ
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com