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

ในตารางแฮช การชนกัน (collision) คืออะไร

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

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

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

แมป (map หรือ dictionary) เก็บอะไร

1. Aคู่คีย์–ค่าที่คีย์ไม่ซ้ำกัน
2. Bค่าตามลำดับการแทรกเท่านั้น
3. Cค่าที่เรียงตามขนาด
4. Dคู่ของคีย์ที่เท่ากัน

สมาชิกใหม่ถูกแทรกลงในฮีปทวิภาคอย่างไร

1. Aแทรกที่ตำแหน่งตามลำดับโดยเลื่อนสมาชิกที่ใหญ่กว่าทั้งหมดไปทางขวาหนึ่งตำแหน่ง
2. Bวางที่รากและเลื่อนลง
3. Cสร้างฮีปใหม่ทั้งหมดตั้งแต่ต้น
4. Dวางที่ท้ายอาร์เรย์และเลื่อนขึ้น (sift up) ตราบที่ยังละเมิดคุณสมบัติฮีป

ต้นไม้ทวิภาคสมบูรณ์เต็ม (perfect binary tree) ที่มีความสูง h มีกี่โหนด เมื่อความสูงนับเป็นเส้นเชื่อม

1. A2h + 1
2. Bh²
3. C2^h
4. D2^h+1 − 1

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

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

การลบโหนดที่มีลูกสองตัวจาก binary search tree มักทำโดย

1. Aสร้างต้นไม้ย่อยที่อยู่ใต้โหนดนั้นขึ้นใหม่ทั้งหมดแล้วแทรกคีย์ทุกตัวที่เคยมีอยู่ลงไปใหม่
2. Bสลับกับราก
3. Cแทนที่ด้วย in-order successor (หรือ predecessor) แล้วลบโหนดนั้น
4. Dลบต้นไม้ย่อยทั้งหมด

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

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