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

การท่องแบบ preorder ของต้นไม้ทวิภาคเยี่ยมโหนดตามลำดับใด

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

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

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

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

1. Aคิว (queue)
2. Bสแตก (stack)
3. Cต้นไม้ทวิภาค (binary tree)
4. Dฮีป (heap)

แทรกคีย์ 50, 30, 70, 20, 40 ตามลำดับนี้ลงใน binary search tree ว่าง ลูกซ้ายของ 30 คืออะไร

1. A20
2. B70
3. C40
4. D50

ใน min-heap ทวิภาคที่เก็บในอาร์เรย์ (ดัชนีเริ่มที่ 0) ลูกของโหนดที่ดัชนี i อยู่ที่

1. Ai + 1 และ i + 2
2. B2i + 1 และ 2i + 2
3. Ci/2 และ i/2 + 1
4. D2i และ 2i + 1

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

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

การค้นหาคีย์ใด ๆ ในฮีป min ทวิภาคที่มี n สมาชิกใช้เวลาเท่าใด

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

การกลับลิงก์ลิสต์เชิงเดี่ยวในที่เดิมมีต้นทุนด้านเวลาและพื้นที่เพิ่มเติมเท่าใด

1. Aเวลา O(n log n) และพื้นที่เพิ่ม O(1)
2. Bเวลา O(n) และพื้นที่เพิ่ม O(1)
3. Cเวลา O(n) และพื้นที่เพิ่ม O(n)
4. Dเวลา O(1) และพื้นที่เพิ่ม O(1)