1.ง่าย
การดำเนินการของสแตกที่เพิ่มสมาชิกไว้ด้านบนเรียกว่าอะไร
- APop
- BPeek
- CPush
- DEnqueue
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
แมป (map หรือ dictionary) เก็บอะไร
- Aค่าที่เรียงตามขนาด
- Bค่าตามลำดับการแทรกเท่านั้น
- Cคู่คีย์–ค่าที่คีย์ไม่ซ้ำกัน
- Dคู่ของคีย์ที่เท่ากัน
3.ง่าย
กราฟมีทิศทาง (directed graph) คืออะไร
- Aกราฟที่ทุกคู่ของจุดยอดที่ต่างกันเชื่อมกันด้วยเส้นเชื่อม
- Bกราฟที่ไม่มีวงจร
- Cกราฟที่เส้นเชื่อมมีทิศทางจากจุดยอดหนึ่งไปอีกจุดหนึ่ง
- Dกราฟที่เส้นเชื่อมทุกเส้นมีน้ำหนัก
4.ปานกลาง
เหตุใดการท่องอาร์เรย์จึงเร็วกว่าการท่องลิงก์ลิสต์ที่ยาวเท่ากันมากในทางปฏิบัติ
- Aอาร์เรย์ใช้คำสั่งน้อยกว่าในการเปรียบเทียบค่า
- Bการท่องอาร์เรย์เป็น O(1) โดยรวม ส่วนการท่องลิงก์ลิสต์เป็น O(n)
- Cลิงก์ลิสต์เก็บสมาชิกบนดิสก์เสมอ
- Dสมาชิกของอาร์เรย์ต่อเนื่องกัน จึงใช้แคชของ CPU ได้ดี
5.ปานกลาง
โปรแกรมที่ทำงานอยู่ใช้โครงสร้างข้อมูลใดติดตามการเรียกฟังก์ชันที่กำลังทำงานและตัวแปรท้องถิ่น
- Aคิวหน่วยความจำฮีป
- Bสแตกการเรียก (call stack)
- Cตารางแฮชของฟังก์ชัน
- Dbinary search tree ของเฟรม
6.ปานกลาง
ตารางแฮชขนาด 7 ใช้ h(k) = k mod 7 และ linear probing หลังแทรก 10 แล้ว 17 ถูกเก็บที่ใด
- Aดัชนี 3
- Bดัชนี 6
- Cดัชนี 0
- Dดัชนี 4
7.ยาก
ความซับซ้อนเชิงเวลาของ decrease-key ในฮีปทวิภาค (เมื่อทราบตำแหน่งของสมาชิก) คือ
- AO(n log n)
- BO(1)
- CO(log n)
- DO(n)
8.ยาก
หากไม่มี union by rank หรือ path compression ต้นทุนในกรณีเลวร้ายที่สุดของ find หนึ่งครั้งในโครงสร้าง union-find ที่มี n สมาชิกคือเท่าใด
- AO(log n)
- BO(n)
- CO(α(n))
- DO(1)
เฉลย
- 1. C · Push
- 2. C · คู่คีย์–ค่าที่คีย์ไม่ซ้ำกัน
- 3. C · กราฟที่เส้นเชื่อมมีทิศทางจากจุดยอดหนึ่งไปอีกจุดหนึ่ง
- 4. D · สมาชิกของอาร์เรย์ต่อเนื่องกัน จึงใช้แคชของ CPU ได้ดี
- 5. B · สแตกการเรียก (call stack)
- 6. D · ดัชนี 4
- 7. C · O(log n)
- 8. B · O(n)
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com