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

กราฟประกอบด้วย

1. Aรากและใบเท่านั้น
2. Bแถวและคอลัมน์
3. Cจุดยอด (โหนด) ที่เชื่อมต่อกันด้วยเส้นเชื่อม
4. Dคีย์และแฮชเท่านั้น

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

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

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

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

แอปพลิเคชันต้องการค้นหาเร็ว และต้องแสดงรายการคีย์เรียงลำดับและตอบคำถามช่วง โครงสร้างใดเหมาะที่สุด

1. Aสแตก
2. Bตารางแฮช
3. Cbinary search tree แบบสมดุล
4. Dลิงก์ลิสต์ที่ไม่เรียงลำดับ

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

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

คุณมีการอ้างอิงถึงโหนดกลางลิสต์ ในลิสต์ชนิดใดลบมันได้ใน O(1)

1. Aอาร์เรย์พลวัต
2. Bลิงก์ลิสต์สองทิศทาง
3. Cลิงก์ลิสต์เชิงเดี่ยว
4. Dอาร์เรย์เรียงลำดับ

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

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

สำหรับแต่ละสมาชิกของอาร์เรย์ คุณต้องการสมาชิกที่ใหญ่กว่าถัดไปทางขวา ในเวลารวม O(n) โครงสร้างใดช่วยได้

1. Aสแตกที่เก็บสมาชิกที่รอคำตอบ
2. Bbinary search tree ที่สร้างใหม่สำหรับแต่ละสมาชิก
3. Cตารางแฮชของสมาชิกทั้งหมด
4. Dคิวที่เก็บทุกคู่ของสมาชิก