1.ง่าย
ในการแทนกราฟด้วยรายการประชิด (adjacency list) เก็บอะไรสำหรับแต่ละจุดยอด
- Aเส้นทางสั้นที่สุดไปยังทุกจุดยอดอื่น
- Bรายการของจุดยอดข้างเคียง
- Cจำนวนเส้นเชื่อมทั้งหมดในกราฟ
- Dแถวของค่าบูลีน V ค่า
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
กราฟมีน้ำหนัก (weighted graph) คืออะไร
- Aกราฟที่จุดยอดบางจุดหนักกว่าจุดอื่นเพราะมีเส้นเชื่อมมากกว่า
- Bกราฟที่แต่ละเส้นเชื่อมมีค่าตัวเลข เช่น ต้นทุนหรือระยะทาง
- Cกราฟที่เก็บบนดิสก์
- Dกราฟที่มีเส้นเชื่อมมากกว่าจุดยอด
3.ง่าย
แมป (map หรือ dictionary) เก็บอะไร
- Aคู่ของคีย์ที่เท่ากัน
- Bคู่คีย์–ค่าที่คีย์ไม่ซ้ำกัน
- Cค่าที่เรียงตามขนาด
- Dค่าตามลำดับการแทรกเท่านั้น
4.ปานกลาง
ในตารางแฮชที่ใช้ open addressing ตัวประกอบการโหลดสูงสุดที่เป็นไปได้คือเท่าใด
- Aไม่มีค่าสูงสุด
- B1
- C2
- D0.5
5.ปานกลาง
เมทริกซ์ประชิด (adjacency matrix) ของกราฟที่มี V จุดยอดใช้หน่วยความจำเท่าใด
- AO(V + E)
- BO(E)
- CO(log V)
- DO(V²)
6.ปานกลาง
การท่องแบบ in-order ของ binary search tree เยี่ยมคีย์ตามลำดับ
- Aตามลำดับการแทรก
- Bเรียงจากน้อยไปมาก
- Cเรียงจากมากไปน้อยเสมอ
- Dตามระดับ
7.ยาก
ในตารางแฮชที่ใช้ open addressing เหตุใดการลบจึงมักทำด้วยเครื่องหมาย "tombstone"
- Aทำให้ตารางเรียงลำดับ
- Bการทำให้ช่องว่างอาจทำลายลำดับการตรวจสอบสำหรับคีย์อื่น
- Cคีย์ที่ลบต้องเก็บไว้ตลอดไปเพื่อความปลอดภัย จึงใช้ช่องนั้นซ้ำไม่ได้
- Dtombstone เร่งการแฮช
8.ยาก
Bloom filter ตอบคำถาม "สมาชิกนี้อยู่ในเซตหรือไม่" ได้ด้วย
- Aคำตอบที่แม่นยำเสมอ
- Bคำตอบสำหรับตัวเลขเท่านั้น
- Cอาจมีผลบวกเท็จ แต่ไม่มีผลลบเท็จ
- Dอาจมีผลลบเท็จ แต่ไม่มีผลบวกเท็จ
เฉลย
- 1. B · รายการของจุดยอดข้างเคียง
- 2. B · กราฟที่แต่ละเส้นเชื่อมมีค่าตัวเลข เช่น ต้นทุนหรือระยะทาง
- 3. B · คู่คีย์–ค่าที่คีย์ไม่ซ้ำกัน
- 4. B · 1
- 5. D · O(V²)
- 6. B · เรียงจากน้อยไปมาก
- 7. B · การทำให้ช่องว่างอาจทำลายลำดับการตรวจสอบสำหรับคีย์อื่น
- 8. C · อาจมีผลบวกเท็จ แต่ไม่มีผลลบเท็จ
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com