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

ในลิงก์ลิสต์เชิงเดี่ยว ตัวชี้ next ของโหนดสุดท้ายมีค่าเป็น

1. Aที่อยู่ของโหนดก่อนหน้า
2. BNull (ไม่มีโหนด)
3. Cที่อยู่ของโหนดแรก
4. Dจำนวนโหนดในลิสต์

คุณสมบัติ max-heap คืออะไร

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

กราฟประกอบด้วย

1. Aแถวและคอลัมน์
2. Bจุดยอด (โหนด) ที่เชื่อมต่อกันด้วยเส้นเชื่อม
3. Cคีย์และแฮชเท่านั้น
4. Dรากและใบเท่านั้น

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

1. A50
2. B20
3. C40
4. D70

เครือข่ายถนนมี 100,000 ทางแยก แต่ละแห่งเชื่อมกับประมาณ 4 แห่ง การแทนแบบใดเหมาะที่สุด

1. Aฮีปทวิภาคของเส้นเชื่อม
2. Bเมทริกซ์ประชิด
3. Cอาร์เรย์เรียงลำดับเดียวของจุดยอด
4. Dรายการประชิด

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

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

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

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

โหนด AVL ไม่สมดุลเพราะต้นไม้ย่อยขวาของลูกซ้ายสูงเกินไป (กรณีซ้าย–ขวา) ใช้วิธีแก้ใด

1. Aหมุนซ้ายที่ลูกซ้าย แล้วหมุนขวาที่โหนด
2. Bหมุนซ้ายหนึ่งครั้งที่โหนด
3. Cหมุนขวาหนึ่งครั้งที่โหนด
4. Dหมุนขวาที่ลูกซ้าย แล้วหมุนซ้ายที่โหนด