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

โครงสร้างข้อมูลใดเหมาะที่สุดสำหรับฟีเจอร์ "ย้อนกลับ" (undo) ในโปรแกรมแก้ไขข้อความ

1. Aสแตก (stack)
2. Bคิว (queue)
3. Cเซตแฮช (hash set)
4. Dกราฟ (graph)

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

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

รากของต้นไม้ (root) คืออะไร

1. Aโหนดบนสุดที่ไม่มีโหนดแม่
2. Bโหนดที่มีค่ามากที่สุด
3. Cโหนดใดก็ได้ตรงกลาง
4. Dโหนดที่ไม่มีโหนดลูก

ใน min-heap ทวิภาคที่เก็บในอาร์เรย์ (ดัชนีเริ่มที่ 0) ลูกของโหนดที่ดัชนี i อยู่ที่

1. Ai + 1 และ i + 2
2. B2i และ 2i + 1
3. C2i + 1 และ 2i + 2
4. Di/2 และ i/2 + 1

จะเกิดอะไรขึ้นเมื่อตารางแฮช rehash หลังตัวประกอบการโหลดเกินเกณฑ์

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

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

1. A50
2. B20
3. C40
4. D70

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

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

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

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