1.ง่าย
การดำเนินการใดเป็น O(1) สำหรับอาร์เรย์แต่เป็น O(n) สำหรับลิงก์ลิสต์เชิงเดี่ยว
- Aการอ่านสมาชิกตัวแรก
- Bการเข้าถึงสมาชิกที่ดัชนี i
- Cการลบสมาชิกหัว
- Dการแทรกที่หัว
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
สมาชิกของอาร์เรย์ถูกเก็บในหน่วยความจำอย่างไร
- Aกระจัดกระจาย เชื่อมด้วยตัวชี้
- Bในตำแหน่งสุ่มที่เลือกด้วยแฮช
- Cในบล็อกต่อเนื่องเดียว ต่อกันทีละตัว
- Dในต้นไม้ของหน้าหน่วยความจำ
3.ง่าย
การท่องแบบ preorder ของต้นไม้ทวิภาคเยี่ยมโหนดตามลำดับใด
- Aต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา แล้วโหนด
- Bโหนด แล้วต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา
- Cทีละระดับจากด้านบน
- Dต้นไม้ย่อยซ้าย แล้วโหนด แล้วต้นไม้ย่อยขวา
4.ปานกลาง
โครงสร้างข้อมูลใดที่การค้นหาในแนวลึก (DFS) แบบวนซ้ำใช้
- Aคิว
- Bสแตก
- Cตารางแฮชเท่านั้น
- Dฮีป
5.ปานกลาง
คิวถูกสร้างด้วยสแตกสองตัว: push ลงสแตก "in" และ pop จากสแตก "out" โดยเติมจาก "in" เมื่อว่าง ต้นทุนกระจายต่อการดำเนินการคือเท่าใด
- AO(n²)
- BO(log n)
- CO(1)
- DO(n)
6.ปานกลาง
รายการประชิดใช้หน่วยความจำเท่าใดสำหรับกราฟที่มี V จุดยอดและ E เส้นเชื่อม
- AO(V²)
- BO(V × E)
- CO(E²)
- DO(V + E)
7.ยาก
segment tree มักใช้เพื่อ
- Aเก็บเส้นเชื่อมของกราฟ
- Bสร้างสแตก
- Cตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)
- Dเรียงสตริงตามตัวอักษรโดยเก็บแต่ละคำนำหน้าไว้ในโหนดต้นไม้แยกกัน
8.ยาก
อาร์เรย์พลวัตเพิ่มเป็นสองเท่าเมื่อเต็ม เหตุใดหลายการสร้างจึงหดมันเมื่อเหลือเพียงหนึ่งในสี่เท่านั้น ไม่ใช่ครึ่งหนึ่ง
- Aเพื่อหลีกเลี่ยงการปรับขนาดซ้ำเมื่อ push และ pop สลับกันใกล้ขอบเขต
- Bเพราะการหดที่ครึ่งหนึ่งทำให้สมาชิกหาย
- Cเพราะตัวจัดสรรหน่วยความจำคืนหน่วยความจำได้เฉพาะเป็นหนึ่งในสี่ของบล็อกเท่านั้น
- Dเพื่อให้อาร์เรย์เรียงลำดับ
เฉลย
- 1. B · การเข้าถึงสมาชิกที่ดัชนี i
- 2. C · ในบล็อกต่อเนื่องเดียว ต่อกันทีละตัว
- 3. B · โหนด แล้วต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา
- 4. B · สแตก
- 5. C · O(1)
- 6. D · O(V + E)
- 7. C · ตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)
- 8. A · เพื่อหลีกเลี่ยงการปรับขนาดซ้ำเมื่อ push และ pop สลับกันใกล้ขอบเขต
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com