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

การดำเนินการใดช้าในอาร์เรย์แต่เร็วที่ส่วนหัวของลิงก์ลิสต์

1. Aการแทรกที่จุดเริ่มต้น
2. Bการเข้าถึงสมาชิกตัวที่ 5
3. Cการอ่านสมาชิกตัวสุดท้ายด้วยดัชนี
4. Dการหาความยาวของอาร์เรย์ขนาดคงที่

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

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

ความสูงของต้นไม้มักถูกนิยามว่า

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

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

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

ในฮีปทวิภาคที่เก็บในอาร์เรย์เริ่มที่ดัชนี 0 แม่ของโหนดที่ดัชนี i อยู่ที่ใด

1. Aที่ดัชนี ⌊(i − 1) / 2⌋
2. Bที่ดัชนี i − 1
3. Cที่ดัชนี 2i + 1
4. Dที่ดัชนี ⌊i / 2⌋ + 1

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

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

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

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

ข้อได้เปรียบหลักของ skip list เหนือลิงก์ลิสต์ที่เรียงลำดับคืออะไร

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