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

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

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

deque (double-ended queue) คืออะไร

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

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

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

ในตารางแฮชที่ใช้ open addressing ตัวประกอบการโหลดสูงสุดที่เป็นไปได้คือเท่าใด

1. Aไม่มีค่าสูงสุด
2. B1
3. C0.5
4. D2

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

1. A40
2. B70
3. C20
4. D50

เหตุใดฮีปทวิภาคจึงเก็บในอาร์เรย์ได้โดยไม่ต้องใช้ตัวชี้

1. Aเป็นต้นไม้ทวิภาคสมบูรณ์ ตำแหน่งจึงเป็นไปตามสูตรดัชนีง่าย ๆ
2. Bฮีปมีสมาชิกไม่เกิน 100 ตัวเสมอ
3. Cอาร์เรย์เก็บคีย์ให้เรียงลำดับโดยอัตโนมัติ จึงไม่ต้องใช้ตัวชี้
4. Dคีย์ทั้งหมดในฮีปเท่ากัน

segment tree มักใช้เพื่อ

1. Aเรียงสตริงตามตัวอักษรโดยเก็บแต่ละคำนำหน้าไว้ในโหนดต้นไม้แยกกัน
2. Bสร้างสแตก
3. Cเก็บเส้นเชื่อมของกราฟ
4. Dตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)

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

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