1.ง่าย
รากของต้นไม้ (root) คืออะไร
- Aโหนดใดก็ได้ตรงกลาง
- Bโหนดที่ไม่มีโหนดลูก
- Cโหนดบนสุดที่ไม่มีโหนดแม่
- Dโหนดที่มีค่ามากที่สุด
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
อะไรคือนิยามของต้นไม้ทวิภาค (binary tree)
- Aทุกโหนดมีลูกสองตัวพอดี
- Bต้นไม้มีสองระดับพอดี
- Cทุกโหนดมีลูกไม่เกินสองตัว
- Dทุกโหนดเก็บเลขฐานสอง
3.ง่าย
โครงสร้างข้อมูลใดเหมาะที่สุดสำหรับฟีเจอร์ "ย้อนกลับ" (undo) ในโปรแกรมแก้ไขข้อความ
- Aสแตก (stack)
- Bคิว (queue)
- Cกราฟ (graph)
- Dเซตแฮช (hash set)
4.ปานกลาง
ต้นไม้ทวิภาคมีราก 1 ลูกซ้าย 2 ลูกขวา 3 โหนด 2 มีลูก 4 (ซ้าย) และ 5 (ขวา) การท่องแบบ postorder คืออะไร
- A5 4 3 2 1
- B4 2 5 1 3
- C4 5 2 3 1
- D1 2 4 5 3
5.ปานกลาง
การตรวจว่ามีเส้นเชื่อม (u, v) หรือไม่ด้วยเมทริกซ์ประชิดใช้เวลาเท่าใด
- AO(log V)
- BO(1)
- CO(E)
- DO(V)
6.ปานกลาง
จุดประสงค์ของโหนดยามเฝ้า (sentinel หรือ dummy) ในลิงก์ลิสต์คืออะไร
- Aเพื่อป้องกันไม่ให้ลิสต์ขยายเกินจำนวนโหนดสูงสุดที่กำหนดไว้
- Bเก็บจำนวนสมาชิก
- Cทำให้โค้ดง่ายขึ้นโดยตัดกรณีพิเศษที่หัวหรือท้าย
- Dทำให้ลิสต์เรียงลำดับ
7.ยาก
ข้อใดเกี่ยวกับ heapsort ถูกต้อง
- Aเรียงในที่เดิมใน O(n log n) กรณีเลวร้ายที่สุด แต่ไม่เสถียร
- Bต้องใช้ binary search tree เป็นที่เก็บเพิ่มเติม จึงใช้หน่วยความจำเพิ่ม O(n)
- Cทำงานใน O(n) กับอินพุตใด ๆ
- Dเสถียรและต้องใช้หน่วยความจำเพิ่ม O(n)
8.ยาก
radix tree (compressed trie) ปรับปรุง trie ธรรมดาอย่างไร
- Aเก็บแต่ละคำไว้ในตารางแฮชที่ราก แทนที่จะเก็บในโหนดแยกกัน
- Bเรียงลูกของแต่ละโหนดตามความถี่
- Cเก็บเฉพาะตัวอักษรแรกของแต่ละคำ
- Dรวมโซ่ของโหนดที่มีลูกตัวเดียวเป็นเส้นเชื่อมเดียวที่ติดป้ายด้วยสตริง
เฉลย
- 1. C · โหนดบนสุดที่ไม่มีโหนดแม่
- 2. C · ทุกโหนดมีลูกไม่เกินสองตัว
- 3. A · สแตก (stack)
- 4. C · 4 5 2 3 1
- 5. B · O(1)
- 6. C · ทำให้โค้ดง่ายขึ้นโดยตัดกรณีพิเศษที่หัวหรือท้าย
- 7. A · เรียงในที่เดิมใน O(n log n) กรณีเลวร้ายที่สุด แต่ไม่เสถียร
- 8. D · รวมโซ่ของโหนดที่มีลูกตัวเดียวเป็นเส้นเชื่อมเดียวที่ติดป้ายด้วยสตริง
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com