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

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

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

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

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

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

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

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

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

ต้นไม้ทวิภาคมีราก 1 ลูกซ้าย 2 ลูกขวา 3 โหนด 2 มีลูก 4 (ซ้าย) และ 5 (ขวา) การท่องแบบ preorder คืออะไร

1. A4 5 2 3 1
2. B1 2 3 4 5
3. C4 2 5 1 3
4. D1 2 4 5 3

ต้นไม้ทวิภาคสมบูรณ์เต็ม (perfect binary tree) ที่มีความสูง h มีกี่โหนด เมื่อความสูงนับเป็นเส้นเชื่อม

1. A2^h
2. B2^h+1 − 1
3. Ch²
4. D2h + 1

ในอัลกอริทึมต้นไม้ทอดข้ามที่น้อยที่สุดของ Kruskal โครงสร้าง union-find ใช้เพื่อ

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

ใน BST ที่มีราก 50 ต้นไม้ย่อยซ้าย 30 (ลูก 20, 40) และต้นไม้ย่อยขวา 70 (ลูก 60, 80) ลบรากโดยใช้ in-order successor คีย์ใดกลายเป็นรากใหม่

1. A80
2. B70
3. C60
4. D40