1.ง่าย
ในกราฟ วงจร (cycle) คืออะไร
- Aจุดยอดที่ไม่มีเส้นเชื่อม
- Bเส้นเชื่อมที่มีน้ำหนักเป็นศูนย์
- Cเส้นทางที่เยี่ยมทุกจุดยอด
- Dเส้นทางที่เริ่มและสิ้นสุดที่จุดยอดเดียวกัน
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
กราฟมีน้ำหนัก (weighted graph) คืออะไร
- Aกราฟที่แต่ละเส้นเชื่อมมีค่าตัวเลข เช่น ต้นทุนหรือระยะทาง
- Bกราฟที่จุดยอดบางจุดหนักกว่าจุดอื่นเพราะมีเส้นเชื่อมมากกว่า
- Cกราฟที่มีเส้นเชื่อมมากกว่าจุดยอด
- Dกราฟที่เก็บบนดิสก์
3.ง่าย
การท่องแบบ postorder ของต้นไม้ทวิภาคเยี่ยมโหนดตามลำดับใด
- Aต้นไม้ย่อยซ้าย แล้วโหนด แล้วต้นไม้ย่อยขวา
- Bต้นไม้ย่อยขวา แล้วโหนด แล้วต้นไม้ย่อยซ้าย
- Cโหนด แล้วต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา
- Dต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา แล้วโหนด
4.ปานกลาง
extract-min ใน min-heap ทวิภาคทำงานอย่างไร
- Aลบสมาชิกสุดท้ายของอาร์เรย์
- Bค้นหาใบทั้งหมดเพื่อหาค่าต่ำสุดใหม่
- Cย้ายสมาชิกสุดท้ายไปที่รากและเลื่อนลง (sift down)
- Dลบรากและเลื่อนสมาชิกทั้งหมดไปทางซ้ายหนึ่งตำแหน่ง
5.ปานกลาง
โครงสร้างข้อมูลใดที่การค้นหาในแนวลึก (DFS) แบบวนซ้ำใช้
- Aสแตก
- Bคิว
- Cตารางแฮชเท่านั้น
- Dฮีป
6.ปานกลาง
ในคิววงกลมที่เก็บในอาร์เรย์ความจุ n ตำแหน่งถัดจากดัชนี i คำนวณอย่างไร
- A(i + 1) mod n
- Bi + 1
- C2i + 1
- D(i − 1) mod n
7.ยาก
โครงสร้างข้อมูลใดรองรับแคช LRU (least recently used) ที่ get และ put เป็น O(1)
- Aอาร์เรย์เรียงลำดับเดียว
- Bbinary search tree เท่านั้น
- Cสแตกเท่านั้น
- Dhash map ร่วมกับลิงก์ลิสต์สองทิศทาง
8.ยาก
segment tree มักใช้เพื่อ
- Aสร้างสแตก
- Bตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)
- Cเรียงสตริงตามตัวอักษรโดยเก็บแต่ละคำนำหน้าไว้ในโหนดต้นไม้แยกกัน
- Dเก็บเส้นเชื่อมของกราฟ
เฉลย
- 1. D · เส้นทางที่เริ่มและสิ้นสุดที่จุดยอดเดียวกัน
- 2. A · กราฟที่แต่ละเส้นเชื่อมมีค่าตัวเลข เช่น ต้นทุนหรือระยะทาง
- 3. D · ต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา แล้วโหนด
- 4. C · ย้ายสมาชิกสุดท้ายไปที่รากและเลื่อนลง (sift down)
- 5. A · สแตก
- 6. A · (i + 1) mod n
- 7. D · hash map ร่วมกับลิงก์ลิสต์สองทิศทาง
- 8. B · ตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com