1.ง่าย
ในต้นไม้ค้นหาแบบทวิภาค (binary search tree) ค่าในต้นไม้ย่อยซ้ายของโหนดมีค่า
- Aน้อยกว่าค่าของโหนด
- Bเรียงลำดับแบบสุ่ม
- Cเท่ากับค่าของโหนด
- Dมากกว่าค่าของโหนด
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
ในกราฟ วงจร (cycle) คืออะไร
- Aเส้นทางที่เริ่มและสิ้นสุดที่จุดยอดเดียวกัน
- Bจุดยอดที่ไม่มีเส้นเชื่อม
- Cเส้นเชื่อมที่มีน้ำหนักเป็นศูนย์
- Dเส้นทางที่เยี่ยมทุกจุดยอด
3.ง่าย
ในลิงก์ลิสต์เชิงเดี่ยว ตัวชี้ next ของโหนดสุดท้ายมีค่าเป็น
- Aที่อยู่ของโหนดก่อนหน้า
- Bจำนวนโหนดในลิสต์
- Cที่อยู่ของโหนดแรก
- DNull (ไม่มีโหนด)
4.ปานกลาง
การค้นหาคำความยาว L ใน trie ที่มีตัวอักษรคงที่ใช้เวลาเท่าใด
- AO(L × n)
- BO(n) เมื่อ n คือจำนวนคำ
- CO(log n) เมื่อ n คือจำนวนคำ
- DO(L) ไม่ขึ้นกับจำนวนคำที่เก็บ
5.ปานกลาง
ใน min-heap ทวิภาคที่เก็บในอาร์เรย์ (ดัชนีเริ่มที่ 0) ลูกของโหนดที่ดัชนี i อยู่ที่
- A2i + 1 และ 2i + 2
- Bi + 1 และ i + 2
- Ci/2 และ i/2 + 1
- D2i และ 2i + 1
6.ปานกลาง
การท่องแบบ in-order ของ binary search tree เยี่ยมคีย์ตามลำดับ
- Aเรียงจากน้อยไปมาก
- Bเรียงจากมากไปน้อยเสมอ
- Cตามลำดับการแทรก
- Dตามระดับ
7.ยาก
ในบัฟเฟอร์วงกลม front == rear อาจหมายถึงว่างหรือเต็ม วิธีทั่วไปในการแยกสองกรณีคืออะไร
- Aทำให้ขนาดบัฟเฟอร์เป็นเลขกำลังสอง
- Bเก็บ front และ rear ในตัวแปรเดียวกัน
- Cล้างบัฟเฟอร์ทุกครั้งที่ front เท่ากับ rear ดังนั้นสถานะจึงเป็นว่าง
- Dเก็บจำนวนสมาชิกแยกต่างหาก หรือเว้นหนึ่งช่องไว้เสมอ
8.ยาก
เหตุใดเซิร์ฟเวอร์จึงเลือกฟังก์ชันแฮชแบบสุ่มจากตระกูลสากล (universal family)
- Aเพื่อตัดความจำเป็นในการปรับขนาดตาราง
- Bเพื่อทำให้ตารางแฮชเรียงลำดับ
- Cเพื่อรับประกันว่าไม่มีคีย์สองตัวชนกันเลย ไม่ว่าผู้โจมตีจะส่งคีย์ใดมา
- Dเพื่อทำให้ผู้โจมตีเลือกคีย์จำนวนมากที่ชนกันทั้งหมดได้ยากมาก
เฉลย
- 1. A · น้อยกว่าค่าของโหนด
- 2. A · เส้นทางที่เริ่มและสิ้นสุดที่จุดยอดเดียวกัน
- 3. D · Null (ไม่มีโหนด)
- 4. D · O(L) ไม่ขึ้นกับจำนวนคำที่เก็บ
- 5. A · 2i + 1 และ 2i + 2
- 6. A · เรียงจากน้อยไปมาก
- 7. D · เก็บจำนวนสมาชิกแยกต่างหาก หรือเว้นหนึ่งช่องไว้เสมอ
- 8. D · เพื่อทำให้ผู้โจมตีเลือกคีย์จำนวนมากที่ชนกันทั้งหมดได้ยากมาก
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com