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

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

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

กราฟมีน้ำหนัก (weighted graph) คืออะไร

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

การดำเนินการใดช้าในอาร์เรย์แต่เร็วที่ส่วนหัวของลิงก์ลิสต์

1. Aการแทรกที่จุดเริ่มต้น
2. Bการเข้าถึงสมาชิกตัวที่ 5
3. Cการอ่านสมาชิกตัวสุดท้ายด้วยดัชนี
4. Dการหาความยาวของอาร์เรย์ขนาดคงที่

ทราย (trie หรือ prefix tree) มีประสิทธิภาพเป็นพิเศษสำหรับ

1. Aการค้นหาด้วยคำนำหน้า เช่น autocomplete
2. Bการเก็บเมทริกซ์
3. Cการเรียงตัวเลข
4. Dการหาเส้นทางสั้นที่สุด

ตารางแฮชขนาด 7 ใช้ h(k) = k mod 7 และ linear probing หลังแทรก 10 แล้ว 17 ถูกเก็บที่ใด

1. Aดัชนี 6
2. Bดัชนี 4
3. Cดัชนี 0
4. Dดัชนี 3

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

1. A1 2 3 4 5
2. B4 5 2 3 1
3. C4 2 5 1 3
4. D1 2 4 5 3

อาร์เรย์พลวัตเพิ่มเป็นสองเท่าเมื่อเต็ม เหตุใดหลายการสร้างจึงหดมันเมื่อเหลือเพียงหนึ่งในสี่เท่านั้น ไม่ใช่ครึ่งหนึ่ง

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

การกลับลิงก์ลิสต์เชิงเดี่ยวในที่เดิมมีต้นทุนด้านเวลาและพื้นที่เพิ่มเติมเท่าใด

1. Aเวลา O(1) และพื้นที่เพิ่ม O(1)
2. Bเวลา O(n) และพื้นที่เพิ่ม O(1)
3. Cเวลา O(n) และพื้นที่เพิ่ม O(n)
4. Dเวลา O(n log n) และพื้นที่เพิ่ม O(1)