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

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

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

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

1. AEnqueue
2. BDequeue
3. CPush
4. DInsert

รากของต้นไม้ (root) คืออะไร

1. Aโหนดบนสุดที่ไม่มีโหนดแม่
2. Bโหนดที่มีค่ามากที่สุด
3. Cโหนดใดก็ได้ตรงกลาง
4. Dโหนดที่ไม่มีโหนดลูก

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

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

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

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

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

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

โครงสร้าง union-find (เซตไม่เชื่อมกัน) ที่ใช้ union by rank และ path compression มีต้นทุนกระจายต่อการดำเนินการเป็น

1. AO(α(n)) ซึ่งเป็นฟังก์ชันผกผันของอัคเคอร์มันน์ ที่แทบเป็นค่าคงที่ในทางปฏิบัติ
2. BO(log n) พอดี
3. CO(n²)
4. DO(n)

สำหรับแต่ละสมาชิกของอาร์เรย์ คุณต้องการสมาชิกที่ใหญ่กว่าถัดไปทางขวา ในเวลารวม O(n) โครงสร้างใดช่วยได้

1. Aคิวที่เก็บทุกคู่ของสมาชิก
2. Bตารางแฮชของสมาชิกทั้งหมด
3. Cสแตกที่เก็บสมาชิกที่รอคำตอบ
4. Dbinary search tree ที่สร้างใหม่สำหรับแต่ละสมาชิก