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

ตัวประกอบการโหลด (load factor) ของตารางแฮชคืออะไร

1. Aจำนวนการชนกันจนถึงตอนนี้
2. Bจำนวนถังหารด้วยความยาวเฉลี่ยของคีย์ที่เก็บ
3. Cจำนวนสมาชิกที่เก็บหารด้วยจำนวนถัง
4. Dเวลาที่ใช้โหลดตารางจากดิสก์

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

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

โครงสร้างใดมักใช้สร้างคิวลำดับความสำคัญ (priority queue)

1. Aสแตก (stack)
2. Bลิงก์ลิสต์เชิงเดี่ยวที่ไม่เรียงลำดับ
3. Cฮีป (heap)
4. Dสตริง

ต้นไม้ทวิภาคมีราก 1 ลูกซ้าย 2 ลูกขวา 3 โหนด 2 มีลูก 4 (ซ้าย) และ 5 (ขวา) การท่องแบบ preorder คืออะไร

1. A4 5 2 3 1
2. B4 2 5 1 3
3. C1 2 3 4 5
4. D1 2 4 5 3

เมทริกซ์ประชิด (adjacency matrix) ของกราฟที่มี V จุดยอดใช้หน่วยความจำเท่าใด

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

ต้นไม้ AVL และต้นไม้แดง–ดำ (red-black) รับประกัน

1. Aไม่มีโหนดใดมีลูกสองตัว
2. Bการค้นหาในเวลาคงที่ทุกกรณี
3. Cคีย์ถูกเก็บตามลำดับการแทรก
4. Dความสูง O(log n) ผ่านการปรับสมดุลใหม่

คุณต้องเก็บค่าที่น้อยที่สุด k ตัวจากสตรีมของตัวเลข n ตัวโดยใช้หน่วยความจำ O(k) แนวทางใดทำงานใน O(n log k)

1. Aคิว FIFO ของ k ค่าล่าสุด
2. Bmax-heap ขนาด k โดยแทนที่รากเมื่อมีค่าที่เล็กกว่ามา
3. Cอาร์เรย์เรียงลำดับของค่าทั้ง n
4. Dmin-heap ที่เก็บค่าทั้ง n ตัว แล้วดึงค่าที่น้อยที่สุด k ตัวออกมาตอนท้าย

ในตารางแฮชที่ใช้ open addressing เหตุใดการลบจึงมักทำด้วยเครื่องหมาย "tombstone"

1. Aการทำให้ช่องว่างอาจทำลายลำดับการตรวจสอบสำหรับคีย์อื่น
2. Bคีย์ที่ลบต้องเก็บไว้ตลอดไปเพื่อความปลอดภัย จึงใช้ช่องนั้นซ้ำไม่ได้
3. Ctombstone เร่งการแฮช
4. Dทำให้ตารางเรียงลำดับ