1.ง่าย
โครงสร้างข้อมูลใดทำงานตามหลักการ "เข้าหลังออกก่อน" (last in, first out)
- Aสแตก (stack)
- Bตารางแฮช (hash table)
- Cลิงก์ลิสต์ (linked list)
- Dคิว (queue)
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
ในกราฟไม่มีทิศทาง ดีกรี (degree) ของจุดยอดคืออะไร
- Aตำแหน่งของมันในรายการประชิด
- Bจำนวนเส้นเชื่อมที่ต่ออยู่กับมัน
- Cจำนวนจุดยอดในกราฟ
- Dความยาวของเส้นทางที่ยาวที่สุดจากมัน
3.ง่าย
สมาชิกของอาร์เรย์ถูกเก็บในหน่วยความจำอย่างไร
- Aในตำแหน่งสุ่มที่เลือกด้วยแฮช
- Bในบล็อกต่อเนื่องเดียว ต่อกันทีละตัว
- Cในต้นไม้ของหน้าหน่วยความจำ
- Dกระจัดกระจาย เชื่อมด้วยตัวชี้
4.ปานกลาง
จุดประสงค์ของโหนดยามเฝ้า (sentinel หรือ dummy) ในลิงก์ลิสต์คืออะไร
- Aทำให้โค้ดง่ายขึ้นโดยตัดกรณีพิเศษที่หัวหรือท้าย
- Bทำให้ลิสต์เรียงลำดับ
- Cเก็บจำนวนสมาชิก
- Dเพื่อป้องกันไม่ให้ลิสต์ขยายเกินจำนวนโหนดสูงสุดที่กำหนดไว้
5.ปานกลาง
หาคีย์ที่น้อยที่สุดใน binary search tree ได้อย่างไร
- Aตามลูกขวาจากรากจนไม่มีลูกขวา
- Bดูเฉพาะราก
- Cเยี่ยมทุกใบและเปรียบเทียบกัน
- Dตามลูกซ้ายจากรากจนไม่มีลูกซ้าย
6.ปานกลาง
ข้อใดเป็นจริงเกี่ยวกับเมทริกซ์ประชิดของกราฟไม่มีทิศทาง
- Aเส้นทแยงมุมหลักมีเลขหนึ่งเสมอ
- Bสมมาตรเทียบกับเส้นทแยงมุมหลัก
- Cเป็นเมทริกซ์สามเหลี่ยมบนเสมอ
- Dแต่ละแถวมี 1 เพียงตัวเดียวพอดี
7.ยาก
คุณต้องเก็บค่าที่น้อยที่สุด k ตัวจากสตรีมของตัวเลข n ตัวโดยใช้หน่วยความจำ O(k) แนวทางใดทำงานใน O(n log k)
- Amin-heap ที่เก็บค่าทั้ง n ตัว แล้วดึงค่าที่น้อยที่สุด k ตัวออกมาตอนท้าย
- Bคิว FIFO ของ k ค่าล่าสุด
- Cmax-heap ขนาด k โดยแทนที่รากเมื่อมีค่าที่เล็กกว่ามา
- Dอาร์เรย์เรียงลำดับของค่าทั้ง n
8.ยาก
ความซับซ้อนเชิงเวลาของ decrease-key ในฮีปทวิภาค (เมื่อทราบตำแหน่งของสมาชิก) คือ
- AO(log n)
- BO(n log n)
- CO(1)
- DO(n)
เฉลย
- 1. A · สแตก (stack)
- 2. B · จำนวนเส้นเชื่อมที่ต่ออยู่กับมัน
- 3. B · ในบล็อกต่อเนื่องเดียว ต่อกันทีละตัว
- 4. A · ทำให้โค้ดง่ายขึ้นโดยตัดกรณีพิเศษที่หัวหรือท้าย
- 5. D · ตามลูกซ้ายจากรากจนไม่มีลูกซ้าย
- 6. B · สมมาตรเทียบกับเส้นทแยงมุมหลัก
- 7. C · max-heap ขนาด k โดยแทนที่รากเมื่อมีค่าที่เล็กกว่ามา
- 8. A · O(log n)
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com