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

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

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

การดำเนินการใดเป็น O(1) สำหรับอาร์เรย์แต่เป็น O(n) สำหรับลิงก์ลิสต์เชิงเดี่ยว

1. Aการลบสมาชิกหัว
2. Bการอ่านสมาชิกตัวแรก
3. Cการเข้าถึงสมาชิกที่ดัชนี i
4. Dการแทรกที่หัว

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

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

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

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

คุณมีการอ้างอิงถึงโหนดกลางลิสต์ ในลิสต์ชนิดใดลบมันได้ใน O(1)

1. Aอาร์เรย์พลวัต
2. Bลิงก์ลิสต์เชิงเดี่ยว
3. Cลิงก์ลิสต์สองทิศทาง
4. Dอาร์เรย์เรียงลำดับ

ความซับซ้อนเชิงเวลาของการค้นหาคีย์ใน binary search tree ที่สมดุลคือเท่าใด

1. AO(n)
2. BO(1)
3. CO(n log n)
4. DO(log n)

คู่การท่องใดกำหนดต้นไม้ทวิภาคที่มีคีย์ไม่ซ้ำได้เพียงแบบเดียวเสมอ

1. Apreorder และ postorder
2. Bpreorder และ inorder
3. Cpreorder เพียงอย่างเดียว
4. Dlevel-order เพียงอย่างเดียว

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

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