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

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

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

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

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

โครงสร้างข้อมูลใดเหมาะที่สุดสำหรับฟีเจอร์ "ย้อนกลับ" (undo) ในโปรแกรมแก้ไขข้อความ

1. Aสแตก (stack)
2. Bเซตแฮช (hash set)
3. Cกราฟ (graph)
4. Dคิว (queue)

ต้นไม้ AVL และต้นไม้แดง–ดำ (red-black) รับประกัน

1. Aคีย์ถูกเก็บตามลำดับการแทรก
2. Bความสูง O(log n) ผ่านการปรับสมดุลใหม่
3. Cไม่มีโหนดใดมีลูกสองตัว
4. Dการค้นหาในเวลาคงที่ทุกกรณี

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

1. A1
2. Bไม่มีค่าสูงสุด
3. C0.5
4. D2

ในฮีปทวิภาคที่เก็บในอาร์เรย์เริ่มที่ดัชนี 0 แม่ของโหนดที่ดัชนี i อยู่ที่ใด

1. Aที่ดัชนี ⌊(i − 1) / 2⌋
2. Bที่ดัชนี i − 1
3. Cที่ดัชนี ⌊i / 2⌋ + 1
4. Dที่ดัชนี 2i + 1

ความซับซ้อนเชิงเวลาของ decrease-key ในฮีปทวิภาค (เมื่อทราบตำแหน่งของสมาชิก) คือ

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

สำหรับแต่ละสมาชิกของอาร์เรย์ คุณต้องการสมาชิกที่ใหญ่กว่าถัดไปทางขวา ในเวลารวม O(n) โครงสร้างใดช่วยได้

1. Aคิวที่เก็บทุกคู่ของสมาชิก
2. Bbinary search tree ที่สร้างใหม่สำหรับแต่ละสมาชิก
3. Cสแตกที่เก็บสมาชิกที่รอคำตอบ
4. Dตารางแฮชของสมาชิกทั้งหมด