1.ง่าย
ความสูงของต้นไม้มักถูกนิยามว่า
- Aจำนวนเส้นเชื่อมบนเส้นทางที่ยาวที่สุดจากรากไปยังใบ
- Bจำนวนโหนดทั้งหมดในต้นไม้ นับทั้งรากและใบทุกใบ
- Cจำนวนใบในต้นไม้
- Dจำนวนลูกของราก
ใบงาน โครงสร้างข้อมูล พร้อมเฉลย
2.ง่าย
แมป (map หรือ dictionary) เก็บอะไร
- Aค่าที่เรียงตามขนาด
- Bคู่คีย์–ค่าที่คีย์ไม่ซ้ำกัน
- Cคู่ของคีย์ที่เท่ากัน
- Dค่าตามลำดับการแทรกเท่านั้น
3.ง่าย
รากของต้นไม้ (root) คืออะไร
- Aโหนดบนสุดที่ไม่มีโหนดแม่
- Bโหนดใดก็ได้ตรงกลาง
- Cโหนดที่ไม่มีโหนดลูก
- Dโหนดที่มีค่ามากที่สุด
4.ปานกลาง
โครงสร้างข้อมูลใดที่การค้นหาในแนวลึก (DFS) แบบวนซ้ำใช้
- Aฮีป
- Bคิว
- Cตารางแฮชเท่านั้น
- Dสแตก
5.ปานกลาง
การท่องแบบ in-order ของ binary search tree เยี่ยมคีย์ตามลำดับ
- Aเรียงจากมากไปน้อยเสมอ
- Bตามระดับ
- Cตามลำดับการแทรก
- Dเรียงจากน้อยไปมาก
6.ปานกลาง
ข้อใดเป็นจริงเกี่ยวกับเมทริกซ์ประชิดของกราฟไม่มีทิศทาง
- Aเป็นเมทริกซ์สามเหลี่ยมบนเสมอ
- Bสมมาตรเทียบกับเส้นทแยงมุมหลัก
- Cแต่ละแถวมี 1 เพียงตัวเดียวพอดี
- Dเส้นทแยงมุมหลักมีเลขหนึ่งเสมอ
7.ยาก
radix tree (compressed trie) ปรับปรุง trie ธรรมดาอย่างไร
- Aเก็บเฉพาะตัวอักษรแรกของแต่ละคำ
- Bรวมโซ่ของโหนดที่มีลูกตัวเดียวเป็นเส้นเชื่อมเดียวที่ติดป้ายด้วยสตริง
- Cเรียงลูกของแต่ละโหนดตามความถี่
- Dเก็บแต่ละคำไว้ในตารางแฮชที่ราก แทนที่จะเก็บในโหนดแยกกัน
8.ยาก
สำหรับแต่ละสมาชิกของอาร์เรย์ คุณต้องการสมาชิกที่ใหญ่กว่าถัดไปทางขวา ในเวลารวม O(n) โครงสร้างใดช่วยได้
- Aตารางแฮชของสมาชิกทั้งหมด
- Bสแตกที่เก็บสมาชิกที่รอคำตอบ
- Cคิวที่เก็บทุกคู่ของสมาชิก
- Dbinary search tree ที่สร้างใหม่สำหรับแต่ละสมาชิก
เฉลย
- 1. A · จำนวนเส้นเชื่อมบนเส้นทางที่ยาวที่สุดจากรากไปยังใบ
- 2. B · คู่คีย์–ค่าที่คีย์ไม่ซ้ำกัน
- 3. A · โหนดบนสุดที่ไม่มีโหนดแม่
- 4. D · สแตก
- 5. D · เรียงจากน้อยไปมาก
- 6. B · สมมาตรเทียบกับเส้นทแยงมุมหลัก
- 7. B · รวมโซ่ของโหนดที่มีลูกตัวเดียวเป็นเส้นเชื่อมเดียวที่ติดป้ายด้วยสตริง
- 8. B · สแตกที่เก็บสมาชิกที่รอคำตอบ
เฉลยทีละขั้นตอนฉบับเต็ม: ฝึกหัวข้อนี้ได้ที่ examproblems.com