1.ง่าย
การดำเนินการของคิวที่เอาสมาชิกด้านหน้าออกเรียกว่าอะไร
- ADequeue
- BInsert
- CEnqueue
- DPush
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
รากของต้นไม้ (root) คืออะไร
- Aโหนดที่ไม่มีโหนดลูก
- Bโหนดที่มีค่ามากที่สุด
- Cโหนดบนสุดที่ไม่มีโหนดแม่
- Dโหนดใดก็ได้ตรงกลาง
3.ง่าย
ตารางแฮชเก็บข้อมูลเป็น
- Aคู่คีย์–ค่าที่หาตำแหน่งด้วยฟังก์ชันแฮช
- Bสตริงความยาวคงที่
- Cต้นไม้ที่คีย์เรียงลำดับ
- Dรายการที่เรียงลำดับเท่านั้น
4.ปานกลาง
สมาชิกใหม่ถูกแทรกลงในฮีปทวิภาคอย่างไร
- Aวางที่รากและเลื่อนลง
- Bวางที่ท้ายอาร์เรย์และเลื่อนขึ้น (sift up) ตราบที่ยังละเมิดคุณสมบัติฮีป
- Cแทรกที่ตำแหน่งตามลำดับโดยเลื่อนสมาชิกที่ใหญ่กว่าทั้งหมดไปทางขวาหนึ่งตำแหน่ง
- Dสร้างฮีปใหม่ทั้งหมดตั้งแต่ต้น
5.ปานกลาง
การท่องแบบ in-order ของ binary search tree เยี่ยมคีย์ตามลำดับ
- Aเรียงจากน้อยไปมาก
- Bตามระดับ
- Cตามลำดับการแทรก
- Dเรียงจากมากไปน้อยเสมอ
6.ปานกลาง
จุดประสงค์ของโหนดยามเฝ้า (sentinel หรือ dummy) ในลิงก์ลิสต์คืออะไร
- Aทำให้โค้ดง่ายขึ้นโดยตัดกรณีพิเศษที่หัวหรือท้าย
- Bเก็บจำนวนสมาชิก
- Cทำให้ลิสต์เรียงลำดับ
- Dเพื่อป้องกันไม่ให้ลิสต์ขยายเกินจำนวนโหนดสูงสุดที่กำหนดไว้
7.ยาก
เหตุใดจึงใช้ B-tree ในฐานข้อมูลและระบบไฟล์
- Aไม่ต้องปรับสมดุลใหม่
- Bเก็บข้อมูลโดยไม่เรียงลำดับ
- Cใช้หน่วยความจำน้อยกว่าอาร์เรย์ใด ๆ ดัชนีทั้งหมดจึงเก็บในหน่วยความจำหลักได้เสมอ
- Dตัวประกอบการแตกแขนงสูงทำให้ต้นไม้ตื้น ลดการอ่านดิสก์ที่ช้า
8.ยาก
ต้นไม้แดง–ดำ (red-black tree) ต้องมีคุณสมบัติใด
- Aทุกโหนดต้องเป็นสีแดง
- Bรากต้องเป็นสีแดง
- Cทุกเส้นทางจากโหนดไปยังใบของลูกหลานมีจำนวนโหนดสีดำเท่ากัน
- Dโหนดสีแดงทุกโหนดต้องมีลูกสีแดง โหนดสีแดงจึงต่อเป็นสายไม่ขาดตอนไปจนถึงใบ
เฉลย
- 1. A · Dequeue
- 2. C · โหนดบนสุดที่ไม่มีโหนดแม่
- 3. A · คู่คีย์–ค่าที่หาตำแหน่งด้วยฟังก์ชันแฮช
- 4. B · วางที่ท้ายอาร์เรย์และเลื่อนขึ้น (sift up) ตราบที่ยังละเมิดคุณสมบัติฮีป
- 5. A · เรียงจากน้อยไปมาก
- 6. A · ทำให้โค้ดง่ายขึ้นโดยตัดกรณีพิเศษที่หัวหรือท้าย
- 7. D · ตัวประกอบการแตกแขนงสูงทำให้ต้นไม้ตื้น ลดการอ่านดิสก์ที่ช้า
- 8. C · ทุกเส้นทางจากโหนดไปยังใบของลูกหลานมีจำนวนโหนดสีดำเท่ากัน
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com