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

ในการแทนกราฟด้วยรายการประชิด (adjacency list) เก็บอะไรสำหรับแต่ละจุดยอด

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

กราฟประกอบด้วย

1. Aแถวและคอลัมน์
2. Bคีย์และแฮชเท่านั้น
3. Cรากและใบเท่านั้น
4. Dจุดยอด (โหนด) ที่เชื่อมต่อกันด้วยเส้นเชื่อม

ในต้นไม้ โหนดพี่น้อง (sibling) คืออะไร

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

ความซับซ้อนเชิงเวลาของการค้นหาคีย์ใน binary search tree ที่สมดุลคือเท่าใด

1. AO(1)
2. BO(n)
3. CO(log n)
4. DO(n log n)

ต้นไม้ AVL รักษาเงื่อนไขสมดุลใดที่ทุกโหนด

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

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

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

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

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

ในบัฟเฟอร์วงกลม front == rear อาจหมายถึงว่างหรือเต็ม วิธีทั่วไปในการแยกสองกรณีคืออะไร

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