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

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

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

ตารางแฮชเก็บข้อมูลเป็น

1. Aรายการที่เรียงลำดับเท่านั้น
2. Bคู่คีย์–ค่าที่หาตำแหน่งด้วยฟังก์ชันแฮช
3. Cสตริงความยาวคงที่
4. Dต้นไม้ที่คีย์เรียงลำดับ

ต้นไม้ที่มี n โหนดมีเส้นเชื่อมกี่เส้น

1. A2n
2. Bn + 1
3. Cn − 1
4. Dn

เมทริกซ์ประชิด (adjacency matrix) ของกราฟที่มี V จุดยอดใช้หน่วยความจำเท่าใด

1. AO(V²)
2. BO(E)
3. CO(log V)
4. DO(V + E)

อัลกอริทึมของ Dijkstra ใช้ชนิดข้อมูลนามธรรมใดเลือกจุดยอดถัดไปที่จะประมวลผล

1. Aคิว FIFO
2. Bเซตที่ไม่มีลำดับ
3. Cคิวลำดับความสำคัญแบบค่าต่ำสุด (min-priority queue)
4. Dสแตก

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

1. A1 2 4 5 3
2. B1 2 3 4 5
3. C4 2 5 1 3
4. D4 5 2 3 1

ความซับซ้อนเชิงเวลาของ decrease-key ในฮีปทวิภาค (เมื่อทราบตำแหน่งของสมาชิก) คือ

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

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

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