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

deque (double-ended queue) คืออะไร

1. Aโครงสร้างที่อนุญาตให้แทรกและเอาออกที่ทั้งสองปลาย
2. Bคิวสองคิวที่ใช้อาร์เรย์ร่วมกัน
3. Cคิวที่อนุญาตให้เอาออกจากด้านหลังเท่านั้น
4. Dคิวที่เรียงตามลำดับความสำคัญ

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

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

ลักษณะเด่นของเซต (set) ในฐานะชนิดข้อมูลนามธรรมคืออะไร

1. Aเข้าถึงได้เฉพาะที่ปลายด้านเดียว
2. Bเก็บสมาชิกโดยไม่มีซ้ำ
3. Cเก็บสมาชิกเรียงลำดับ
4. Dเก็บคู่คีย์–ค่า

ต้นไม้ AVL รักษาเงื่อนไขสมดุลใดที่ทุกโหนด

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

จะเกิดอะไรขึ้นเมื่อตารางแฮช rehash หลังตัวประกอบการโหลดเกินเกณฑ์

1. Aคีย์ที่มีอยู่ถูกเรียงในที่เดิม
2. Bย้ายเฉพาะคีย์ที่ชนกันไปยังลิสต์ล้นใหม่ที่ท้ายตาราง
3. Cจัดสรรตารางใหม่ที่ใหญ่กว่าและแทรกทุกคีย์ใหม่
4. Dคีย์เก่าที่สุดถูกลบเพื่อให้มีที่ว่าง

เหตุใดการท่องอาร์เรย์จึงเร็วกว่าการท่องลิงก์ลิสต์ที่ยาวเท่ากันมากในทางปฏิบัติ

1. Aลิงก์ลิสต์เก็บสมาชิกบนดิสก์เสมอ
2. Bการท่องอาร์เรย์เป็น O(1) โดยรวม ส่วนการท่องลิงก์ลิสต์เป็น O(n)
3. Cอาร์เรย์ใช้คำสั่งน้อยกว่าในการเปรียบเทียบค่า
4. Dสมาชิกของอาร์เรย์ต่อเนื่องกัน จึงใช้แคชของ CPU ได้ดี

เหตุใดเซิร์ฟเวอร์จึงเลือกฟังก์ชันแฮชแบบสุ่มจากตระกูลสากล (universal family)

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

ในอัลกอริทึมต้นไม้ทอดข้ามที่น้อยที่สุดของ Kruskal โครงสร้าง union-find ใช้เพื่อ

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