1.ง่าย
แต่ละโหนดในลิงก์ลิสต์สองทิศทาง (doubly linked list) มีอะไร
- Aข้อมูลสองชุดและตัวชี้หนึ่งตัว
- Bข้อมูล ตัวชี้ไปโหนดถัดไป และตัวชี้ไปโหนดก่อนหน้า
- Cข้อมูลและตัวชี้สองตัว ตัวหนึ่งไปโหนดถัดไปและอีกตัวไปโหนดที่ถัดจากนั้นอีกหนึ่งโหนด
- Dข้อมูลและตัวชี้ไปโหนดถัดไปเท่านั้น
2.ง่าย
ในลิงก์ลิสต์เชิงเดี่ยว (singly linked list) แต่ละโหนดประกอบด้วย
- Aข้อมูลและการอ้างอิงไปยังโหนดอื่นทั้งหมด
- Bข้อมูลและดัชนี
- Cข้อมูลเท่านั้น
- Dข้อมูลและการอ้างอิงไปยังโหนดถัดไป
3.ง่าย
ในต้นไม้ โหนดพี่น้อง (sibling) คืออะไร
- Aโหนดที่ไม่มีลูก
- Bโหนดที่ระดับความลึกเดียวกันในต้นไม้ย่อยต่างกัน
- Cโหนดที่มีแม่เดียวกัน
- Dโหนดและแม่ของมัน
4.ปานกลาง
โปรแกรมที่ทำงานอยู่ใช้โครงสร้างข้อมูลใดติดตามการเรียกฟังก์ชันที่กำลังทำงานและตัวแปรท้องถิ่น
- Aสแตกการเรียก (call stack)
- Bbinary search tree ของเฟรม
- Cตารางแฮชของฟังก์ชัน
- Dคิวหน่วยความจำฮีป
5.ปานกลาง
แอปพลิเคชันต้องการค้นหาเร็ว และต้องแสดงรายการคีย์เรียงลำดับและตอบคำถามช่วง โครงสร้างใดเหมาะที่สุด
- Aสแตก
- Bbinary search tree แบบสมดุล
- Cตารางแฮช
- Dลิงก์ลิสต์ที่ไม่เรียงลำดับ
6.ปานกลาง
ความซับซ้อนเชิงเวลาของการค้นหาคีย์ใน binary search tree ที่สมดุลคือเท่าใด
- AO(n)
- BO(log n)
- CO(n log n)
- DO(1)
7.ยาก
เหตุใดจึงลบสมาชิกออกจาก Bloom filter มาตรฐานโดยเพียงล้างบิตของมันไม่ได้
- Aบิตใน Bloom filter เปลี่ยนไม่ได้หลังสร้าง
- BBloom filter เก็บสมาชิกเต็มรูป ซึ่งเมื่อถูกแฮชแล้วหาไม่พบอีก
- Cการลบจะเพิ่มอัตราผลบวกเท็จเป็น 100%
- Dบิตเหล่านั้นอาจเป็นของสมาชิกอื่นด้วย ซึ่งจะทำให้เกิดผลลบเท็จ
8.ยาก
ภายใต้การแฮชสม่ำเสมออย่างง่าย เวลาคาดหมายของการค้นหาในตารางแฮชแบบ chaining ที่มี n คีย์และ m ถังคือเท่าใด
- AO(m)
- BO(1 + α) เมื่อ α = n / m
- CO(log n)
- DO(n)
เฉลย
- 1. B · ข้อมูล ตัวชี้ไปโหนดถัดไป และตัวชี้ไปโหนดก่อนหน้า
- 2. D · ข้อมูลและการอ้างอิงไปยังโหนดถัดไป
- 3. C · โหนดที่มีแม่เดียวกัน
- 4. A · สแตกการเรียก (call stack)
- 5. B · binary search tree แบบสมดุล
- 6. B · O(log n)
- 7. D · บิตเหล่านั้นอาจเป็นของสมาชิกอื่นด้วย ซึ่งจะทำให้เกิดผลลบเท็จ
- 8. B · O(1 + α) เมื่อ α = n / m
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com