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

แต่ละโหนดในลิงก์ลิสต์สองทิศทาง (doubly linked list) มีอะไร

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

ในกราฟไม่มีทิศทาง ดีกรี (degree) ของจุดยอดคืออะไร

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

โครงสร้างข้อมูลใดทำงานตามหลักการ "เข้าก่อนออกก่อน" (first in, first out)

1. Aต้นไม้ทวิภาค (binary tree)
2. Bสแตก (stack)
3. Cฮีป (heap)
4. Dคิว (queue)

ต้นไม้ AVL และต้นไม้แดง–ดำ (red-black) รับประกัน

1. Aไม่มีโหนดใดมีลูกสองตัว
2. Bความสูง O(log n) ผ่านการปรับสมดุลใหม่
3. Cการค้นหาในเวลาคงที่ทุกกรณี
4. Dคีย์ถูกเก็บตามลำดับการแทรก

เครือข่ายถนนมี 100,000 ทางแยก แต่ละแห่งเชื่อมกับประมาณ 4 แห่ง การแทนแบบใดเหมาะที่สุด

1. Aเมทริกซ์ประชิด
2. Bอาร์เรย์เรียงลำดับเดียวของจุดยอด
3. Cรายการประชิด
4. Dฮีปทวิภาคของเส้นเชื่อม

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

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

คุณต้องเก็บค่าที่น้อยที่สุด k ตัวจากสตรีมของตัวเลข n ตัวโดยใช้หน่วยความจำ O(k) แนวทางใดทำงานใน O(n log k)

1. Aอาร์เรย์เรียงลำดับของค่าทั้ง n
2. Bmin-heap ที่เก็บค่าทั้ง n ตัว แล้วดึงค่าที่น้อยที่สุด k ตัวออกมาตอนท้าย
3. Cคิว FIFO ของ k ค่าล่าสุด
4. Dmax-heap ขนาด k โดยแทนที่รากเมื่อมีค่าที่เล็กกว่ามา

คุณสมบัติใดทำให้ B-tree ทุกต้นสมดุลอย่างสมบูรณ์

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