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

การดำเนินการของสแตกที่เพิ่มสมาชิกไว้ด้านบนเรียกว่าอะไร

1. APop
2. BPeek
3. CPush
4. DEnqueue

deque (double-ended queue) คืออะไร

1. Aคิวที่อนุญาตให้เอาออกจากด้านหลังเท่านั้น
2. Bคิวที่เรียงตามลำดับความสำคัญ
3. Cคิวสองคิวที่ใช้อาร์เรย์ร่วมกัน
4. Dโครงสร้างที่อนุญาตให้แทรกและเอาออกที่ทั้งสองปลาย

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

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

โปรแกรมที่ทำงานอยู่ใช้โครงสร้างข้อมูลใดติดตามการเรียกฟังก์ชันที่กำลังทำงานและตัวแปรท้องถิ่น

1. Aสแตกการเรียก (call stack)
2. Bคิวหน่วยความจำฮีป
3. Cตารางแฮชของฟังก์ชัน
4. Dbinary search tree ของเฟรม

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

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

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

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

โครงสร้างใดช่วยคำนวณค่าสูงสุดของทุกหน้าต่างขนาด k ในอาร์เรย์ในเวลารวม O(n)

1. Amin-heap ที่สร้างใหม่ทุกหน้าต่าง
2. Bdeque ที่เก็บดัชนีเรียงตามค่าจากมากไปน้อย
3. Cลิงก์ลิสต์เชิงเดี่ยวของสมาชิกในหน้าต่าง
4. Dอาร์เรย์เรียงลำดับที่อัปเดตด้วยการเลื่อน

วัตถุถูกเก็บเป็นคีย์ใน hash map จากนั้นฟิลด์ที่ฟังก์ชันแฮชใช้ถูกเปลี่ยน ผลลัพธ์ที่น่าจะเกิดคืออะไร

1. Amap โยนข้อผิดพลาดทันทีที่ฟิลด์เปลี่ยน
2. Bการค้นหาวัตถุอาจล้มเหลว เพราะมันอยู่ในถังของแฮชเก่า
3. Cmap ย้ายคีย์ไปถังใหม่โดยอัตโนมัติ
4. Dไม่มีอะไรเปลี่ยน เพราะแฮชของคีย์คำนวณเพียงครั้งเดียวตอนโปรแกรมเริ่มทำงาน