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

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

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

การดำเนินการใดเป็น O(1) สำหรับอาร์เรย์แต่เป็น O(n) สำหรับลิงก์ลิสต์เชิงเดี่ยว

1. Aการลบสมาชิกหัว
2. Bการอ่านสมาชิกตัวแรก
3. Cการแทรกที่หัว
4. Dการเข้าถึงสมาชิกที่ดัชนี i

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

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

เหตุใดการท่องอาร์เรย์จึงเร็วกว่าการท่องลิงก์ลิสต์ที่ยาวเท่ากันมากในทางปฏิบัติ

1. Aลิงก์ลิสต์เก็บสมาชิกบนดิสก์เสมอ
2. Bการท่องอาร์เรย์เป็น O(1) โดยรวม ส่วนการท่องลิงก์ลิสต์เป็น O(n)
3. Cอาร์เรย์ใช้คำสั่งน้อยกว่าในการเปรียบเทียบค่า
4. Dสมาชิกของอาร์เรย์ต่อเนื่องกัน จึงใช้แคชของ CPU ได้ดี

ข้อใดเป็นจริงเกี่ยวกับเมทริกซ์ประชิดของกราฟไม่มีทิศทาง

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

การตรวจว่ามีเส้นเชื่อม (u, v) หรือไม่ด้วยเมทริกซ์ประชิดใช้เวลาเท่าใด

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

ภายใต้การแฮชสม่ำเสมออย่างง่าย เวลาคาดหมายของการค้นหาในตารางแฮชแบบ chaining ที่มี n คีย์และ m ถังคือเท่าใด

1. AO(n)
2. BO(m)
3. CO(1 + α) เมื่อ α = n / m
4. DO(log n)

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

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