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

โครงสร้างข้อมูลใดใช้ท่องต้นไม้แบบ level-order

1. Aตารางแฮช
2. Bคิว
3. Cคิวลำดับความสำคัญ
4. Dสแตก

ลักษณะเด่นของเซต (set) ในฐานะชนิดข้อมูลนามธรรมคืออะไร

1. Aเก็บสมาชิกเรียงลำดับ
2. Bเก็บสมาชิกโดยไม่มีซ้ำ
3. Cเก็บคู่คีย์–ค่า
4. Dเข้าถึงได้เฉพาะที่ปลายด้านเดียว

ในกราฟ วงจร (cycle) คืออะไร

1. Aเส้นเชื่อมที่มีน้ำหนักเป็นศูนย์
2. Bจุดยอดที่ไม่มีเส้นเชื่อม
3. Cเส้นทางที่เริ่มและสิ้นสุดที่จุดยอดเดียวกัน
4. Dเส้นทางที่เยี่ยมทุกจุดยอด

ความสูงในกรณีเลวร้ายที่สุดของ binary search tree ที่มี n โหนดคือเท่าใด ถ้าแทรกคีย์ตามลำดับที่เรียงแล้ว

1. A√n
2. B1
3. Cn (กลายเป็นลิงก์ลิสต์)
4. Dlog₂ n

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

1. A1 2 4 5 3
2. B4 5 2 3 1
3. C1 2 3 4 5
4. D4 2 5 1 3

นิพจน์ postfix 3 4 + 2 * มีค่าเท่าใด

1. A14
2. B10
3. C11
4. D24

การค้นหาคีย์ใด ๆ ในฮีป min ทวิภาคที่มี n สมาชิกใช้เวลาเท่าใด

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

หากไม่มี union by rank หรือ path compression ต้นทุนในกรณีเลวร้ายที่สุดของ find หนึ่งครั้งในโครงสร้าง union-find ที่มี n สมาชิกคือเท่าใด

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