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

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

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

กราฟประกอบด้วย

1. Aคีย์และแฮชเท่านั้น
2. Bรากและใบเท่านั้น
3. Cแถวและคอลัมน์
4. Dจุดยอด (โหนด) ที่เชื่อมต่อกันด้วยเส้นเชื่อม

ข้อแตกต่างหลักระหว่างอาร์เรย์สถิตกับอาร์เรย์พลวัตคืออะไร

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

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

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

การตรวจว่ามีเส้นเชื่อม (u, v) หรือไม่ด้วยเมทริกซ์ประชิดใช้เวลาเท่าใด

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

บัฟเฟอร์วงกลม (circular buffer หรือ ring buffer) มักใช้สร้าง

1. Aต้นไม้ค้นหาแบบทวิภาค
2. Bฟังก์ชันแฮช
3. Cคิวขนาดคงที่
4. Dการท่องกราฟ

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

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

segment tree มักใช้เพื่อ

1. Aตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)
2. Bเก็บเส้นเชื่อมของกราฟ
3. Cสร้างสแตก
4. Dเรียงสตริงตามตัวอักษรโดยเก็บแต่ละคำนำหน้าไว้ในโหนดต้นไม้แยกกัน