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

สมาชิกของอาร์เรย์ถูกเก็บในหน่วยความจำอย่างไร

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

ในลิงก์ลิสต์เชิงเดี่ยว ตัวชี้ next ของโหนดสุดท้ายมีค่าเป็น

1. Aที่อยู่ของโหนดแรก
2. BNull (ไม่มีโหนด)
3. Cจำนวนโหนดในลิสต์
4. Dที่อยู่ของโหนดก่อนหน้า

กราฟมีน้ำหนัก (weighted graph) คืออะไร

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

แอปพลิเคชันต้องการค้นหาเร็ว และต้องแสดงรายการคีย์เรียงลำดับและตอบคำถามช่วง โครงสร้างใดเหมาะที่สุด

1. Aสแตก
2. Bลิงก์ลิสต์ที่ไม่เรียงลำดับ
3. Cbinary search tree แบบสมดุล
4. Dตารางแฮช

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

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

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

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

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

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

ตรวจว่าลิงก์ลิสต์เชิงเดี่ยวมีวงจรหรือไม่โดยใช้หน่วยความจำเพิ่ม O(1) ได้อย่างไร

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