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

โครงสร้างข้อมูลใดทำงานตามหลักการ "เข้าก่อนออกก่อน" (first in, first out)

1. Aฮีป (heap)
2. Bต้นไม้ทวิภาค (binary tree)
3. Cคิว (queue)
4. Dสแตก (stack)

โครงสร้างข้อมูลใดทำงานตามหลักการ "เข้าหลังออกก่อน" (last in, first out)

1. Aคิว (queue)
2. Bลิงก์ลิสต์ (linked list)
3. Cสแตก (stack)
4. Dตารางแฮช (hash table)

ฟังก์ชันแฮชทำอะไรในตารางแฮช

1. Aนับว่ามีกี่คีย์ที่เก็บอยู่
2. Bเข้ารหัสค่าในตาราง
3. Cเรียงคีย์ในตาราง
4. Dแปลงคีย์เป็นดัชนีในตาราง

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

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

การค้นหาคำความยาว L ใน trie ที่มีตัวอักษรคงที่ใช้เวลาเท่าใด

1. AO(L × n)
2. BO(L) ไม่ขึ้นกับจำนวนคำที่เก็บ
3. CO(n) เมื่อ n คือจำนวนคำ
4. DO(log n) เมื่อ n คือจำนวนคำ

ใน min-heap ทวิภาคที่เก็บในอาร์เรย์ (ดัชนีเริ่มที่ 0) ลูกของโหนดที่ดัชนี i อยู่ที่

1. A2i และ 2i + 1
2. Bi/2 และ i/2 + 1
3. C2i + 1 และ 2i + 2
4. Di + 1 และ i + 2

วัตถุถูกเก็บเป็นคีย์ใน hash map จากนั้นฟิลด์ที่ฟังก์ชันแฮชใช้ถูกเปลี่ยน ผลลัพธ์ที่น่าจะเกิดคืออะไร

1. Aไม่มีอะไรเปลี่ยน เพราะแฮชของคีย์คำนวณเพียงครั้งเดียวตอนโปรแกรมเริ่มทำงาน
2. Bmap โยนข้อผิดพลาดทันทีที่ฟิลด์เปลี่ยน
3. Cการค้นหาวัตถุอาจล้มเหลว เพราะมันอยู่ในถังของแฮชเก่า
4. Dmap ย้ายคีย์ไปถังใหม่โดยอัตโนมัติ

โครงสร้างข้อมูลใดรองรับแคช LRU (least recently used) ที่ get และ put เป็น O(1)

1. Aอาร์เรย์เรียงลำดับเดียว
2. Bbinary search tree เท่านั้น
3. Cสแตกเท่านั้น
4. Dhash map ร่วมกับลิงก์ลิสต์สองทิศทาง