1.ง่าย
อะไรคือนิยามของต้นไม้ทวิภาค (binary tree)
- Aต้นไม้มีสองระดับพอดี
- Bทุกโหนดเก็บเลขฐานสอง
- Cทุกโหนดมีลูกสองตัวพอดี
- Dทุกโหนดมีลูกไม่เกินสองตัว
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
deque (double-ended queue) คืออะไร
- Aคิวที่เรียงตามลำดับความสำคัญ
- Bโครงสร้างที่อนุญาตให้แทรกและเอาออกที่ทั้งสองปลาย
- Cคิวที่อนุญาตให้เอาออกจากด้านหลังเท่านั้น
- Dคิวสองคิวที่ใช้อาร์เรย์ร่วมกัน
3.ง่าย
ในตารางแฮช การชนกัน (collision) คืออะไร
- Aตารางหน่วยความจำหมด
- Bคีย์ไม่สามารถแฮชได้เลย
- Cคีย์ที่เท่ากันสองตัวถูกเก็บสองครั้ง
- Dคีย์สองตัวที่ต่างกันแปลงเป็นดัชนีเดียวกัน
4.ปานกลาง
โหนดใน binary search tree มีต้นไม้ย่อยขวา in-order successor ของมันอยู่ที่ใด
- Aแม่ของมันเสมอ
- Bโหนดขวาสุดของต้นไม้ย่อยซ้าย
- Cลูกขวาของมันเสมอ
- Dโหนดซ้ายสุดของต้นไม้ย่อยขวา
5.ปานกลาง
การท่องแบบ in-order ของ binary search tree เยี่ยมคีย์ตามลำดับ
- Aเรียงจากมากไปน้อยเสมอ
- Bตามลำดับการแทรก
- Cเรียงจากน้อยไปมาก
- Dตามระดับ
6.ปานกลาง
ความสูงในกรณีเลวร้ายที่สุดของ binary search tree ที่มี n โหนดคือเท่าใด ถ้าแทรกคีย์ตามลำดับที่เรียงแล้ว
- An (กลายเป็นลิงก์ลิสต์)
- Blog₂ n
- C1
- D√n
7.ยาก
ความซับซ้อนเชิงเวลาของ decrease-key ในฮีปทวิภาค (เมื่อทราบตำแหน่งของสมาชิก) คือ
- AO(n)
- BO(log n)
- CO(1)
- DO(n log n)
8.ยาก
โครงสร้าง union-find (เซตไม่เชื่อมกัน) ที่ใช้ union by rank และ path compression มีต้นทุนกระจายต่อการดำเนินการเป็น
- AO(n)
- BO(α(n)) ซึ่งเป็นฟังก์ชันผกผันของอัคเคอร์มันน์ ที่แทบเป็นค่าคงที่ในทางปฏิบัติ
- CO(n²)
- DO(log n) พอดี
เฉลย
- 1. D · ทุกโหนดมีลูกไม่เกินสองตัว
- 2. B · โครงสร้างที่อนุญาตให้แทรกและเอาออกที่ทั้งสองปลาย
- 3. D · คีย์สองตัวที่ต่างกันแปลงเป็นดัชนีเดียวกัน
- 4. D · โหนดซ้ายสุดของต้นไม้ย่อยขวา
- 5. C · เรียงจากน้อยไปมาก
- 6. A · n (กลายเป็นลิงก์ลิสต์)
- 7. B · O(log n)
- 8. B · O(α(n)) ซึ่งเป็นฟังก์ชันผกผันของอัคเคอร์มันน์ ที่แทบเป็นค่าคงที่ในทางปฏิบัติ
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com