1.ง่าย
คุณสมบัติ max-heap คืออะไร
- Aคีย์เรียงจากซ้ายไปขวา
- Bใบทั้งหมดมีคีย์สูงสุด
- Cคีย์ของลูกซ้ายทุกตัวมากกว่าหรือเท่ากับคีย์ของพี่น้องฝั่งขวา
- Dคีย์ของแม่แต่ละตัวมากกว่าหรือเท่ากับคีย์ของลูก
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
ในต้นไม้ค้นหาแบบทวิภาค (binary search tree) ค่าในต้นไม้ย่อยซ้ายของโหนดมีค่า
- Aเรียงลำดับแบบสุ่ม
- Bน้อยกว่าค่าของโหนด
- Cมากกว่าค่าของโหนด
- Dเท่ากับค่าของโหนด
3.ง่าย
ในต้นไม้ โหนดพี่น้อง (sibling) คืออะไร
- Aโหนดที่ไม่มีลูก
- Bโหนดและแม่ของมัน
- Cโหนดที่มีแม่เดียวกัน
- Dโหนดที่ระดับความลึกเดียวกันในต้นไม้ย่อยต่างกัน
4.ปานกลาง
ความซับซ้อนเชิงเวลาของการค้นหาคีย์ใน binary search tree ที่สมดุลคือเท่าใด
- AO(log n)
- BO(n log n)
- CO(n)
- DO(1)
5.ปานกลาง
ใน min-heap ทวิภาคที่เก็บในอาร์เรย์ (ดัชนีเริ่มที่ 0) ลูกของโหนดที่ดัชนี i อยู่ที่
- A2i + 1 และ 2i + 2
- Bi + 1 และ i + 2
- C2i และ 2i + 1
- Di/2 และ i/2 + 1
6.ปานกลาง
การค้นหาคำความยาว L ใน trie ที่มีตัวอักษรคงที่ใช้เวลาเท่าใด
- AO(L × n)
- BO(n) เมื่อ n คือจำนวนคำ
- CO(log n) เมื่อ n คือจำนวนคำ
- DO(L) ไม่ขึ้นกับจำนวนคำที่เก็บ
7.ยาก
segment tree มักใช้เพื่อ
- Aเรียงสตริงตามตัวอักษรโดยเก็บแต่ละคำนำหน้าไว้ในโหนดต้นไม้แยกกัน
- Bสร้างสแตก
- Cตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)
- Dเก็บเส้นเชื่อมของกราฟ
8.ยาก
Fenwick tree (binary indexed tree) บนอาร์เรย์ที่มีตัวเลข n ตัว รองรับการดำเนินการใดใน O(log n)
- Aการเรียงอาร์เรย์และการค้นหาแบบทวิภาค
- Bคำถามผลรวมคำนำหน้าและการอัปเดตสมาชิกเดียว
- Cการแทรกสมาชิกที่ตำแหน่งใดก็ได้
- Dการหามัธยฐานใน O(1)
เฉลย
- 1. D · คีย์ของแม่แต่ละตัวมากกว่าหรือเท่ากับคีย์ของลูก
- 2. B · น้อยกว่าค่าของโหนด
- 3. C · โหนดที่มีแม่เดียวกัน
- 4. A · O(log n)
- 5. A · 2i + 1 และ 2i + 2
- 6. D · O(L) ไม่ขึ้นกับจำนวนคำที่เก็บ
- 7. C · ตอบคำถามช่วง (เช่น ผลรวมช่วง) และอัปเดตใน O(log n)
- 8. B · คำถามผลรวมคำนำหน้าและการอัปเดตสมาชิกเดียว
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com