1.ง่าย
โครงสร้างข้อมูลใดใช้ท่องต้นไม้แบบ level-order
- Aคิว
- Bตารางแฮช
- Cสแตก
- Dคิวลำดับความสำคัญ
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
สมาชิกที่เล็กที่สุดของ min-heap ทวิภาคอยู่ที่ใด
- Aในใบใดก็ได้ ซึ่งต้องค้นหา
- Bในใบซ้ายสุด
- Cที่ราก
- Dในตำแหน่งสุดท้ายของอาร์เรย์
3.ง่าย
ในต้นไม้ โหนดพี่น้อง (sibling) คืออะไร
- Aโหนดที่ระดับความลึกเดียวกันในต้นไม้ย่อยต่างกัน
- Bโหนดและแม่ของมัน
- Cโหนดที่ไม่มีลูก
- Dโหนดที่มีแม่เดียวกัน
4.ปานกลาง
extract-min ใน min-heap ทวิภาคทำงานอย่างไร
- Aลบรากและเลื่อนสมาชิกทั้งหมดไปทางซ้ายหนึ่งตำแหน่ง
- Bค้นหาใบทั้งหมดเพื่อหาค่าต่ำสุดใหม่
- Cย้ายสมาชิกสุดท้ายไปที่รากและเลื่อนลง (sift down)
- Dลบสมาชิกสุดท้ายของอาร์เรย์
5.ปานกลาง
ในตารางแฮชที่ใช้ open addressing ตัวประกอบการโหลดสูงสุดที่เป็นไปได้คือเท่าใด
- A1
- B2
- C0.5
- Dไม่มีค่าสูงสุด
6.ปานกลาง
อัลกอริทึมของ Dijkstra ใช้ชนิดข้อมูลนามธรรมใดเลือกจุดยอดถัดไปที่จะประมวลผล
- Aเซตที่ไม่มีลำดับ
- Bคิว FIFO
- Cสแตก
- Dคิวลำดับความสำคัญแบบค่าต่ำสุด (min-priority queue)
7.ยาก
คีย์ 5, 3, 8, 1 ถูกแทรกตามลำดับนี้ลงใน min-heap ทวิภาคแบบอาร์เรย์ที่ว่าง อาร์เรย์สุดท้ายคืออะไร
- A[1, 5, 8, 3]
- B[1, 3, 5, 8]
- C[3, 1, 8, 5]
- D[1, 3, 8, 5]
8.ยาก
คุณต้องเก็บค่าที่น้อยที่สุด k ตัวจากสตรีมของตัวเลข n ตัวโดยใช้หน่วยความจำ O(k) แนวทางใดทำงานใน O(n log k)
- Amin-heap ที่เก็บค่าทั้ง n ตัว แล้วดึงค่าที่น้อยที่สุด k ตัวออกมาตอนท้าย
- Bmax-heap ขนาด k โดยแทนที่รากเมื่อมีค่าที่เล็กกว่ามา
- Cอาร์เรย์เรียงลำดับของค่าทั้ง n
- Dคิว FIFO ของ k ค่าล่าสุด
เฉลย
- 1. A · คิว
- 2. C · ที่ราก
- 3. D · โหนดที่มีแม่เดียวกัน
- 4. C · ย้ายสมาชิกสุดท้ายไปที่รากและเลื่อนลง (sift down)
- 5. A · 1
- 6. D · คิวลำดับความสำคัญแบบค่าต่ำสุด (min-priority queue)
- 7. D · [1, 3, 8, 5]
- 8. B · max-heap ขนาด k โดยแทนที่รากเมื่อมีค่าที่เล็กกว่ามา
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com