1.ง่าย
การท่องแบบ preorder ของต้นไม้ทวิภาคเยี่ยมโหนดตามลำดับใด
- Aโหนด แล้วต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา
- Bต้นไม้ย่อยซ้าย แล้วโหนด แล้วต้นไม้ย่อยขวา
- Cต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา แล้วโหนด
- Dทีละระดับจากด้านบน
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
กราฟมีทิศทาง (directed graph) คืออะไร
- Aกราฟที่เส้นเชื่อมทุกเส้นมีน้ำหนัก
- Bกราฟที่เส้นเชื่อมมีทิศทางจากจุดยอดหนึ่งไปอีกจุดหนึ่ง
- Cกราฟที่ไม่มีวงจร
- Dกราฟที่ทุกคู่ของจุดยอดที่ต่างกันเชื่อมกันด้วยเส้นเชื่อม
3.ง่าย
รากของต้นไม้ (root) คืออะไร
- Aโหนดใดก็ได้ตรงกลาง
- Bโหนดที่ไม่มีโหนดลูก
- Cโหนดที่มีค่ามากที่สุด
- Dโหนดบนสุดที่ไม่มีโหนดแม่
4.ปานกลาง
โครงสร้างข้อมูลใดใช้ตรวจว่าวงเล็บใน "{[()]}" สมดุลหรือไม่
- Aตารางแฮช
- Bbinary search tree
- Cคิว
- Dสแตก
5.ปานกลาง
รายการประชิดใช้หน่วยความจำเท่าใดสำหรับกราฟที่มี V จุดยอดและ E เส้นเชื่อม
- AO(V²)
- BO(V × E)
- CO(E²)
- DO(V + E)
6.ปานกลาง
โครงสร้างข้อมูลใดที่การค้นหาในแนวลึก (DFS) แบบวนซ้ำใช้
- Aตารางแฮชเท่านั้น
- Bสแตก
- Cฮีป
- Dคิว
7.ยาก
โครงสร้าง union-find (เซตไม่เชื่อมกัน) ที่ใช้ union by rank และ path compression มีต้นทุนกระจายต่อการดำเนินการเป็น
- AO(n)
- BO(log n) พอดี
- CO(α(n)) ซึ่งเป็นฟังก์ชันผกผันของอัคเคอร์มันน์ ที่แทบเป็นค่าคงที่ในทางปฏิบัติ
- DO(n²)
8.ยาก
คุณต้องเก็บค่าที่น้อยที่สุด k ตัวจากสตรีมของตัวเลข n ตัวโดยใช้หน่วยความจำ O(k) แนวทางใดทำงานใน O(n log k)
- Amax-heap ขนาด k โดยแทนที่รากเมื่อมีค่าที่เล็กกว่ามา
- Bmin-heap ที่เก็บค่าทั้ง n ตัว แล้วดึงค่าที่น้อยที่สุด k ตัวออกมาตอนท้าย
- Cอาร์เรย์เรียงลำดับของค่าทั้ง n
- Dคิว FIFO ของ k ค่าล่าสุด
เฉลย
- 1. A · โหนด แล้วต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา
- 2. B · กราฟที่เส้นเชื่อมมีทิศทางจากจุดยอดหนึ่งไปอีกจุดหนึ่ง
- 3. D · โหนดบนสุดที่ไม่มีโหนดแม่
- 4. D · สแตก
- 5. D · O(V + E)
- 6. B · สแตก
- 7. C · O(α(n)) ซึ่งเป็นฟังก์ชันผกผันของอัคเคอร์มันน์ ที่แทบเป็นค่าคงที่ในทางปฏิบัติ
- 8. A · max-heap ขนาด k โดยแทนที่รากเมื่อมีค่าที่เล็กกว่ามา
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com