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

ในกราฟ วงจร (cycle) คืออะไร

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

การดำเนินการใดเป็น O(1) สำหรับอาร์เรย์แต่เป็น O(n) สำหรับลิงก์ลิสต์เชิงเดี่ยว

1. Aการลบสมาชิกหัว
2. Bการอ่านสมาชิกตัวแรก
3. Cการแทรกที่หัว
4. Dการเข้าถึงสมาชิกที่ดัชนี i

ความลึก (depth) ของโหนดในต้นไม้คือ

1. Aจำนวนเส้นเชื่อมจากโหนดนั้นถึงใบที่ลึกที่สุด
2. Bจำนวนลูกของโหนดนั้น
3. Cจำนวนโหนดในต้นไม้ย่อยของมัน
4. Dจำนวนเส้นเชื่อมจากรากถึงโหนดนั้น

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

1. A2^h+1 − 1
2. B2h + 1
3. Ch²
4. D2^h

ในคิววงกลมที่เก็บในอาร์เรย์ความจุ n ตำแหน่งถัดจากดัชนี i คำนวณอย่างไร

1. A(i − 1) mod n
2. Bi + 1
3. C2i + 1
4. D(i + 1) mod n

ความซับซ้อนเชิงเวลาของการค้นหาคีย์ใน binary search tree ที่สมดุลคือเท่าใด

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

คุณสมบัติใดทำให้ B-tree ทุกต้นสมดุลอย่างสมบูรณ์

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

ต้นไม้แดง–ดำ (red-black tree) ต้องมีคุณสมบัติใด

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