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

กราฟมีทิศทาง (directed graph) คืออะไร

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

ในต้นไม้ โหนดพี่น้อง (sibling) คืออะไร

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

การดำเนินการ peek (หรือ top) บนสแตกทำอะไร

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

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

1. A70
2. B20
3. C50
4. D40

โครงสร้างข้อมูลใดที่การค้นหาในแนวลึก (DFS) แบบวนซ้ำใช้

1. Aตารางแฮชเท่านั้น
2. Bคิว
3. Cสแตก
4. Dฮีป

ตารางแฮชขนาด 7 ใช้ h(k) = k mod 7 และ linear probing หลังแทรก 10 แล้ว 17 ถูกเก็บที่ใด

1. Aดัชนี 4
2. Bดัชนี 0
3. Cดัชนี 3
4. Dดัชนี 6

ความซับซ้อนเชิงเวลาของ decrease-key ในฮีปทวิภาค (เมื่อทราบตำแหน่งของสมาชิก) คือ

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

Bloom filter ตอบคำถาม "สมาชิกนี้อยู่ในเซตหรือไม่" ได้ด้วย

1. Aอาจมีผลบวกเท็จ แต่ไม่มีผลลบเท็จ
2. Bอาจมีผลลบเท็จ แต่ไม่มีผลบวกเท็จ
3. Cคำตอบสำหรับตัวเลขเท่านั้น
4. Dคำตอบที่แม่นยำเสมอ