1.ง่าย
รากของต้นไม้ (root) คืออะไร
- Aโหนดที่ไม่มีโหนดลูก
- Bโหนดที่มีค่ามากที่สุด
- Cโหนดบนสุดที่ไม่มีโหนดแม่
- Dโหนดใดก็ได้ตรงกลาง
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
ในตารางแฮช การชนกัน (collision) คืออะไร
- Aคีย์ที่เท่ากันสองตัวถูกเก็บสองครั้ง
- Bตารางหน่วยความจำหมด
- Cคีย์สองตัวที่ต่างกันแปลงเป็นดัชนีเดียวกัน
- Dคีย์ไม่สามารถแฮชได้เลย
3.ง่าย
อะไรคือนิยามของต้นไม้ทวิภาค (binary tree)
- Aทุกโหนดมีลูกสองตัวพอดี
- Bทุกโหนดเก็บเลขฐานสอง
- Cทุกโหนดมีลูกไม่เกินสองตัว
- Dต้นไม้มีสองระดับพอดี
4.ปานกลาง
การค้นหาคำความยาว L ใน trie ที่มีตัวอักษรคงที่ใช้เวลาเท่าใด
- AO(L) ไม่ขึ้นกับจำนวนคำที่เก็บ
- BO(L × n)
- CO(n) เมื่อ n คือจำนวนคำ
- DO(log n) เมื่อ n คือจำนวนคำ
5.ปานกลาง
ความสูงในกรณีเลวร้ายที่สุดของ binary search tree ที่มี n โหนดคือเท่าใด ถ้าแทรกคีย์ตามลำดับที่เรียงแล้ว
- An (กลายเป็นลิงก์ลิสต์)
- B√n
- Clog₂ n
- D1
6.ปานกลาง
โครงสร้างข้อมูลใดที่การค้นหาในแนวลึก (DFS) แบบวนซ้ำใช้
- Aตารางแฮชเท่านั้น
- Bคิว
- Cสแตก
- Dฮีป
7.ยาก
คีย์ 5, 3, 8, 1 ถูกแทรกตามลำดับนี้ลงใน min-heap ทวิภาคแบบอาร์เรย์ที่ว่าง อาร์เรย์สุดท้ายคืออะไร
- A[1, 3, 5, 8]
- B[3, 1, 8, 5]
- C[1, 3, 8, 5]
- D[1, 5, 8, 3]
8.ยาก
ต้นไม้แดง–ดำ (red-black tree) ต้องมีคุณสมบัติใด
- Aรากต้องเป็นสีแดง
- Bทุกโหนดต้องเป็นสีแดง
- Cทุกเส้นทางจากโหนดไปยังใบของลูกหลานมีจำนวนโหนดสีดำเท่ากัน
- Dโหนดสีแดงทุกโหนดต้องมีลูกสีแดง โหนดสีแดงจึงต่อเป็นสายไม่ขาดตอนไปจนถึงใบ
เฉลย
- 1. C · โหนดบนสุดที่ไม่มีโหนดแม่
- 2. C · คีย์สองตัวที่ต่างกันแปลงเป็นดัชนีเดียวกัน
- 3. C · ทุกโหนดมีลูกไม่เกินสองตัว
- 4. A · O(L) ไม่ขึ้นกับจำนวนคำที่เก็บ
- 5. A · n (กลายเป็นลิงก์ลิสต์)
- 6. C · สแตก
- 7. C · [1, 3, 8, 5]
- 8. C · ทุกเส้นทางจากโหนดไปยังใบของลูกหลานมีจำนวนโหนดสีดำเท่ากัน
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com