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

การดำเนินการของคิวที่เอาสมาชิกด้านหน้าออกเรียกว่าอะไร

1. AInsert
2. BDequeue
3. CEnqueue
4. DPush

กราฟมีน้ำหนัก (weighted graph) คืออะไร

1. Aกราฟที่เก็บบนดิสก์
2. Bกราฟที่จุดยอดบางจุดหนักกว่าจุดอื่นเพราะมีเส้นเชื่อมมากกว่า
3. Cกราฟที่แต่ละเส้นเชื่อมมีค่าตัวเลข เช่น ต้นทุนหรือระยะทาง
4. Dกราฟที่มีเส้นเชื่อมมากกว่าจุดยอด

อะไรคือนิยามของต้นไม้ทวิภาค (binary tree)

1. Aทุกโหนดมีลูกสองตัวพอดี
2. Bทุกโหนดมีลูกไม่เกินสองตัว
3. Cทุกโหนดเก็บเลขฐานสอง
4. Dต้นไม้มีสองระดับพอดี

จุดประสงค์ของโหนดยามเฝ้า (sentinel หรือ dummy) ในลิงก์ลิสต์คืออะไร

1. Aเพื่อป้องกันไม่ให้ลิสต์ขยายเกินจำนวนโหนดสูงสุดที่กำหนดไว้
2. Bทำให้ลิสต์เรียงลำดับ
3. Cเก็บจำนวนสมาชิก
4. Dทำให้โค้ดง่ายขึ้นโดยตัดกรณีพิเศษที่หัวหรือท้าย

วิธีแก้การชนกันแบบใดเก็บคีย์ที่ชนกันไว้ในลิสต์ที่ถังเดียวกัน

1. Aการแฮชซ้อน (double hashing)
2. Bการเชื่อมโซ่แยก (separate chaining)
3. Cการตรวจสอบกำลังสอง (quadratic probing)
4. Dการตรวจสอบเชิงเส้น (linear probing)

ตารางแฮชขนาด 7 ใช้ h(k) = k mod 7 และ linear probing หลังแทรก 10 แล้ว 17 ถูกเก็บที่ใด

1. Aดัชนี 6
2. Bดัชนี 3
3. Cดัชนี 4
4. Dดัชนี 0

ในตารางแฮชที่ใช้ open addressing เหตุใดการลบจึงมักทำด้วยเครื่องหมาย "tombstone"

1. Aการทำให้ช่องว่างอาจทำลายลำดับการตรวจสอบสำหรับคีย์อื่น
2. Btombstone เร่งการแฮช
3. Cคีย์ที่ลบต้องเก็บไว้ตลอดไปเพื่อความปลอดภัย จึงใช้ช่องนั้นซ้ำไม่ได้
4. Dทำให้ตารางเรียงลำดับ

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

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