1.ง่าย
สมาชิกของอาร์เรย์ถูกเก็บในหน่วยความจำอย่างไร
- Aในต้นไม้ของหน้าหน่วยความจำ
- Bในตำแหน่งสุ่มที่เลือกด้วยแฮช
- Cในบล็อกต่อเนื่องเดียว ต่อกันทีละตัว
- Dกระจัดกระจาย เชื่อมด้วยตัวชี้
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
การดำเนินการ peek (หรือ top) บนสแตกทำอะไร
- Aเอาสมาชิกบนสุดออกและคืนค่า
- Bเอาสมาชิกทั้งหมดออกจากสแตก
- Cคืนสมาชิกบนสุดโดยไม่เอาออก
- Dคืนสมาชิกล่างสุดของสแตก
3.ง่าย
กราฟมีน้ำหนัก (weighted graph) คืออะไร
- Aกราฟที่มีเส้นเชื่อมมากกว่าจุดยอด
- Bกราฟที่แต่ละเส้นเชื่อมมีค่าตัวเลข เช่น ต้นทุนหรือระยะทาง
- Cกราฟที่จุดยอดบางจุดหนักกว่าจุดอื่นเพราะมีเส้นเชื่อมมากกว่า
- Dกราฟที่เก็บบนดิสก์
4.ปานกลาง
การค้นหาคำความยาว L ใน trie ที่มีตัวอักษรคงที่ใช้เวลาเท่าใด
- AO(log n) เมื่อ n คือจำนวนคำ
- BO(L) ไม่ขึ้นกับจำนวนคำที่เก็บ
- CO(n) เมื่อ n คือจำนวนคำ
- DO(L × n)
5.ปานกลาง
extract-min ใน min-heap ทวิภาคทำงานอย่างไร
- Aค้นหาใบทั้งหมดเพื่อหาค่าต่ำสุดใหม่
- Bย้ายสมาชิกสุดท้ายไปที่รากและเลื่อนลง (sift down)
- Cลบสมาชิกสุดท้ายของอาร์เรย์
- Dลบรากและเลื่อนสมาชิกทั้งหมดไปทางซ้ายหนึ่งตำแหน่ง
6.ปานกลาง
วิธีแก้การชนกันแบบใดเก็บคีย์ที่ชนกันไว้ในลิสต์ที่ถังเดียวกัน
- Aการตรวจสอบกำลังสอง (quadratic probing)
- Bการแฮชซ้อน (double hashing)
- Cการตรวจสอบเชิงเส้น (linear probing)
- Dการเชื่อมโซ่แยก (separate chaining)
7.ยาก
อาร์เรย์พลวัตเพิ่มเป็นสองเท่าเมื่อเต็ม เหตุใดหลายการสร้างจึงหดมันเมื่อเหลือเพียงหนึ่งในสี่เท่านั้น ไม่ใช่ครึ่งหนึ่ง
- Aเพื่อหลีกเลี่ยงการปรับขนาดซ้ำเมื่อ push และ pop สลับกันใกล้ขอบเขต
- Bเพื่อให้อาร์เรย์เรียงลำดับ
- Cเพราะตัวจัดสรรหน่วยความจำคืนหน่วยความจำได้เฉพาะเป็นหนึ่งในสี่ของบล็อกเท่านั้น
- Dเพราะการหดที่ครึ่งหนึ่งทำให้สมาชิกหาย
8.ยาก
ข้อได้เปรียบหลักของ skip list เหนือลิงก์ลิสต์ที่เรียงลำดับคืออะไร
- Aไม่ใช้หน่วยความจำเพิ่ม
- Bเก็บคีย์โดยไม่เรียงลำดับ
- Cรับประกันการค้นหา O(1) เพราะทุกโหนดเก็บตัวชี้ไปยังทุกโหนดอื่น
- Dการค้นหา O(log n) คาดหมาย โดยใช้ตัวชี้ไปข้างหน้าหลายระดับ
เฉลย
- 1. C · ในบล็อกต่อเนื่องเดียว ต่อกันทีละตัว
- 2. C · คืนสมาชิกบนสุดโดยไม่เอาออก
- 3. B · กราฟที่แต่ละเส้นเชื่อมมีค่าตัวเลข เช่น ต้นทุนหรือระยะทาง
- 4. B · O(L) ไม่ขึ้นกับจำนวนคำที่เก็บ
- 5. B · ย้ายสมาชิกสุดท้ายไปที่รากและเลื่อนลง (sift down)
- 6. D · การเชื่อมโซ่แยก (separate chaining)
- 7. A · เพื่อหลีกเลี่ยงการปรับขนาดซ้ำเมื่อ push และ pop สลับกันใกล้ขอบเขต
- 8. D · การค้นหา O(log n) คาดหมาย โดยใช้ตัวชี้ไปข้างหน้าหลายระดับ
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com