1.ง่าย
การดำเนินการใดช้าในอาร์เรย์แต่เร็วที่ส่วนหัวของลิงก์ลิสต์
- Aการอ่านสมาชิกตัวสุดท้ายด้วยดัชนี
- Bการหาความยาวของอาร์เรย์ขนาดคงที่
- Cการแทรกที่จุดเริ่มต้น
- Dการเข้าถึงสมาชิกตัวที่ 5
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
การท่องแบบ postorder ของต้นไม้ทวิภาคเยี่ยมโหนดตามลำดับใด
- Aโหนด แล้วต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา
- Bต้นไม้ย่อยซ้าย แล้วโหนด แล้วต้นไม้ย่อยขวา
- Cต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา แล้วโหนด
- Dต้นไม้ย่อยขวา แล้วโหนด แล้วต้นไม้ย่อยซ้าย
3.ง่าย
แมป (map หรือ dictionary) เก็บอะไร
- Aค่าที่เรียงตามขนาด
- Bค่าตามลำดับการแทรกเท่านั้น
- Cคู่ของคีย์ที่เท่ากัน
- Dคู่คีย์–ค่าที่คีย์ไม่ซ้ำกัน
4.ปานกลาง
ต้นไม้ทวิภาคมีราก 1 ลูกซ้าย 2 ลูกขวา 3 โหนด 2 มีลูก 4 (ซ้าย) และ 5 (ขวา) การท่องแบบ postorder คืออะไร
- A4 5 2 3 1
- B5 4 3 2 1
- C1 2 4 5 3
- D4 2 5 1 3
5.ปานกลาง
หาคีย์ที่น้อยที่สุดใน binary search tree ได้อย่างไร
- Aตามลูกซ้ายจากรากจนไม่มีลูกซ้าย
- Bตามลูกขวาจากรากจนไม่มีลูกขวา
- Cดูเฉพาะราก
- Dเยี่ยมทุกใบและเปรียบเทียบกัน
6.ปานกลาง
จุดประสงค์ของโหนดยามเฝ้า (sentinel หรือ dummy) ในลิงก์ลิสต์คืออะไร
- Aเพื่อป้องกันไม่ให้ลิสต์ขยายเกินจำนวนโหนดสูงสุดที่กำหนดไว้
- Bเก็บจำนวนสมาชิก
- Cทำให้ลิสต์เรียงลำดับ
- Dทำให้โค้ดง่ายขึ้นโดยตัดกรณีพิเศษที่หัวหรือท้าย
7.ยาก
ข้อได้เปรียบหลักของ skip list เหนือลิงก์ลิสต์ที่เรียงลำดับคืออะไร
- Aรับประกันการค้นหา O(1) เพราะทุกโหนดเก็บตัวชี้ไปยังทุกโหนดอื่น
- Bไม่ใช้หน่วยความจำเพิ่ม
- Cเก็บคีย์โดยไม่เรียงลำดับ
- Dการค้นหา O(log n) คาดหมาย โดยใช้ตัวชี้ไปข้างหน้าหลายระดับ
8.ยาก
คุณสมบัติใดทำให้ B-tree ทุกต้นสมดุลอย่างสมบูรณ์
- Aใบทั้งหมดอยู่ที่ความลึกเดียวกัน
- Bทุกโหนดมีลูกสองตัวพอดี
- Cแต่ละโหนดเก็บหนึ่งคีย์
- Dคีย์ถูกเก็บเฉพาะที่ราก
เฉลย
- 1. C · การแทรกที่จุดเริ่มต้น
- 2. C · ต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา แล้วโหนด
- 3. D · คู่คีย์–ค่าที่คีย์ไม่ซ้ำกัน
- 4. A · 4 5 2 3 1
- 5. A · ตามลูกซ้ายจากรากจนไม่มีลูกซ้าย
- 6. D · ทำให้โค้ดง่ายขึ้นโดยตัดกรณีพิเศษที่หัวหรือท้าย
- 7. D · การค้นหา O(log n) คาดหมาย โดยใช้ตัวชี้ไปข้างหน้าหลายระดับ
- 8. A · ใบทั้งหมดอยู่ที่ความลึกเดียวกัน
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com