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

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

1. AInsert
2. BEnqueue
3. CPush
4. DDequeue

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

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

สมาชิกที่เล็กที่สุดของ min-heap ทวิภาคอยู่ที่ใด

1. Aในใบใดก็ได้ ซึ่งต้องค้นหา
2. Bในตำแหน่งสุดท้ายของอาร์เรย์
3. Cที่ราก
4. Dในใบซ้ายสุด

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

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

ทราย (trie หรือ prefix tree) มีประสิทธิภาพเป็นพิเศษสำหรับ

1. Aการเรียงตัวเลข
2. Bการหาเส้นทางสั้นที่สุด
3. Cการเก็บเมทริกซ์
4. Dการค้นหาด้วยคำนำหน้า เช่น autocomplete

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

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

segment tree มักใช้เพื่อ

1. Aตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)
2. Bเก็บเส้นเชื่อมของกราฟ
3. Cเรียงสตริงตามตัวอักษรโดยเก็บแต่ละคำนำหน้าไว้ในโหนดต้นไม้แยกกัน
4. Dสร้างสแตก

เพื่อให้ตารางแฮชทำงานถูกต้อง แฮชและความเท่ากันต้องเป็นไปตามกฎใด

1. Aคีย์ที่เท่ากันต้องมีค่าแฮชเท่ากัน
2. Bคีย์ที่ต่างกันต้องมีค่าแฮชต่างกัน
3. Cค่าแฮชต้องเป็นจำนวนเฉพาะ
4. Dค่าแฮชที่เท่ากันหมายถึงคีย์เท่ากัน