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

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

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

การดำเนินการ peek (หรือ top) บนสแตกทำอะไร

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

ในต้นไม้ โหนดพี่น้อง (sibling) คืออะไร

1. Aโหนดที่ไม่มีลูก
2. Bโหนดที่ระดับความลึกเดียวกันในต้นไม้ย่อยต่างกัน
3. Cโหนดที่มีแม่เดียวกัน
4. Dโหนดและแม่ของมัน

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

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

โหนดใน binary search tree มีต้นไม้ย่อยขวา in-order successor ของมันอยู่ที่ใด

1. Aลูกขวาของมันเสมอ
2. Bโหนดซ้ายสุดของต้นไม้ย่อยขวา
3. Cแม่ของมันเสมอ
4. Dโหนดขวาสุดของต้นไม้ย่อยซ้าย

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

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

การลบโหนดที่มีลูกสองตัวจาก binary search tree มักทำโดย

1. Aแทนที่ด้วย in-order successor (หรือ predecessor) แล้วลบโหนดนั้น
2. Bลบต้นไม้ย่อยทั้งหมด
3. Cสร้างต้นไม้ย่อยที่อยู่ใต้โหนดนั้นขึ้นใหม่ทั้งหมดแล้วแทรกคีย์ทุกตัวที่เคยมีอยู่ลงไปใหม่
4. Dสลับกับราก

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

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