1.ง่าย
ตารางแฮชเก็บข้อมูลเป็น
- Aรายการที่เรียงลำดับเท่านั้น
- Bคู่คีย์–ค่าที่หาตำแหน่งด้วยฟังก์ชันแฮช
- Cสตริงความยาวคงที่
- Dต้นไม้ที่คีย์เรียงลำดับ
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
รากของต้นไม้ (root) คืออะไร
- Aโหนดใดก็ได้ตรงกลาง
- Bโหนดบนสุดที่ไม่มีโหนดแม่
- Cโหนดที่ไม่มีโหนดลูก
- Dโหนดที่มีค่ามากที่สุด
3.ง่าย
กราฟมีทิศทาง (directed graph) คืออะไร
- Aกราฟที่ไม่มีวงจร
- Bกราฟที่เส้นเชื่อมมีทิศทางจากจุดยอดหนึ่งไปอีกจุดหนึ่ง
- Cกราฟที่ทุกคู่ของจุดยอดที่ต่างกันเชื่อมกันด้วยเส้นเชื่อม
- Dกราฟที่เส้นเชื่อมทุกเส้นมีน้ำหนัก
4.ปานกลาง
บัฟเฟอร์วงกลม (circular buffer หรือ ring buffer) มักใช้สร้าง
- Aคิวขนาดคงที่
- Bฟังก์ชันแฮช
- Cต้นไม้ค้นหาแบบทวิภาค
- Dการท่องกราฟ
5.ปานกลาง
ในตารางแฮชที่ใช้ open addressing ตัวประกอบการโหลดสูงสุดที่เป็นไปได้คือเท่าใด
- A1
- B0.5
- Cไม่มีค่าสูงสุด
- D2
6.ปานกลาง
ตารางแฮชขนาด 7 ใช้ h(k) = k mod 7 และ linear probing หลังแทรก 10 แล้ว 17 ถูกเก็บที่ใด
- Aดัชนี 4
- Bดัชนี 3
- Cดัชนี 0
- Dดัชนี 6
7.ยาก
การแทรกคีย์ในต้นไม้ AVL ทำให้ต้นไม้ย่อยซ้ายของโหนดสูงเกินไป และคีย์ใหม่อยู่ในต้นไม้ย่อยซ้ายของลูกซ้าย (กรณีซ้าย–ซ้าย) ใช้วิธีแก้ใด
- Aหมุนขวาหนึ่งครั้งที่โหนดที่ไม่สมดุล
- Bหมุนซ้ายหนึ่งครั้งที่โหนดที่ไม่สมดุล
- Cหมุนซ้ายที่ลูก แล้วหมุนขวาที่โหนด
- Dเปลี่ยนสีโหนดและลูกของมัน
8.ยาก
หากไม่มี union by rank หรือ path compression ต้นทุนในกรณีเลวร้ายที่สุดของ find หนึ่งครั้งในโครงสร้าง union-find ที่มี n สมาชิกคือเท่าใด
- AO(n)
- BO(log n)
- CO(1)
- DO(α(n))
เฉลย
- 1. B · คู่คีย์–ค่าที่หาตำแหน่งด้วยฟังก์ชันแฮช
- 2. B · โหนดบนสุดที่ไม่มีโหนดแม่
- 3. B · กราฟที่เส้นเชื่อมมีทิศทางจากจุดยอดหนึ่งไปอีกจุดหนึ่ง
- 4. A · คิวขนาดคงที่
- 5. A · 1
- 6. A · ดัชนี 4
- 7. A · หมุนขวาหนึ่งครั้งที่โหนดที่ไม่สมดุล
- 8. A · O(n)
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com