1.ง่าย
กราฟมีทิศทาง (directed graph) คืออะไร
- Aกราฟที่เส้นเชื่อมทุกเส้นมีน้ำหนัก
- Bกราฟที่เส้นเชื่อมมีทิศทางจากจุดยอดหนึ่งไปอีกจุดหนึ่ง
- Cกราฟที่ทุกคู่ของจุดยอดที่ต่างกันเชื่อมกันด้วยเส้นเชื่อม
- Dกราฟที่ไม่มีวงจร
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
การดำเนินการ peek (หรือ top) บนสแตกทำอะไร
- Aคืนสมาชิกบนสุดโดยไม่เอาออก
- Bเอาสมาชิกทั้งหมดออกจากสแตก
- Cคืนสมาชิกล่างสุดของสแตก
- Dเอาสมาชิกบนสุดออกและคืนค่า
3.ง่าย
ฟังก์ชันแฮชทำอะไรในตารางแฮช
- Aเข้ารหัสค่าในตาราง
- Bเรียงคีย์ในตาราง
- Cนับว่ามีกี่คีย์ที่เก็บอยู่
- Dแปลงคีย์เป็นดัชนีในตาราง
4.ปานกลาง
การตรวจว่ามีเส้นเชื่อม (u, v) หรือไม่ด้วยเมทริกซ์ประชิดใช้เวลาเท่าใด
- AO(log V)
- BO(E)
- CO(1)
- DO(V)
5.ปานกลาง
ต้นไม้ทวิภาคมีราก 1 ลูกซ้าย 2 ลูกขวา 3 โหนด 2 มีลูก 4 (ซ้าย) และ 5 (ขวา) การท่องแบบ postorder คืออะไร
- A4 5 2 3 1
- B5 4 3 2 1
- C1 2 4 5 3
- D4 2 5 1 3
6.ปานกลาง
โครงสร้างข้อมูลใดใช้ตรวจว่าวงเล็บใน "{[()]}" สมดุลหรือไม่
- Aตารางแฮช
- Bbinary search tree
- Cสแตก
- Dคิว
7.ยาก
โครงสร้างใดช่วยคำนวณค่าสูงสุดของทุกหน้าต่างขนาด k ในอาร์เรย์ในเวลารวม O(n)
- Amin-heap ที่สร้างใหม่ทุกหน้าต่าง
- Bอาร์เรย์เรียงลำดับที่อัปเดตด้วยการเลื่อน
- Cลิงก์ลิสต์เชิงเดี่ยวของสมาชิกในหน้าต่าง
- Ddeque ที่เก็บดัชนีเรียงตามค่าจากมากไปน้อย
8.ยาก
Bloom filter ตอบคำถาม "สมาชิกนี้อยู่ในเซตหรือไม่" ได้ด้วย
- Aคำตอบสำหรับตัวเลขเท่านั้น
- Bอาจมีผลบวกเท็จ แต่ไม่มีผลลบเท็จ
- Cคำตอบที่แม่นยำเสมอ
- Dอาจมีผลลบเท็จ แต่ไม่มีผลบวกเท็จ
เฉลย
- 1. B · กราฟที่เส้นเชื่อมมีทิศทางจากจุดยอดหนึ่งไปอีกจุดหนึ่ง
- 2. A · คืนสมาชิกบนสุดโดยไม่เอาออก
- 3. D · แปลงคีย์เป็นดัชนีในตาราง
- 4. C · O(1)
- 5. A · 4 5 2 3 1
- 6. C · สแตก
- 7. D · deque ที่เก็บดัชนีเรียงตามค่าจากมากไปน้อย
- 8. B · อาจมีผลบวกเท็จ แต่ไม่มีผลลบเท็จ
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com