ใบงาน โครงสร้างข้อมูล พร้อมเฉลย

การท่องแบบ preorder ของต้นไม้ทวิภาคเยี่ยมโหนดตามลำดับใด

1. Aโหนด แล้วต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา
2. Bต้นไม้ย่อยซ้าย แล้วโหนด แล้วต้นไม้ย่อยขวา
3. Cต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา แล้วโหนด
4. Dทีละระดับจากด้านบน

ลักษณะเด่นของเซต (set) ในฐานะชนิดข้อมูลนามธรรมคืออะไร

1. Aเก็บสมาชิกโดยไม่มีซ้ำ
2. Bเก็บคู่คีย์–ค่า
3. Cเก็บสมาชิกเรียงลำดับ
4. Dเข้าถึงได้เฉพาะที่ปลายด้านเดียว

ในลิงก์ลิสต์เชิงเดี่ยว (singly linked list) แต่ละโหนดประกอบด้วย

1. Aข้อมูลและการอ้างอิงไปยังโหนดอื่นทั้งหมด
2. Bข้อมูลและการอ้างอิงไปยังโหนดถัดไป
3. Cข้อมูลเท่านั้น
4. Dข้อมูลและดัชนี

สมาชิกใหม่ถูกแทรกลงในฮีปทวิภาคอย่างไร

1. Aแทรกที่ตำแหน่งตามลำดับโดยเลื่อนสมาชิกที่ใหญ่กว่าทั้งหมดไปทางขวาหนึ่งตำแหน่ง
2. Bวางที่รากและเลื่อนลง
3. Cวางที่ท้ายอาร์เรย์และเลื่อนขึ้น (sift up) ตราบที่ยังละเมิดคุณสมบัติฮีป
4. Dสร้างฮีปใหม่ทั้งหมดตั้งแต่ต้น

แทรกคีย์ 50, 30, 70, 20, 40 ตามลำดับนี้ลงใน binary search tree ว่าง ลูกซ้ายของ 30 คืออะไร

1. A70
2. B40
3. C50
4. D20

ต้นไม้ทวิภาคมีราก 1 ลูกซ้าย 2 ลูกขวา 3 โหนด 2 มีลูก 4 (ซ้าย) และ 5 (ขวา) การท่องแบบ preorder คืออะไร

1. A4 5 2 3 1
2. B4 2 5 1 3
3. C1 2 4 5 3
4. D1 2 3 4 5

เหตุใดจึงใช้ B-tree ในฐานข้อมูลและระบบไฟล์

1. Aเก็บข้อมูลโดยไม่เรียงลำดับ
2. Bตัวประกอบการแตกแขนงสูงทำให้ต้นไม้ตื้น ลดการอ่านดิสก์ที่ช้า
3. Cไม่ต้องปรับสมดุลใหม่
4. Dใช้หน่วยความจำน้อยกว่าอาร์เรย์ใด ๆ ดัชนีทั้งหมดจึงเก็บในหน่วยความจำหลักได้เสมอ

ต้นไม้แดง–ดำ (red-black tree) ต้องมีคุณสมบัติใด

1. Aโหนดสีแดงทุกโหนดต้องมีลูกสีแดง โหนดสีแดงจึงต่อเป็นสายไม่ขาดตอนไปจนถึงใบ
2. Bทุกโหนดต้องเป็นสีแดง
3. Cทุกเส้นทางจากโหนดไปยังใบของลูกหลานมีจำนวนโหนดสีดำเท่ากัน
4. Dรากต้องเป็นสีแดง