1.ง่าย
โครงสร้างข้อมูลใดใช้ท่องต้นไม้แบบ level-order
- Aคิว
- Bสแตก
- Cตารางแฮช
- Dคิวลำดับความสำคัญ
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
การท่องแบบ preorder ของต้นไม้ทวิภาคเยี่ยมโหนดตามลำดับใด
- Aทีละระดับจากด้านบน
- Bต้นไม้ย่อยซ้าย แล้วโหนด แล้วต้นไม้ย่อยขวา
- Cต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา แล้วโหนด
- Dโหนด แล้วต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา
3.ง่าย
อะไรคือนิยามของต้นไม้ทวิภาค (binary tree)
- Aต้นไม้มีสองระดับพอดี
- Bทุกโหนดมีลูกไม่เกินสองตัว
- Cทุกโหนดเก็บเลขฐานสอง
- Dทุกโหนดมีลูกสองตัวพอดี
4.ปานกลาง
ในฮีปทวิภาคที่เก็บในอาร์เรย์เริ่มที่ดัชนี 0 แม่ของโหนดที่ดัชนี i อยู่ที่ใด
- Aที่ดัชนี 2i + 1
- Bที่ดัชนี ⌊(i − 1) / 2⌋
- Cที่ดัชนี ⌊i / 2⌋ + 1
- Dที่ดัชนี i − 1
5.ปานกลาง
การตรวจว่ามีเส้นเชื่อม (u, v) หรือไม่ด้วยเมทริกซ์ประชิดใช้เวลาเท่าใด
- AO(E)
- BO(V)
- CO(1)
- DO(log V)
6.ปานกลาง
โครงสร้างข้อมูลใดใช้ตรวจว่าวงเล็บใน "{[()]}" สมดุลหรือไม่
- Aคิว
- Bbinary search tree
- Cตารางแฮช
- Dสแตก
7.ยาก
อาร์เรย์พลวัตเพิ่มเป็นสองเท่าเมื่อเต็ม เหตุใดหลายการสร้างจึงหดมันเมื่อเหลือเพียงหนึ่งในสี่เท่านั้น ไม่ใช่ครึ่งหนึ่ง
- Aเพราะตัวจัดสรรหน่วยความจำคืนหน่วยความจำได้เฉพาะเป็นหนึ่งในสี่ของบล็อกเท่านั้น
- Bเพราะการหดที่ครึ่งหนึ่งทำให้สมาชิกหาย
- Cเพื่อให้อาร์เรย์เรียงลำดับ
- Dเพื่อหลีกเลี่ยงการปรับขนาดซ้ำเมื่อ push และ pop สลับกันใกล้ขอบเขต
8.ยาก
คุณสมบัติใดทำให้ B-tree ทุกต้นสมดุลอย่างสมบูรณ์
- Aทุกโหนดมีลูกสองตัวพอดี
- Bใบทั้งหมดอยู่ที่ความลึกเดียวกัน
- Cคีย์ถูกเก็บเฉพาะที่ราก
- Dแต่ละโหนดเก็บหนึ่งคีย์
เฉลย
- 1. A · คิว
- 2. D · โหนด แล้วต้นไม้ย่อยซ้าย แล้วต้นไม้ย่อยขวา
- 3. B · ทุกโหนดมีลูกไม่เกินสองตัว
- 4. B · ที่ดัชนี ⌊(i − 1) / 2⌋
- 5. C · O(1)
- 6. D · สแตก
- 7. D · เพื่อหลีกเลี่ยงการปรับขนาดซ้ำเมื่อ push และ pop สลับกันใกล้ขอบเขต
- 8. B · ใบทั้งหมดอยู่ที่ความลึกเดียวกัน
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com