1.ง่าย
การท่องแบบ postorder ของต้นไม้ทวิภาคเยี่ยมโหนดตามลำดับใด
- Aต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา แล้วโหนด
- Bต้นไม้ย่อยซ้าย แล้วโหนด แล้วต้นไม้ย่อยขวา
- Cโหนด แล้วต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา
- Dต้นไม้ย่อยขวา แล้วโหนด แล้วต้นไม้ย่อยซ้าย
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
deque (double-ended queue) คืออะไร
- Aคิวที่อนุญาตให้เอาออกจากด้านหลังเท่านั้น
- Bคิวสองคิวที่ใช้อาร์เรย์ร่วมกัน
- Cคิวที่เรียงตามลำดับความสำคัญ
- Dโครงสร้างที่อนุญาตให้แทรกและเอาออกที่ทั้งสองปลาย
3.ง่าย
ในต้นไม้ โหนดพี่น้อง (sibling) คืออะไร
- Aโหนดที่ไม่มีลูก
- Bโหนดที่ระดับความลึกเดียวกันในต้นไม้ย่อยต่างกัน
- Cโหนดที่มีแม่เดียวกัน
- Dโหนดและแม่ของมัน
4.ปานกลาง
ในฮีปทวิภาคที่เก็บในอาร์เรย์เริ่มที่ดัชนี 0 แม่ของโหนดที่ดัชนี i อยู่ที่ใด
- Aที่ดัชนี ⌊(i − 1) / 2⌋
- Bที่ดัชนี 2i + 1
- Cที่ดัชนี ⌊i / 2⌋ + 1
- Dที่ดัชนี i − 1
5.ปานกลาง
โหนดใน binary search tree มีต้นไม้ย่อยขวา in-order successor ของมันอยู่ที่ใด
- Aลูกขวาของมันเสมอ
- Bแม่ของมันเสมอ
- Cโหนดขวาสุดของต้นไม้ย่อยซ้าย
- Dโหนดซ้ายสุดของต้นไม้ย่อยขวา
6.ปานกลาง
โปรแกรมที่ทำงานอยู่ใช้โครงสร้างข้อมูลใดติดตามการเรียกฟังก์ชันที่กำลังทำงานและตัวแปรท้องถิ่น
- Aตารางแฮชของฟังก์ชัน
- Bสแตกการเรียก (call stack)
- Cคิวหน่วยความจำฮีป
- Dbinary search tree ของเฟรม
7.ยาก
ในตารางแฮชที่ใช้ open addressing เหตุใดการลบจึงมักทำด้วยเครื่องหมาย "tombstone"
- Atombstone เร่งการแฮช
- Bคีย์ที่ลบต้องเก็บไว้ตลอดไปเพื่อความปลอดภัย จึงใช้ช่องนั้นซ้ำไม่ได้
- Cทำให้ตารางเรียงลำดับ
- Dการทำให้ช่องว่างอาจทำลายลำดับการตรวจสอบสำหรับคีย์อื่น
8.ยาก
การค้นหาคีย์ใด ๆ ในฮีป min ทวิภาคที่มี n สมาชิกใช้เวลาเท่าใด
- AO(1)
- BO(log log n)
- CO(log n)
- DO(n)
เฉลย
- 1. A · ต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา แล้วโหนด
- 2. D · โครงสร้างที่อนุญาตให้แทรกและเอาออกที่ทั้งสองปลาย
- 3. C · โหนดที่มีแม่เดียวกัน
- 4. A · ที่ดัชนี ⌊(i − 1) / 2⌋
- 5. D · โหนดซ้ายสุดของต้นไม้ย่อยขวา
- 6. B · สแตกการเรียก (call stack)
- 7. D · การทำให้ช่องว่างอาจทำลายลำดับการตรวจสอบสำหรับคีย์อื่น
- 8. D · O(n)
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com