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