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

ในต้นไม้ ใบ (leaf) คืออะไร

1. Aโหนดที่ไม่มีโหนดลูก
2. Bโหนดที่ไม่มีโหนดแม่
3. Cโหนดที่มีลูกหนึ่งตัวพอดี
4. Dโหนดที่มีค่ามากที่สุด

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

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

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

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

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

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

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

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

คิวถูกสร้างด้วยสแตกสองตัว: push ลงสแตก "in" และ pop จากสแตก "out" โดยเติมจาก "in" เมื่อว่าง ต้นทุนกระจายต่อการดำเนินการคือเท่าใด

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

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

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

เหตุใดจึงลบสมาชิกออกจาก Bloom filter มาตรฐานโดยเพียงล้างบิตของมันไม่ได้

1. Aบิตเหล่านั้นอาจเป็นของสมาชิกอื่นด้วย ซึ่งจะทำให้เกิดผลลบเท็จ
2. Bบิตใน Bloom filter เปลี่ยนไม่ได้หลังสร้าง
3. CBloom filter เก็บสมาชิกเต็มรูป ซึ่งเมื่อถูกแฮชแล้วหาไม่พบอีก
4. Dการลบจะเพิ่มอัตราผลบวกเท็จเป็น 100%