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

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

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

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

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

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

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

ในตารางแฮชที่ใช้ open addressing ตัวประกอบการโหลดสูงสุดที่เป็นไปได้คือเท่าใด

1. Aไม่มีค่าสูงสุด
2. B0.5
3. C2
4. D1

การท่องแบบ in-order ของ binary search tree เยี่ยมคีย์ตามลำดับ

1. Aตามระดับ
2. Bตามลำดับการแทรก
3. Cเรียงจากมากไปน้อยเสมอ
4. Dเรียงจากน้อยไปมาก

เหตุใดฮีปทวิภาคจึงเก็บในอาร์เรย์ได้โดยไม่ต้องใช้ตัวชี้

1. Aคีย์ทั้งหมดในฮีปเท่ากัน
2. Bฮีปมีสมาชิกไม่เกิน 100 ตัวเสมอ
3. Cอาร์เรย์เก็บคีย์ให้เรียงลำดับโดยอัตโนมัติ จึงไม่ต้องใช้ตัวชี้
4. Dเป็นต้นไม้ทวิภาคสมบูรณ์ ตำแหน่งจึงเป็นไปตามสูตรดัชนีง่าย ๆ

อาร์เรย์พลวัตเพิ่มเป็นสองเท่าเมื่อเต็ม เหตุใดหลายการสร้างจึงหดมันเมื่อเหลือเพียงหนึ่งในสี่เท่านั้น ไม่ใช่ครึ่งหนึ่ง

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

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

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