1.ง่าย
กราฟมีน้ำหนัก (weighted graph) คืออะไร
- Aกราฟที่มีเส้นเชื่อมมากกว่าจุดยอด
- Bกราฟที่จุดยอดบางจุดหนักกว่าจุดอื่นเพราะมีเส้นเชื่อมมากกว่า
- Cกราฟที่เก็บบนดิสก์
- Dกราฟที่แต่ละเส้นเชื่อมมีค่าตัวเลข เช่น ต้นทุนหรือระยะทาง
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
ความลึก (depth) ของโหนดในต้นไม้คือ
- Aจำนวนเส้นเชื่อมจากรากถึงโหนดนั้น
- Bจำนวนเส้นเชื่อมจากโหนดนั้นถึงใบที่ลึกที่สุด
- Cจำนวนโหนดในต้นไม้ย่อยของมัน
- Dจำนวนลูกของโหนดนั้น
3.ง่าย
ต้นไม้ที่มี n โหนดมีเส้นเชื่อมกี่เส้น
- A2n
- Bn
- Cn − 1
- Dn + 1
4.ปานกลาง
โครงสร้างข้อมูลใดใช้ตรวจว่าวงเล็บใน "{[()]}" สมดุลหรือไม่
- Aคิว
- Bตารางแฮช
- Cสแตก
- Dbinary search tree
5.ปานกลาง
เครือข่ายถนนมี 100,000 ทางแยก แต่ละแห่งเชื่อมกับประมาณ 4 แห่ง การแทนแบบใดเหมาะที่สุด
- Aเมทริกซ์ประชิด
- Bรายการประชิด
- Cฮีปทวิภาคของเส้นเชื่อม
- Dอาร์เรย์เรียงลำดับเดียวของจุดยอด
6.ปานกลาง
ใน min-heap ทวิภาคที่เก็บในอาร์เรย์ (ดัชนีเริ่มที่ 0) ลูกของโหนดที่ดัชนี i อยู่ที่
- Ai/2 และ i/2 + 1
- B2i + 1 และ 2i + 2
- Ci + 1 และ i + 2
- D2i และ 2i + 1
7.ยาก
การค้นหาคีย์ใด ๆ ในฮีป min ทวิภาคที่มี n สมาชิกใช้เวลาเท่าใด
- AO(log n)
- BO(1)
- CO(log log n)
- DO(n)
8.ยาก
ภายใต้การแฮชสม่ำเสมออย่างง่าย เวลาคาดหมายของการค้นหาในตารางแฮชแบบ chaining ที่มี n คีย์และ m ถังคือเท่าใด
- AO(1 + α) เมื่อ α = n / m
- BO(log n)
- CO(n)
- DO(m)
เฉลย
- 1. D · กราฟที่แต่ละเส้นเชื่อมมีค่าตัวเลข เช่น ต้นทุนหรือระยะทาง
- 2. A · จำนวนเส้นเชื่อมจากรากถึงโหนดนั้น
- 3. C · n − 1
- 4. C · สแตก
- 5. B · รายการประชิด
- 6. B · 2i + 1 และ 2i + 2
- 7. D · O(n)
- 8. A · O(1 + α) เมื่อ α = n / m
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com