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

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

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

ความลึก (depth) ของโหนดในต้นไม้คือ

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

ในต้นไม้ค้นหาแบบทวิภาค (binary search tree) ค่าในต้นไม้ย่อยซ้ายของโหนดมีค่า

1. Aมากกว่าค่าของโหนด
2. Bเท่ากับค่าของโหนด
3. Cน้อยกว่าค่าของโหนด
4. Dเรียงลำดับแบบสุ่ม

เหตุใดการท่องอาร์เรย์จึงเร็วกว่าการท่องลิงก์ลิสต์ที่ยาวเท่ากันมากในทางปฏิบัติ

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

ในตารางแฮชที่ใช้ open addressing ตัวประกอบการโหลดสูงสุดที่เป็นไปได้คือเท่าใด

1. A2
2. B1
3. Cไม่มีค่าสูงสุด
4. D0.5

ต้นไม้ทวิภาคสมบูรณ์เต็ม (perfect binary tree) ที่มีความสูง h มีกี่โหนด เมื่อความสูงนับเป็นเส้นเชื่อม

1. A2h + 1
2. B2^h
3. C2^h+1 − 1
4. Dh²

อัลกอริทึมของ Kahn สำหรับการเรียงทอพอโลยีลบจุดยอดที่มี in-degree 0 ซ้ำ ๆ โครงสร้างใดเก็บจุดยอดเหล่านั้น

1. Aเมทริกซ์ประชิดที่บันทึกว่าจุดยอดใดถูกลบไปแล้ว
2. Bคิว (หรือคอลเล็กชันใดก็ได้) ของจุดยอดที่มี in-degree เป็น 0
3. Cmax-heap เรียงตาม out-degree
4. Dสแตกของเส้นเชื่อมที่เยี่ยมทั้งหมด

ในตารางแฮชที่ใช้ open addressing เหตุใดการลบจึงมักทำด้วยเครื่องหมาย "tombstone"

1. Aการทำให้ช่องว่างอาจทำลายลำดับการตรวจสอบสำหรับคีย์อื่น
2. Btombstone เร่งการแฮช
3. Cคีย์ที่ลบต้องเก็บไว้ตลอดไปเพื่อความปลอดภัย จึงใช้ช่องนั้นซ้ำไม่ได้
4. Dทำให้ตารางเรียงลำดับ