1.ง่าย
กราฟมีทิศทาง (directed graph) คืออะไร
- Aกราฟที่ไม่มีวงจร
- Bกราฟที่เส้นเชื่อมทุกเส้นมีน้ำหนัก
- Cกราฟที่เส้นเชื่อมมีทิศทางจากจุดยอดหนึ่งไปอีกจุดหนึ่ง
- Dกราฟที่ทุกคู่ของจุดยอดที่ต่างกันเชื่อมกันด้วยเส้นเชื่อม
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
ความลึก (depth) ของโหนดในต้นไม้คือ
- Aจำนวนเส้นเชื่อมจากรากถึงโหนดนั้น
- Bจำนวนโหนดในต้นไม้ย่อยของมัน
- Cจำนวนเส้นเชื่อมจากโหนดนั้นถึงใบที่ลึกที่สุด
- Dจำนวนลูกของโหนดนั้น
3.ง่าย
กราฟมีน้ำหนัก (weighted graph) คืออะไร
- Aกราฟที่เก็บบนดิสก์
- Bกราฟที่จุดยอดบางจุดหนักกว่าจุดอื่นเพราะมีเส้นเชื่อมมากกว่า
- Cกราฟที่แต่ละเส้นเชื่อมมีค่าตัวเลข เช่น ต้นทุนหรือระยะทาง
- Dกราฟที่มีเส้นเชื่อมมากกว่าจุดยอด
4.ปานกลาง
ทราย (trie หรือ prefix tree) มีประสิทธิภาพเป็นพิเศษสำหรับ
- Aการหาเส้นทางสั้นที่สุด
- Bการค้นหาด้วยคำนำหน้า เช่น autocomplete
- Cการเก็บเมทริกซ์
- Dการเรียงตัวเลข
5.ปานกลาง
ความซับซ้อนเชิงเวลาของการค้นหาคีย์ใน binary search tree ที่สมดุลคือเท่าใด
- AO(1)
- BO(log n)
- CO(n log n)
- DO(n)
6.ปานกลาง
ในตารางแฮชที่ใช้ open addressing ตัวประกอบการโหลดสูงสุดที่เป็นไปได้คือเท่าใด
- A0.5
- B2
- Cไม่มีค่าสูงสุด
- D1
7.ยาก
การแทรกคีย์ในต้นไม้ AVL ทำให้ต้นไม้ย่อยซ้ายของโหนดสูงเกินไป และคีย์ใหม่อยู่ในต้นไม้ย่อยซ้ายของลูกซ้าย (กรณีซ้าย–ซ้าย) ใช้วิธีแก้ใด
- Aหมุนขวาหนึ่งครั้งที่โหนดที่ไม่สมดุล
- Bหมุนซ้ายที่ลูก แล้วหมุนขวาที่โหนด
- Cเปลี่ยนสีโหนดและลูกของมัน
- Dหมุนซ้ายหนึ่งครั้งที่โหนดที่ไม่สมดุล
8.ยาก
segment tree มักใช้เพื่อ
- Aเรียงสตริงตามตัวอักษรโดยเก็บแต่ละคำนำหน้าไว้ในโหนดต้นไม้แยกกัน
- Bสร้างสแตก
- Cตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)
- Dเก็บเส้นเชื่อมของกราฟ
เฉลย
- 1. C · กราฟที่เส้นเชื่อมมีทิศทางจากจุดยอดหนึ่งไปอีกจุดหนึ่ง
- 2. A · จำนวนเส้นเชื่อมจากรากถึงโหนดนั้น
- 3. C · กราฟที่แต่ละเส้นเชื่อมมีค่าตัวเลข เช่น ต้นทุนหรือระยะทาง
- 4. B · การค้นหาด้วยคำนำหน้า เช่น autocomplete
- 5. B · O(log n)
- 6. D · 1
- 7. A · หมุนขวาหนึ่งครั้งที่โหนดที่ไม่สมดุล
- 8. C · ตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com