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

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

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

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

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

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

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

เครือข่ายถนนมี 100,000 ทางแยก แต่ละแห่งเชื่อมกับประมาณ 4 แห่ง การแทนแบบใดเหมาะที่สุด

1. Aอาร์เรย์เรียงลำดับเดียวของจุดยอด
2. Bฮีปทวิภาคของเส้นเชื่อม
3. Cรายการประชิด
4. Dเมทริกซ์ประชิด

บัฟเฟอร์วงกลม (circular buffer หรือ ring buffer) มักใช้สร้าง

1. Aต้นไม้ค้นหาแบบทวิภาค
2. Bฟังก์ชันแฮช
3. Cคิวขนาดคงที่
4. Dการท่องกราฟ

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

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

อาร์เรย์พลวัตเพิ่มเป็นสองเท่าเมื่อเต็ม เหตุใดหลายการสร้างจึงหดมันเมื่อเหลือเพียงหนึ่งในสี่เท่านั้น ไม่ใช่ครึ่งหนึ่ง

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

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

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