1.ง่าย
ในตารางแฮช การชนกัน (collision) คืออะไร
- Aคีย์ที่เท่ากันสองตัวถูกเก็บสองครั้ง
- Bตารางหน่วยความจำหมด
- Cคีย์สองตัวที่ต่างกันแปลงเป็นดัชนีเดียวกัน
- Dคีย์ไม่สามารถแฮชได้เลย
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
การดำเนินการใดเป็น O(1) สำหรับอาร์เรย์แต่เป็น O(n) สำหรับลิงก์ลิสต์เชิงเดี่ยว
- Aการเข้าถึงสมาชิกที่ดัชนี i
- Bการลบสมาชิกหัว
- Cการแทรกที่หัว
- Dการอ่านสมาชิกตัวแรก
3.ง่าย
ต้นไม้ที่มี n โหนดมีเส้นเชื่อมกี่เส้น
- An − 1
- B2n
- Cn + 1
- Dn
4.ปานกลาง
ต้นไม้ทวิภาคมีราก 1 ลูกซ้าย 2 ลูกขวา 3 โหนด 2 มีลูก 4 (ซ้าย) และ 5 (ขวา) การท่องแบบ postorder คืออะไร
- A4 2 5 1 3
- B1 2 4 5 3
- C5 4 3 2 1
- D4 5 2 3 1
5.ปานกลาง
จุดประสงค์ของโหนดยามเฝ้า (sentinel หรือ dummy) ในลิงก์ลิสต์คืออะไร
- Aทำให้โค้ดง่ายขึ้นโดยตัดกรณีพิเศษที่หัวหรือท้าย
- Bเก็บจำนวนสมาชิก
- Cทำให้ลิสต์เรียงลำดับ
- Dเพื่อป้องกันไม่ให้ลิสต์ขยายเกินจำนวนโหนดสูงสุดที่กำหนดไว้
6.ปานกลาง
ความสูงในกรณีเลวร้ายที่สุดของ binary search tree ที่มี n โหนดคือเท่าใด ถ้าแทรกคีย์ตามลำดับที่เรียงแล้ว
- A1
- Bn (กลายเป็นลิงก์ลิสต์)
- Clog₂ n
- D√n
7.ยาก
segment tree มักใช้เพื่อ
- Aเก็บเส้นเชื่อมของกราฟ
- Bตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)
- Cสร้างสแตก
- Dเรียงสตริงตามตัวอักษรโดยเก็บแต่ละคำนำหน้าไว้ในโหนดต้นไม้แยกกัน
8.ยาก
เหตุใดฐานข้อมูลจึงมักใช้ B+ tree แทน B-tree ธรรมดาสำหรับดัชนี
- Aระเบียนทั้งหมดอยู่ในใบที่เชื่อมกัน ทำให้สแกนช่วงได้มีประสิทธิภาพ
- BB+ tree ใช้โหนดภายในแบบทวิภาค ซึ่งลดจำนวนการอ่านดิสก์
- CB+ tree เก็บข้อมูลที่รากเท่านั้น
- DB+ tree ไม่จำเป็นต้องสมดุล
เฉลย
- 1. C · คีย์สองตัวที่ต่างกันแปลงเป็นดัชนีเดียวกัน
- 2. A · การเข้าถึงสมาชิกที่ดัชนี i
- 3. A · n − 1
- 4. D · 4 5 2 3 1
- 5. A · ทำให้โค้ดง่ายขึ้นโดยตัดกรณีพิเศษที่หัวหรือท้าย
- 6. B · n (กลายเป็นลิงก์ลิสต์)
- 7. B · ตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)
- 8. A · ระเบียนทั้งหมดอยู่ในใบที่เชื่อมกัน ทำให้สแกนช่วงได้มีประสิทธิภาพ
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com