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

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

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

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

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

สมาชิกของอาร์เรย์ถูกเก็บในหน่วยความจำอย่างไร

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

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

1. Ai + 1
2. B(i − 1) mod n
3. C2i + 1
4. D(i + 1) mod n

ต้นไม้ทวิภาคมีราก 1 ลูกซ้าย 2 ลูกขวา 3 โหนด 2 มีลูก 4 (ซ้าย) และ 5 (ขวา) การท่องแบบ postorder คืออะไร

1. A4 2 5 1 3
2. B5 4 3 2 1
3. C1 2 4 5 3
4. D4 5 2 3 1

อัลกอริทึมของ Dijkstra ใช้ชนิดข้อมูลนามธรรมใดเลือกจุดยอดถัดไปที่จะประมวลผล

1. Aคิวลำดับความสำคัญแบบค่าต่ำสุด (min-priority queue)
2. Bเซตที่ไม่มีลำดับ
3. Cคิว FIFO
4. Dสแตก

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

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

โครงสร้างใดช่วยคำนวณค่าสูงสุดของทุกหน้าต่างขนาด k ในอาร์เรย์ในเวลารวม O(n)

1. Aลิงก์ลิสต์เชิงเดี่ยวของสมาชิกในหน้าต่าง
2. Bdeque ที่เก็บดัชนีเรียงตามค่าจากมากไปน้อย
3. Cmin-heap ที่สร้างใหม่ทุกหน้าต่าง
4. Dอาร์เรย์เรียงลำดับที่อัปเดตด้วยการเลื่อน