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

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

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

ข้อแตกต่างหลักระหว่างอาร์เรย์สถิตกับอาร์เรย์พลวัตคืออะไร

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

โครงสร้างใดมักใช้สร้างคิวลำดับความสำคัญ (priority queue)

1. Aฮีป (heap)
2. Bสแตก (stack)
3. Cสตริง
4. Dลิงก์ลิสต์เชิงเดี่ยวที่ไม่เรียงลำดับ

ความสูงในกรณีเลวร้ายที่สุดของ binary search tree ที่มี n โหนดคือเท่าใด ถ้าแทรกคีย์ตามลำดับที่เรียงแล้ว

1. A√n
2. Blog₂ n
3. C1
4. Dn (กลายเป็นลิงก์ลิสต์)

สมาชิกใหม่ถูกแทรกลงในฮีปทวิภาคอย่างไร

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

คิวถูกสร้างด้วยสแตกสองตัว: push ลงสแตก "in" และ pop จากสแตก "out" โดยเติมจาก "in" เมื่อว่าง ต้นทุนกระจายต่อการดำเนินการคือเท่าใด

1. AO(1)
2. BO(n)
3. CO(log n)
4. DO(n²)

ตรวจว่าลิงก์ลิสต์เชิงเดี่ยวมีวงจรหรือไม่โดยใช้หน่วยความจำเพิ่ม O(1) ได้อย่างไร

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

splay tree ทำอะไรหลังการเข้าถึงแต่ละครั้ง

1. Aหมุนโหนดที่เข้าถึงขึ้นไปที่ราก
2. Bย้ายโหนดที่เข้าถึงไปเป็นใบ
3. Cเปลี่ยนสีโหนดตามเส้นทางการค้นหา
4. Dสร้างต้นไม้ใหม่ทั้งหมดให้สมดุล