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

โครงสร้างข้อมูลใดทำงานตามหลักการ "เข้าหลังออกก่อน" (last in, first out)

1. Aคิว (queue)
2. Bตารางแฮช (hash table)
3. Cสแตก (stack)
4. Dลิงก์ลิสต์ (linked list)

สมาชิกของอาร์เรย์ถูกเก็บในหน่วยความจำอย่างไร

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

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

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

extract-min ใน min-heap ทวิภาคทำงานอย่างไร

1. Aลบรากและเลื่อนสมาชิกทั้งหมดไปทางซ้ายหนึ่งตำแหน่ง
2. Bย้ายสมาชิกสุดท้ายไปที่รากและเลื่อนลง (sift down)
3. Cค้นหาใบทั้งหมดเพื่อหาค่าต่ำสุดใหม่
4. Dลบสมาชิกสุดท้ายของอาร์เรย์

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

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

ในคิววงกลมที่เก็บในอาร์เรย์ความจุ n ตำแหน่งถัดจากดัชนี i คำนวณอย่างไร

1. A2i + 1
2. B(i + 1) mod n
3. Ci + 1
4. D(i − 1) mod n

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

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

ในบัฟเฟอร์วงกลม front == rear อาจหมายถึงว่างหรือเต็ม วิธีทั่วไปในการแยกสองกรณีคืออะไร

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