ใบงาน โครงสร้างข้อมูล พร้อมเฉลย

ในตารางแฮช การชนกัน (collision) คืออะไร

1. Aตารางหน่วยความจำหมด
2. Bคีย์สองตัวที่ต่างกันแปลงเป็นดัชนีเดียวกัน
3. Cคีย์ที่เท่ากันสองตัวถูกเก็บสองครั้ง
4. Dคีย์ไม่สามารถแฮชได้เลย

กราฟประกอบด้วย

1. Aรากและใบเท่านั้น
2. Bจุดยอด (โหนด) ที่เชื่อมต่อกันด้วยเส้นเชื่อม
3. Cแถวและคอลัมน์
4. Dคีย์และแฮชเท่านั้น

ในกราฟ วงจร (cycle) คืออะไร

1. Aเส้นเชื่อมที่มีน้ำหนักเป็นศูนย์
2. Bเส้นทางที่เยี่ยมทุกจุดยอด
3. Cจุดยอดที่ไม่มีเส้นเชื่อม
4. Dเส้นทางที่เริ่มและสิ้นสุดที่จุดยอดเดียวกัน

ต้นไม้ทวิภาคสมบูรณ์เต็ม (perfect binary tree) ที่มีความสูง h มีกี่โหนด เมื่อความสูงนับเป็นเส้นเชื่อม

1. A2^h
2. Bh²
3. C2h + 1
4. D2^h+1 − 1

คิวถูกสร้างด้วยสแตกสองตัว: push ลงสแตก "in" และ pop จากสแตก "out" โดยเติมจาก "in" เมื่อว่าง ต้นทุนกระจายต่อการดำเนินการคือเท่าใด

1. AO(n²)
2. BO(n)
3. CO(1)
4. DO(log n)

เหตุใดการท่องอาร์เรย์จึงเร็วกว่าการท่องลิงก์ลิสต์ที่ยาวเท่ากันมากในทางปฏิบัติ

1. Aอาร์เรย์ใช้คำสั่งน้อยกว่าในการเปรียบเทียบค่า
2. Bการท่องอาร์เรย์เป็น O(1) โดยรวม ส่วนการท่องลิงก์ลิสต์เป็น O(n)
3. Cสมาชิกของอาร์เรย์ต่อเนื่องกัน จึงใช้แคชของ CPU ได้ดี
4. Dลิงก์ลิสต์เก็บสมาชิกบนดิสก์เสมอ

คุณต้องเก็บค่าที่น้อยที่สุด k ตัวจากสตรีมของตัวเลข n ตัวโดยใช้หน่วยความจำ O(k) แนวทางใดทำงานใน O(n log k)

1. Amin-heap ที่เก็บค่าทั้ง n ตัว แล้วดึงค่าที่น้อยที่สุด k ตัวออกมาตอนท้าย
2. Bคิว FIFO ของ k ค่าล่าสุด
3. Cอาร์เรย์เรียงลำดับของค่าทั้ง n
4. Dmax-heap ขนาด k โดยแทนที่รากเมื่อมีค่าที่เล็กกว่ามา

Fenwick tree (binary indexed tree) บนอาร์เรย์ที่มีตัวเลข n ตัว รองรับการดำเนินการใดใน O(log n)

1. Aการหามัธยฐานใน O(1)
2. Bคำถามผลรวมคำนำหน้าและการอัปเดตสมาชิกเดียว
3. Cการเรียงอาร์เรย์และการค้นหาแบบทวิภาค
4. Dการแทรกสมาชิกที่ตำแหน่งใดก็ได้