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

ในลิงก์ลิสต์เชิงเดี่ยว (singly linked list) แต่ละโหนดประกอบด้วย

1. Aข้อมูลและดัชนี
2. Bข้อมูลและการอ้างอิงไปยังโหนดถัดไป
3. Cข้อมูลและการอ้างอิงไปยังโหนดอื่นทั้งหมด
4. Dข้อมูลเท่านั้น

ความสูงของต้นไม้มักถูกนิยามว่า

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

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

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

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

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

ความสูงในกรณีเลวร้ายที่สุดของ binary search tree ที่มี n โหนดคือเท่าใด ถ้าแทรกคีย์ตามลำดับที่เรียงแล้ว

1. A1
2. Bn (กลายเป็นลิงก์ลิสต์)
3. C√n
4. Dlog₂ n

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

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

Fenwick tree (binary indexed tree) บนอาร์เรย์ที่มีตัวเลข n ตัว รองรับการดำเนินการใดใน O(log n)

1. Aการหามัธยฐานใน O(1)
2. Bการแทรกสมาชิกที่ตำแหน่งใดก็ได้
3. Cการเรียงอาร์เรย์และการค้นหาแบบทวิภาค
4. Dคำถามผลรวมคำนำหน้าและการอัปเดตสมาชิกเดียว

กฎของต้นไม้แดง–ดำรับประกันอะไรเกี่ยวกับความสูงของต้นไม้ที่มี n คีย์

1. Aความสูงไม่เกิน log₂ n + 1
2. Bความสูงเท่ากับ log₂ n พอดี
3. Cความสูงไม่เกิน 2 log₂(n + 1)
4. Dความสูงไม่เกิน n / 2